MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we have a set $M = (0,1) \subset R$ of reals well-ordered as the first uncountable ordinal.

Let $M(a) = \lbrace x \in M : x < a \rbrace$. For every $a \in M$ set $M(a)$ is countable. That's why every increasing sequence is bounded:
$$(*) ~~~~~~~~~~ \forall \lbrace a_1,...,a_n,...\rbrace \subset M ~~\exists b \in M : a_i < b ~~\forall i \in \mathbb{N}.$$

Now suppose that we can pick elements from $M$ at random. And let's try to build an increasing random sequence by the following algorithm. Let's say we have an increasing sequence of elements $\{a_1,...,a_n\}$. Pick some random number $b$. If $b > a_n$ set $a_{n+1} = b$. Otherwise pick other random number instead of $b$ and check $b > a_n$ condition. Continue this till success. Since we pick numbers at random it shouldn't be a problem to construct an infinite sequence. But every infinite sequence is bounded! Which means that in our infinite process we will never be able to pick random number which is greater than some number $c \in M$. This is even more astonishing since $M(c)$ is countable and $M \setminus M(c)$ is uncountable!

Any thoughts how to "solve" this paradox?

share|cite|improve this question
To pick elements from $M$ at random you need to have a probability measure on $M$ to sample from. What is it? – François G. Dorais Jun 6 '13 at 13:36
@François I guess he uses Lebesgue measure on $M$. – The User Jun 6 '13 at 13:41
@User: So $M$ is Lebesgue measurable and not null? – François G. Dorais Jun 6 '13 at 13:42
@François Hm? The standard probability measure (Lebesgue measure) on the unit interval is not null. – The User Jun 6 '13 at 13:47
@User: So Dan is assuming CH? – François G. Dorais Jun 6 '13 at 13:52
up vote 11 down vote accepted

I think the paradox can be solved by the observation that $c$ is defined a posteriori, so it is not true that you avoid $c$ during all the process, since $c$ is in fact an outcome of the process.

You could do a similar paradox without bothering with well-orderings: pick a sequence $X=\{a_1,a_2,\dots\}$ in $(0,1)$ by choosing each $a_i$ at random, one after the other.

Then your "paradox" is that each $a_i$ you chose belong to $X$, which has measure $0$ and is countable, whereas $(0,1)$ is uncountable with measure $1$. But since $X$ is the outcome of the process and was not defined at the time of the choosing, it is not a real paradox.

share|cite|improve this answer

I agree with DK that the "paradox" has nothing to do with the assumed well-ordering. I think it also has nothing to do with the decision to choose a countable sequence of elements $a_n$. Suppose we just pick a single $a$, at random, with respect to Lebesgue measure. Since the one-element set $\{a\}$ has measure zero, we can say, paraphrasing the question, "in our process, we never pick a number outside $\{a\}$. This is even more astonishing since $\{a\}$ has just a single element and its complement is uncountable."

I trust that this situation, involving just a single $a$, is more familiar to most people and therefore doesn't look paradoxical. I claim that the situation in the question is quite analogous and should not be considered paradoxical either.

share|cite|improve this answer
Well, $a,a,a,\ldots$ could be randomly chosen. The problem with random things is that you never know! :-) Also and – Asaf Karagila Jun 6 '13 at 16:41

The answers already given amount to, "With probability 1, a probability-zero event will happen when you do something randomly." This is absolutely correct, but let me give a slightly different take on the OP's argument that is more specifically about well-orderings.

Let's simplify matters, and just do the following: select $\alpha,\beta\in\omega_1$ randomly. What is the probability that $\alpha<\beta$ (in the usual ordering on $\omega_1$)? Naive arguments show that the probability is 1. But by those same arguments, the probability that $\beta<\alpha$ is 1.

In the reals context, the paradox is: if I select a real $r=\langle s_0, s_1\rangle$, what is the probability that $r\in X$, where $$ X=\lbrace u=\langle v_0, v_1\rangle: f^{-1}(v_0) < f^{-1}(v_1)\rbrace,$$ and in turn $$ f: \omega_1\rightarrow\mathbb{R} $$ is a bijection? (Note that this argument is really about well-orderings, and not just about the inevitability of probability-zero events.)

This is just Freiling's argument against $CH$ (see This argument was discussed on MO here: Axiom of Symmetry, aka Freiling's argument against CH. Briefly, the reason it isn't generally found convincing as an argument against $CH$ is that it tacitly assumes that the reals are well-orderable if and only if they are well-orderable in a measurable way. So if you believe that there are non-measurable sets, this argument really shouldn't be very convincing.

(On the other hand, if you find this argument intuitively appealing, maybe $L(\mathbb{R})$ is right for you!)

share|cite|improve this answer

For simplicity let us drop the condition that $a_{n+1}>a_n$. It just means that we exclude a countable set in every step, that should not be very interesting. We can still consider the supremum of a sequence with respect to the well-order and ask whether it is a given countable ordinal $c$. This event has probability zero, since it is contained in the set of all sequences where the first value is contained in a certain countable set. This set is contained the countable union of sets of the form $\left\{a\right\}\times [0,1]^{\mathbb{N}}$, which have measure zero. QED. You simply constructed many different sets of probability zero containing sequences with infinitely many different values (but you enforce that the values are contained in a certain countable set, and there are many countable subsets of the reals). I do not think that this is very astonishing.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.