An easy constructive proof of a version of Tarski's Undefinability of Truth

Tarski's Undefinability of Truth theorem says that given a language that contains enough material cannot have a truth predicate, i.e., a predicate that holds of all and only the true sentences. This yields Goedel's Incompleteness Theorem if you let the predicate be IsProvable.

 Here's a proof in a string setting. Suppose that L is a language that (under some interpretation--I will generally drop that qualification for simplicity) lets you talk about finite strings of characters. Suppose L has a concatenation function +: a+b is a string consisting of the characters of a followed by the characters of b.  Suppose further that every character has a name in L given by surrounding the character with asterisks.  Thus, *+* is a name for the plus sign.  Suppose that there is a function Q in L such that if a is a string, then Q(a) is a string that consists of the names of the asterisk-based names for the characters in a interspersed with pluses.  I will call Q(a) a quotation of a.  Thus Q("abc")="*a*+*b*+*c*".  I will say that a substring q of a string s is a quotation in s provided that q is a substring of s of the form "*a*+*b*+*c*+..." and q cannot be extended to a longer quotation.  I will also use "*abc*" (etc.) to abbreviate "*a*+*b*+*c*".

Suppose that we can define a predicate T in L that is veridical, i.e., T(a) is true only if a is true.  We will now construct a sentence g in L such that g is true and T(g) is false.  This shows that there is no predicate true of all and only all sentences of g.  Here's how.  Let g be the following sentence:

• (x)[(z)(z=*AlmostMe* → ((FirstQuotes(x,z) & FirstQuoteRemoved(x,z)))→~T(x))]

Here, AlmostMe is an abbreviation (I will put abbreviations in bold) for the following sequence of characters:

• (x)[(z)z=() → ((FirstQuotes(x,z) & FirstQuoteRemoved(x,z)))→~T(x))]

I.e., AlmostMe is an abbreviation for g except for the quotation of AlmostMe inside g.  FirstQuotes(x,z) is an abbreviation of a complex predicate that says that the first quotation inside x is a quotation of z.  FirstQuoteRemoved(x,z) is an abbreviation of a predicate that says that z is what you get when you take x and replace the first quotation in it with "()".

Lemma 1. One can define FirstQuotes(x,z) and FirstQuoteRemoved(x,z) satisfying the above description.

I'll leave out the proof of this easy fact.

Lemma 2. The one and only string x that satisfies both FirstQuotes(x,*AlmostMe*) and FirstQuoteRemoved(x,*AlmostMe*) is g.

Here's an informal proof of Lemma 2.  The first quotation in x is indeed a quotation of AlmostMe, and so FirstQuotes(x,*AlmostMe*) does indeed hold.  Moreover, if we remove that quotation of AlmostMe and replace it with "()", we get AlmostMe.  So g does satisfy both predicates.  

Suppose now that h satisfies both predicates.  We must show that h=g.  Start with the fact that FirstQuoteRemoved(h,*AlmostMe*).  This shows that h is of the form:

• (x)[(z)(z=*...* → ((FirstQuotes(x,z) & FirstQuoteRemoved(x,z)))→~T(x))]

where *...* is some quotation.  But because FirstQuotes(x,*AlmostMe*), that first quotation must be a quotation of AlmostMe.  But then h is g.  

Given Lemma 2, the proof of our theorem is easy.  By First Order Logic, g is equivalent to:

• (x)((FirstQuotes(x,*AlmostMe*) & FirstQuoteRemoved(x,*AlmostMe*))→~T(x))

But the one and only x that satisfies the antecedent of the conditional is g.  Hence, g is true if and only if ~T(g).  Now, g is either true or false.  If it is false, then ~T(g) is true as T is veridical, and so g is true, which is a contradiction.  Therefore, g is true.  But if it is true, then ~T(g) and so g does not satisfy T.  That completes the proof.

I'm going to try out a version of this proof on undergraduates one of these days.