From: weigand@informatik.uni-erlangen.de (Ulrich Weigand) Subject: Re: Is Zermelo-Fraenkel set theory inconsistent? Date: 1 Apr 1999 23:22:34 +0200 Newsgroups: sci.math Keywords: let's hope we never know :-) baez@galaxy.ucr.edu (john baez) writes: >I leave it to you to decide if this is an April Fool's joke. It was >posted by Paul Taylor to the category theory mailing list. [long snip] > Let L(0) be Zermelo set theory > (or the axioms for an elementary topos). > For each n, let L(n+1) be L(n) plus > as much of the axiom-scheme of replacement as is needed > to justify the gluing construction that shows that > L(n+1) |- ``L(n) is consistent.'' > Now let L(infinity) be the union of L(n) over n:N. > If L(infinity) |- false then L(n) |- false for some n. > But L(infinity) |- ``L(n) is consistent,'' > so L(infinity) proves its OWN consistency, > contradicting Godel's theorem. Oh, indeed? Even stipulating that L(inf) |- Cons(L(n)) for every n (which I have not thought about), this is still far from showing L(inf) |- \forall x Cons(L(x)) which would seem to be necessary to prove Cons(L(inf)) :-/ There's a much simpler version of this trick: for every single natural number n, ZF proves that n is not Goedel number of a ZF proof of '0=1'. Hence, ZF has proven that there exists no ZF proof of '0=1', implying the consistency of ZF, right? :-) -- Ulrich Weigand, IMMD 1, Universitaet Erlangen-Nuernberg, Martensstr. 3, D-91058 Erlangen, Phone: +49 9131 85-7688 ============================================================================== From: weigand@informatik.uni-erlangen.de (Ulrich Weigand) Subject: Re: Is Zermelo-Fraenkel set theory inconsistent? Date: 3 Apr 1999 00:37:34 +0200 Newsgroups: sci.math "Kevin Lacker" writes: >>There's a much simpler version of this trick: for every single natural >>number n, ZF proves that n is not Goedel number of a ZF proof of '0=1'. >>Hence, ZF has proven that there exists no ZF proof of '0=1', implying >>the consistency of ZF, right? :-) >I don't really know much about this; what's the trick about this trick? [ I'll use Peano Arithmetic (PA) instead of ZF; the problem is the same, but the situation is somewhat simpler ... ] The important point is that if you have a formula F(x) with a free variable x, it can be the case that PA proves F(n) for every *numeral* n, i.e. every term of the form SSS...SS0, but still PA is unable to prove the statement \forall x F(x). This means that PA is incomplete, of course, because PA cannot prove the statement \not\forall x F(x), either (since it can't be true in the standard model, and PA is correct). On the other hand, it should be no surprise that PA is incomplete, since this is just what Goedel proved. The intuitive explanation for that phenomenon would be that if PA did prove \forall x F(x), it would mean that F(x) would be true in *all* models of PA, with x interpreted by *any* element of that model. Now, we know that PA has a lot of non-standard models different from the usual model (consisting of the natural numbers), and in these models you have a lot of elements that are *not* named by any numeral term. Hence, it can be possible that in a non-standard model, both F(n) is true for any numeral, and \forall x F(x) is false, because F(x) is false for some of these non-standard elements. To return to the question of consistency proofs: the statement 'PA is consistent' is formalized as '\forall x F(x)' where F(x) is a formula with the intuitive meaning 'x is not (Goedel number of) a PA proof of 0=1'. Note that PA does indeed prove F(n) for any numeral n. This is because F is actually a primitive-recursive predicate, and it is easy to see that PA 'decides' all such predicates applied to numeral terms (i.e. it must be the case that either PA |- F(n) or PA |- \not F(n)). The latter cannot be the case, though, because if PA would actually prove about a numeral n that n is Goedel number of a PA proof of 0=1, then PA would be inconsistent. Nevertheless, it would be incorrect to conclude that PA would prove \forall x F(x), i.e. the consistency of PA, for reasons detailed above. And indeed, as Goedel has shown, PA does *not* prove that statement. -- Ulrich Weigand, IMMD 1, Universitaet Erlangen-Nuernberg, Martensstr. 3, D-91058 Erlangen, Phone: +49 9131 85-7688