Teorema de indefinibilidad de Tarski

Teorema de que la verdad aritmética no puede definirse en aritmética

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

El teorema se aplica de forma más general a cualquier sistema formal suficientemente fuerte , mostrando 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 de diversas formas como numeración de Gödel , codificación y, de forma más general, como aritmetización. En particular, varios conjuntos de expresiones se codifican como conjuntos de números. Para varias 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, existen 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 determinar si las fórmulas en el lenguaje de la aritmética de Peano son verdaderas en el modelo estándar de la aritmética ^[2] ) debe tener un poder expresivo que exceda al del lenguaje objeto. El metalenguaje incluye nociones primitivas, axiomas y reglas 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, 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 enfatizó 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 bosquejo de la prueba se añadieron a la monografía sólo después de que el manuscrito hubiera sido enviado a la imprenta en 1931. Tarski informa allí que, cuando presentó el contenido de su monografía a la Academia de Ciencias de Varsovia el 21 de marzo de 1931, expresó en este lugar 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 metamathematische Resultate über Entscheidungsdefinitheit und Widerspruchsfreiheit " [Algunos resultados metamatemáticos sobre la definitividad de la decisión y la consistencia], 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 , incluida su adición 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 los 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 . ${\displaystyle L}$

Sea la estructura estándar de ie, que consiste en el conjunto ordinario de números naturales y su adición y multiplicación. Cada oración en puede interpretarse en y luego se convierte en verdadera o falsa. Así es el "lenguaje interpretado de primer orden de la aritmética". ${\displaystyle {\mathcal {N}}}$ ${\displaystyle L,}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle L}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle (L,{\mathcal {N}})}$

Cada fórmula en 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 en no solo de números. Sea 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: ¿Puede definirse 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 ninguna -fórmula que defina Es decir, no existe ninguna -fórmula tal que para cada -oración se cumpla en . ${\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}}}$

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

Para demostrar el teorema, procedemos por contradicción y suponemos que existe una -fórmula que es verdadera para el número natural en si y solo si es el número de Gödel de una oración en que es verdadera en . Podríamos entonces usar para definir una nueva -fórmula que es verdadera para el número natural si y solo si es el número de Gödel de una fórmula (con una variable libre ) tal que es falsa cuando se interpreta en (es decir, la fórmula cuando se aplica a su propio 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 un 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 por reductio ad absurdum como sigue. Suponiendo que es aritméticamente definible, hay un número natural tal que es definible por una fórmula en el nivel de la jerarquía aritmética . Sin embargo, es -hard 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 fuerte que el enunciado 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 para que se cumpla 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 la 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 en . Entonces no hay ninguna -fórmula con la siguiente propiedad: para 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 reductio ad absurdum . Supongamos que existiera una fórmula como la anterior, es decir, si es una oración aritmética, entonces se cumple en si y solo si se cumple en . Por lo tanto, para todo , la fórmula se cumple en . Pero el lema diagonal produce un contraejemplo a esta equivalencia, al dar una fórmula "mentirosa" tal que se cumple en . 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 completamente elemental, excepto por la diagonalización que requiere el lema diagonal. La prueba del lema diagonal es igualmente sorprendentemente simple; por ejemplo, no invoca funciones recursivas de ninguna manera. La prueba sí 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 lo tanto, el teorema de Tarski es mucho más fácil de motivar y demostrar que los teoremas más célebres 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 que han recibido los teoremas de incompletitud de Gödel . No es tan evidente que estos últimos teoremas tengan mucho que decir sobre toda la matemática y, más controvertidamente, sobre una serie de cuestiones filosóficas (por ejemplo, Lucas 1961). El teorema de Tarski, por otra parte, no trata directamente de la matemática, sino de las limitaciones inherentes de cualquier lenguaje formal lo suficientemente expresivo como para ser de verdadero interés. Dichos lenguajes son necesariamente capaces de una autorreferencia suficiente para que el lema diagonal se les pueda aplicar. La importancia filosófica más amplia del teorema de Tarski es más llamativamente 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 asigna una fórmula a su valor de verdad y la "función de denotación semántica" que asigna un término al objeto que denota. El teorema de Tarski se generaliza entonces de la siguiente manera: Ningún lenguaje lo suficientemente poderoso es fuertemente semánticamente autorrepresentativo . ${\displaystyle A}$ ${\displaystyle ||A||,}$ ${\displaystyle t}$

El teorema de indefinibilidad no impide que la verdad de una teoría se defina en una teoría más fuerte. Por ejemplo, el conjunto de (códigos para) fórmulas de aritmética de Peano de primer orden que son verdaderas en es definible por 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 -ésimo orden para cualquier ) se puede definir por una fórmula en ZFC de primer orden . ${\displaystyle {\mathcal {N}}}$ ${\displaystyle n}$ ${\displaystyle n}$

Véase también

• Teorema de incompletitud de Chaitin  : medida de la complejidad algorítmicaPages displaying short descriptions of redirect targets
• Teorema de completitud de Gödel  – Teorema fundamental de la 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 [math.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 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.

Lectura adicional

• Bell, JL; Machover, M. (1977). Un curso de lógica matemática . Holanda Septentrional.
• Boolos, G. ; Burgess, J. ; Jeffrey, R. (2002). Computabilidad y lógica (4ª ed.). Cambridge University Press.
• Lucas, JR (1961). "Mente, máquinas y Gödel". Philosophy . 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, EE. UU. ISBN 0-19-504672-2.
• Smullyan, R. (2001). "Teoremas de incompletitud de Gödel". En Goble, L. (ed.). The Blackwell Guide to Philosophical Logic . Blackwell. págs. 72–89. ISBN 978-0-631-20693-4.