¿Es válida mi prueba? Demostrar que el Principio de Ordenación implica el Principio de Inducción Matemática

Question

En primer lugar, convierto el PMI en notación simbólica: $$S=\left \{ n\in \mathbb{N}\mid 1\in S, \left ( \forall n\in \mathbb{N} \right)\left ( n\in S \Rightarrow n + 1 \in S \right ) \right \} \Rightarrow S = \mathbb{N}$$ Y cambiar el nombre de WOP por el de P(X). Entonces, ahora mi pensamiento es tomar la negación de la implicación y llegar a una contradicción. Lo convierto en notación simbólica. $$P(X)\Rightarrow \left \{ S=\left \{ n\in \mathbb{N}\mid 1\in S, \left ( \forall n\in \mathbb{N} \right)\left ( n\in S \Rightarrow n + 1 \in S \right ) \right \} \Rightarrow S = \mathbb{N} \right \}$$ y su negación: $$P(X) \wedge S=\left \{ n\in \mathbb{N}\mid 1\in S,\left ( \forall n\in \mathbb{N} \right )\left ( n\in S\Rightarrow n+1\in S \right ) \right \}\wedge S\neq \mathbb{N}$$ Entonces, supongamos que la negación es verdadera. Entonces, $P(X)\Rightarrow S$ tiene un elemento más pequeño, $m$ . Si $m=1$ , entonces S = $\mathbb{N}$ , lo cual es una contradicción. Por lo tanto, supongamos $m < 1$ . Entonces $m \notin \mathbb{N}$ pero $S \subseteq \mathbb{N}$ (porque cada $n \in \mathbb{N}$ ), lo cual es una contradicción. Por lo tanto, la implicación es verdadera.

La prueba "de libro" es esta: "Prueba. Sea S un subconjunto de $\mathbb{N}$ tal que $1 \in S$ y S es inductivo. En queremos demostrar que $S = \mathbb{N}$ . Supongamos que $S \neq \mathbb{N}$ y que $S = \mathbb{N} - T$ . Por la WOP, el conjunto no vacío $T$ tiene un elemento mínimo. Este menor elemento no es $1$ porque $1 \in S$ . Si el menor elemento es $n$ entonces $n \in T$ y $n-1 \in S$ . Pero por la propiedad inductiva de $S$ , $n-1 \in S$ implica que $n \in S$ . Esto es una contradicción. Por lo tanto, $S = \mathbb{N}$ ."

¿Por qué son capaces de construir $S = \mathbb{N} - T$ y luego concluir que $S = \mathbb{N}$ para todo el universo? ¿Cuál es la versión simbólica de esta prueba?

Answer 1

Lo que escribes para el principio de inducción es una tontería. Observe que en su conjunto $S$ El $n$ en la notación del constructor de conjuntos es una variable libre, ya que en la fórmula dentro de la notación está acotada. Lo que escribes no es lo que crees que quieres decir.

El Principio de Inducción Matemática debería decir algo así: $$(S\subseteq\mathbb{N})\wedge(1\in S)\wedge(\forall n(n\in S\rightarrow n+1\in S)) \implies S=\mathbb{N}.$$

Así que visto así, la negación de WO que implica esto, sería que WO se mantiene, y $S\subseteq \mathbb{N}$ y $1\in S$ y $\forall n(n\in S\rightarrow n+1\in S)$ pero $S\neq \mathbb{N}$ .

Su argumento, por tanto, no es correcto. Por ejemplo, no tiene ninguna garantía para afirmar que "si $m=1$ entonces $S=\mathbb{N}$ ". Eso no se deduce de una afirmación correcta. (De hecho, no entiendo cómo se deduce de lo que has escrito...) Y además nunca dices qué pasa si $m\gt 1$ Así que tu argumento no funciona.

En cuanto a sus preguntas:

1. Puedes "construir" $\mathbb{N}-S$ porque si $S$ está dado, entonces por Separación tenemos que $A=\{n\in\mathbb{N}\mid n\notin S\} = \mathbb{N}-S$ existe.

2. Si $\mathbb{N}-S$ es no vacía, entonces tiene un elemento mínimo. Ese elemento no es $1$ (ya que $1\in S$ ). Si sabemos que todo elemento que no sea $1$ es un sucesor ( ¡que es un punto clave que hay que probar y no es obvio! ) entonces si $n$ es el menor elemento de $\mathbb{N}-S$ entonces $n\gt 1$ así que $n=m+1$ para algunos $m$ . Desde $m\lt n$ y $n$ es el menor elemento de $\mathbb{N}-S$ entonces $m\notin \mathbb{N}-S$ Por lo tanto $m\in\mathbb{S}$ . Pero $m\in S\rightarrow m+1=n\in S$ contradiciendo nuestra suposición de que $n\in\mathbb{N}-S$ .

3. Esta contradicción surge de la suposición no descargada de que $\mathbb{N}-S$ es no vacía. Por lo tanto, $\mathbb{N}-S$ está vacía.

4. Esto significa que $\forall n(n\in\mathbb{N}\implies n\in S)$ . Así, $\mathbb{N}\subseteq S$ .

5. Como ya estábamos asumiendo $S\subseteq\mathbb{N}$ se deduce entonces que $S=\mathbb{N}$ según sea necesario.