Parámetros en los esquemas de los axiomas de inducción aritmética

Question

El esquema de inducción de la Aritmética de Peano se da de forma estándar como el cierre universal de $\phi(0)\land \forall x (\phi(x)\rightarrow \phi(x+1)) \rightarrow \forall x\phi(x)$ . Sin embargo, dado que el lenguaje de la aritmética tiene un nombre para cada número estándar, no es obvio (para un principiante como yo) por qué son necesarios los parámetros en el esquema de inducción; por qué no restringirse al caso en que $x$ es la única variable libre en $\phi$ ?

• ¿Tener parámetros en el esquema de inducción realmente hace que el sistema sea más fuerte y, si es así, cómo se demuestra eso?
• ¿Existen teoremas naturales que sólo o más fácilmente puedan demostrarse utilizando el sistema más fuerte?
• ¿Tiene algún interés el sistema más débil?

Answer 1

$\def\fii{\varphi}$ Mientras que las otras respuestas resuelven la cuestión, una forma sencilla de derivar la inducción para una fórmula $\fii(x,\vec p)$ con parámetros $\vec p$ es utilizar la inducción sin parámetros sobre la fórmula

$$\psi(x)=\forall\vec p\,[\fii(0,\vec p)\land\forall y\,(\fii(y,\vec p)\to\fii(y+1,\vec p))\to\fii(x,\vec p)].$$

De hecho, esto deriva el esquema de inducción con parámetros de la inducción (sin parámetros) regla ya que $\psi(0)$ y $\psi(x)\to\psi(x+1)$ son demostrables en Q sin ninguna suposición sobre $\fii$ .

Answer 2

Las dos teorías son equivalentes. Para ver esto, supongamos que tenemos la inducción sin parámetros, y supongamos que $\phi(x,y)$ es una fórmula con dos variables libres. Supongamos que tenemos un modelo $M$ satisfaciendo la inducción sin parámetros, y hay un $b\in M$ tal que $\phi(x,b)$ obedece a la hipótesis del esquema de inducción con parámetro $b$ pero no la conclusión. Afirmo que hay un mínimo de tal $b$ en $M$ . La razón es que la colección de tales $b$ violando el esquema de inducción para $\phi(x,b)$ con el parámetro $b$ es un subconjunto definible sin parámetros de $M$ ya que esta propiedad es expresable, pero el esquema de inducción sin parámetros demuestra que todo conjunto definible no vacío $B$ tiene un miembro mínimo, porque de lo contrario la afirmación $\psi(x)$ expresando que $x$ está por debajo de todos los miembros de $B$ sería inductivo y, por tanto, universal, en contra de $B$ siendo no vacía. Por lo tanto, hay un mínimo de tal $b$ .

En particular, el menor de estos $b$ es realmente definible, por lo que no lo necesitamos como parámetro después de todo, y así el esquema de inducción para $\phi(x,b)$ se sigue por el esquema de inducción sin parámetros. Por lo tanto, no puede haber tal $b$ para los que el esquema de inducción de parámetros falla.

Así, la teoría de la inducción sin parámetros implica la teoría completa que mencionas.

Answer 3

Aunque la inducción sin parámetros y la inducción parametrizada son equivalentes, hay una sutileza importante que a menudo justifica la adición de parámetros.

Supongamos que $\phi(x,p)$ es tal que $$\exists p(\phi(0,p) \land \forall x(\phi(x,p) \to \phi(x+1,p)) \land \lnot \forall x \phi(x,p)).$$ El truco de Joel es que $$p_0 = \min\lbrace p : \phi(0,p) \land \forall x(\phi(x,p) \to \phi(x+1,p)) \land \lnot\forall x\phi(x,p)\rbrace$$ es definible sin parámetros. Sin embargo, la existencia de $p_0$ es otro caso de inducción (bajo la forma del principio del mínimo elemento).

La complejidad de una fórmula en aritmética suele medirse contando el número de alternancias de cuantificadores cuando se pone en forma prenex (a menudo ignorando los cuantificadores acotados). Con esta medida, la complejidad de la inducción que justifica la existencia de $p_0$ es estrictamente mayor que la de la fórmula original $\phi(x,p)$ . Así que hay que pagar un precio por eliminar los parámetros.

Por lo tanto, al considerar las teorías atíticas con formas limitadas de inducción ( $EFA$ , $PRA$ , $IOpen$ , $I\Delta_n$ , $I\Sigma_n$ ) es necesario incluir parámetros. También es natural pensar en $PA$ como la unión de estas teorías restringidas, lo que lleva a la inclusión de parámetros al formular el esquema de inducción.

Answer 4

Puedes demostrar que las dos teorías son, de hecho, equivalentes. Por inducción (NB: 'meta-inducción') sobre el número de parámetros, podemos reducir la afirmación al caso en que se tiene una teoría $T$ con el esquema de inducción habitual y una teoría $T'$ que es una extensión de $T$ por un esquema de inducción de un parámetro.

Por lo tanto, asuma $T$ y $T'$ no son equivalentes. Esto implica que hay un modelo $\mathcal{M} \vDash T'$ y una sentencia abierta de dos posiciones $\phi(x,y)$ tal que

$$\mathcal{M} \vDash \phi(0,\beta) \wedge (\forall x (\phi(x,\beta) \rightarrow \phi(x+1,\beta))) $$

pero también,

$$\mathcal{M} \nvDash \forall x \phi(x,\beta)$$

para algunos $\beta \in \mathcal{M}$ . Pero ahora observe que lo anterior es equivalente a

$$ \mathcal{M} \vDash \exists y (\phi(0,y) \wedge (\forall z (\phi(z,y) \rightarrow \phi(z+1,y))) \wedge \neg \forall z \phi(z,y) $$

y si llamas a esta última frase $S$ entonces se obtiene que $S \wedge \phi ' (x)$ viola el esquema de inducción habitual, donde $\phi ' (x)$ es la frase abierta de un lugar que obtenemos cerrando $y$ bajo el cuantificador existencial en $S$ . Es decir, tenemos $S \wedge \phi ' (0)$ y $ \forall x (S \wedge \phi ' (x) \rightarrow S \wedge \phi ' (x+1))$ pero no $\forall x S \wedge \phi ' (x)$ . Pero eso es una contradicción ya que $\mathcal{M}$ es un modelo de $T$ . Por lo tanto, las dos teorías son equivalentes.