Demostrar que el conjunto de los números naturales está bien ordenado

Question

Consideremos el siguiente teorema:

"Todo conjunto no vacío de números enteros positivos tiene un elemento mínimo".

La prueba que suelo ver es una que utiliza la contradicción, y no parece la prueba más fácil posible. Creo que hay una prueba más fácil, y me pregunto por qué nunca la veo. ¿Contiene alguna suposición inválida? La prueba es la siguiente:

Primero, demuestre por inducción que el teorema es cierto para conjuntos finitos. Caso base: Es cierto para un conjunto de tamaño 1, trivialmente. Paso de inducción: Consideremos un conjunto finito $S$ de tamaño $n+1$ . Sea $s$ ser miembro de $S$ . Por I.H., $|S-s|$ tiene un mínimo $s'$ . Si $s\lt s'$ entonces $s$ es el mínimo de $S$ . De lo contrario, es $s'$ .

Segundo $T$ cualquier conjunto no vacío de números enteros positivos ( $T$ podría ser infinito). Sea $t$ sea un elemento de $T$ . Consideremos el conjunto $T\cap [0,t]$ . El conjunto es claramente finito, por lo que tiene un elemento mínimo $min$ . A continuación, demostramos que $min$ es también un elemento mínimo de $T$ . Sea $x$ sea un elemento de $T$ . Si $t\lt x$ entonces $min\leq x$ . De lo contrario, $x\in T\cap [0,t]$ Así que $min\leq x$ .

¿Hay algún problema con esta prueba? Creo que cuando la gente demuestra que N está bien ordenado, lo hacen en los libros de teoría de conjuntos en un punto en el que se ha demostrado muy poco, por lo que no pueden suponer mucho. ¿Estoy suponiendo demasiado en esta demostración? Si no es así, ¿por qué la gente nunca usa esta prueba tan sencilla?

Answer 1

Para ampliar un poco la respuesta de Levon, en una introducción seria a la teoría de conjuntos es probable que los números enteros positivos se definan de forma que se garantice que están bien ordenados, en cuyo caso es automático que todo conjunto no vacío de ellos tenga un elemento mínimo. En ese enfoque lo que tienes que demostrar es que la prueba por inducción es válida en conjuntos bien ordenados (y por tanto en los enteros positivos). Si es un curso riguroso, también demostrarás que las definiciones por recursión son legítimas.

Allí son otras formas de desarrollar la teoría de los enteros positivos, y algunas de ellas toman alguna forma de inducción como axiomática, haciendo del buen ordenamiento una propiedad derivada, pero en mi experiencia estos enfoques son menos comunes, especialmente en los cursos de teoría de conjuntos.

Los cursos informales son harina de otro costal. En ellos se suelen dar por sentadas las propiedades básicas de los números enteros, incluidos el buen orden y la inducción. Normalmente, los autores se limitan a demostrar que las dos son lógicamente equivalentes, de modo que no importa cuál de las dos le parezca intuitivamente obvia a un lector determinado. (Sospecho que los autores esperan que la mayoría de los lectores encuentren al menos una de las dos propiedades intuitivamente obvia). En realidad, es en estos cursos donde más a menudo veo una prueba por contradicción, pero es la prueba de que el buen orden implica inducción, no al revés.

Answer 2

En primer lugar, permítanme decir que he visto pruebas inductivas del buen ordenamiento de los naturales en libros que no son de teoría de conjuntos.

La razón por la que no se ven pruebas de este tipo en los libros de teoría de conjuntos, creo, es que la inducción y el buen orden están estrechamente relacionados entre sí en la teoría de conjuntos. Se puede hacer inducción sobre un conjunto linealmente ordenado si y sólo si está bien ordenado. Así que, en cierto sentido, deberías demostrar que los naturales están bien ordenados y luego hacer inducción sobre ellos.