From: rusin@vesuvius.math.niu.edu (Dave Rusin) Subject: Re: Proofs of Independence and Consistency Date: 3 Feb 2000 18:00:41 GMT Newsgroups: sci.math Summary: [missing] In article <3894c133.19020925@news.caps.maine.edu>, Matthew Burgess wrote: > >I have read in my undergrad math class that Godel and Cohen proved >that the Axiom of Choice is independent of the Zermelo-Frankel axioms. >In general, how are things proven to be independent of certain axioms? By constructing models in which the axioms hold but the other "thing" either does or does not. For example, Euclid's fifth postulate is independent of the other because there are models in which the axioms hold and the parallel postulate also holds ("space"=plane,"line"=line) and yet there are also models in which the axioms hold but the p.p. does not hold ("space"=sphere, "line"=great circle). >How does one prove consistency? Can someone explain it or point me to >the appropriate resources? Where can I find these proofs? That's harder. Again, consistency is proved by constructing a model in which the axioms hold (the Soundness Theorem assures us there cannot be a model in which inconsistent axioms hold). There is the teensy little problem that the construction of the model uses other mathematical constructs (sets, say) whose consistency is unknown. So what you really prove in these cases is _relative consistency_: such and such a theory is consistent _assuming_ set theory is consistent. Unfortunately we know that one could _never_ prove consistency of any theory (set of axioms) as strong as set theory (ZF). Oh, well, except in one case: if the axioms are _inconsistent_, then they prove a falsehood, and so, logically speaking, they prove any result at all -- including the consistency of the theory. So you should be very nervous when you see a proof of the consistency of set theory, because it would actually be a proof of the inconsistency of set theory! (This is Model Theory, a branch of Mathematical Logic. See index/03EXX.html ) dave