FOM: a question re. completeness
wtait@ix.netcom.com
wtait at ix.netcom.com
Wed Feb 4 09:43:05 EST 1998
Kanovei 2/3/98 write in response to Detlefsen's query
>I would suggest
>
>--------------
>T is consistency-complete iff for every sentence s of the
>language of T that is not provable in T, the following is
>a theorem of T:
>if Prov_T(s) then \neg Consis s
>--------------
I assume that he means \neg Consis_T and this seems to be what Mic
intended. Then PA is not consistency-complete. Here is a witness, though
probably not the simplest. Choose S so that S \coimplies [Prov(S)
\implies Prov(negS)] is a theorem of PA. S is not a theorem, since
otherwise Prov(S) would be; hence so would Prov(\negS) and PA would prove
its own inconsistency. So on the assumption of consistency-completeness,
Prov(S) \implies Prov(0=1) is a theorem. But so is Prov(0=1) \implies
Prove(negS). Hence, Prov(S) \implies Prov(\negS) is a theorem. But S is
the fixed point for this; so S is a theorem.
Bill Tait
More information about the FOM
mailing list