Tarski's indefinability theorem

In mathematical logic, Tarski's Indefinability Theorem is a theorem due to Alfred Tarski concerning the foundations of mathematics. Informally, the theorem states that arithmetic truth cannot be defined in arithmetic.

Kurt Gödel discovered his incompleteness theorems (1931) partly by showing how to represent syntax within arithmetic. Each expression of the language of arithmetic is assigned a distinct number. This procedure is called gödel-numbering or sometimes just coding; more generally, arithmetization. If E is an expression, then let #E be its code number, and let "E" be the linguistic numeral denoting this code number.

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 of numbers are recursive. And, it is already known that any recursive set X of numbers can be defined by some arithmetic formula. For example, there is a formula Sent(x) in the language of arithmetic which defines the set of sentences of the language of arithmetic.

Can the same be done for semantical concepts, such as truth? Tarski's discovered around 1933 (in part after studying Gödel's methods: in particular, arithmetization and the Diagonal Lemma) that in the most interesting cases, the answer is No. Roughly, a sufficiently rich interpreted language cannot represent its own semantics. It follows that, generically, the meta-language must be richer than the object language.

In fact, Gödel himself had discovered the Indefinability Theorem in 1930, on his way to proving the Incompleteness Theorems, and before Tarski's work appeared. Gödel did not publish his discovery, but did describe it in a 1931 letter to John von Neumann.

For arithmetic, this is how it works (the proof can be generalized to any language which is at least as rich as the interpreted language of arithmetic). Let L be the first-order language of arithmetic. Let N be the standard structure for L. So, (L, N) is the interpreted first-order language of arithmetic. Let T be the set of truths in N. Let T* be the set of code numbers of sentences in T. The question is: can T* be defined by an arithmetic formula?

Tarski's indefinability theorem: There is no L-formula True(x) which defines T*.

Proof: By reductio ad absurdum. Suppose that such a formula True(x) existed. 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, using Goedel's Diagonal Lemma, we could construct a Liar sentence S such that S <-> ~True("S") would be true in N. But this contradicts True("S") <-> S. Hence, no such L-formula True(x) exists in the language of arithmetic. QED.

Informally speaking, the concept of arithmetical truth is not arithmetically definable. Notice that this states a limit on self-representation. For it is possible to define a formula True(x) whose extension is the set T* of (code numbers of) truths in the language of first-order arithmetic. However, this formula must be in a richer metalanguage, such as the language of second order arithmetic.

Despite some claims to the contrary, Tarski's Indefinability Theorem really is quite general, and is not restricted only to bivalent languages based on classical logic. For example, it can in a certain sense be generalized to interpreted languages based on many-valued logic. For example, fuzzy logic, dialetheism, paraconsistent logic, etc. Let us say that an interpreted language is strongly-semantically-self-representational just in case the language contains predicates and function symbols which define all the semantic concepts specific to that language (for example, the semantic valuation function which maps a formula A to its truth value ||A|| and the semantic denotation function which maps a term t to the object it denotes).

Then, Tarski's Theorem generalizes to: no sufficiently powerful language is strongly-semantically-self-representational.

References

[1] Tarski, A. 1956: "The Concept of Truth in Formalized Languages", in Tarski, A. 1956: Logic, Semantics and Metamathematics, edited by J.H. Woodger (Oxford University Press). This is the English translation of the classic 1935 article in German, Der Wahrheitsbegriff in den formalisierten Sprachen, which is a translation of a 1933 Polish book.

[2] Boolos, G.S., Burgess, J.P and Jeffrey, R.C. 2002: Computability and Logic. Cambridge University Press. 4th Edition.

[3] Bell, J.L. & Machover, M. 1974: A Course in Mathematical Logic. North-Holland.fr:Théorème d’incomplétude de Tarski