Subconjunto explícito de segundo orden de los naturales.

Question

La aritmética de segundo orden de los naturales es más fuerte que PA porque permite la inducción sobre subconjuntos arbitrarios de los naturales, mientras que PA sólo lo permite sobre subconjuntos que son una extensión de algún predicado, esta última colección es contable y la primera es incontable.

Pero cualquier subconjunto que se me ocurra está en este último, por ejemplo, todos los conjuntos r.e. sólo implican un cuantificador de primer orden, y se pueden tener tantos cuantificadores como se quiera. ¿Se puede construir un ejemplo explícito de un subconjunto de los naturales que no sea la extensión de un predicado en PA? Si es así, por favor proporcione uno.

Nota: Creo que la respuesta es no, porque recuerdo haber leído que la escuela de Markov de matemáticas constructivas adoptó la "falsa tesis de la iglesia" de que ${Rec}=\mathbb{N}^\mathbb{N}$ Si este es el caso, me interesaría cualquier referencia a una prueba de esto. Si no es así, tal vez alguien más erudito pueda explicar qué pretendía Markov...

Answer 1

Bueno, dejando $\#$ sea la función de numeración habitual de Godel, la teoría codificada de primer orden de la aritmética $\{\#(\varphi):\varphi\in\mathsf{FOL},\mathbb{N}\models\varphi\}$ es definible de segundo orden pero (por Tarski ) no es definible en primer orden.

Para un ejemplo más "estructural", puede consultar Kleene's $\mathcal{O}$ que es esencialmente el conjunto de códigos para las ordenaciones computables. De nuevo, esto no es definible en primer orden en $\mathbb{N}$ - de hecho, es mucho más complicado que el ejemplo anterior en un sentido preciso aunque al principio pueda parecer más concreto.