En matemáticas , el lema de Dickson establece que todo conjunto de-tuplas de números naturales tiene un número finito de elementos mínimos . Este simple hecho de la combinatoria se ha atribuido al algebrista estadounidense LE Dickson , quien lo usó para probar un resultado en la teoría de números sobre números perfectos . [1] Sin embargo, el lema ciertamente se conocía antes, por ejemplo, a Paul Gordan en su investigación sobre la teoría invariante . [2]
Ejemplo
Dejar ser un número fijo, y dejar ser el conjunto de pares de números cuyo producto es al menos . Cuando se define sobre los números reales positivos , tiene infinitos elementos mínimos de la forma , uno por cada número positivo ; este conjunto de puntos forma una de las ramas de una hipérbola . Los pares en esta hipérbola son mínimos, porque no es posible para un par diferente que pertenece a ser menor o igual a en sus dos coordenadas. Sin embargo, el lema de Dickson se refiere solo a tuplas de números naturales, y sobre los números naturales solo hay un número finito de pares mínimos. Cada par mínimo de números naturales tiene y , porque si x fuera mayor que K entonces ( x −1, y ) también pertenecería a S , contradiciendo la minimidad de ( x , y ), y simétricamente si y fuera mayor que K entonces ( x , y −1) también pertenecer a S . Por lo tanto, sobre los números naturales, tiene como máximo elementos mínimos, un número finito. [nota 1]
Declaración formal
Dejar sea el conjunto de enteros no negativos ( números naturales ), sea n cualquier constante fija y sea ser el conjunto de -tuplas de números naturales. A estas tuplas se les puede dar un orden parcial puntual , el orden del producto , en el que si y solo si, para cada , . El conjunto de tuplas que son mayores o iguales a alguna tupla en particular.forma un orthant positivo con su vértice en la tupla dada.
Con esta notación, el lema de Dickson puede expresarse en varias formas equivalentes:
- En cada subconjunto de , hay al menos uno, pero no más de un número finito de elementos que son elementos mínimos depara el orden parcial puntual. [3]
- Por cada secuencia infinita de -tuplas de números naturales, existen dos índices tal que se mantiene con respecto al orden puntual. [4]
- El conjunto parcialmente ordenado no contiene antichains infinitos ni secuencias infinitas (estrictamente) descendentes de-tuplas. [4]
- El conjunto parcialmente ordenado es un pedido bien parcial . [5]
- Cada subconjunto de puede estar cubierto por un conjunto finito de ortos positivos, cuyos vértices pertenecen todos a .
Generalizaciones y aplicaciones
Dickson usó su lema para demostrar que, para cualquier número dado , sólo puede existir un número finito de números perfectos impares que tienen como máximo factores primos . [1] Sin embargo, permanece abierto si existe algún número perfecto impar.
La relación de divisibilidad entre los P -números suaves , números naturales cuyos factores primos pertenecen todos al conjunto finito P , da a estos números la estructura de un conjunto parcialmente ordenado isomorfo a. Por tanto, para cualquier conjunto S de P -números suaves, hay un subconjunto finito de S tal que cada elemento de S es divisible por uno de los números de este subconjunto. Este hecho se ha utilizado, por ejemplo, para demostrar que existe un algoritmo para clasificar los movimientos ganadores y perdedores desde la posición inicial en el juego de la acuñación de Sylver , aunque el algoritmo en sí sigue siendo desconocido. [6]
Las tuplas en corresponder uno por uno con los monomios sobre un conjunto de variables . Según esta correspondencia, el lema de Dickson puede verse como un caso especial del teorema de la base de Hilbert que establece que todo ideal polinomial tiene una base finita para los ideales generados por los monomios. De hecho, Paul Gordan utilizó esta reformulación del lema de Dickson en 1899 como parte de una prueba del teorema de base de Hilbert. [2]
Ver también
- Lema de Jordán
Notas
- ^ Con más cuidado, es posible demostrar que uno de y es como máximo , y que hay como máximo un par mínimo para cada elección de una de las coordenadas, de lo que se sigue que hay como máximo elementos mínimos.
Referencias
- ^ a b Dickson, LE (1913), "Finitud de los números abundantes primitivos y perfectos impares con n factores primos distintos", American Journal of Mathematics , 35 (4): 413–422, doi : 10.2307 / 2370405 , JSTOR 2370405.
- ^ a b Buchberger, Bruno ; Winkler, Franz (1998), Bases y aplicaciones de Gröbner , Serie de notas de conferencia de la Sociedad Matemática de Londres, 251 , Cambridge University Press, p. 83, ISBN 9780521632980.
- ^ Kruskal, Joseph B. (1972). "La teoría del bien-cuasi-ordenamiento: un concepto descubierto con frecuencia" . Revista de teoría combinatoria . Serie A. 13 (3): 298. doi : 10.1016 / 0097-3165 (72) 90063-5 .
- ^ a b Figueira, Diego; Figueira, Santiago; Schmitz, Sylvain; Schnoebelen, Philippe (2011), "Límites ackermannianos y primitivo-recursivos con el lema de Dickson", 26º Simposio Anual de IEEE sobre Lógica en Ciencias de la Computación (LICS 2011) , IEEE Computer Soc., Los Alamitos, CA, p. 269, arXiv : 1007.2989 , doi : 10.1109 / LICS.2011.39 , MR 2858898.
- ^ Onn, Shmuel (2008), "Optimización discreta convexa", en Floudas, Christodoulos A .; Pardalos, Panos M. (eds.), Enciclopedia de optimización, vol. 1 (2.a ed.), Springer, págs. 513–550, arXiv : math / 0703575 , Bibcode : 2007math ...... 3575O , ISBN 9780387747583.
- ^ Berlekamp, Elwyn R .; Conway, John H .; Guy, Richard K. (2003), "18 El emperador y su dinero", Formas ganadoras para sus juegos matemáticos , vol. 3 , Academic Press, págs. 609–640. Consulte especialmente "¿Se pueden calcular los resultados?", Pág. 630.