The Semantical Antinomies: Tarski's Paradox

References

[Tarski30] Alfred Tarski, "Fundamental Concepts of the Methodology of the Deductive Sciences"

[Tarski36] Alfred Tarski, "The Concept of Truth in Formalized Languages"

[Tarski39] Alfred Tarski, "On Undecidable Statements in Enlarged Systems of Logic and the Concept of Truth", Journal of Symbolic Logic, 1939, pp. 106-112.

[Tarski44] Alfred Tarski, "The Semantic Concept of Truth and the Foundations of Semantics"

[Restall] Greg Restall, "Arithmetic and Truth in Lukasiewicz's Infinitely Valued Logic", Technical Report for the Automated Reasoning Project at Austalian National University.

Outline

The purpose of this note is to provide a careful analysis of the antinomy of the liar from §1 of [Tarski36] (see also [Tarski44,§7].) Some care will be made to lay out the assumptions with some consideration about how we may evade the antinomy and allow a truth definition for a language within the language itself.

Tarski's Theorem

Tarski presents the antinomy of the liar in [Tarski36, middle of §1;] and [Tarski44,§7], in essentially the same form; he also draws a conclusion, which I am going to call Tarski's Theorem, which can be summarized as

No consistent language can satisfy all of the following

The language is semantically closed.

The ordinary (classical) rules of logic hold for the language.

The language has some mechanism allowing self-reference.

The statement can be found in either [Tarski36, end of §2;, where Tarski uses the term universal in place of semantically closed] or [Tarksi44,§8], and are essentially the same; although it is significant that Tarski understood Tarski's Theorem subtly differently in [Tarski36] from [Tarski44], because he took the range of the term language to be different in each.

One important consequences Tarski draws from Tarski's Theorem is that

There can be no consistent semantically closed languages.

This is explicitly stated in [Tarski44,§8], although it is clear from the argument given that Tarski certainly accepted the claim at the time of [Tarski36]. (More on this below.) Given this claim it is imperative to show how we can use semantic terms like truth without requiring a semantically closed language to do so. Tarski's solution is to show how a language on which we want to use semantic terms can be strengthened to a new language in which the semantic terms we need can be introduced. We can then carry on our discussion in this new language. The original language is the object language and the new language is the meta-language. In [Tarski44, §10] Tarski argues that this strengthening of the original language is an essential condition for the formulation of semantic terms for the language

The condition of essential richness of the metalanguage over the object language is a necessary and sufficient condition for the construction of a satisfactory definition of truth for the object language in the metalanguage.

I have not found any comparable claim in [Tarski36]. Tarski does not spell out what it means for one language to be essentially richer then another.

What I will do here is to explore the first consequence Tarski draws, that there can be no consistent semantically closed languages. In particular, I will

Consider more closely what is meant by language and the subtle differences between Tarski's understanding of Tarski's Theorem
Analyze each of the three premises, nailing down a more exact formulation sufficient for the antinomy of the liar.
Review the argument of the antinomy of the liar
Explore the possiblity of having a semantically closed language, in the face of rejecting either (II) or (III)

The main conclusion to be drawn about the fourth point is that we can have a semantically closed language (I), and even satisfy either of (II) or (III).

A Note About Notation

Lets fix a name for the language, L, and worry about the particular features that must be included about it later. I will use italized lower case roman letters for names (a b c) and variables (x y z) which are found in the language. I will also be talking about the language (in an informal metalanguage--not the more formal notion of metalanguage used by Tarski to solve the problem of defining truth in a language); in this capacity I will use lower case greek letters for variables ranging over names (α β γ) in the language and as place holders to denote a position in an expression that a name would go (ξ). I will use upper case greek letters for predicates in the language together with a place holder (Π(ξ)) and for sentences of the language (Φ). Finally, I will use double quotes (") surrounding an expression of the language to denote some definite name for the expression. It will be clear in what follows what special properties this name must have. This use of double quotes is similar to Quine's use of corner quotes (not available in HTML). No assumption is being made about the shape of the name in the language which is denoted by a double quoted expression.

Semantically Closed Languages

The term semantically closed occurs in [Tarski44, §8], and is actually the amalgamation of the first two conditions from the argument for Tarski's theorem in [Tarski36,§1].

A language is semantically closed if (Ia) it contains a name for each of its sentences and (Ib) it provides a materially adequate truth predicate for its sentences.

Tarski's Theorem does not depend on how the truth predicate is given--whether defined, determined axiomatically, or fixed through useage--and Tarski in his argument in both [Tarski36] and [Tarski44] does not assume there is any such definition.

Assumption (Ia) is that every sentence in the language has a name in the language. It can be stated in the metalanguage as

(Ia) For every sentence Φ of the language there is a name α in the language such that α = "Φ"

Assumption (Ib) corresponds to the principle claim of Convention T: the criteria of materially adequate truth predicate. Let TR(ξ) be a predicate in L expressing truth. This means that TR(ξ) can only be asserted of names for sentences in L. It must also be the case that

(T) For every sentence Φ of the language, the following sentence is assertible in L
TR("Φ") ↔ Φ

There are a couple of subtle points here. First, Convention T is a statement in the metalanguage which is making a claim about what is assertible in L. It is worth exploring what resources L would require to be able to explicitly state (T) as a single sentence. This I will explore below. A second point is that L need only be able to assert (T) for some name in the language, namely the one picked-out by the double quote operator in the metalanguage. (T) also justifies our saying that "Φ" names Φ.

It is worth emphasizing this second point, because it is rather pregnant with implications. Tarski is not always clear on this point. It is tempting to read condition (II) in [Tarski36,§1] as claiming (T) must hold for every name of φ. On the other hand, his explicit definition of Convertion T in [Tarski36, §3] and [Tarski44,§4] is more carefully stated to apply only to a particular structural desciption of the name. This is a much stronger condition then what is stated in (T) where no assumption about how the name is actually constructed in L. If we insist that the names be structural-descriptive, this is because we are insisting that we be able to define a range of basic syntactic operations, and assert connexions between expressions. This is a profoundly important point for condition (III) of Tarski's Theorem, as we will see.

Why all the fuss here, and not insist that (T) hold for every name for Φ? We cannot assert (T) for every such name. Consider the name the first sentence uttered by Abe Lincoln on April 6, 1863 and suppose that Φ happened to be that sentence, but this information is lost today. But is the T-sentence

The first sentence uttered by Abe Lincoln on April 6, 1863 is true if and only if Φ

assertible? For languages which include simple (Peano) arithmetic, no materially adequate truth predicate would be possible, if the language the truth predicate was given could only assert theorems, and these were determined axiomatically (and so computably enumerable.)

Self-Reference

Tarski's examples of self-reference uses some empirical means for establishing the self-reference. In [Tarski44, 348-9] he claims that assumption (III) is not essential for generating the antinomy, and that (I) and (II) alone are sufficient. If we take these words strictly, it is false. An example will be given below of a language in which classical logic holds and which is semantically closed, but which is consistent nonetheless. This is possible, because it lacks a means for generating self-referential sentences. What Tarski is claiming is that it is not essential that the self-reference be establish empirically. In fact, if we have the means in L to provide structural descriptive names, we can generate self-referential names using a technique called diagonalization. Examples of this technique can be found in [Tarski36,§5] and which was based on Kurt Gödel's use of diagonalization to establish the undecidability of Peano Arithmetic. I will state (III) as an example of the diagonalization lemma of Gödel

(DIAG) For every predicate Π(ξ) in L there is a sentence Φ in L such that the following is assertible in L Π("Φ") ↔ Φ

Again be aware that (DIAG) is only being claimed to hold for certain names of the language, and these once again are denoted by the double quote name.

Languages and Theories

Several of the assumptions in Tarski's Theorem have made assumptions about what is assertible in L. In fact, Tarski's Theorem states conditions sufficient for a language being inconsistent, and he understands this in terms of what sentences are assertible. The Abe Lincoln example may already make one a bit uneasy about what the assertible sentences of a colloquial even are. The argument of [Tarski36,§1] is specifically directed against colloquial languages, and leads him to the conclusion that all colloquial languages are inconsistent. But, in [Tarski44] Tarski's theorem is only applicable to a certain class of languages, formal languages. Tarski questions whether we can specify the assertible sentences in a colloquial language (he actually uses the term natural language in this later work) to the extent that it is possible to meaningfully assert such a language is inconsistent. So, in the earlier work Tarski took his theorem to be applicable to all languages, colloquial and formal, but in his later work he took his theorem to apply only to formal languages.

My proposal here is to assume the language L is given by a definitely determined set of sentences S_L (all sentences of L) and a definitely determined subset of sentences A_L of assertible sentences. This set will have the further property that it is closed under classical inference, where this will be spelled-out more fully below.

A Little Logic

Assertion (II) requires that the ordinary rules of logic hold for L; in this context I will take the assumption as a requirement that A_L, the assertible sentences of L are closed under certain classically valid inference rules. The sentences of L, S_L, will be assumed to safisfy the following

The sentential closure conditions are given by

There is a contradictory sentence, ⊥. (This could be a sentence like 'There are squared circles' or 'Roses are both red and not red.'

Whenever Φ and Ψ are sentences, then so is Φ → Ψ

(Not strictly needed) Whenever Φ and Ψ are sentences, then so are ¬Φ and Φ ↔ Ψ. (We can replace negations ¬Φ by Φ → ⊥ and biconditionals Φ ↔ Ψ by a rather long sentences involving only → and ⊥)

Laws of logic will be given by closure under certain rules of inference. The two main rules are

(MP) (modus ponens) Φ, Φ → Ψ ⇒ Ψ
(⊥) (ex fals quodlibet) ⊥ ⇒ Φ

These are assertion closure conditions for the assertible sentences A_L, and they are to be understood to require

(MP) Whenever Φ is assertible and Φ → Ψ is assertible, then Ψ will also be assertible
(⊥) If ⊥ is assertible then so is Φ, for any sentence of the language.

(MP) is a basic rule of inference governing the conditional, and (⊥) explains why having a contradiction is so bad: if a contradiction is ever assertible, then so will be any sentence. Now, we can make precise what it means for L to be inconsistent

A language L is inconsistent if S_L = A_L

This is exactly how Tarski defines an inconsistent language in [Tarski30,§6]; in [Tarski36,§2;, Definition 19] he gives a slightly different definition, which is equivalent because of the rules (MP) and (⊥)
: A language L if inconsistent if both Φ and ¬Φ are assertible, for some sentence Φ. Notice that by our convention for negations, this is the same as Φ and Φ → ⊥ being assertible for some Φ; now use (MP) and (⊥) to get that S_L = A_L. (NOTE:Tarski has in mind a sharper concept then language as I am using it here: deductive system or formal language. The main differences are that the set of sentences are computable and countable, and that the assertible sentences are computably enumerable. As Tarski puts it, we have a structural description of the primitive symbols the language and the rules for constructing expressions, and a structural description of the basic axioms and rules of inference for the assertions of the language. See [Tarski36,§2], [Tarski39,footnote 4] or [Tarski44,§6].)

We will need some rules for governing the behavior of biconditionals.

(↔1) Whenever Φ ↔ ;Ψ is assertible and Π(Φ) is assertible then so is Π(Ψ), where Π(Ψ) results from substituting Ψ for none, some or all occurrences of Φ in the sentence Π(Φ).
(↔2)Whenever Φ ↔ ;Ψ is assertible then so are both Φ → ;Ψ is assertible and Ψ → ;Φ.
(↔3) Whenever Φ ↔ ¬Φ is assertible, so is ⊥

The first rule is the rule of replacement for equivalents and the second rule establishes that the biconditional is just the holding jointly of two conditionals. The final rule gives a condition under which we can assert a contradiction. All are valid rules of inference in classical logic.

With these rules in place we are in a position to more formally state assumption (II)

(II): The language L satisfies the following closure conditions

S_Lsatisfies the sentential closure conditions

A_L is closed under the rules of inference (MP), (⊥), (↔1), (↔2), (↔3)

The Antinomy of the Liar

Now, we can present Tarksi's argument for Tarski's Theorem, which takes the form of the antinomy of the liar:

(1) ¬TR("Φ") ↔ Φ (DIAG)

(2) TR("Φ") ↔ Φ (T)

(3) ¬Φ ↔ Φ (↔1), (1), (2)

(4) ⊥ (↔3)

Alternative Logics

In the face of the paradox some plausible assumption must be dropped. Tarski's preferred choice was assumption (I), rejecting the use of semantically closed languages. We might also consider rejecting (II), and changing our underlying logic, to evade the paradox. Tarski's response to this possibility is to note that it would be superfluous to stress the consequences of changing the logic ([Tarski44,§8]). This is a bit of preaching to the choir, but I think his point is that changing the underlying logic may evade the paradox, but often severely impairs sciences which are based on deductive systems, like mathematics. The example Tarski had in mind was probably intuitionistic logics which grew out of a response to Russell's paradox (and possibly the Burali-Forti paradox) at the turn of the century. Intuitionistic versions of mathematical systems are often impoverished compared to their classical counterparts (although, it may be a matter of perspective how severe one takes this to be.) For Tarski, the cost of changing the logic was too great compared to the loss of sciences based on deductive systems.

On the other hand, many alternatives to classical logic have been justified on broader grounds then avoiding paradox. I think intuitionism grew out of an analysis of why the paradoxes occurred, and so intended to impair mathematics and not just change the logic of reasoning. This is an important point, since as we will see, it is not a simple matter of rejecting some rule of inference or other to avoid paradox; alot of the underlying logic must be changed. But lets start by examining what rules of inference look like good candidates to reject.

The rules of inference (MP), (↔1) and (↔1) are basic rules governing the conditional and biconditional, and lie at the heart of any logic. The two rules involving ⊥, (⊥) and (↔3) also play a central role in the many other antinomies in logic: Russell paradox of naive set theory, Richard paradox for denotation, Grelling paradox for satisfaction. Lets consider controling the damage of asserting a contradiction, by rejecting (⊥). In this case, we treat ⊥ like any other sentence in the language. The intuitionistic logic of Johansson from the thirties, and systems of relevance logic advanced in the late fifties reject this rule of inference (although motivated by different concerns.) Relevance logics insist that the premises of an inference must be related in content (relevant) to the conclusion; what content does a contradiction share with every sentence in the language?

Alternatively, one can reject (↔3). The validity of (↔3) depends on two assumptions about truth

every sentence by either true or false
a formula and its negation must have different truth values

Thus, at least one of Φ or ¬Φ must be true by (a), and if Φ ↔ ¬Φ were true, then both Φ andr ¬Φ would be true. This contradicts (b). My shift from assertion to truth was deliberate, because neither (a) nor (b) are plausible conditions of assertion. For (a) it is not plausible to think that every sentence is either assertible or not assertible. For (b), it is also not plausible that if a sentence Φ is not assertible, its negation is assertible, since the language may be non-commital. One possiblity suggested by this is to recognize three "truth values": assertible, deniable, and non-commital. This move blocks the argument for (↔3). Back in the twenties the logician Jan Lukasiewicz proposed a three-valued logic as an attempt to block the paradoxes. He also introduced logics with multiple truth-values including infinitely many truth-values (this last was to model probabilistic reasoning --truth values measured something like degree of confidence-- although today the logic has recieved prominence to model fuzzy reasoning.) Another important class of logics rejecting (↔3) are intuitionistic logics which are often based on what we are held to be able to assert.

Two ⊥ Free Paradoxes

Simply rejecting one or both of the ⊥ rules will not avoid paradox. I will present two versions of the paradox which can still be generated using plausible assumptions of classical logic, but which avoids ⊥. Both are based on an argument from Haskell Curry (showing how to generate a paradox in naive set theory while avoiding the use of negation.) The first version assumes that the sentences of our language L are closed under conjunction: ∧, and that the following pair of laws are assertible

(∧1) (Φ ∧ Φ) ↔ Φ is assertible for every sentence Φ
(∧2)(Φ ∧ (Φ → Ψ)) → Ψ is assertible for every sentence Φ and Ψ

The first law states that asserting Φ ∧ Φ is redundant, and means no more than Φ. Every logic with conjunction accepts this law. The second law states in L that the rule of inference (MP) is valid. It is a law which holds in intuitionistic logic, although not in relevance logics and some many-valued logics. These are enough to generate a contradiction

(1)	(TR("Φ") → Ψ) ↔ Φ	(DIAG)
(2)	TR("Φ") ↔ Φ	(T)
(3)	(Φ ∧ (Φ → Ψ)) → Ψ	(∧2)
(4)	(Φ ∧ (TR("Φ") → Ψ)) → Ψ	(↔1), (2), (3)
(5)	(Φ ∧ Φ) → Ψ	(↔1), (1), (4)
(6)	(Φ ∧ Φ) ↔ Φ	(∧1)
(7)	Φ → Ψ	(↔1), (6), (5)
(8)	TR("Φ") → Ψ	(↔1), (2), (7)
(9)	Φ	(↔1), (1), (8)
(10)	Ψ	(MP), (7), (9)

The argument given here was used by Leon Henkin to show that Santa Claus exists. (Substitute "Santa Claus exists" for Ψ in the argument below) His argument in turn is based on work done in the mid-fifties by M.H. Löb (in response to a question posed by Henkin). The argument uses the logical law of the contraction of premises for the conditional

(CONTRACTION) Whenever Φ → (Φ → Ψ) is assertible, then so is Φ → Ψ

The law holds in Relevance logics and Intuitionistic logics. It is rejected by the many-valued logics of Lukasiewicz, although in most of these logics weaker forms of (CONTRACTION) hold which are susceptible to variants of the argument presented below. The exception is the infinite-valued logic posed by Lukasiewicz. This logic can consistently support languages which are semantically closed, and which allow diagonalization. See [Restall], for example.

(1) (TR("Φ") → Ψ) ↔ Φ (DIAG)

(2) TR("Φ") ↔ Φ (T)

(3) (Φ → Ψ) ↔ Φ (↔1)

(4) Φ → (Φ → Ψ) (↔2), (3)

(5) Φ → Ψ (CONTRACTION), (4)

(6) (Φ → Ψ) → Φ (↔2), (3)

(7) Φ (MP, (6), (5)

(8) Ψ (MP, (5), (7)

A Classical Semantically Closed Language which is Consistent

As I mentioned above, Tarski held that assumptions (I) and (II) are sufficient to generate inconsistency. I It is possible to have a language in which classical logic holds and which is semantically closed, but which is consistent. Of course, as pointed out earlier, Tarski tended to assume that Convention (T) held for names which were generated in a particular way, and this choice ensures that the diagonalization lemma (assumption III) holds for these names. In the example given below, names for sentences are taken to be syntactically simple. For these names the diagonalization lemma fails to hold. See link for the technique to construct such languages.

(1)	¬TR("Φ") ↔ Φ	(DIAG)
(2)	TR("Φ") ↔ Φ	(T)
(3)	¬Φ ↔ Φ	(↔1), (1), (2)
(4)	⊥	(↔3)