Axiomas cardinales grandes y funciones recursivas totales

Question

¿Existen relaciones conocidas entre axiomas cardinales grandes (digamos cardinales de Mahlo o Woodin) y funciones recursivas totales (sobre los números naturales) del tipo

$ZFC$ + gran axioma cardinal $\vdash$ $f$ es una función recursiva total,

pero:

$ZFC \not\vdash$ $f$ es una función recursiva total,

así se conoce para diferentes sistemas de axiomas de la matemática inversa, por ejemplo

$ATR_0 \vdash$ la función Goodstein $G$ es totalmente recursivo,

pero para el sistema más débil $ACA_0$ que tenemos:

$ACA_0 \not\vdash$ la función Goodstein $G$ es totalmente recursivo.

O, en términos más generales, ¿existe una relación del tipo siguiente?

Si $LCA_1$ (axioma cardinal grande 1) es más fuerte (wrt. fuerza de consistencia) que $LCA_2$ entonces $ZFC + LCA_1$ demuestra la totalidad de una función recursiva $f$ que crece más rápido que todas las funciones recursivas que tienen pruebas de totalidad en $ZFC + LCA_2$ ?

Esta cuestión se plantea en las investigaciones sobre la relación entre aprendizaje y la demostrabilidad, donde se utilizan funciones recursivas se utilizan para programar el proceso de aprendizaje. Un sistema de aprendizaje $\Lambda(\Sigma_1)$ utilizando $\Sigma_1$ como teoría de fondo es más fuerte que un sistema de aprendizaje $\Lambda(\Sigma_2)$ , si $\Sigma_1$ permite la demostración de la totalidad de las funciones recursivas crecer más rápido que todas las funciones recursivas que tienen pruebas de totalidad en $\Sigma_2$ .

Answer 1

$\def\zfc{\mathrm{ZFC}}\def\lca{\mathrm{LCA}}$ Sí. Normalmente, $\zfc+\lca_1$ demuestra no sólo la consistencia de $\zfc+\lca_2$ sino también el principio de reflexión uniforme de $\zfc+\lca_2$ (al menos para las fórmulas aritméticas). En particular, el $\Sigma^0_1$ -el principio de reflexión es un $\Pi^0_2$ sentencia demostrable en $\zfc+\lca_1$ pero no en $\zfc+\lca_2$ y puede expresarse como la totalidad de la siguiente función $f$ : si $x$ es un código de $\zfc+\lca_2$ prueba de una $\Sigma^0_1$ -sentencia de la forma $\exists u\,\theta(u)$ con $\theta\in\Delta^0_0$ , dejemos que $f(x)$ sea el mínimo $u$ tal que $\mathbb N\models\theta(u)$ Si no es así $f(x)=0$ .

Para ver que $f$ crece más rápido que cualquier función recursiva total demostrable de $\zfc+\lca_2$ , dejemos que $g$ sea una función de este tipo. Podemos suponer sin pérdida de generalidad que $g$ está aumentando, y $g(x)=y$ tiene un $\Sigma^0_1$ -definición $\exists w\,\lambda(x,y,w)$ que es demostrablemente total y (estrictamente) creciente en $\zfc+\lca_2$ . Sea $\theta(x,u)$ sea la fórmula $\exists y,w\le u\,\lambda(2^x,y,w)$ (esto no es estrictamente $\Delta^0_0$ Pero esto es fácil de arreglar, lo dejaré así para simplificar la presentación). Entonces las fórmulas $\exists u\,\theta(\ulcorner n\urcorner,u)$ (donde $\ulcorner n\urcorner$ denota el número binario de $n$ ) tienen $\zfc+\lca_2$ pruebas del número de Gödel limitadas por $p(n)$ para algún polinomio $p$ pero sus testigos más pequeños tienen una magnitud de al menos $g(2^n)>g(p(n))$ para que sea lo suficientemente grande $n$ .

Este argumento demuestra que $f(m)>g(m)$ para un número infinito de $m$ . Si queremos que esto se cumpla para todos los casos suficientemente grandes $m$ basta con hacer que la función sea creciente utilizando $f_2(x)=\max_{y\le x}f(y)$ en lugar de $f$ .

Answer 2

Dado que los grandes axiomas cardinales tienen consecuencias aritméticas no demostrables sin ellos, la respuesta a tu primera pregunta es sí. Por ejemplo, dejemos que $f(n)=1$ siempre y cuando $n$ no es el código de Goedel de una prueba de una contradicción en ZFC. Dado que los cardinales grandes implican Con(ZFC), la teoría ZFC+cardinales grandes demuestra que $f$ es total. Pero ZFC por sí sola no demuestra esto (si es consistente), ya que es relativamente consistente con ZFC que haya pruebas de contradicciones a partir de ZFC.

Para la cuestión más general, supongamos que la teoría más fuerte no sólo demuestra la teoría más débil, sino que también demuestra que siempre que la teoría más débil demuestra que un programa de MT calcula una función total, entonces realmente lo hace. Esta es la situación para la mayoría de los cardinales grandes--por ejemplo, la teoría que afirma que hay un cardinal débilmente compacto implica torres de cardinales inaccesibles más pequeños, y entonces si un programa es total dentro de tal $V_\kappa$ entonces es realmente en $V$ . Dada esta situación, dejemos que $f(n)$ sea la función que inspecciona primero todos los $m\leq n$ para ver qué código prueba de la teoría más débil que una determinada función $g_m$ es total, y entonces dejemos que $f(n)$ sea mayor que todos esos $g_m(n)$ . Nuestra suposición sobre la teoría más fuerte asegura que podemos estar seguros de que el cálculo de $g_m(n)$ converge, por lo que $f(n)$ se definirá.