Showing posts with label diagonal lemma. Show all posts
Showing posts with label diagonal lemma. Show all posts

Monday, February 28, 2011

Syntactic self-reference without diagonal lemma or Gödel numbers

For the proof of Goedel's incompleteness theorem and in work on the Liar Paradox it is usual to use the Diagonal Lemma to secure self-reference. The challenge of self-reference is this. Given a predicate Q, find a syntactically definable predicate P such that
  1. (s)(P(s) → R(s))
is provably the one and only sequence of symbols satisfying P. Then (1) says that Q holds of itself. (To get the (Strengthened) Liar Paradox, just make R(s) say that s is not true.) But the proof of the diagonal lemma is hard to understand.

I find the following way of securing self-reference easier to understand. Start with a language that has nestable quotation marks, which I'll represent with ‘...’, and some string manipulation tools. I'll use straight double quotation marks for meta-language quotation. Add to the language a new symbol "@" which is ungrammatical (i.e., no well-formed formula may contain it). For any sequence of symbols s, we define two new sequences of symbols N(s) and Q(s) by the following rules. If s contains no quoted expressions or contains imbalanced opening and closing quotation marks, N(s) and Q(s) are just "@". If s contains a quoted expression, Q(s) is the first quoted expression, without its outermost quotation marks (but with any nested quotations being included), and N(s) is the result of taking s and replacing that first quoted occurrence of Q(s), as well as its surrounding single quotation marks, with "@". Thus:
  1. Q("abc‘def‘ghi’’+jkl")="def‘ghi’"
  2. N("abc‘def‘ghi’’+jkl")="abc@+jkl".
It is easy to see that Q and N are syntactically defined. Now, let M(s) be equal to N(s) if N(s)=Q(s) and let M(s) be an empty sequence "" otherwise. Again, M(s) is syntactic. Now consider this sentence:
  1. (s)(‘(s)(@=M(s) → R(s))’=M(s) → R(s)).
It is easy to prove (given a bit of string manipulation resources) that the only sequence s that satisfies the antecedent of the conditional is (4) itself. So we have constructed the syntactic predicate P(s). It is: ‘(s)(@=M(s) → R(s))’=M(s).

One can also adapt this to work with Goedel numbers and hence presumably for use in proving incompleteness.

[Removed a nasty typo.]