| Science Forum Index » Logic Forum » Diagonal Lemma - self-reference |
|
Page 1 of 1 |
|
| Author |
Message |
| Michiel Borkent |
 Posted: Mon Jan 26, 2004 4:01 pm |
|
|
|
Guest
|
|
| Back to top |
|
|
|
| Jeffrey Ketland |
| Posted: Mon Jan 26, 2004 4:36 pm |
|
|
|
Guest
|
Michiel Borkent wrote in message ...
[quote:956e6ab7ca]I was interested in the matter of self-reference and the famous Liar
example: "This sentence is false".
Someone told me Don Perlis wrote an article on Self-Reference and I am
reading it now:
http://citeseer.nj.nec.com/cache/papers/cs/27798/http:zSzzSzwww.cs.umd.eduz
SzprojectszSzactivezSzdoczSzpaperszSzbigphi.pdf/theory-and-application-of.pd[/quote:956e6ab7ca]
f
[quote:956e6ab7ca]
I get stuck on page 3 where Don talks about the Diagonal Lemma. Also he
uses
the term "wff". Can someone explain to me what those are?
[/quote:956e6ab7ca]
Either the sound a dog makes, or it's short for "well-formed formula". A&B
is a well-formed formula. &&AB isn't.
[quote:956e6ab7ca]easy-to-digest example of the Diagonal Lemma?
[/quote:956e6ab7ca]
1. The *diagonalization* of a formula phi with one free variable is the
result of substituting the quotation name of phi for any occurrence of a
free variable in phi.
For example, the diagonalization of
(1) x is an anarchist
is the sentence
(2) "x is an anarchist" is an anarchist
Now, consider the diagonalization of
(3) the diagonalization of x is an anarchist
which is
(4) the diagonalization of "the diagonalization of x is
an anarchist" is an anarchist
Now, statement (4) is true if the diagonalization of (3) is an anarchist.
But statement (4) *is* the diagonalization of (3). So, (4) is true if (4) is
an anarchist. I.e., (4) is a self-referential statement. It means "This very
statement is an anarchist". A silly statement, of course, but
self-referential nonetheless.
Finally, diagonalize
(5) the diagonaliation of x is false
to get
(6) the diagonalization of "the diagonalization of x is false" is false.
The statement (6) means "I am false".
The Diagonal Lemma says that you can do this trick in formalised arithmetic.
If phi is a formula with one free variable, there is a sentence A such that
arithmetic proves
A <-> phi("A")
The sentence A says: "A has the property phi".
--- Jeff |
|
|
| Back to top |
|
|
|
| G. Frege |
| Posted: Mon Jan 26, 2004 5:04 pm |
|
|
|
Guest
|
On Mon, 26 Jan 2004 22:01:01 +0100, "Michiel Borkent"
<borkent@cs.utwente.nl> wrote:
[quote:0c1df4e075]
Also he uses the term "wff" ...
wff is short hand for "well-formed formula". It just means that a[/quote:0c1df4e075]
formula is part of the system considered.
F. |
|
|
| Back to top |
|
|
|
|
