# Axiom of Choice: Can someone explain the fallacy in this reasoning?

Not a "set theory" guru (apologies if my terms are imprecise), but I have heard that it is an elementary result that the set of rational numbers has a measure of zero - intuitively meaning that the set of rationals is "less dense" than the set of real numbers (or equivalently than the set of irrational numbers).

However, I read this article which seems to provide a rather simple proof showing that the rationals have a cardinality at least as big as the irrationals, which would contradict the above paragraph. So at least one of the results should be wrong? However I cannot find the fallacy in the reasoning in the article - the author places the blame on the axiom of choice (bit of a whipping boy of set theory I think).

Any ideas? or is the author's argument sound?

-
Seems like a crank work, I'll go through it and will try to give a review of the fallacy. –  Asaf Karagila Apr 26 '11 at 13:15
There is also an error in the proof on page 5, in that when one does an argument like that by transfinite induction one has to show that a choice is possible even at limit stages. By assuming that the rationals are not exhausted before the irrationals, the author is already assuming the result that is being proved, that the cardinality of the irrationals is no bigger than the cardinality of the rationals. The author tries to address this lower on page 5, but that argument is only valid if only finitely many rationals have been chosen so far in the construction. –  Carl Mummert Apr 26 '11 at 13:31
You could summarize the argument (keeping the link to the original). It looks like this to me: Well-order the positive reals. Consider building a set of rationals. For each real in turn, add a rational less than (conventional order) the real that has not been added so far. As the rationals are dense, this can always be done. This makes a bijection between the reals and the rationals. –  Ross Millikan Apr 26 '11 at 13:31
@Carl: As usual with such work, talking about "the" error seems to be giving too much credit to the author. There seem to be many errors, throughout the manuscript. –  Arturo Magidin Apr 26 '11 at 13:31
Just a general piece of advice: stay away from papers with such strong claims, especially if submitted in the math.GM (general mathematics) part of the ArXiV before the endorsement system was installed. The use of Microsoft Word instead of LaTeX is another thing that should turn on all warning signs. –  t.b. Apr 26 '11 at 15:11

The author's argument is, of course, not solid.

His main argument proceeds as follows: let $(\mathbb{X},\preceq)$ be a well ordering of the positive irrational numbers.

He then attempts to construct, through transfinite induction, an embedding of $\mathbb{X}$ into a subset of $\mathbb{Q}\cap[0,\infty)$ as follows: let $\zeta\in\mathbb{X}$.

• Assuming that all elements $\xi\prec \zeta$ have been mapped into $\mathbb{Q}$, there exists $q\in\mathbb{Q}$ such that either $q=0$ or $q$ is the image of some $\xi\prec\zeta$. Let $q'$ be any rational such that $q\lt q'\lt \xi$, and $q\neq 0$ and $q$ is not the image of any $\xi\in\mathbb{X}$ with $\xi\prec \zeta$. Define the image of $\zeta$ to be $q'$.

He claims that $q'$ will always exist "because there is always a rational between any two real numbers". But this assertion is empty: the existence of such a rational does not imply the existence of a rational that has not yet been chosen. The author never actually establishes the existence of such a $q'$.

Added. Note also that your first paragraph is not very apt. While (Lebesgue) measure is very weakly connected to cardinality (in that any set that is countable must have Lebesgue measure $0$), the connection is not very good. The Cantor set has measure $0$, but has the same cardinality as the entire real line; and the Cantor set has empty interior, so it is very much "not dense".

-
Thanks for that @Arturo - not my forte, set theory. Interesting about the lebesgue measure though - learn something new every day. I am a bit confused with how q' could not exist, because it is a dense set. Seems like one could "keep going" to find a suitable q'. On having read the answers and comments here, and having another think, the concept of "exhausting" an infinite set seems a bit impossible. Didn't think I'd get this much of a response so quickly! –  probabilityislogic Apr 26 '11 at 13:58
@probabilityislogic: The idea of exhausting infinite set is that the process is not finitary, but we describe "all" the steps needed for it to finish, even if by one-step-at-a-time we can never even reach the first limit point. This sort of idea is very common in mathematics and particularly in set theory. –  Asaf Karagila Apr 26 '11 at 14:04
The connection between measure and cardinality is somewhat stronger, assuming the axiom of choice. I learned this from Walter Rudin. Suppose that $A$ is a set whose measure is greater than $0$. Then the set $A + A = \{a_{0} + a_{1} \colon a_{0}, a_{1} \in A \}$ contains an interval, hence has the same cardinality as the reals. Since $|A| = |A + A|$ the cardinality of $A$ is the same as the cardinality of the reals. –  Jay Apr 26 '11 at 14:42
@user9176: I think that's giving too much credit. I don't think he understands, period. –  Arturo Magidin Apr 26 '11 at 17:20
@Arturo: I hope you remember next time or I'll start taking money for these things ;-) –  Asaf Karagila Apr 26 '11 at 17:34

Have you never seen a simple proof that the cardinality of the rationals is less than that of the irrationals? It's easy to find such proofs in texts or on the web, they are quite satisfactory in every way. There is no need to look at the article to which you refer. It must be wrong, and it is the author's job, not yours or mine, to find out where the mistake is.

-
@gerry - while this is all true and I completely agree with you, getting some "expert" answers to such questions is invaluable helps me to understand the subtleties of what is going on here. And if I don't ask, and I can't find the fallacy myself, then I am simply left with two apparently reasonable yet incompatible results. For which am I to believe is correct? I think what threw me off is the author's blaming of the axiom of choice, which seems "dodgy" compared to the other axioms, from what I know about it (which is not much). –  probabilityislogic Apr 26 '11 at 14:54
@Theo: Sorry, a slightly offhand remark referring to this ABBA song: azlyrics.com/lyrics/abba/whataboutlivingstone.html, which basically says that if people like Livingstone hadn't gone ahead, nothing new would have been discovered. I understand Gerry's point of view, but I also like the fact that a lot of other people here engaged the "proof" and pointed out the blatant errors. Deciding which unorthodox challenges to spend time on is a non-trivial task; perhaps not in this case, but more generally, and science stays healthy by being exposed to unorthodox challenges... –  joriki Apr 26 '11 at 19:33
..., so Gerry's no-nonsense don't-waste-your-time-on-cranks attitude struck me as somewhat too absolute, and the remark was just intended to express that sentiment without getting into a long discussion over pseudoscience and the relative merits of keeping an open mind and focussing on things known to make sense. But now I may get into one after all... :-) –  joriki Apr 26 '11 at 19:33
@joriki: Ah! That makes sense now :) Thanks for the clarification! (ABBA was a bit before my time and my knowledge about them doesn't extend much beyond Money... Let's close that file, though). I agree with the thrust of your comment, in general, but Mr Mückenheim and his pal Jailton Ferreira were among our favorite math.GM contributors on the ArXiV when we were studying... –  t.b. Apr 26 '11 at 19:42
@probabilityislogic, the one you are to believe is correct is the one you understand. That's why I pointed out that there are simple proofs of the correct result all over the place. You can read them, and understand them, and then you will know which to believe. I have no problem with someone writing, "help me find the flaw in this alleged proof of a result which is known to be wrong;" I do have a problem with "is the author's argument sound?" when you can know that the author's argument can't possibly be sound. –  Gerry Myerson Apr 28 '11 at 1:46

This is a work of someone who clearly does not understand the idea behind the axiom of choice and ordinal arithmetics.

For to address the minor issue your first paragraph has, the rational has measure zero because singletons have measure zero, and the measure is countably additive, that is a union of countably many disjoint sets is the sum of the measure.

Firstly he is very mistaken in the part where he claims that cuts are characterized by their end points. How can you characterize the rational numbers smaller than $\pi$? It has no end point. The thing is that those are subsets, as the excerpt from Levy's text say. And Cantor's theorem says that $|P(X)|>X$ (a theorem whose proof requires no choice whatsoever), so there are many more subsets (cuts) than end points, and possibly many of those are unrealized cuts/gaps (i.e. irrational numbers).

This shows that it is very possible to have many many more cuts than end points within the actual ordering.

As for the bijection, the writer has no grasp about the idea of infinitary processes. Consider the following:

Take an enumeration of $\mathbb{Q}=\{q_n\mid n\in\omega\}$. Now take an enumeration of the irrationals such that the first $\omega$ many are those of the form $\{q_n+\pi\mid n\in\omega\}$ and then enumerate the rest of the irrationals as you wish. The bijection described in the article will exhaust exactly after $\omega$ steps while you still have at least $2^{\aleph_0}$ many steps to go with the irrationals.

In order to work with infinite well-ordered sets one needs to say what happens at limit points, i.e. steps which has no preceding ones, this is not handled in the construction and he just says "continue until $\mathbb X$ is exhausted".

This is similar to proving that every ordinal number is finite:

Start with $0$, finite. Then assume $n$ is finite therefore $n+1$ is finite. Continue until you exhaust the class of ordinal numbers. Therefore all ordinals are finite.

This is wrong because eventually we exhaust natural numbers and we find ourselves at the realm of infinite ordinals, as we did not specify what is going to happen at the limit stages, this induction can (and will) fail at the first limit point - $\omega$.

-
very nice. This is what I suspected, but could put it precisely. An unambiguous limiting process needs to be described when handling "infinities". Got a bit of a barrage for my poor knowledge of measure theory :). "common sense" + "infinity" - "infinitesimal" = "crazy" –  probabilityislogic Apr 26 '11 at 14:10
@probabilityislogic: To be fair, your comment makes little to no sense to me. :-P –  Asaf Karagila Apr 26 '11 at 14:14