Teorema de indefinibilidad de Tarski

El teorema de indefinibilidad de Tarski, declarado y demostrado por Alfred Tarski en 1933, es un resultado limitativo importante en lógica matemática, fundamentos de las matemáticas y semántica formal. En términos coloquiales, el teorema establece que "la verdad aritmética no se puede definir en aritmética".​

El teorema se aplica de manera más general a cualquier sistema formal suficientemente fuerte, y demuestra que la verdad en el modelo estándar de un sistema no se puede definir dentro del propio sistema.

Historia

En 1931, Kurt Gödel publicó los teoremas de incompletitud, que demostró en parte evidenciando cómo representar la sintaxis de la lógica formal dentro de la aritmética de primer orden. A cada expresión del lenguaje formal de la aritmética se le asigna un número distinto. Este procedimiento se conoce como numeración de Gödel, codificación y, más generalmente, como aritmetización. En particular, varios conjuntos de expresiones se codifican como conjuntos de números. Para diversas propiedades sintácticas (como ser una fórmula, ser una oración u otras), estos conjuntos son computables. Además, cualquier conjunto computable de números puede definirse mediante alguna fórmula aritmética. Por ejemplo, hay fórmulas en el lenguaje de la aritmética que definen el conjunto de códigos para oraciones aritméticas y para oraciones aritméticas demostrables.

El teorema de indefinibilidad muestra que esta codificación no se puede realizar para conceptos semánticos como la verdad. Muestra que ningún lenguaje interpretado suficientemente rico puede representar su propia semántica. Un corolario es que cualquier metalenguaje capaz de expresar la semántica de algún lenguaje objeto (por ejemplo, un predicado se puede definir según los axiomas de Zermelo-Fraenkel para saber si las fórmulas en el lenguaje de los axiomas de Peano son verdaderas en el modelo estándar de aritmética​) debe tener un poder expresivo superior al del lenguaje objeto. El metalenguaje incluye nociones, axiomas y reglas primitivas ausentes en el lenguaje objeto, de modo que hay teoremas demostrables en el metalenguaje que no son demostrables en el lenguaje objeto.

El teorema de indefinibilidad se atribuye convencionalmente a Alfred Tarski. Gödel también descubrió el teorema de indefinibilidad en 1930, mientras demostraba sus teoremas de incompletitud publicados en 1931, y mucho antes de la publicación en 1933 del trabajo de Tarski (Murawski 1998). Si bien Gödel nunca publicó nada relacionado con su descubrimiento independiente de la indefinibilidad, sí lo describió en una carta de 1931 a John von Neumann. Tarski había obtenido casi todos los resultados de su monografía de 1933 "El concepto de verdad en los lenguajes de las ciencias deductivas" entre 1929 y 1931, y habló sobre ellos ante audiencias polacas. Sin embargo, como destacó en el artículo, el teorema de indefinibilidad fue el único resultado que no obtuvo antes. Según la nota a pie de página del teorema de indefinibilidad (Twierdzenie I) de la monografía de 1933, el teorema y el esquema de la demostración no se añadieron a la monografía hasta que el manuscrito fue enviado a la imprenta en 1931. Tarski informa allí que, cuando presentó el contenido de su monografía en la Academia de Ciencias de Varsovia el 21 de marzo de 1931, expresó solo algunas conjeturas, basadas en parte en sus propias investigaciones y en parte en el breve informe de Gödel sobre los teoremas de incompletitud "Einige metamathematische Resultate über Entscheidungsdefinitheit und Widerspruchsfreiheit" (Algunos resultados metamatemáticos sobre la precisión de la decisión y la coherencia), Academia Austríaca de Ciencias, Viena, 1930.

Enunciado

En primer lugar se enuncia una versión simplificada del teorema de Tarski, luego se enuncia y se demuestra en la siguiente sección el teorema que Tarski formalizó en 1933.

Sea $L$ el idioma de una aritmética de primer orden. Esta es la teoría de los números naturales, incluyendo su suma y multiplicación, axiomatizada por los axiomas de Peano de primer orden. Esta es una teoría "primer orden": los cuantificadores se extienden a los números naturales, pero no a conjuntos o funciones de números naturales. La teoría es lo suficientemente sólida como para describir funciones enteras definidas recursivamente como la exponenciación, los factoriales o la sucesión de Fibonacci.

Sea ${\mathcal {N}}$ la estructura estándar para $L,$ es decir, ${\mathcal {N}}$ consta del conjunto ordinario de los números naturales y su suma y multiplicación. Cada oración en $L$ se puede interpretar en ${\mathcal {N}}$ y luego se vuelve verdadera o falsa. Por tanto, $(L,{\mathcal {N}})$ es el lenguaje aritmético interpretado de primer orden.

Cada fórmula $\varphi$ en $L$ tiene un número de Gödel $g(\varphi ),$ un número natural que codifica $\varphi .$ De esa manera, el lenguaje $L$ puede hablar de fórmulas en $L,$ y no solo de números. Sea $T$ el conjunto de oraciones $L$ verdaderas en ${\mathcal {N}}$, y $T^{*}$ el conjunto de números de Gödel de las oraciones en $T.$ El siguiente teorema responde a la pregunta: ¿Se puede definir $T^{*}$ mediante una fórmula de aritmética de primer orden?

Teorema de indefinibilidad de Tarski: No existe una fórmula $L$ $\mathrm {True} (n)$ que defina $T^{*}.$ Es decir, no existe una fórmula $L$ $\mathrm {True} (n)$ tal que por cada oración $L$ $A,$ $\mathrm {True} (g(A))\iff A$ se mantenga en ${\mathcal {N}}$.

Informalmente, el teorema dice que el concepto de verdad de los enunciados aritméticos de primer orden no puede definirse mediante una fórmula en aritmética de primer orden. Esto implica una limitación importante en el alcance de la autorrepresentación. "Es" posible definir una fórmula $\mathrm {True} (n)$ cuya extensión sea $T^{*},$ pero solo recurriendo a una metalenguaje cuyo poder expresivo vaya más allá del de $L$. Por ejemplo, un predicado verdadero para la aritmética de primer orden se puede definir en aritmética de segundo orden. Sin embargo, esta fórmula solo podría definir un predicado de verdad para fórmulas en el idioma original $L$. Definir un predicado de verdad para el metalenguaje requeriría un metametalenguaje aún superior, y así sucesivamente.

Para probar el teorema, se procede por contradicción y se asume que existe una fórmula $L$ $\mathrm {True} (n)$ que es verdadera para el número natural $n$ en ${\mathcal {N}}$ si y solo si $n$ es el número de Gödel de una oración en $L$ que es verdadera en ${\mathcal {N}}$. Entonces, se puede usar $\mathrm {True} (n)$ para definir una nueva fórmula $L$ $S(m)$ que sea verdadera para el número natural $m$ si y solo si $m$ es el número de Gödel de una fórmula $\varphi (x)$ (con una variable libre $x$) tal que $\varphi (m)$ sea falso cuando se interpreta en ${\mathcal {N}}$ (es decir, la fórmula $\varphi (x),$ cuando se aplica a su propio número de Gödel, produce una afirmación falsa). Si ahora se considera el número de Gödel $g$ de la fórmula $S(m)$ y se pregunta si la oración $S(g)$ es verdadera en ${\mathcal {N}}$, se obtiene una contradicción (lo que se conoce como argumento diagonal).

El teorema es un corolario del teorema de Post sobre la jerarquía aritmética, demostrado algunos años después del trabajo de Tarski (1933). Por reducción al absurdo se obtiene una prueba semántica del teorema de Tarski a partir del teorema de Post de la siguiente manera. Suponiendo que $T^{*}$ se puede definir aritméticamente, existe un número natural $n$ tal que $T^{*}$ se puede definir mediante una fórmula en el nivel $\Sigma _{n}^{0}$ de jerarquía aritmética. Sin embargo, $T^{*}$ es $\Sigma _{k}^{0}$-difícil para todos los $k.$ Por lo tanto, la jerarquía aritmética colapsa en el nivel $n$, contradiciendo el teorema de Post.

Forma general

Tarski demostró un teorema más sólido que el expuesto anteriormente, utilizando un método enteramente sintáctico. El teorema resultante se aplica a cualquier lenguaje formal con negación lógica y con capacidad suficiente para la autorreferencia que contenga el lema diagonal. La aritmética de primer orden satisface estas condiciones previas, pero el teorema se aplica a sistemas formales mucho más generales, como los axiomas de Zermelo-Fraenkel.

Teorema de indefinibilidad de Tarski (forma general): sea $(L,{\mathcal {N}})$ cualquier lenguaje formal interpretado que incluya la negación y tenga una numeración de Gödel $g(\varphi )$ que satisfaga el lema diagonal, es decir, para cada fórmula $L$ $B(x)$ (con una variable libre $x$) existe una oración $A$ tal que $A\iff B(g(A))$ se cumple en ${\mathcal {N}}$. Entonces, no existe una fórmula $L$ $\mathrm {True} (n)$ con la siguiente propiedad: para cada oración $L$ $A,$ $\mathrm {True} (g(A))\iff A$ es verdadero en ${\mathcal {N}}$.

La prueba del teorema de indefinibilidad de Tarski en esta forma es nuevamente mediante reducción al absurdo. Supóngase que existiera una fórmula $L$ $\mathrm {True} (n)$ como la anterior, es decir, si $A$ es una oración aritmética, entonces $\mathrm {True} (g(A))$ se cumple en ${\mathcal {N}}$ si y solo si $A$ se cumple en ${\mathcal {N}}$. Por lo tanto, para todo $A$, la fórmula $\mathrm {True} (g(A))\iff A$ se cumple en ${\mathcal {N}}$. Pero el lema diagonal produce un contraejemplo a esta equivalencia, al dar una fórmula mentirosa $S$ tal que $S\iff \lnot \mathrm {True} (g(S))$ se cumple en ${\mathcal {N}}$. Esto es una contradicción, como se quería demostrar.

Discusión

La maquinaria formal de la prueba dada anteriormente es totalmente elemental excepto por la diagonalización que requiere el lema diagonal. La demostración del lema diagonal es también sorprendentemente sencilla, y por ejemplo, no implica recursión de ninguna manera. La prueba supone que cada fórmula $L$ tiene asignado un número de Gödel, pero no se requieren los detalles de un método de codificación. Por lo tanto, el teorema de Tarski es mucho más fácil de motivar y demostrar que los más célebres teoremas de Gödel sobre las propiedades metamatemáticas de la aritmética de primer orden.

Smullyan (1991, 2001) ha argumentado enérgicamente que el teorema de indefinibilidad de Tarski merece gran parte de la atención suscitada por los teoremas de incompletitud de Gödel. Que estos últimos teoremas tengan mucho que decir sobre todas las matemáticas y, lo que es más controvertido, sobre una serie de cuestiones filosóficas (por ejemplo, Lucas 1961) es menos que evidente. El teorema de Tarski, por otra parte, no trata directamente de las matemáticas sino de las limitaciones inherentes de cualquier lenguaje formal lo suficientemente expresivo como para ser de interés real. Dichos lenguajes son necesariamente capaces de tener suficiente autorreferencia para que se les aplique el lema diagonal. La importancia filosófica más amplia del teorema de Tarski es más evidente de forma sorprendente.

Un lenguaje interpretado es fuertemente semánticamente autorrepresentativo exactamente cuando el lenguaje contiene predicados y símbolos de funciones que definen todos los conceptos semánticos específicos del lenguaje. Por lo tanto, las funciones requeridas incluyen la función de valoración semántica que asigna una fórmula $A$ a su valor de verdad $||A||,$ y la función de denotación semántica que asigna un término $t$ al objeto que denota. El teorema de Tarski se generaliza entonces de la siguiente manera: Ningún lenguaje suficientemente poderoso es fuertemente semánticamente autorrepresentativo.

El teorema de indefinibilidad no impide que la verdad en una teoría se defina en una teoría más sólida. Por ejemplo, el conjunto de (códigos para) fórmulas de primer orden de la aritmética de Peano que son verdaderas en ${\mathcal {N}}$ se puede definir mediante una fórmula en aritmética de segundo orden. De manera similar, el conjunto de fórmulas verdaderas del modelo estándar de aritmética de segundo orden (o aritmética de orden $n$ para cualquier $n$) se puede definir mediante una fórmula en los axiomas de Zermelo-Fraenkel de primer orden.

Véase también

• Teorema de incompletitud de Chaitin
• Teorema de completitud de Gödel
• Teoremas de incompletitud de Gödel

Bibliografía

• Tarski, A. (1933). Pojęcie Prawdy w Językach Nauk Dedukcyjnych (en polaco). Nakładem Towarzystwa Naukowego Warszawskiego. 
• Tarski, A. (1936). «Der Wahrheitsbegriff in den formalisierten Sprachen». Studia Philosophica (en alemán) 1: 261-405. Archivado desde el original el 9 January 2014. Consultado el 26 June 2013. 
  • Tarski, A. (1983). «The Concept of Truth in Formalized Languages». En Corcoran, J., ed. Logic, Semantics, Metamathematics (J. H. Woodger, trad.). Hackett.  traducción al inglés de l Artículo de rski de 1936.

Lecturas adicionales

• Bell, J. L.; Machover, M. (1977). A Course in Mathematical Logic. North-Holland. 
• Boolos, G.; Burgess, J.; Jeffrey, R. (2002). Computability and Logic (4th edición). Cambridge University Press. 
• Lucas, J. R. (1961). «Mind, Machines, and Gödel». Philosophy 36 (137): 112-27. S2CID 55408480. doi:10.1017/S0031819100057983. Archivado desde el original el 19 de agosto de 2007. 
• Murawski, R. (1998). «Undefinability of truth. The problem of the priority: Tarski vs. Gödel». History and Philosophy of Logic 19 (3): 153-160. doi:10.1080/01445349808837306. Archivado desde el original el 8 de junio de 2011. 
• Smullyan, Raymond M. (1992). Gödel's Incompleteness Theorems. Oxford: Oxford University Press, USA. ISBN 0-19-504672-2. 
• Smullyan, R. (2001). «Gödel’s Incompleteness Theorems». En Goble, L., ed. The Blackwell Guide to Philosophical Logic. Blackwell. pp. 72-89. ISBN 978-0-631-20693-4. 

• Datos: Q574902