I used this proof to show $(a,b)$ is uncountable, but looking at it, I don't really see if it uses AC or not. Until recently I was thinking it does use AC (In the choice of the $a_n,b_n$), now I think I'm mistaking about that, but can't see it clearly.

So this is how it goes: Let's suppose that $(a,b)$ is countable, so it's elements can be listed like this: $$(a,b)=\{r_1,r_2,...\}$$ Now choose $a_1,b_1$ reals such that $r_1\notin (a_1,b_1)$ and $(a_1,b_1)\subset (a,b)$.

Now choose $a_2,b_2$ reals such that $a_1<a_2<b_2<b_1$ and $r_2\notin (a_2,b_2)$. We repeat the process, such that being chosen $a_n,b_n$, we now choose $a_{n+1},b_{n+1}$ such that $a_n<a_{n+1}<b_{n+1}<b_n$ and $r_{n+1}\notin (a_{n+1},b_{n+1})$.

Let's now consider that $\{a_1,a_2,...,a_n,...\}$ is bounded above (by the $b_i$s) and so it posesses a supremum $r$, and we see that $r<b_{n}$ for all $n\in\mathbb{N}$. So $r\in (a_n,b_n)$ for all $n$, and as $r_n\notin (a_n,b_n)$ we get that for all $n$, $r\neq r_n$ that is, we got an element out of the list, and that is a contradiction.

Does it use AC (Or some weaker form)? Why?

  • $\begingroup$ At first glance, it seems to use the axiom of choice, though you can get away with the weaker form of the axiom of countable choice. (Since you are only making countably many choices, not arbitrary) $\endgroup$ – Alan Sep 2 '15 at 3:12
  • 2
    $\begingroup$ No, it does not necessarily use the axiom of choice. You can choose $a_i$ and $b_i$ to be rational, and thus you can use a well ordering of the rationals to avoid using the axiom choice in any form (not AC, not dependent choice, and not countable choice). I will wait a while to see whether Asaf wants to write this up as an answer. $\endgroup$ – Carl Mummert Sep 2 '15 at 3:25
  • $\begingroup$ Why not scale (a, b) to (0,1) and use the standard Cantor diagonal argument. That does not use the axiom of choice. $\endgroup$ – John Douma Sep 2 '15 at 3:33
  • 1
    $\begingroup$ It uses the axiom of coolness. $\endgroup$ – Forever Mozart Sep 2 '15 at 3:39
  • $\begingroup$ @John Douma I knew that, but I didn't want to use decimal expansions for some reasons (In the course we have not formally shown we can use them, for example). $\endgroup$ – David Molano Sep 2 '15 at 3:43

It looks like it requires countable choice, but you can certainly modify it so that it no longer requires choice.

Namely, define $a_1=r_1$ and $b_1=b$. Then, for each $n \in \mathbb{N}$, given $a_n,b_n$, there are two possibilities:

  • $r_{n+1} \le a_n$ or $r_{n+1} \ge b_n$. In this case, let $a_{n+1} = \frac{2a_n+b_n}{3}$ and $b_{n+1} = \frac{a_n+2b_n}{3}$; all this does is make the interval shorter.
  • $a_n < r_{n+1} < b_n$. In this case, let $a_{n+1}=r_{n+1}$ and $b_{n+1}=\frac{r_{n+1}+b_{n+1}}{2}$; this bumps the lower bound of the interval up to $r_{n+1}$ and ensures that the upper bound of the interval decreases.

You can check that your desired conditions hold at each stage, and so you reach your desired contradiction. Not only does this proof not require the axiom of choice, it's entirely constructive!

  • $\begingroup$ The key point here is that many proofs that seem to use the axiom of choice can be made more constructive to avoid it. But not always, of course. Usually nobody bothers because the axiom of choice is well accepted in modern mathematics, $\endgroup$ – Carl Mummert Sep 2 '15 at 3:36
  • $\begingroup$ Oh, that seems very beautiful. $\endgroup$ – David Molano Sep 2 '15 at 3:41
  • $\begingroup$ @Carl Mummert It's only accepted by some of modern mathematics. $\endgroup$ – user117644 Sep 2 '15 at 8:11
  • $\begingroup$ @mistermarko: It is accepted enough to be assumed implicitly in introductory courses in most places. While intuitionstic logics, or working in ZF is interesting, they usually require that you first understand "standard" mathematics. $\endgroup$ – Asaf Karagila Sep 2 '15 at 11:03
  • 1
    $\begingroup$ @mistermarko: no matter what the topic, it will only be accepted by some in modern mathematics :) Unlike, say, ultrafinitism, the axiom of choice is widely - in fact, nearly universally - accepted in the areas of modern mathematics where it is relevant. $\endgroup$ – Carl Mummert Sep 2 '15 at 11:25

The proof is presented in a way that supposedly use dependent choice, which is in fact stronger than countable choice.

However this can be avoided in one of several ways.

  1. As Clive suggested, using $(a,b)$ as a bootstrap, you can generate algorithmically smaller and smaller intervals.

  2. As Carl suggested, you can use the fact that the rational numbers are dense in $(a,b)$ and countable to fix an enumeration of the rationals, then use the first rational numbers in the enumeration that work.

  3. Or, you can just argue directly from the assumption by contradiction. We assumed the interval is countable and fixed an enumeration of it, now take $(a_{n+1},b_{n+1})$ to be the least indexed $r_i$ and $r_j$ such that $r_i<r_j$ and $r_n\notin(r_i,r_j)$. If you want, you can also require that the indices $i,j$ are always strictly increasing. Just to ensure that you get a non-repeating sequence.

Let me also add two points here. Most of the proofs of this form are presented to use the axiom of choice, since (as pointed by Carl under Clive's answer) the axiom is generally accepted in mathematics. But even if the proof can be modified, we will often not entirely bother to do it if the modification is minor. And while there are theorems with proofs that are entirely different without assuming choice, most of the time when the change is "avoid choice by using the countability of such and such" we're not going to fully bother with it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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