Teorema de indefinibilidad de Tarski

Teorema de que la verdad aritmética no se puede definir en aritmética

El teorema de indefinibilidad de Tarski , enunciado y demostrado por Alfred Tarski en 1933, es un resultado limitante importante en la lógica matemática , los fundamentos de las matemáticas y la semántica formal . Informalmente, el teorema establece que "la verdad aritmética no se puede definir en aritmética". ^[1]

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

Historia

En 1931, Kurt Gödel publicó los teoremas de incompletitud , que demostró en parte mostrando 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 indistintamente como numeración de Gödel , codificación y, más en general, 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 , etc.), 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 es definible en la teoría de conjuntos de Zermelo-Fraenkel para saber si las fórmulas en el lenguaje de la aritmética de Peano son verdaderas en el modelo estándar de aritmética ^[2] ) debe tener 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, allí expresó sólo 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 metamatematische Resultate über Entscheidungsdefinitheit und Widerspruchsfreiheit " [Algunos resultados metamatemáticos sobre la precisión de la decisión y la coherencia], Academia Austriaca de Ciencias , Viena, 1930.

Declaración

Primero enunciaremos una versión simplificada del teorema de Tarski, luego enunciaremos y demostraremos en la siguiente sección el teorema que Tarski demostró en 1933.

Sea el lenguaje de la aritmética de primer orden . Se trata de la teoría de los números naturales , incluidas su suma y multiplicación, axiomatizada por los axiomas de Peano de primer orden . Se trata de una teoría de " 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 de forma recursiva, como la exponenciación, los factoriales o la secuencia de Fibonacci . ${\displaystyle L}$

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

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

Teorema de indefinibilidad de Tarski : No existe una fórmula que defina. Es decir, no existe una fórmula tal que se cumpla para cada oración . ${\displaystyle L}$ ${\displaystyle \mathrm {True} (n)}$ ${\displaystyle T^{*}.}$ ${\displaystyle L}$ ${\displaystyle \mathrm {True} (n)}$ ${\displaystyle L}$ ${\displaystyle A,}$ ${\displaystyle \mathrm {True} (g(A))\iff A}$ ${\displaystyle {\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 cuya extensión sea , pero sólo recurriendo a un metalenguaje cuyo poder expresivo va más allá del de . Por ejemplo, un predicado de verdad para la aritmética de primer orden se puede definir en aritmética de segundo orden . Sin embargo, esta fórmula sólo podría definir un predicado de verdad para fórmulas en el idioma original . Definir un predicado de verdad para el metalenguaje requeriría un metametalenguaje aún superior, y así sucesivamente. ${\displaystyle \mathrm {True} (n)}$ ${\displaystyle T^{*},}$ ${\displaystyle L}$ ${\displaystyle L}$

Para probar el teorema, procedemos por contradicción y asumimos que existe una fórmula que es verdadera para el número natural en si y sólo si es el número de Gödel de una oración en que es verdadera en . Entonces podríamos usar para definir una nueva fórmula que sea verdadera para el número natural si y sólo si el número de Gödel de una fórmula (con una variable libre ) es tal que es falso cuando se interpreta en (es decir, la fórmula cuando se aplica a su propia número de Gödel, produce una afirmación falsa). Si ahora consideramos el número de Gödel de la fórmula y preguntamos si la oración es verdadera en , obtenemos una contradicción. (Esto se conoce como argumento diagonal ). ${\displaystyle L}$ ${\displaystyle \mathrm {True} (n)}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle n}$ ${\displaystyle L}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle \mathrm {True} (n)}$ ${\displaystyle L}$ ${\displaystyle S(m)}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle \varphi (x)}$ ${\displaystyle x}$ ${\displaystyle \varphi (m)}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle \varphi (x),}$ ${\displaystyle g}$ ${\displaystyle S(m)}$ ${\displaystyle S(g)}$ ${\displaystyle {\mathcal {N}}}$

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

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 y con suficiente capacidad de autorreferencia como se cumple 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 ZFC .

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

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

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; por ejemplo, no invoca funciones recursivas de ninguna manera. La prueba supone que cada fórmula tiene un número de Gödel , pero no se requieren los detalles de un método de codificación. Por 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. ${\displaystyle L}$

Smullyan (1991, 2001) ha argumentado enérgicamente que el teorema de indefinibilidad de Tarski merece gran parte de la atención obtenida 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) no es nada 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. Tales lenguajes son necesariamente capaces de suficiente autorreferencia para que se les pueda aplicar el lema de la diagonal. La importancia filosófica más amplia del teorema de Tarski es más sorprendentemente evidente.

Un lenguaje interpretado es fuertemente semánticamente autorrepresentativo exactamente cuando el lenguaje contiene predicados y símbolos de función 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 relaciona una fórmula con su valor de verdad y la "función de denotación semántica" que relaciona un término con el objeto que denota. El teorema de Tarski luego se generaliza de la siguiente manera: Ningún lenguaje suficientemente poderoso es fuertemente semánticamente autorrepresentativo . ${\displaystyle A}$ ${\displaystyle ||A||,}$ ${\displaystyle t}$

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 aritmética de Peano de primer orden que son verdaderas en 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 décimo orden para cualquiera ) se puede definir mediante una fórmula en ZFC de primer orden . ${\displaystyle {\mathcal {N}}}$ ${\displaystyle n}$ ${\displaystyle n}$

Ver también

• Teorema de incompletitud de Chaitin  : medida de complejidad algorítmicaPages displaying short descriptions of redirect targets
• Teorema de completitud de Gödel  - Teorema fundamental en lógica matemática
• Teoremas de incompletitud de Gödel  : resultados limitativos en lógica matemática

Referencias

1. Cezary Cieśliński, "Cómo Tarski definió lo indefinible", European Review 23.1 (2015): 139-149.
2. Joel David Hamkins; Yang, Ruizhi (2013). "La satisfacción no es absoluta". arXiv : 1312.0670 [matemáticas.LO].

Fuentes primarias

• 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" (PDF) . Studia Philosophica (en alemán). 1 : 261–405. Archivado desde el original (PDF) el 9 de enero de 2014 . Consultado el 26 de junio de 2013 .
  • Tarski, A. (1983). «El concepto de verdad en los lenguajes formalizados» (PDF) . En Corcoran, J. (ed.). Lógica, Semántica, Metamatemática . Traducido por JH Woodger. Hackett.Traducción al inglés del artículo de Tarski de 1936.

Otras lecturas

• Bell, JL; Machover, M. (1977). Un curso de lógica matemática . Holanda del Norte.
• Boolos, G .; Burgess, J .; Jeffrey, R. (2002). Computabilidad y Lógica (4ª ed.). Prensa de la Universidad de Cambridge.
• Lucas, JR (1961). "Mente, máquinas y Gödel". Filosofía . 36 (137): 112–27. doi : 10.1017/S0031819100057983 . S2CID  55408480. Archivado desde el original el 19 de agosto de 2007.
• Murawski, R. (1998). "Indefinibilidad de la verdad. El problema de la prioridad: Tarski vs. Gödel". Historia y Filosofía de la Lógica . 19 (3): 153–160. doi :10.1080/01445349808837306. Archivado desde el original el 8 de junio de 2011.
• Smullyan, Raymond M. (1992). Teoremas de incompletitud de Gödel . Oxford: Oxford University Press, Estados Unidos. ISBN 0-19-504672-2.
• Smullyan, R. (2001). "Teoremas de incompletitud de Gödel". En Goble, L. (ed.). La guía Blackwell de lógica filosófica . Blackwell. págs. 72–89. ISBN 978-0-631-20693-4.