# Truth Value of Theorems in Axiomatic Set Theory

I encountered set theory these past couple of days in discrete mathematics, and my professor was talking about the axiom of choice and ZFC. He said that depending on which axiom you started from, you could prove or disprove the Continuum Hypothesis.

Now this really intrigued and distressed me. I thought mathematics was the language that is all proof, all universal truth. How can there be two theorems that lead to two different outcomes? Is one or both of them wrong?

-
Whether or not you believe that mathematics is the study of "universal truth" (whatever that means), why do you believe that "universal truth" is the same as "things that can be proven in ZFC"? Also, it sounds like you're not aware of the incompleteness theorem: en.wikipedia.org/wiki/G%C3%B6del's_incompleteness_theorems –  Qiaochu Yuan Sep 12 '11 at 22:29
It's like discovering that Santa Claus doesn't exist, isn't it? (Except I've never met anyone who claims to have genuinely believed in Santa, whereas the notion of mathematics as an objective source of undoubtable truth is widespread). But in order to do actual work with it, one needs to come to terms with the fact that the foundations of mathematics get shiftier the deeper you dig. I've found it somewhat soothing to consider that different set theories allow different collections to be called "sets", and equipotency is as much about the available mappings as about the sets themselves. –  Henning Makholm Sep 12 '11 at 23:10

There is a theorem that says the angles of a triangle always add up to 180 degrees. There is another theorem that says the angles of a triangle always add up to more than 180 degrees. How can there be two theorems that lead to two different outcomes? Easy: they are based on different situations. The first one is predicated on the axioms of Euclidean geometry. The second is based on the axioms of spherical geometry; every triangle (suitably defined) on a sphere has angles adding up to more than 180 degrees.

There's even a third system, where every triangle has angles adding up to less than 180 degrees; it's called hyperbolic (or, Lobachevskian) geometry.

Which one is the true geometry? Unask the question. There is no such thing as the true geometry, there are just different models that are useful in different circumstances.

The situation with the Continuum Hypothesis is similar. There is a set theory in which it is true, and a set theory in which it is false, and no one has come up with a convincing argument that one of these is the true set theory and the other a fake. For the time being, and perhaps forever, we have to accept that there are different models that are useful in different situations.

If it's any comfort to you, none of this has any effect whatsoever on the mathematics of the typical introductory discrete math class. Everything you are likely to see in such a class will hold regardless of what goes on with the Continuum Hypothesis.

-
thank you, this was REALLY helpful! –  Caleb Jares Sep 13 '11 at 2:59
if I could +5, I would –  Caleb Jares Sep 13 '11 at 3:01
Most physicists would tell you current models of the geometry of black holes conclude the geometry within is hyperbolic. The physics of the 20th century essentially shattered all preconceptions of what "reasonable" models of reality would be-so the idea that Euclid's geometry was The Geometry Of All Reality is now merely a quaint antiquated notion. Or to put it another way:"The universe is not only stranger then we imagine, it's stranger then we CAN imagine." -Arthur C.Clarke –  Mathemagician1234 Sep 13 '11 at 6:15
Never seen it attributed to Clarke. Haldane, Eddington, and Heisenberg come up on web searches. –  Gerry Myerson Sep 13 '11 at 7:30
@Gwrry Well,I first read it in an interview with Clarke. So if it wasn't his, he didn't give credit where credit was due. –  Mathemagician1234 Sep 15 '11 at 7:13

Mathematics is about deducing theorems from previous theorems and axioms, using logical axioms (for example $\lnot\lnot\alpha\rightarrow\alpha$).

In first order logic, in which much of set theory is done, there is a theorem known as The Deduction Theorem. This theorem says that if we can prove $\beta$ from $T\cup\{\alpha\}$ then we can prove from $T$ the statement $\alpha\rightarrow\beta$.

The importance is that if we assume that ZFC is consistent then we can prove from that ZFC+CH and ZFC+$2^{\aleph_0}=\aleph_2$ are both consistent.

In fact, in a very strange sense we prove that ZFC proves that there is no proof from ZFC alone that $2^{\aleph_0}=\aleph_1$. We can of course prove CH from a stronger theory ZFC+CH.

Whether or not the statement itself is true or not is a philosophical question, whether or not there is a single universe or a multiverse with multitude of truth values. This is much discussed in several papers (such as this one).

Regardless to the nature of mathematics, universal or multiversal, we cannot prove all statements from a theory which has certain properties, as tells us Gödel's incompleteness theorems.

-

What this material is doing in a standard discrete mathematics course is beyond me-unless your professor is an expert in mathematical logic and axiomatic set theory and just decided to toss it out there.

In any event,what your professor is referring to is one of the deepest results of these areas in the last half of the 20th century-namely,Paul Cohen's proof that the validity of either the axiom of choice or the continuum hypothesis is dependent on the axiom system chosen. To understand this, you first have to understand one of the most powerful results in all of mathematical logic: The Godel Incompleteness Theorum:

http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems

In essence, Cohen constructed 2 internally consistent but mutually inconsistent axiom systems for the Zermelo-Frankel system with the Axiom of Choice (ZFC) when in each system, one of the 2 was true and the other was false. This was a huge development because there had been a great deal of speculation whether or not this could in fact be done while creating complete axiom systems for ZFC that were consistent in the Godel sense.Many wondered since models of the ZFC that could prove all the truths of arithmetic where by the Godel theorum inconsistent, would any system capable of asserting one while falsifying the other be consistent? Cohen showed the answer was in fact yes.In other words, he proved that the validity of both The Axiom of Choice and the Continuum Hypothesis was completely independent of the ZFC axioms. If you're interested in these deep results and the fields of mathematical logic and set theory-which are both altogether fascinating,especially for people who like to ask "why" things work in mathematics-then I can't recommend a better book then Robert S.Wolf's A Tour Through Mathematical Logic. Not only does it contain very detailed and wonderful discussions of all these matters,the book is very up to date and even includes a basic introduction to Hugh Woodin's recent follow-up to Cohen's work,which is very much a hot topic right now.

-
I once had a student spending actual time trying to prove using naive set theory (not even knowing what ZFC is) that $|P(X)|=|P(Y)|\Rightarrow |X|=|Y|$. Should I have not told him that this proof cannot be found like that? Of course I should have done that, and I did. I do agree that it is questionable whether or not to say that in the course itself. –  Asaf Karagila Sep 12 '11 at 23:34
@Asaf That's the kind of proof that clearly demonstrates the student doesn't have a clue what he or she is talking about. Most of us did it at the beginning at one time or another.In mathematics, the admission of ignorance truly IS the beginning of wisdom. –  Mathemagician1234 Sep 12 '11 at 23:45
It's a computer science class, and he went over it while discussing cardinality and infinite sets (right before set theory and powersets and such). But it really intrigues me, I like mathematics and logic. I might try to take a philo class soon. Also, I can't believe I'm catching a glimpse of the deep end of the well already freshman year, it's really exciting that I'm finally getting there. –  Caleb Jares Sep 13 '11 at 2:55
@Mathemagician1234: Actually he was the strongest student in class, and regarding the material taught he knew excellent what he is talking about. Again, it was not a course about axiomatic set theory but rather naive one. –  Asaf Karagila Sep 13 '11 at 5:45
He did not prove it. He tried, as it seemed like a plausible assertion. –  Asaf Karagila Sep 13 '11 at 6:33