¿Por qué la inducción debe ser un axioma?

Question

Me di cuenta de que hay un axioma que dice que si $S(n)\implies S(n+1)$, y $S(1)$ es true, $\forall n \in \Bbb N, S(n).$

Mi pregunta es ¿por qué esto es un axioma? ¿por qué no podemos derivar esto de los otros axiomas?

Answer 1

Si usted está buscando en los axiomas de Peano para la Aritmética, y por 'los otros axiomas' te refieres:

$1. \bf{\forall x \ \neg s(x) = 0}$

$2. \bf{\forall x \forall y (s(x) = s(y) \rightarrow x = y)}$

$3. \bf{\forall x \ x+0=x}$

$4. \bf{\forall x \forall y \ x+s(y)=s(x+y)}$

$5. \bf{\forall x \ x\cdot0=0}$

$6. \bf{\forall x \forall y \ x\cdot s(y)=(x \cdot y) + x}$

entonces no, no podemos derivar el axioma de inducción, que voy a formalizar como:

$\bf{(S(0) \land \forall x (S(x) \rightarrow S(s(x))))\rightarrow \forall x \ S(x)}$ (Incluyo $0$$\mathbb{N}$, por lo que la base es $\bf{S(0)}$)

Aquí es un contraejemplo:

Tome $\bf{S(x): s(x) \not = x}$

Por el axioma $1$,$\bf{\neg s(0)=0}$, y por lo tanto, tenemos $\bf{S(0)}$

También, si tenemos $\bf{S(k)}$, es decir, si tenemos $\bf{s(k) \not = k}$, entonces si sería cierto $\bf{s(s(k)) = s(k)}$), luego por el Axioma 2 tenemos $\bf{s(k)=k}$, lo que contradice $\bf{S(k)}$, y así tenemos el $\bf{s(s(k)) \not = s(k)}$, es decir, $\bf{S(s(k))}$

OK, así que con esto $S(x)$, $\bf{S(0) \land \forall x (S(x) \rightarrow S(s(x)))}$ simplemente por virtud de los Axiomas 1 y 2 solamente.

Pero, que no necesariamente tienen $\bf{\forall x \ S(x)}$

Considere un modelo con el dominio $\mathbb{N} \cup \{ q \}$, es decir, los números naturales junto con algunos "extras" elemento $q$.

Interpretar la $\bf{0}$ constante símbolo $0$

Interpretar la $\bf{s}$ símbolo de función como una función de $f$ que $f(n)=n+1$ cualquier $n \in \mathbb{N}$, y para el que $f(q)=q$

Interpretar la $\bf{+}$ símbolo de función como una función de $g$ que $g(m,n)=m+n$ $g(m,q)=g(q,n)=g(q,q)=q$ cualquier $m,n \in \mathbb{N}$

Interpretar la $\bf{\cdot}$ símbolo de función como una función de $h$ que $h(m,n)=m\cdot n$ cualquier $m,n \in \mathbb{N}$, por lo que $h(0,q)=h(q,0)=0$, y para el que $h(m,q)=h(q,n)=h(q,q)=q$ cualquier $m, n \in \mathbb{N}\setminus \{ 0 \}$

A continuación, se puede comprobar con facilidad que todos los $6$ axiomas se cumplen, y por lo tanto de acuerdo a esta interpretación es cierto que $\bf{S(0) \land \forall x (S(x) \rightarrow S(s(x)))}$. Pero, puesto que el $f(q)=q$, es falso que $\bf{\forall x \ s(x) \not = x}$. Por lo tanto, es falso que $\bf{S(0) \land \forall x (S(x) \rightarrow S(s(x))))\rightarrow \forall x \ S(x)}$, es decir, el axioma de inducción no de acuerdo a esta interpretación. Por lo tanto, el axioma de Inducción no se siguen de los axiomas $1$ a través de $6$.

Answer 2

Los Postulados de Peano describir lo que queremos los números naturales. Una cosa que queremos es que los números naturales a ser una continua corriente de

0, 1, 2, 3, ...

y no se compone de varias secuencias infinitas como

0, 1, 2, 3, ..., 0', 1', 2', ...

donde cada número tiene un sucesor y aritmética funciona bien, pero si empieza a contar en algún lugar en la primera secuencia nunca vas a llegar a cualquier número en el segundo (cebado) de la secuencia.

El axioma de inducción prohíbe esta situación diciendo que para cada número N, si se empieza a contar desde 0 que finalmente va a llegar a N.

Answer 3

En última instancia, la manera en que podemos demostrar (por lo general) de que un determinado axioma $\alpha$ no es ya una consecuencia de un conjunto de axiomas $T$ es mediante la construcción de un modelo (me he ligado a una definición formal, pero usted debe saltar en la primera lectura - sólo pensar en un modelo de manera informal, como "una cosa que la satisfacción de los axiomas") de $T$ que $\alpha$ falla. El ejemplo más famoso de esto es el postulado paralelo, lo que fue demostrado para ser independiente de los restantes postulados de Euclides a través de la construcción de geometrías no Euclidianas realizados.$^1$

Ahora, en nuestro caso - supongo que estás hablando de la teoría de la PA - nuestra teoría tiene dos partes:

• Un "algebraica" de parte, la afirmación de que los números naturales forman un discreto ordenó semiring.

• La inducción de axiomas (un "conjunto de la teoría de la" parte).

No es trivial para construir un modelo de la antigua, en la que éste puede fallar, pero que existen; ver, por ejemplo, aquí o aquí.

(Por cierto, una vez que incluyen la inducción se hace muy difícil la construcción de otros modelos de la habitual - que podemos ver, por ejemplo, en Tennenbaum del teorema. Con Tennenbaum en mente, de hecho tenemos una receta muy fácil de cocinar discretos ordenó semirings donde la inducción se produce un error: simplemente elija cualquiera de los "fácilmente descriptible" discretos ordenó semiring no isomorfo a $\mathbb{N}$!)

---

$^1$No quiero dar la impresión equivocada aquí: independencia de los resultados puede ser extremadamente difícil de establecer, desde el más complicado que una teoría es la más difícil de sus modelos para describir en general. Por ejemplo, a un nivel más avanzado, también nos muestran que la hipótesis continua es independiente de la habitual de los axiomas de la teoría de conjuntos, suponiendo que estos últimos son consistentes, por supuesto. Gödel construido el interior del modelo de $L$ y mostró que satisfecho CH; más tarde, Cohen desarrollado forzar y demostró que se podía producir modelos donde CH falla (así como de los modelos en CAD se mantiene, pero el primero es más impresionante: además de ser el resto de la pieza que falta, una de las consecuencias de Gödel trabajo fue que el establecimiento de la consistencia de la falta de CH es en un sentido preciso más difícil de establecer la consistencia de CH). Sin embargo, a diferencia de la geometría no Euclidiana y ligeramente inusual discretos ordenó semirings, los modelos de la teoría de conjuntos son muy complicados y que no hay buena manera de describir estos resultados sin un montón de trabajo técnico.

Answer 4

Es tal vez útil pensar en términos de pruebas. Para cada uno de los $n$, una prueba formal de las $S(n)$ se ve algo como esto:

$$\begin{align*} S(1), S(1) &\implies S(2)\\ S(2), S(2) &\implies S(3)\\ &\vdots \\ S(n-1), S(n) &\implies S(n) \end{align*}$$

los que usamos el modus ponens para ir de cada línea a la siguiente, y $S(i) \implies S(i+1)$ se corta la mano para una prueba formal de esta declaración, el uso de los otros (no inductiva) axiomas en su sistema elegido.

Pero aunque nos puede dar una prueba formal de las $S(n)$ por cada $n \in \mathbb{N}$, no hay nada por encima de la que se compara a una prueba formal de la fórmula $(\forall n \in \mathbb{N}) S(n)$.

Para decirlo de otra manera: pruebas son objetos limitados, así que no hay ningún sentido en el que podemos 'roll-up" de las pruebas para cada uno de los $n$ en una sola prueba formal de tratar con todos los $n$ a la vez. En su lugar tenemos el axioma de inducción.

Answer 5

La respuesta corta es que sin un axioma, hay una diferencia entre

$$\text{You can have as many apples as you want.$ ^ * % $ $}$y $$\text{You can have infinitely many apples.}$ $

$^*$$\scriptsize\text{(finite amount implied)}$