¿Cómo se demuestra el Bien-Ordenamiento sin Inducción Matemática? (y viceversa)

Question

Aquí está mi intento de probar el Principio de Ordenación, es decir, que cualquier subconjunto no vacío de $\Bbb N$, el conjunto de números naturales, tiene un elemento mínimo.

Prueba. Supongamos que existe un subconjunto no vacío $S$ de $\Bbb N$ tal que $S$ NO tiene un elemento mínimo. Definimos $A = \left\{n\in \Bbb N : (\forall s\in S)(n \leq s)\right\}$. Es obvio que $1\in A$. Supongamos que $n\in A$, entonces para cada $s \in S$, existe un $q \in N$ tal que $n + q = s$. Dado que $q \ge 1$, $n+1 \leq s$, para todo $s\in S$. Por el Principio de inducción matemática, $A = \Bbb N$. Tomamos cualquier $s_0 S$, entonces $(\forall s\in S)(s_0 \leq s)$. (Esto contradice que $S$ no tiene un elemento mínimo).

¿Cómo puedo probar la afirmación sin recurrir a la Inducción Matemática? Además, leí que la prueba del Principio de Inducción Matemática hace uso de la Ordenación. ¿Se puede demostrar independientemente de la Ordenación?

Answer 1

En una versión de los números naturales $\mathbb{N}$ donde cada número además de cero tiene un predecesor (único), como los ordinales de von Neumann, u otro modelo de los Axiomas de Peano (incluyendo el axioma de inducción), tenemos lo siguiente:

La inducción implica la buena ordenación:

Supongamos que $S$ no tiene un elemento mínimo. Entonces $ n = 0 \notin S$, porque de lo contrario $n$ sería mínimo. De manera similar, $n = 1 \notin S$, porque entonces $1$ sería mínimo, ya que $n = 0$ no está en $S$. Supongamos que ninguno de los números $0, 1, 2, \cdots, n$ está en $S$. Luego $n+1 \notin S$, porque de lo contrario sería mínimo. Entonces por inducción $S$ está vacío, lo cual es una contradicción.

La buena ordenación implica la inducción:

Supongamos que $P(0)$ es verdadero, y que $P(n+1)$ es verdadero siempre que $P(n)$ es cierto. Si $P(k)$ no es verdadero para todos los enteros, entonces dejemos que $S$ sea el conjunto no vacío de $k$ para los cuales $P(k)$ no es verdadero. Por la buena ordenación, $S$ tiene un elemento mínimo, que no puede ser $k = 0$. Pero entonces $P(k-1)$ es verdadero, y así $P(k)$ es verdadero, una contradicción.

Answer 2

El principio de inducción matemática es equivalente al principio de inducción fuerte y ambos son equivalentes al principio de buena ordenación. Al menos si asumimos que los números naturales son una estructura que satisface algunos axiomas básicos.

Esto significa que si asumimos uno, tenemos el otro. Por supuesto, si asumimos un sistema de axiomas mucho más fuerte, o tenemos un universo mucho más grande que pueda hacer afirmaciones significativas sobre los números naturales, entonces podemos demostrar cada uno de ellos a partir de esos axiomas, pero su equivalencia seguiría presente.

De hecho, esta equivalencia es una de las cosas más fundamentales en las matemáticas modernas: algo está bien ordenado si y solo si podemos realizar una inducción sobre él. Por eso a menudo demostramos uno a partir del otro, y viceversa.

Answer 3

El principio del buen orden es equivalente al PMI.

Primero demostraremos que PMI $\implies$ WOP usando inducción fuerte. $P(n)$ Cada subconjunto de $\mathbb{N}$ que contiene n tiene un elemento mínimo

Base: $1$ es ciertamente el elemento mínimo de cualquier subconjunto de N que contiene $1$. Por lo tanto, P(1) es verdadero.

Inducción: Consideremos cualquier conjunto S que contiene $k + 1$.

Si S contiene algún elemento, digamos m, menor que $k + 1$, entonces por inducción fuerte, como $P(m)$ es verdadero, sabemos que S contiene un elemento mínimo.

Si S no contiene ningún elemento menor que $k + 1$, entonces S contiene un elemento más pequeño, que es $k + 1$. Por lo tanto, $P(k + 1)$ es verdadero. Ahora demostraremos la dirección inversa, es decir, WOP $\implies$ PMI.

Por contradicción, asumamos que hay una propiedad P tal que

$P(1)$ es verdadero y siempre que $P(k)$ es verdadero, $P(k + 1)$ también es verdadero.

Existe un número m tal que $P(m)$ es falso.

Sea $S=\left \{x\in \mathbb{N}|P(x)\text{ es falso} \right \}$.

Dado que $m\in S$, S es un subconjunto no vacío de N y por lo tanto tiene un elemento mínimo que llamaremos s.

$s\neq 1$ porque $P(1)$ es verdadero. Dado que s es el elemento mínimo de S, $s − 1 \notin S$ .

∴ $P(s−1)$ es verdadero. Pero entonces $P((s −1)+1)$ también debe ser verdadero y por lo tanto $s \notin S$

Answer 4

Principio de orden bien $\implies $ principio de inducción matemática

Prueba: Sea, $P(n) $ una proposición válida para todo $n\in \Bbb{N}$.

Supongamos que, $P(1) $ se cumple y $P(n) $ se cumple implica que $P(n+1) $ se cumple.

Para demostrar: $P(n) $ se cumple para todo $n\in \Bbb{N}$.

Sea, $A=\{ n\in \Bbb{N} : P(n) \text { no se cumple } \}$

Si $A\neq \emptyset$, entonces por el principio de orden bien, $A$ tiene un elemento menor, digamos $a$.

Entonces, para cualquier $a-1, $P(a-1) $ se cumple.

Pero esto contradice la hipótesis de que $P(n) \implies P(n+1) $ se cumple.

Por lo tanto, $A=\emptyset$. Así que $P(n)$ se cumple para todo $n\in \Bbb{N}$.

principio de inducción matemática$\implies $ Principio de orden bien.

Supongamos que, $A\subset \Bbb{N}$ no tiene un elemento menor.

Afirmamos que $A=\emptyset$ o $A^c (\Bbb{N}\setminus A) =\Bbb{N}$

$P(n) : n\in \Bbb{N}\text{ tal que } n\in A^c$

Entonces, $1\in A^c$ de lo contrario sería el elemento menor de $A$.

Supongamos, $n\in A^c$ .

Dado que $n\notin A$ y todos los predecesores de $n\notin A$ implica que $n+1\notin A$ .

Por lo tanto, $n\in A^c \implies n+1\in A^c$ .

Por lo tanto, por el principio de inducción matemática, $P(n) $ es verdadero para todo $n\in \Bbb{N}$ y por lo tanto $A^c=\Bbb{N}$ .

Por lo tanto, $A=\emptyset$ y por lo tanto todos los subconjuntos no vacíos de $\Bbb{N}$ tienen un elemento menor.