Proof that $(a,b)\subset\mathbb{R}$ is not countable. Does it use Axiom of Choice?

Question

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?

Answer 1

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!

Answer 2

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.