¿Cómo se demuestra el buen orden sin inducción matemática? (y viceversa)

Question

Aquí está mi intento de demostrar el Principio de Buen Orden, es decir, que cualquier subconjunto no vacío de $\Bbb N$ el conjunto de los 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 ningún elemento mínimo. Defina $A = \left\{n\in \Bbb N : (\forall s\in S)(n \leq s)\right\}$ . Es evidente que $1\in A$ . Supongamos que $n\in A$ para cada $s \in S$ existe $q \in N$ tal que $n + q = s$ . Desde $q \ge 1$ , $n+1 \leq s$ para todos $s\in S$ . Por Principio de inducción matemática, $A = \Bbb N$ . Tome cualquier $s_0 S$ entonces $(\forall s\in S)(s_0 \leq s)$ . (Esto contradice $S$ no tiene elemento mínimo).

¿Cómo demuestro la afirmación sin invocar la inducción matemática? Además, he leído que la prueba del Principio de Inducción Matemática hace uso del Ordenamiento Bueno. ¿Puede demostrarse también 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 (único) predecesor, como los ordinales de von Neumann, o cualquier otro modelo de los Axiomas de Peano (incluyendo el axioma de inducción), tenemos lo siguiente:

La inducción implica una buena ordenación:

Supongamos que $S$ no tiene ningún elemento mínimo. Entonces $ n = 0 \notin S$ porque de lo contrario $n$ sería mínima. Del mismo modo $n = 1 \notin S$ porque entonces $1$ sería mínima, ya que $n = 0$ no está en $S$ . Supongamos que ninguno de $0, 1, 2, \cdots, n$ está en $S$ . Entonces $n+1 \notin S$ porque de lo contrario sería mínimo. Entonces por inducción $S%$ es vacío, una contradicción.

Ordenar bien implica inducción:

Supongamos que $P(0)$ es verdadera, y $P(n+1)$ es verdadera siempre que $P(n)$ es cierto. Si $P(k)$ no es cierto para todos los números enteros, entonces dejemos que $S$ sea el conjunto no vacío de $k$ para lo cual $P(k)$ no es cierto. Ordenando bien $S$ tiene un elemento mínimo, que no puede ser $k = 0$ . Pero entonces $P(k-1)$ es verdadera, y por tanto $P(k)$ es verdadera, una contradicción.

Answer 2

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

Esto significa que si asumimos una, tenemos la otra. 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 se mantendría.

De hecho, esta equivalencia es una de las cosas más fundamentales de las matemáticas modernas: algo está bien ordenado si y sólo si podemos realizar una inducción sobre ello. Por eso a menudo demostramos una cosa a partir de la otra, y viceversa.

Answer 3

El principio de ordenación es equivalente al PMI.

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

Base: $1$ es ciertamente el menor elemento de cualquier subconjunto de N que contenga $1$ . Por tanto, P(1) es cierta.

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

Si S contiene algún elemento, digamos m, menor que $k + 1$ entonces por inducción fuerte, como $P(m)$ es cierto, 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, a saber $k + 1$ . Así $P(k + 1)$ es cierto. Ahora mostraremos la dirección inversa, es decir, WOP $\implies$ PMI.

Por contradicción, supongamos que existe una propiedad P tal que

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

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

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

Desde $m\in S$ S es un subconjunto no vacío de N y, por tanto, tiene un elemento mínimo, digamos s.

$s\neq 1$ porque $P(1)$ es cierto. Puesto que s es el menor elemento de S, $s 1 \notin S$ .

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

Answer 4

Principio de ordenación de pozos $\implies $ principio de inducción matemática

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

Supongamos, $P(1) $ sostiene y $P(n) $ implica $P(n+1) $ retenciones.

Para mostrar : $P(n) $ es válido para $n\in \Bbb{N}$ .

Déjalo, $A=\{ n\in \Bbb{N} : P(n) \text { doesn't holds } \}$

Si $A\neq \emptyset$ entonces por principio de ordenación de pozos, $A$ tiene un elemento menor, digamos $a$ .

Entonces, para cualquier $a-1<a$ , $P(a-1) $ retenciones.

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

Por lo tanto, $A=\emptyset$ . Así $P(n)$ es válido para $n\in \Bbb{N}$ .

principio de inducción matemática $\implies $ Bien principio de ordenación .

Supongamos , $A\subset \Bbb{N}$ no tiene ningún elemento mínimo.

Reclamación $A=\emptyset$ o $A^c (\Bbb{N}\setminus A) =\Bbb{N}$

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

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

Supongamos, $n\in A^c$ .

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

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

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

Así que.., $A=\emptyset$ y, por tanto, todos los subconjuntos no vacíos de $\Bbb{N}$ tiene el menor elemento.