Principio de ordenamiento adecuado

En matemáticas , el principio de buen orden , también llamado propiedad de buen orden ^{[ 1 ]} o principio del menor número natural , ^{[ 2 ] [ 3 ]} establece que todo subconjunto no vacío de los enteros no negativos ^{[ 4 ]} contiene un elemento mínimo , ^{[ 5 ]} también llamado elemento más pequeño . ^{[ 6 ]} En otras palabras, si${\displaystyle A}$es un subconjunto no vacío de los enteros no negativos, entonces existe un elemento de${\displaystyle A}$que sea menor que , o igual a , cualquier otro elemento de${\displaystyle A}$. ^{[ 1 ]} Formalmente,${\displaystyle \forall A\left[\left(A\subseteq \mathbb {Z} _{\geq 0}\land A\neq \varnothing \right)\rightarrow \left(\exists m\in A\,\forall a\in A\,(m\leq a)\right)\right]}$[ ^{7 ]} La mayoría de las fuentes lo presentan como un axioma o teorema sobre los números naturales , pero aquí se evitó la frase "número natural" debido a la ambigüedad sobre la inclusión del cero . La afirmación es verdadera sobre el conjunto de ^los números naturales.${\displaystyle \mathbb {N} }$independientemente de si se define como${\displaystyle \mathbb {Z} _{\geq 0}}$(enteros no negativos) o como${\displaystyle \mathbb {Z} ^{+}}$(enteros positivos), ya que uno de los axiomas de Peano para${\displaystyle \mathbb {N} }$, el axioma de inducción (o principio de inducción matemática ) es lógicamente equivalente al principio de buen ordenamiento. ^{[ 8 ]} Dado que${\displaystyle \mathbb {Z} ^{+}\subseteq \mathbb {Z} _{\geq 0}}$y la relación de subconjunto${\displaystyle \subseteq }$es transitivo , la afirmación sobre${\displaystyle \mathbb {Z} ^{+}}$está implícito en la declaración sobre${\displaystyle \mathbb {Z} _{\geq 0}}$.

El orden estándar en${\displaystyle \mathbb {N} }$está bien ordenado por el principio de buen ordenamiento, ya que comienza con un elemento mínimo, independientemente de si es 1 o 0. Por el contrario, el orden estándar en${\displaystyle \mathbb {R} }$(o en${\displaystyle \mathbb {Z} }$) no está bien ordenado por este principio, ya que no hay un número negativo más pequeño. ^{[ 9 ]} Según Deaconu y Pfaff, ^{[ 10 ]} la frase "principio de buen ordenamiento" es utilizada por algunos autores (sin nombre) como nombre para el " teorema de buen ordenamiento " de Zermelo en teoría de conjuntos , según el cual todo conjunto puede estar bien ordenado. Este teorema, que no es el tema de este artículo, implica que "en principio hay algún otro orden en${\displaystyle \mathbb {R} }$que está bien ordenado, aunque no parece haber una descripción concreta de dicho orden." ^{[ 9 ]}

El principio de buen orden es lógicamente equivalente al principio de inducción matemática, según el cual${\displaystyle \forall n\in \mathbb {Z} _{\geq 0}\left[\left(P(0)\land \left(\forall k\in \mathbb {Z} _{\geq 0}[P(k)\rightarrow P(k+1)]\right)\right]\rightarrow P(n)\right]}$. ^{[ 11 ] [ 12 ] [ 13 ]} En otras palabras, si se toma el principio de inducción matemática como un axioma , se puede demostrar el principio de buen ordenamiento como un teorema (como se hizo en ^{[ 14 ] [ 15 ]} ), y a la inversa , si se toma el principio de buen ordenamiento como un axioma, se puede demostrar el principio de inducción matemática como un teorema (como se hizo en ^{[ 16 ] [ 17 ] [ 18 ]} ). ^{[ 11 ] [ 12 ]} El primero es más común debido a la tradición , ya que el principio de inducción matemática fue uno de los axiomas de Peano para los números naturales, y Peano fue un matemático influyente .

El principio de inducción matemática y el principio de buen orden son cada uno equivalente al principio de inducción fuerte (también llamado principio de inducción completa), según el cual${\displaystyle \left[\left(P(0)\land \forall k\left(\left(\forall j\,(0\leq j\leq k)\rightarrow P(j)\right)\rightarrow P(k+1)\right)\right)\right]\rightarrow \forall n\in \mathbb {Z} _{\geq 0},\,P(n)}$. ^{[ 19 ]} En consecuencia, también se puede usar el principio de inducción fuerte como un axioma para probar el principio de buen ordenamiento como un teorema (como se hizo en ^{[ 20 ] [ 21 ] [ 22 ] [ 23 ]} ), o tomar el principio de buen ordenamiento como un axioma para probar el principio de inducción fuerte como un teorema (como en ^{[ 24 ] [ a ]} ​​).

Esto también significa que, en la teoría axiomática de conjuntos , la definición de los números naturales como el conjunto inductivo más pequeño ,${\displaystyle \mathbb {N} =\{x\in S\mid 0\in S\land \forall n\in S,\;n+1\in S\}}$, es equivalente a afirmar que el principio de buen ordenamiento es verdadero para ello. ^{[ 8 ]}

Aunque la equivalencia entre inducción y buen orden es un resultado común, Lars-Daniel Öhman ha argumentado que las "pruebas" de inducción basadas en el buen orden asumen implícitamente que todos los números naturales distintos de cero tienen un único predecesor inmediato, lo cual no se deduce de los axiomas no inductivos de Peano ni del principio de buen orden; de hecho, el conjunto de números ordinales menores que ω+ω sirve como contramodelo. ^{[ 27 ]} Por lo tanto, la inducción es más fuerte que el buen orden con respecto a los axiomas de Peano.

Si se sabe, como axioma o teorema, que los números reales son completos , entonces se puede usar esto para demostrar el principio de buen orden para enteros no negativos. ^{[ 28 ]} Esto se debe a que la propiedad de completitud implica que todo subconjunto acotado inferiormente de${\displaystyle \mathbb {R} }$tiene un ínfimo , lo que significa que, dado que${\displaystyle \mathbb {Z} _{\geq 0}}$es un subconjunto acotado inferiormente de${\displaystyle \mathbb {R} }$(y la relación de subconjunto${\displaystyle \subseteq }$es transitivo), entonces también cada conjunto${\displaystyle A\subseteq \mathbb {Z} _{\geq 0}}$tiene un ínfimo${\displaystyle a}$, lo que implica que existe un número entero${\displaystyle n}$de tal manera que${\displaystyle a}$se encuentra en el intervalo semiabierto${\displaystyle (n-1,n]}$, lo que implica que${\displaystyle a=n}$y${\displaystyle n\in A}$. ^{[ 29 ]}

El principio de buen ordenamiento, al igual que el axioma de cota superior mínima para números reales, ^{[ 30 ] [ 31 ]} no es algebraico, es decir, no puede deducirse de las propiedades algebraicas de los enteros (que forman un dominio de integridad ordenado ). ^{[ 32 ] [ 33 ]}

El principio de buen orden se utiliza en las demostraciones por contraejemplo mínimo , también conocido informalmente como el método de demostración " criminal mínimo " ^{[ 34 ]} , en el que se prueba que cada número natural pertenece a un conjunto especificado.${\displaystyle S}$Se asume lo contrario, lo que implica que el conjunto de contraejemplos no es vacío y, por lo tanto (dado el principio de buen orden), contiene un contraejemplo mínimo . Luego se demuestra que, para cualquier contraejemplo, existe otro aún menor, lo que produce una contradicción. Este modo de argumentación es la contrapositiva de la prueba por inducción completa y es similar en su naturaleza al método de Fermat de " descenso infinito ". A continuación se presentan ejemplos de esto que se han encontrado en la literatura.

• Demostración de la equivalencia entre el principio del buen orden y el principio de inducción matemática.