Teorema de indefinibilidad de Tarski

El teorema de indefinibilidad de Tarski , enunciado y demostrado por Alfred Tarski en 1933, es un importante resultado limitativo en lógica matemática , fundamentos de las matemáticas y semántica formal . De manera informal, el teorema afirma 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 , demostrando que la verdad en el modelo estándar del sistema no puede definirse dentro del sistema. ^{[ 2 ] : 491, 493}

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 como numeración de Gödel , codificación y, más generalmente, 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, 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 (un conjunto computablemente enumerable ).

El teorema de la indefinibilidad demuestra que esta codificación no puede realizarse 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 números naturales de la aritmética ^{[ 3 ]} ) debe tener un poder expresivo superior al del lenguaje objeto. El metalenguaje incluye nociones primitivas, axiomas y reglas de inferencia ausentes en el lenguaje objeto, de modo que existen teoremas demostrables en el metalenguaje que no lo son en el lenguaje objeto.

El teorema de la indefinibilidad se atribuye convencionalmente a Alfred Tarski . Gödel también descubrió este teorema en 1930, mientras demostraba sus teoremas de incompletitud, publicados en 1931, mucho antes de la publicación del trabajo de Tarski en 1933 (Murawski 1998). Si bien Gödel nunca publicó nada relacionado con su descubrimiento independiente de la indefinibilidad, sí la describió en una carta a John von Neumann en 1931. 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 los presentó ante audiencias polacas. Sin embargo, como enfatizó en el artículo, el teorema de la indefinibilidad fue el único resultado que no había obtenido con anterioridad. Según la nota al pie del teorema de indefinibilidad ( Twierdzenie I ) de la monografía de 1933, el teorema y el esbozo de la demostración se añadieron a la monografía solo después de que el manuscrito se enviara 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 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 definitividad de la decisión y la consistencia], Academia Austríaca de Ciencias , Viena, 1930.

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

Dejar${\displaystyle L}$es el lenguaje de la 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 de " primer orden ": los cuantificadores se extienden sobre los números naturales, pero no sobre conjuntos o funciones de números naturales. La teoría es lo suficientemente fuerte como para describir funciones enteras definidas recursivamente, como la exponenciación, los factoriales o la sucesión de Fibonacci .

Dejar${\displaystyle \mathbb {N} }$ser la estructura estándar para${\displaystyle L}$, es decir${\displaystyle \mathbb {N} }$consta del conjunto ordinario de números naturales y su suma y multiplicación. Cada oración en${\displaystyle L}$puede interpretarse en${\displaystyle \mathbb {N} }$y luego se convierte en verdadero o falso. Por lo tanto${\displaystyle (L,\mathbb {N})}$es el "lenguaje interpretado de primer orden de la aritmética".

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

Teorema de indefinibilidad de Tarski (forma simplificada) : No existe${\displaystyle L}$-fórmula${\displaystyle \mathrm {Verdadero} (n)}$que define${\displaystyle T^{*}}$. Es decir, no hay${\displaystyle L}$-fórmula${\displaystyle \mathrm {Verdadero} (n)}$de tal manera que para cada${\displaystyle L}$-oración${\displaystyle A}$, la fórmula${\displaystyle \mathrm {Verdadero} (g(A))\iff A}$se sostiene en${\displaystyle \mathbb {N} }$.

De manera informal, el teorema dice que el concepto de verdad de las proposiciones aritméticas 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". Al trabajar en un sistema más fuerte (por ejemplo, agregando una especie de subconjuntos de${\displaystyle \mathbb {N} }$como en la aritmética de segundo orden ) es posible definir una fórmula${\displaystyle \mathrm {Verdadero} (n)}$que se mantiene exactamente en el conjunto${\displaystyle T^{*}}$, pero eso no define la verdad para el sistema más fuerte: esta fórmula${\displaystyle \mathrm {Verdadero} (n)}$solo define un predicado de verdad para fórmulas en el lenguaje original.${\displaystyle L}$(por ejemplo, porque${\displaystyle T^{*}}$no contiene códigos para oraciones que cuantifican sobre subconjuntos de${\displaystyle \mathbb {N} }$). Para definir la verdad en este sistema más fuerte, sería necesario ascender a un sistema aún más fuerte, y así sucesivamente.

Para probar el teorema, procedemos por contradicción y suponemos que un${\displaystyle L}$-fórmula${\displaystyle \mathrm {Verdadero} (n)}$existe algo que sea cierto para los números naturales.${\displaystyle n}$en${\displaystyle \mathbb {N} }$si y solo si${\displaystyle n}$es el número Gödel de una oración en${\displaystyle L}$eso es cierto en${\displaystyle \mathbb {N} }$Entonces podríamos usar${\displaystyle \mathrm {Verdadero} (n)}$para definir un nuevo${\displaystyle L}$-fórmula${\displaystyle S(m)}$Eso es cierto para los números naturales.${\displaystyle m}$si y solo si${\displaystyle m}$es el número de Gödel de una fórmula${\displaystyle \varphi (x)}$(con una variable libre)${\displaystyle x}$) tal que${\displaystyle \varphi (m)}$es falso cuando se interpreta en${\displaystyle \mathbb {N} }$(es decir la fórmula)${\displaystyle \varphi (x)}$, 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${\displaystyle g}$de la fórmula${\displaystyle S(m)}$y preguntar si la oración${\displaystyle S(g)}$es cierto en${\displaystyle \mathbb {N} }$Obtenemos una contradicción. (Esto 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 de Tarski (1933). Una demostración semántica del teorema de Tarski a partir del teorema de Post se obtiene por contradicción de la siguiente manera. Suponiendo${\displaystyle T^{*}}$es definible aritméticamente, hay un número natural${\displaystyle n}$de tal manera que${\displaystyle T^{*}}$es definible por una fórmula en el nivel${\displaystyle \Sigma _{n}^{0}}$de la jerarquía aritmética . Sin embargo,${\displaystyle T^{*}}$es${\displaystyle \Sigma _{k}^{0}}$-difícil para todos${\displaystyle k}$. Por lo tanto, la jerarquía aritmética se derrumba en el nivel${\displaystyle n}$, contradiciendo el teorema de Post.

Tarski demostró un teorema más fuerte que el mencionado anteriormente, utilizando un método completamente sintáctico. El teorema resultante se aplica a cualquier lenguaje formal con negación y con capacidad suficiente para la autorreferencia, de modo 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${\displaystyle (L,{\mathcal {N}})}$cualquier lenguaje formal interpretado que incluya la negación y tenga una numeración de Gödel.${\displaystyle g(\varphi )}$que satisface el lema diagonal, es decir, para cada${\displaystyle L}$-fórmula${\displaystyle B(x)}$(con una variable libre)${\displaystyle x}$) hay una oración${\displaystyle A}$de tal manera que${\displaystyle A\iff B(g(A))}$se sostiene en${\displaystyle {\mathcal {N}}}$Entonces no hay${\displaystyle L}$-fórmula${\displaystyle \mathrm {Verdadero} (n)}$con la siguiente propiedad: para cada${\displaystyle L}$-oración${\displaystyle A,}$la fórmula${\displaystyle \mathrm {Verdadero} (g(A))\iff A}$es cierto en${\displaystyle {\mathcal {N}}}$.

La demostración del teorema de indefinibilidad de Tarski en esta forma es nuevamente por reducción al absurdo . Supongamos que un${\displaystyle L}$-fórmula${\displaystyle \mathrm {Verdadero} (n)}$como existía anteriormente, es decir, si${\displaystyle A}$es un${\displaystyle L}$-oración, entonces${\displaystyle \mathrm {Verdadero} (g(A))}$se sostiene en${\displaystyle {\mathcal {N}}}$si y solo si${\displaystyle A}$se sostiene en${\displaystyle {\mathcal {N}}}$Por lo tanto, para todos${\displaystyle A}$, la fórmula${\displaystyle \mathrm {Verdadero} (g(A))\iff A}$se sostiene en${\displaystyle {\mathcal {N}}}$. Pero el lema diagonal, con${\displaystyle B(x)}$instanciado a${\displaystyle \lnot \mathrm {Verdadero} (x)}$, proporciona un contraejemplo a esta equivalencia, al dar una fórmula "mentirosa"${\displaystyle S}$de tal manera que${\displaystyle S\iff \lnot \mathrm {Verdadero} (g(S))}$se sostiene en${\displaystyle {\mathcal {N}}}$Esto es una contradicción. QED.

La maquinaria formal de la demostración dada anteriormente es completamente elemental, excepto por la diagonalización que requiere el lema diagonal. La demostración del lema diagonal es igualmente sorprendentemente simple; por ejemplo, no invoca funciones recursivas de ninguna manera. La demostración asume que todo${\displaystyle L}$La fórmula tiene un número de Gödel , pero no se requieren detalles específicos del método de codificación. Por lo tanto, el teorema de Tarski es mucho más fácil de justificar y demostrar que los teoremas más conocidos de Gödel sobre las propiedades metamatemáticas de la aritmética de primer orden.

Smullyan (1991, 2001) ha argumentado con vehemencia que el teorema de indefinibilidad de Tarski merece gran parte de la atención que han recibido los teoremas de incompletitud de Gödel . Que estos últimos teoremas tengan mucho que decir sobre toda la matemática y, de forma más controvertida, sobre una serie de cuestiones filosóficas (p. ej., Lucas 1961) no es tan evidente. El teorema de Tarski, por otro lado, no trata directamente sobre matemáticas, sino sobre las limitaciones inherentes de cualquier lenguaje formal suficientemente expresivo como para ser de verdadero interés. Dichos lenguajes son necesariamente capaces de autorreferenciarse lo suficiente como para que el lema diagonal les sea aplicable. La importancia filosófica más amplia del teorema de Tarski es más notablemente evidente.

Un lenguaje interpretado es fuertemente semánticamente autorrepresentacional precisamente cuando 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${\displaystyle A}$a su valor de verdad${\displaystyle ||A||}$y la "función de denotación semántica" que asigna un término${\displaystyle 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 autorrepresentacional .

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

• Atopia (filosofía) – Impracticabilidad de ser asimilado a un tema. 
• Teorema de incompletitud de Chaitin : medida de complejidad algorítmica. Páginas que muestran breves descripciones de destinos de redireccionamiento. 
• Cierre cognitivo (filosofía) : limitaciones inherentes de la mente humana. 
• Teorema de completitud de Gödel : un teorema fundamental de la lógica matemática. 
• Teoremas de incompletitud de Gödel : resultados limitativos en lógica matemática. 
• Ignoramus et ignorabimus – Máxima sobre los límites del conocimiento científico 
• Inefabilidad : Incapacidad de una idea o sentimiento para ser expresado con palabras. 
• Incognoscibilidad – Idea filosófica de cosas imposibles de conocer. 

• Bell, JL; Machover, M. (1977). Un curso de lógica matemática . North-Holland.
• 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" . Filosofía . 36 (137): 112–27 . doi : 10.1017/S0031819100057983 . hdl : 10077/5466 . S2CID 55408480. Archivado del original el 19 de agosto de 2007. 
• Murawski, R. (1998). «La 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 del 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). «Los teoremas de incompletitud de Gödel». En Goble, L. (ed.). The Blackwell Guide to Philosophical Logic . Blackwell. pp. 72–89 . ISBN  978-0-631-20693-4.