- #51

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,950

- 19

"Secondly, the problem the liar's paradox brings to light is that various rules for forming formulas conflict with logical semantics. If one is not to alter logic, one must instead alter the grammar by which formulas are constructed."

Perhaps this is what the previous posters were trying to do but in doing so then there is no paradox -- and hence there is nothing to prove. However, if we are left with nothing to prove then all attempts to do so are superfluous.

There

*is*nothing to do in the various forms of logic used today. For example, first-order logic solved the issue by simply disallowing predicates to operate on predicates entirely. The grammar only allows one to evaluate predicates at variable symbols. P(Q), for example, is simply not in the language of well-formed formulas, if P and Q are both predicate symbols.

One can look for other ways to slip self reference into the logic: this is essentially what a Gödel numbering is, and the liar's paradox becomes becomes Tarski's theorem on the undefinability of truth. (Gödel's first incompleteness theorem is the same idea, but referring to provability rather than truth)

This continues with higher-order logics. e.g. second-order logic introduces second-order predicates that are allowed to operate upon first-order predicates and variables, but not second-order predciates. Both steps of the usual formal version of the liar's paradox fail:

- We can't define a predicate [itex]\Phi(P) := \neg P(P)[/itex] because P(P) isn't a well-formed formula. (P is a first-order predicate, so we cannot evaluate P at P)
- Even if we could, we can't consider [itex]\Phi(\Phi)[/itex] anyways. ([itex]\Phi[/itex] is a second-order predicate, so we cannot evaluate [itex]\Phi[/itex] at [itex]\Phi[/itex])

In lambda calculus, all of the steps of the usual version of the Liar's paradox can be executed:

[tex]F := \lambda x. \mathrm{NOT}(x x)[/tex]

[tex]S := F F[/tex]

it's easy to see that S is a liar sentence:

[tex]S = FF = (\lambda x. \mathrm{NOT}(x x)) F = \mathrm{NOT}(F F) = \mathrm{NOT\ } S[/tex]

It's also easy to see the right hand sides are both lambda expressions so one cannot weasel out of a paradox by claiming that either F or S is not well-formed. So we are stuck with a lambda expression S with the property that S is neither TRUE nor FALSE.

Fortunately, there are plenty of other things S can be, so there is no paradox.

Note that an older form of Lambda calculus suffered from the Kleene-Rosser paradox. Stanford's pages state that Curry considered the paradox as analogous to Russel's paradox and the Liar's paradox.

In the theory of computation, the recursion theorem lets us write down a liar Turing machine directly, by the program:

- Let P be my own source code.
- Simulate the execution of P.
- If P returns True, then return False.
- return True

In various modern forms of logic, the Liar's paradox simply isn't paradoxical. Or more precisely, no way is known to construct an inconsistency of logic using the idea of the Liar's paradox. Instead, the idea simply becomes a useful proof by contradiction technique, e.g. to prove in ZFC that the class of all sets is a proper class, or in the theory of computation to demonstrate the halting problem is not computable.

The Liar's paradox only remains a threat of

*inconsistency*when one is trying to devise new logics, trying to understand the semantics of natural languages, or other similar sorts of situations.