Maquinaria de tuplas en I-Sigma_0

Question

Después de pensar en la respuesta de Joel en Modelos computables no estándar para sistemas débiles de aritmética durante unos días, no veo cómo desarrollar suficiente maquinaria de tuplas en I-Sigma_0 (PA con inducción restringida a fórmulas Sigma_0) para demostrar el resultado necesario.

¿Prueba I-Sigma_0 que "para cualquier número d, existe un número c que codifica el conjunto de programas de máquinas de Turing menores que d que se detienen en la entrada 0 con salida 0 en un máximo de d pasos", con una codificación tal que determinar si un número estándar n está en el conjunto es computable a partir de (=,0,S,+,*)?

Con la codificación sugerida por Joel, que es code(set) := $\displaystyle\Pi_{n \in set} \; p_n$ , ni siquiera veo la forma de que I-Sigma_0 demuestre "Para todo n, existe un número que codifica el conjunto de números menores que n", y tampoco se me ocurre una codificación mejor.

Answer 1

Según recuerdo, el método de McAloon para demostrar que no existen modelos computables no estándar de $I\Delta_0$ era demostrar que hay segmentos iniciales que son modelos no estándar de AP. A continuación, se pueden utilizar los trucos habituales de Tennenbaum para demostrar que la suma y la multiplicación no son computables.

Comentario adicional Aquí están las referencias para el documento de McAloon y el documento de Wilmers que demuestra un resultado similar para $IE_1$ el fragmento de $I\Delta_0$ donde sólo tienes inducción para fórmulas con cuantificadores existenciales acotados

McAloon, Kenneth, Sobre la complejidad de los modelos de aritmética. J. Symbolic Logic 47 (1982), nº 2, 403--415.

Wilmers, George Inducción existencial limitada. J. Symbolic Logic 50 (1985), nº 1, 72--90.