¿Principio de ordenación bien en $\mathbb N \iff$ principio de inducción $\iff$ principio de inducción fuerte: Cómo probar una de ellas?

Question

Bien-principio de orden en $\mathbb N \iff$ Principio de inducción $\iff$ Principio de la fuerte inducción

Cómo probar uno de ellos ?

En Proofwiki hay un artículo demostrando la equivalencia de las declaraciones mencionadas anteriormente. Sin embargo, la prueba de una declaración individual depende de la prueba de uno de los otros, con el fin de probar de todo, uno debe demostrar que uno de ellos ?

Sé que podemos demostrar el Principio de la inducción asumiendo que hay una smallets $n \in \mathbb N$ tal que $P(n)$ no espera y, a continuación, obtener una contradicción, puesto que ya se ha demostrado $P(0) \land P(n-1) \Rightarrow P(n)$, lo $P(n)$ es de hecho verdad.

Sin embargo, en esta prueba que en realidad estamos confiando en el principio de orden en $\mathbb N$ ? De lo contrario, ¿cómo se puede asumir que hay un smallets $n\in \mathbb N$ tal que $P(n)$ es falso ?

Answer 1

Estos son principios, no de los teoremas.

Si en un principio se mantiene, entonces todos ellos deben tener. Si en un principio no lleva a cabo, todos ellos no para mantener. Por lo tanto, los principios son equivalentes. (Esta es la razón por la que vemos el bicondicional $\iff$ se utiliza.)

Dicho de otra manera, lo que tenemos es el siguiente afirmación verdadera:

Bien-principio de orden en $\mathbb N \iff$ Principio de inducción $\iff$ Principio de la fuerte inducción.

Esta afirmación reivindicaciones nada sobre el valor de verdad de cualquier uno de los principios: afirma sólo que si un principio es verdadero, que todo debe ser verdad, y si un principio es falso, todos deben ser falsas.

Y, por lo tanto, adoptamos el principio de buena ordenación en $\mathbb N$, como un axioma, o bien derivado del principio de inducción, que es en sí mismo básica (que es cierto).

Answer 2

Sí, el punto de equivalencia es que si $\mathbb{N}$ tiene una de las tres características mencionadas, que tiene a todos.

Es interesante pensar acerca de lo que se necesitaría para demostrar que uno de estos (es decir, bien el pedido) no en el hecho de sostener para $\mathbb{N}$. Que los axiomas ¿piensa utilizar? Usted tiene los axiomas de la aritmética, y el hecho de que $\mathbb{N}$ es totalmente ordenado -, pero estos no pueden ser suficiente, porque los números racionales positivos $\mathbb{Q}^+$ también la satisfacción de estos axiomas, y no bien ordenadas. Usted necesita algo más: por ejemplo, un axioma que indica que no existen números naturales entre 0 y 1, y luego también un axioma que prohíbe a los elementos "después de" los elementos $1, 1+1, 1+1+1, \ldots$, etc. Desde los axiomas de la aritmética no son suficientes para distinguir los números naturales desde otro número, como los sistemas de $\mathbb{Q}^+$, algo más de axiomas -- buen orden, u otros equivalentes a él-debe ser añadido.

Answer 3

Estas son propiedades muy básicas de los números naturales, por lo que cualquier prueba dependerá de la definición del (conjunto de) los números naturales. ¿Qué es?