¿Por qué la inducción limitada es más fuerte que la inducción abierta?

Question

Me parece que cualquier fórmula en el lenguaje de la aritmética de primer orden que sólo tenga cuantificadores acotados puede ser escrita como una fórmula sin cuantificadores. Por ejemplo, "Existe un n < 1000 tal que P(n)" puede escribirse como "P(1) o P(2) o ... o P(999)", y "para todos los n < 100, P(n)" puede escribirse como "P(1) y P(2) y ... P(99)". Entonces, ¿cómo puede la aritmética acotada, es decir, la inducción de Q + en todas las fórmulas con cuantificadores acotados, ser más fuerte que la inducción abierta, es decir, la inducción de Q + en todas las fórmulas sin cuantificadores? ¿No se puede probar ningún teorema utilizando la inducción en cuantificadores acotados también sin ella, ya que sólo se puede aplicar la inducción para probar las expresiones libres de cuantificadores, como P(1), P(2), ..., P(999), utilizando la inducción abierta, y luego al final utilizar esas proposiciones para derivar la proposición con los cuantificadores acotados?

Cualquier ayuda sería muy apreciada.

Gracias por adelantado.

Answer 1

Creo que estás asumiendo que el límite en un cuantificador limitado tiene que ser un término cerrado - un número. Pero no es así. Aquí hay una fórmula de cuantificador limitado en el lenguaje de la aritmética: $$ \phi(x) = (x > 1) \land (\forall a < x)(\forall b < x) [ ab = x \to a = 1 \lor b = 1] $$

Esta fórmula define el conjunto de números naturales primos. Este conjunto no puede ser definido por una fórmula sin cuantificadores. (Esquema de la prueba: verificar que un conjunto definible por una fórmula sin cuantificador debe ser finito o cofinito).