Mostrar que la PA puede probar el pigeon-hole principio

Question

Para el siguiente ejercicio es de Richard Kaye Libro ejercicio 5.12 (Capítulo 5)

El pigeon-hole principio es el esquema:

Para cualquier fórmula, $\psi$, en el lenguaje de la aritmética,

$\forall s\ (\forall x<s+1, \exists e<s\ \psi(x,e) \rightarrow\ \exists x, \exists r < s+1, \exists e<s (x \neq r\ \wedge\psi(x,e) \wedge\psi(r,e)))$

Mostrar que la PA puede demostrar (todos los casos) de la declaración.

Esta declaración es tan intuitivamente cierto, pero estoy teniendo algunos problemas para probarlo y no me entiendo muy bien las sugerencias dadas en el libro.

Cualquier ayuda o ideas es muy apreciado.

Answer 1

Desde la prueba sugerida por Kaye está esbozado en otra respuesta, voy a hablar de un más de alta potencia manera de probar esto. Debido a que el segundo-orden de sistema de $\mathsf{ACA}_0$ es conservador sobre la PA de las frases en el idioma de la PA, se puede probar la declaración en $\mathsf{ACA}_0$. Esto es más fácil porque se puede trabajar directamente con las funciones de$\mathbb{N}$$\mathbb{N}$, y puede formar cualquier función que es aritméticamente definibles.

En primer lugar, podemos probar en $\mathsf{ACA}_0$ que si $f$ es cualquier inyección de $\mathbb{N}$ $\mathbb{N}$a continuación, para todos los $s$, $f([s+1]) \not \subseteq [s]$. Para ello se utiliza el ordinario de la prueba del principio del palomar.

A continuación, mostramos que si cualquiera de las declaraciones Kaye está considerando la posibilidad de fallo, se puede utilizar para construir una inyección que se contradice con la anterior afirmación. En particular, si la instrucción no se puede ejecutar en $s$, se le deje $f(i) = (\mu j \leq s) \psi(i,j)$$i \leq s+1$$f(i) = i$$i > s+1$, que es aritméticamente definibles.

Answer 2

Esto es más complicado de lo que parece a primera. Si intenta demostrar directamente por inducción en $s$ te encuentras con el problema de que tendrás la hipótesis de inducción para las diferentes $\psi$ -- lo cual no está permitido, porque es diferente de la inducción.

Creo que usted necesita para ir a "el largo camino" y empezar por la sustitución de la $\psi$ con algo que se puede cuantificar, como Gödel $\beta$ función de: $$ \forall s,b,c: \bigl( \forall x<s+1: (\beta(b,c,x)<s ) \to \exists x,r<s+1: (x\ne r \land \beta(b,c,x) = \beta(b,c,r)) \bigr) $$ Desde $\beta$ es una función cuya fórmula es la misma sin importar los valores de $b$$c$, usted puede probar esto por inducción en $s$.

A lo largo de la manera usted necesita un número de lemas acerca de la manipulación de $\beta$-secuencias codificadas. Si usted ya tiene los lemas en su caja de herramientas de la ir no es tan malo; de lo contrario hay un montón de trabajo que hacer, que incluirá probar alguna forma de que el Teorema del Resto Chino a lo largo del camino.

Por último, demostrar como un metatheorem que por cada $\psi$ puede derivar $$ \forall s: (\forall x<s+1\,\exists e<s : \psi(x,e)) \to \exists b,c\, \forall x<s+1 : \bigl( (\beta(b,c,x)<s \land \psi(x,\beta(b,c,x)) \bigr) $$ que luego se puede combinar con el de arriba para obtener la fórmula que usted está después.