Formulas for the liar paradox - MathOverflow

Formulas for the liar paradox

2010-06-10T12:15:01Z

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

Answer by supercooldave for Formulas for the liar paradox

2010-06-10T12:30:04Z

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

Answer by Joel David Hamkins for Formulas for the liar paradox

2010-06-10T12:30:11Z

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.

Answer by Timothy Chow for Formulas for the liar paradox

2010-06-10T16:00:00Z

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.

Answer by Jon Awbrey for Formulas for the liar paradox

2010-06-11T13:50:29Z

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.

Answer by Charles Stewart for Formulas for the liar paradox

2010-06-13T09:44:03Z

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

First-order equational logic which may, but need not be, equipped with constants, functions and relations; together with:
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;
Possibly, some constants that are names of certain individuals; and
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.

Answer by radams for Formulas for the liar paradox

2010-07-14T00:23:00Z

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.