From: israel@math.ubc.ca (Robert Israel)
Subject: Re: I am not a crook
Date: 26 Jul 1999 22:27:52 GMT
Newsgroups: sci.logic,sci.math
Keywords: Loeb's (Lob's) Theorem: "Is provable" is provable
In article <7nfprp$u3k$1@iradj.is-bremen.de>,
"Marco Manfredini" writes:
> I somewhat curious about self-confirming statements:
>
> (1) 'This statement is false' is the basic form of well known and
> popularized antinomies
>
> (2) 'This statement is true' is what?
It's not necessarily either: in any system of logic that allows "this
statement is false", there is no consistent way of assigning "true" or
"false" to all statements.
However, the similar statement "This statement is provable" is indeed
provable. The formal version of this is called L\"ob's Theorem. See
G. Boolos, "The Logic of Provability", American Mathematical Monthly
91 (Oct. 1984) 470.
Here's an informal proof of "This statement is provable".
Call that statement S (i.e. S asserts "S is provable"). Let T be the
statement that asserts "if T is provable then S".
If T is provable, there is a proof of "If T is provable then S".
But by combining this with the proof of T and modus ponens, you have
a proof of S. Thus if T is provable then S is provable. But since
S asserts "S is provable", we see that if T is provable then S.
Now the above paragraph is a proof of T. Thus T is indeed provable.
Therefore S is true (and thus provable).
Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2