Tarski's undefinability theorem

Tarski's undefinability theorem

Tarski's undefinability theorem, stated and proved by Alfred Tarski in 1936, is an important limitative result in mathematical logic, the foundations of mathematics, and in formal semantics. Informally, the theorem states that "arithmetical truth cannot be defined in arithmetic".

The theorem applies more generally to any sufficiently strong formal system, showing that truth in the standard model of the system cannot be defined within the system.

History

In 1931, Kurt Gödel published his famous incompleteness theorems, which he proved in part by showing how to represent "syntax" within (first-order) arithmetic. Each expression of the language of arithmetic is assigned a distinct number. This procedure is known variously as Gödel-numbering, "coding", and more generally, as arithmetization.

In particular, various "sets" of expressions are coded as sets of numbers. It turns out that for various syntactic properties (such as "being a formula", "being a sentence", etc.), these sets are computable. Moreover, any computable set of numbers can be defined by some arithmetical formula. For example, there are formulas in the language of arithmetic defining the set of codes for arithmetic sentences, and for provable arithmetic sentences.

The indefinability theorem shows that this encoding cannot be done for semantical concepts such as truth. It shows that no sufficiently rich interpreted language can represent its own semantics. A corollary is that any metalanguage capable of expressing the semantics of some object language must have expressive power exceeding that of the object language. The metalanguage includes primitive notions, axioms, and rules absent from the object language, so that there are theorems provable in the metalanguage not provable in the object language.

The indefinability theorem is conventionally attributed to Alfred Tarski. Gödel also discovered the indefinability theorem in 1930, while proving his incompleteness theorems published in 1931, and well before the 1936 publication of Tarski's work. While Gödel never published anything bearing on his independent discovery of indefinability, he did describe it in a 1931 letter to John von Neumann. Tarski had obtained almost all results of his 1936 paper "Der Wahrheitsbegriff in den formalisierten Sprachen" between 1929 and 1931, and spoke about them to Polish audiences. However, as he emphasized in the paper, the indefinability theorem was the only one exception. According to the footnote of the indefinability theorem (Satz I) of the 1936 paper, the theorem and the sketch of the proof were added to the paper only after the paper was sent to print. When he presented the paper to Warsow Academy of Science on March 21 1931, he wrote only some conjectures instead of the results after his own investigations and partly after Gödel's short report on the incompleteness theorems "Einige metamathematische Resultate über Entscheidungsdefinitheit und Widerspruchsfreiheit", Akd. der Wiss. in Wien, 1930.

Statement of the theorem

We will first state a simplified version of Tarski's theorem, then state and prove in the next section the theorem Tarski actually proved in 1936.Let "L" be the language of first-order arithmetic, and let "N" be the standard structure for "L". Thus ("L", "N") is the "interpreted first-order language of arithmetic." Let "T" denote the set of "L"-sentences true in "N", and "T"* the set of code numbers of the sentences in "T". The following theorem answers the question: Can "T"* be defined by a formula of first-order arithmetic?

Tarski's undefinability theorem: There is no "L"-formula "True"("x") which defines "T"*.That is, there is no "L" formula "True"("x") such that for every "L"-formula "x", "True"("x") ↔ "x" is true.

Informally, the theorem says that given some formal arithmetic, the concept of truth in that arithmetic is not definable using the expressive means that arithmetic affords. This implies a major limitation on the scope of "self-representation." It "is" possible to define a formula "True"("x") whose extension is "T"*, but only by drawing on a metalanguage whose expressive power goes beyond that of "L", second-order arithmetic for example.

The theorem just stated is a corollary of Post's theorem about the arithmetical hierarchy, proved some years after Tarski (1936). A semantic proof of Tarski's theorem from Post's theorem is obtained by reductio ad absurdum as follows. Assuming "T"* is arithmetically definable, there is a natural number "n" such that "T"* is definable by a formula at level Sigma^0_n of the arithmetical hierarchy. However, "T"* is Sigma^0_k complete for all "k". Thus the arithmetical hierarchy collapses at level "n", contradicting Post's theorem.

General form of the theorem

Tarski proved a stronger theorem than the one stated above, using an entirely syntactical method applicable to formal systems far more general than first-order arithmetic. The resulting theorem applies to any formal languages with negation and sufficient capability for self-reference that Gödel's Diagonal Lemma holds. First-order arithmetic satisfies these preconditions, of course.

The following is a proof of Tarski's undefinability theorem in its most general form by reductio ad absurdum. Suppose that an "L"- formula "True"("x") defines "T"*. In particular, if "A" is a sentence of arithmetic then "True"("A") is true in "N" if and only if "A" is true in "N". Hence for all "A", the Tarski "T"-sentence "True"("A") ↔ "A" is true in "N". But Gödel's diagonal lemma yields a counterexample to this equivalence: the "Liar" sentence "S" such that "S" ↔ ¬"True"("S") holds. Thus no "L"-formula "True"("x") can define "T"*. QED.

The formal machinery of this proof is wholly elementary except for the diagonalization encapsulated in the diagonal lemma. The proof of that Lemma is likewise surprisingly simple; for example, it does not invoke recursive functions in any way. The proof does assume that every "L"-formula has a Gödel number, but the specifics of the coding method are not required. Hence Tarski's theorem is much easier to motivate and prove than the more celebrated theorems of Gödel concerning the metamathematical properties of first-order arithmetic.

Discussion

Smullyan (1991, 2001) has argued forcefully that Tarski's undefinability theorem deserves much of the attention garnered by Gödel's incompleteness theorems. That the latter theorems have much to say about all of mathematics and more controversially, about a range of philosophical issues (e.g., Lucas 1961) is less than evident. Tarski's theorem, on the other hand, is not directly about mathematics but about the inherent limitations of any formal language sufficiently expressive to be of any real interest. Such languages are necessarily capable of enough self-reference for the diagonal lemma to apply to them. The broader philosophical import of Tarski's theorem is more strikingly evident.

An interpreted language is "strongly-semantically-self-representational" exactly when the language contains predicates and function symbols defining all the semantic concepts specific to the language. Hence the required functions include the "semantic valuation function" mapping a formula "A" to its truth value ||"A"||, and the "semantic denotation function" mapping a term "t" to the object it denotes. Tarski's theorem then generalizes as follows: "No sufficiently powerful language is strongly-semantically-self-representational".

References

* Bell, J.L., and Machover, M., 1977. "A Course in Mathematical Logic". North-Holland.
* George Boolos, John Burgess, and Richard Jeffrey, 2002. "Computability and Logic", 4th ed. Cambridge University Press.
*Lucas, J. R., 1961, " [http://users.ox.ac.uk/~jrlucas/Godel/mmg.html Mind, Machines, and Gödel,] " "Philosophy 36": 112-27.
*Raymond Smullyan, 1991. "Godel's Incompleteness Theorems". Oxford Univ. Press.
*Raymond Smullyan, 2001, "Gödel’s Incompleteness Theorems" in Goble, Lou, ed., "The Blackwell Guide to Philosophical Logic". Blackwell: 72-89.
* Alfred Tarski, 1983, "The Concept of Truth in Formalized Languages" in Corcoran, J., ed., "Logic, Semantics and Metamathematics". Indianapolis: Hackett. The English translation of Tarski's 1936 "Der Wahrheitsbegriff in den formalisierten Sprachen".


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Tarski's theorem — Several results obtained by the noted logician Alfred Tarski are commonly referred to as Tarski s theorem:*Tarski s theorem on real closed fields established the decidability of the first order theory of real numbers. *The Knaster Tarski theorem… …   Wikipedia

  • List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

  • Gödel's incompleteness theorems — In mathematical logic, Gödel s incompleteness theorems, proved by Kurt Gödel in 1931, are two theorems stating inherent limitations of all but the most trivial formal systems for arithmetic of mathematical interest. The theorems are of… …   Wikipedia

  • Metalogic — is the study of the metatheory of logic. While logic is the study of the manner in which logical systems can be used to decide the correctness of arguments, metalogic studies the properties of the logical systems themselves.[1] According to… …   Wikipedia

  • Semantic theory of truth — A semantic theory of truth is a theory of truth in the philosophy of language which holds that truth is a property of sentences.[1] Contents 1 Origin 2 Tarski s Theory 3 See also …   Wikipedia

  • Dependence logic — is a logical formalism, created by Jouko Väänänen[1], which adds dependence atoms to the language of first order logic. A dependence atom is an expression of the form , where are terms, and corresponds to the statement that the value of is… …   Wikipedia

  • Münchhausen Trilemma — The Münchhausen Trilemma (after Baron Münchhausen, who allegedly pulled himself (and the horse he was sitting on) out of a swamp by his own hair), also called Agrippa s Trilemma (after Agrippa the Skeptic), is a philosophical term coined to… …   Wikipedia

  • Warsaw School of Mathematics — is the name given to a group of mathematicians who worked at Warsaw, Poland, in the two decades between the World Wars, especially in the fields of logic, set theory, point set topology and real analysis. They published in the journal Fundamenta… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”