¿Diferencia entre la inducción de primer y segundo orden?

Question

¿Puede alguien explicar la diferencia entre la inducción tal y como se plantea en la lógica de primer orden y la de segundo orden? No entiendo la diferencia en lo que respecta a cosas como los axiomas de Peano.

Answer 1

La declaración informal de la inducción es:

Para cualquier propiedad $P$ de números naturales, si $P(0)$ se mantiene, y $P(n)$ implica $P(n+1)$ para todos $n$ entonces $P(n)$ es válida para todos los $n$ .

Por supuesto, esto plantea la pregunta: ¿Qué queremos decir exactamente con una "propiedad de los números naturales"?

Una interpretación natural es identificar las propiedades de los números naturales con los conjuntos de números naturales. Es decir, para cualquier propiedad $P$ podemos formar el conjunto de todos los números naturales que satisfacen esa propiedad. Y para cualquier conjunto de números naturales $X$ podemos considerar la propiedad de estar en $X$ . Por ejemplo, la propiedad de ser un número primo corresponde al conjunto $\{n\in \mathbb{N}\mid n\text{ is prime}\}$

Otra interpretación natural es identificar las propiedades de los números naturales con fórmulas en una variable libre en alguna lógica (en esta discusión, vamos a hablar sólo de la lógica de primer orden en el lenguaje de la aritmética). Aquí la sintaxis de la lógica nos da un lenguaje para escribir las propiedades de los números naturales. Por ejemplo, la propiedad de ser un número primo corresponde a la fórmula $\lnot (x= 1)\land \forall y\, (\exists z\, (y\cdot z = x) \rightarrow (y = 1 \lor y = x))$ .

La inducción bajo la interpretación "las propiedades son conjuntos" puede formalizarse como sigue:

$\forall P\subseteq \mathbb{N}: ((0\in P\land \forall n\in \mathbb{N}: (n\in P \rightarrow (n+1)\in P))\rightarrow \forall n\in \mathbb{N}: n\in P)$

Esta es una sentencia de lógica de segundo orden ya que implica una cuantificación $\forall P\subseteq \mathbb{N}$ en subconjuntos de $\mathbb{N}$ .

La interpretación "las propiedades son fórmulas" conduce a la siguiente formalización de la inducción:

$(\varphi(0)\land \forall n\, (\varphi(n)\rightarrow \varphi(n+1)) \rightarrow \forall n\,\varphi(n)$

Aquí tenemos un esquema infinito de sentencias de lógica de primer orden uno para cada fórmula de primer orden $\varphi(x)$ . Es de primer orden porque los cuantificadores sólo abarcan elementos de $\mathbb{N}$ , no subconjuntos, y las fórmulas $\varphi(x)$ son a su vez de primer orden.

Cabe destacar que la inducción de segundo orden es mucho más fuerte que la de primer orden. La inducción de segundo orden se aplica a todo subconjuntos, mientras que la inducción de primer orden sólo se aplica a aquellos que pueden ser definidos por alguna fórmula de primer orden (y como hay $2^{\aleph_0}$ -muchos subconjuntos de $\mathbb{N}$ y sólo $\aleph_0$ -muchas fórmulas de primer orden, hay muchos subconjuntos que no son definibles).

Los axiomas de Peano de segundo orden (que consisten en algunas reglas básicas de la aritmética, junto con el axioma de inducción de segundo orden anterior) bastan para precisar $\mathbb{N}$ hasta el isomorfismo.

Los axiomas de Peano de primer orden (que consisten en algunas reglas básicas de la aritmética, junto con el esquema del axioma de inducción de primer orden anterior) no pueden esperar precisar $\mathbb{N}$ hasta el isomorfismo (gracias a los teoremas de Löwenheim-Skolem). Es decir, existen "modelos no estándar" de los axiomas de Peano de primer orden, que satisfacen la inducción para todo definible de primer orden pero no para subconjuntos arbitrarios.