Sesión Lógica y Computabilidad

Diciembre 12, 17:30 ~ 18:10

Sobre un problema en el campo de las aritméticas débiles y su relación con construcciones de funciones computables

Cordón-Franco, Andrés

La Aritmética de Peano $PA$ está axiomatizada, sobre una teoría base que expresa propiedades algebraicas básicas de los números naturales, por el esquema de inducción para toda propiedad de primer orden. Los fragmentos de la Aritmética son subsistemas de $PA$ obtenidos al restringir, de una manera u otra, dicho esquema de inducción (u otros principios combinatorios relacionados). De entre estos fragmentos, denominamos \textit{Aritméticas débiles} a aquellos subsistemas de $PA$ que no son lo suficientemente fuertes para poder demostrar el axioma $exp \equiv \forall x \, \exists y \, (y=2^x)$ que expresa que la función exponencial es una función total. Ejemplos clásicos de dichas aritméticas débiles son: \textit{a)} la teoría de inducción para fórmulas acotadas, $I\Delta_0$; y \textit{b)} la teoría axiomatizada por el principio de colección para fórmulas $\Sigma_1$, $B\Sigma_1$. Ciertas herramientas básicas en el estudio de fragmentos de $PA$ (definiciones de validez parcial, codificación uniforme de sucesiones finitas, \dots) requieren la construcción de objetos de tama\~{n}o exponencial y no están pues disponibles, al menos de manera directa, en el estudio de las aritméticas débiles. En consecuencia, el campo de las aritméticas débiles requiere una metodología propia y, de hecho, es bien conocido que el estudio estas aritméticas está estrechamente relacionado con construcciones típicas del campo de la \emph{Complejidad Computacional}. Más aún, muchos problemas abiertos en el campo de las aritméticas débiles pueden considerarse como versiones formales de importantes problemas abiertos de la Teoría de la Complejidad Computacional. Dos importantes problemas de este tipo son los siguientes, propuestos por Jeff Paris y Alex Wilkie en los a\~{n}os 1980 (véase [WP]). \begin{itemize} \item Problema de la extensión final: \textit{?`Todo modelo numerable de $B\Sigma_1$ tiene una extensión final propia a un modelo de $I\Delta_0$?} \item Problema NE(=no exponencial): \textit{?`Existe algún modelo de $I\Delta_0 + \neg exp + \neg B\Sigma_1$?} \end{itemize} En este trabajo, nos centramos en el estudio del problema (NE) y presentamos una nueva línea de ataque para resolver dicho problema abierto. La noción de \emph{función computable demostrablemente total} en una teoría $T$ permite asociar de manera canónica a cada teoría aritmética $T$ un álgebra de funciones computables $\mathcal{R}(T)$. Vía el uso de estas álgebras de funciones computables, establecemos un resultado que pone de manifiesto el \textit{contenido computacional} detrás del problema (NE) y, como principal aplicación del mismo, obtenemos el siguiente teorema que reduce el problema (NE) a una cuestión puramente computacional sobre la construcción de la función máximo. \medskip \noindent \textbf{Teorema.} Si existe una función recursiva elemental, $f$, con grafo $\Delta_0$-definible tal que $max(f)$ no pueda obtenerse por composición a partir de $f$ y funciones rudimentarias, entonces existe un modelo de $I\Delta_0 + \neg exp + \neg B\Sigma_1$. \bigskip \noindent Referencias \smallskip \noindent [WP] Wilkie, A.; Paris, J. \textit{On the existence of end extensions of models of bounded induction}. Logic, methodology and philosophy of science, VIII (Moscow, 1987), 143-161, North-Holland. 1989.

Autores: Cordón-Franco, Andrés / Lara-Martín, Francisco Félix.