MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Formulas for the liar paradox

How can the liar paradox be expressed concisely in symbols? In which formal languages?

-

The Liar is the statement "this sentence is false." It is expressible in any language able to perform self-reference and having a truth predicate. Thus, $L$ is a statement equivalent to $\neg T(L)$.

Goedel proved that the usual formal languages of mathematics, such as the language of arithmetic, are able to perform self-reference in the sense that for any assertion $\varphi(x)$ in the language of arithmetic, there is a sentence $\psi$ such that PA proves $\psi\iff\varphi(\langle\psi\rangle)$, where $\langle\psi\rangle$ denotes the Goedel code of $\psi$. Thus, the sentence $\psi$ asserts that "$\varphi$ holds of me".

Tarski observed that it follows from this that truth is not definable in arithmetic. Specifically, he proved that there can be no first order formula $T(x)$ such that $\psi\iff T(\langle\psi\rangle)$ holds for every sentence $\psi$. The reason is that the formula $\neg T(x)$ must have a fixed point, and so there will be a sentence $\psi$ for which PA proves $\psi\iff\neg T(\langle\psi\rangle)$, which would contradict the assumed property of T. The sentence $\psi$ is excactly the Liar.

Goedel observed that the concept of "provable", in contrast, is expressible, since a statement is provable (in PA) say, if and only if there is a finite sequence of symbols having the form of a proof. Thus, again by the fixed point lemma, there is a sentence $\psi$ such that PA proves $\psi\iff\neg\text{Prov}(\langle\psi\rangle)$. In other words, $\psi$ asserts "I am not provable". This statement is sufficiently close to the Liar paradox statement that one can fruitfully run the analysis, but instead of a contradiction, what one gets is that $\psi$ is true, but unprovable. This is how Goedel proved the Incompleteness Theorem.

-
 Minor quibble: I think you want to say $\psi$ is equivalent to $\phi(|\psi|)$, not $\phi(|\phi|)$. – Ketil Tveiten Jun 11 2010 at 14:50 Ketil, thanks very much! I have now corrected this. – Joel David Hamkins Jun 11 2010 at 15:10 Thanks for the clear answer. It's quite articulated, so let me see if I get this straight. Tarsky's theorem states that a truth predicate T cannot be defined for all sentences; were it definable, THEN (and only then) we could show that there exists a sentence \psi (the liar paradox) such that \psi\iff\neg T(\langle\psi\rangle) Let me ask you another question then. Does Goedel theorem state that - there exist sentences which have a definite truth value but are neither provable nor disprovable or only the weaker - there exist sentences which are neither provable nor disprovable ? – tomate Jun 12 2010 at 15:13 Tomate, thanks for accepting my answer. About the question in your comment, every statement has a definite truth value in the standard model of arithmetic, even if we don't know which occurs. What the Incompletness Theorem asserts is that for any formal axiomatic system, there will be statements that are neither provable nor refutable in that system. Such a statement will have a definite truth value, and so there will be true unprovable statements. – Joel David Hamkins Jun 12 2010 at 15:28

As Joel David Hamkins said, the standard answer to your question is that formal languages like the first-order language of arithmetic cannot express the liar paradox because they cannot express the predicate "is true" as applied to all its own sentences. Why not? Well, if it could, then we would get a contradiction, following the standard liar-paradoxical reasoning.

However, this is not the end of the story. For example, there is an interesting paper by Saul Kripke, Outline of a theory of truth, J. Philosophy 72 (1975), 690-716, better known among philosophers than among mathematicians, which explains how to define a truth predicate in such a way that the liar paradox can be expressed. The conclusion is just that the liar-paradoxical sentence has an undefined truth value.

-
Indeed, and there has been quite a bit of work along similar lines, leading to the subject of Revision Theories of Truth. The basic idea is to introduce a truth predicate T(x). It is unproblematic to apply it to assertions in the base language; the difficulty arises from attempting to apply T to assertions in the language with T. So one can proceed inductively, saying that if $\varphi$ is true at a stage, then $T(\varphi)$ becomes true at the next stage. Kripke in effect seeks fixed points in this procedure, and others have considered more complex rules at limit stages. – Joel David Hamkins Jun 10 2010 at 17:58
@Joel: Your comment reminds me of a remark that Kripke makes in his paper on page 697, that extending his work to transfinite levels lead to "mathematical difficulties that make the the problem highly nontrivial." Do you know what he is talking about and whether he or others have carried out this transfinite extension? – Timothy Chow Jun 10 2010 at 23:35
Oh yes, it has definitely been carried out. For example, see plato.stanford.edu/entries/truth-revision. There are various choices of limit rules used by Herzeberger, Gupta and others (see Philip Welch for some interesting criticism). – Joel David Hamkins Jun 11 2010 at 13:37
Thanks for the interesting reference, I'm going through it. – tomate Jun 13 2010 at 9:57

There is an extensive discussion of this issue in Vicious Circles by Jon Barwise and Lawrence S. Moss.

-

Aladdin M. Yaqūb (1993) The Liar Speaks the Truth, OUP, formalises a very simple language for naturally expressing the liar paradox, consisting of:

1. First-order equational logic which may, but need not be, equipped with constants, functions and relations; together with:
2. A constant for each sentence, which is the "name" of that sentence: i.e., a realisation of the countably infinite set of quoted sentences by the obviously bijective set of constants; this way of doing things avoid the need for any kind of syntactically (at least) second-order Quinean quotation operator from propositions to individuals;
3. Possibly, some constants that are names of certain individuals; and
4. A predicate T, together with a countably infinite set of axioms involving the names from (2) and (3) that are in the obvious bijective correspondence with the T-schema for the whole language we approach.

Yaqūb carried this out in the usual single-sorted first-order logic: I think it is more natural to formulate this in a two-sorted logic, but Yaqūb's handling of his system is concise and elegant, and this discpline shows that no kind of second-orderness, not even Henkin semantics, is required to model Tarski's T-schema, but only an expansion of the universe to include names, an additional predicate, and axioms sufficient to model the T-schema.

It shows, therefore, that an object language can be be its own meta-language without leaving the realm of the straightforwardly first order. As a consequence, the liar paradox exists within this logic, but it can be "tamed" with a family of possible tweaks to the T-schema. Yaqūb argues for one such tweaking that result in the liar paradox being not self-referential, but generating a sequence of formulae each involving one more T predicate. By looking at how the interpretation of these formulae evolve in each model, he classifies each formula of the base language —i.e., the subset of sentences that do not use the T predicate— into one of seven classes, depending on whether the sequence converges on a truth value, or whether they oscillate between values, and if so, in what manner. Paradoxical self-referential sentences are reseolved in a more pleasing manner than Tarski did, by being able to treat them in a unitary formalism that embeds the tower of formulae that are the progressive unwindings within the usual semantics of first-order logic, and without forbidding sentences that talk about themselves.

I found Yaqūb's monograph to be much more readable (I read it in an evening whilst travelling), and his argument much more elegant and compelling than that of Barwise & Etchemendy, and I highly recommend it to anyone who found B&E worth reading.

I would be very interested to read an effort to "intuitionise" Yaqūb's theory, by embedding it in intuitionistic first-order logic in a similarly elegant manner, and using a constructive model theory.

-

The liar paradox could be expressed in Church's original lambda calculus of 1932. Let $F$ be the function

$\lambda x. \sim x(x)$

Then $F(P) = \sim P(P)$ for any function $P$. In particular,

$F(F) = \sim F(F)$

and so $F(F)$ is a sentence that asserts its own falsehood.

-

Short Answer (SA). No Paradox, All Liar.

Bit Longer Answer (BLA). You don't need a theory of truth to say that a statement is false. You need only deny the statement. And if you tell me that a statement, say, Statement 1 (S1), is identical or even just logically equivalent to a statement that S1 is false, then you are telling me a falsehood, at least, according to principles that both of us probably took for granted beforehand.

-
-1: Please do not continue to answer questions of mathematical logic with answers that ignore or even flout the subject of mathematical logic. Such answers are not helpful. – Pete L. Clark Jul 14 2010 at 5:45