# The Use of the Axiom of Choice in an Elementary Proof

I wanted to give some of the new undergrad analysis students the following problem: given the real numbers (with the standard topology, as they'd expect) one cannot have an uncountable set such that every point is an isolated point. A few of my fellow grad students attempted solutions first.

A sketch of a potential proof was given as follows: take each point and create as large a ball as is possible without it containing any other point of the set, so say $(a-\alpha, a+\alpha)$. Then construct corresponding balls with a smaller radius: $(a-\frac{\alpha}{2}, a+\frac{\alpha}{2})$. These new balls will intersect each other trivially. Then choose a rational point from each of these new balls. This set will be in one-to-one correspondence with the balls which are in one-to-one correspondence with the points of the original set.

After presenting this proof, it was argued that it requires the (non-finite) axiom of choice (as we are picking one point from a potentially uncountable set). We modified the proof by using the density of the rationals to pick rationals $p_{a},q_{a}$ such that $(a-p_{a},a+q_{a})\subseteq (a-\frac{\alpha}{2}, a+\frac{\alpha}{2})$, and then have our function pick the "left-most" end-point. It was still argued that this used the axiom of choice.

Because I am not entirely familiar with what constitutes use of the axiom of choice, I wanted to open the question up to all of you. Do these proofs require the (non-finite) axiom of choice? If so, is there a proof you know of which does not require it?

-
At first sight I think you would still have to argue why $\alpha>0$. For instance in the set $\{0,1,1/2,1/3,1/4,...\}$ for the point $0$ one would find that $\alpha=0$ and the open ball would be empty. If i'm right you might want to fix that first, and then think about the axiom of choice. You do use it indeed, not because you pick a number from a set that may be infinite but because you have to do this an infinite number of times: once for each ball. – Myself Mar 19 '11 at 8:34
@Myself: That's because that set has a non-isolated point, $0$. The idea of the proof (which wasn't stated explicitly) is to assume that all points are isolated and conclude that they are countable. – joriki Mar 19 '11 at 10:38
@joriki: Well indeed, seems like I was somehow expecting a proof by contradiction even though it isn't. Thanks for enlightening me! – Myself Mar 19 '11 at 10:43
You never need the axiom of choice to choose rational numbers. They can be explicitly well ordered, so just choose the minimum possible values wrt that order. – George Lowther Mar 19 '11 at 15:16

Firstly I should probably mention that when I took the introductory course in topology (point-set topology that is) the teacher told us and retold us that we rely heavily on the axiom of choice.

I also want to add that there is nothing wrong with the axiom of choice, it just simplifies infinitary processes to work as we want them to work. Someone told me once that a good set of axioms is such which you don't "feel" when you use them. Such is the axiom of choice. (I should say that my research interest is directed towards models which negate AC, but I don't see much point avoiding it outside this field).

The axiom of choice is in fact being used here, in both the accounts. As you choose a rational number arbitrarily close to your real number. (See edit notes below)

Here is an alternative proof which comes to mind: (problematic proof, see edit notes for details)
Suppose $A\subseteq\mathbb{R}$ is an uncountable set. By the pigeonhole principle there exists some $z\in\mathbb{Z}$ such that $A\cap [z,z+1]$ is uncountable. Without the loss of generality $z=0$. Now by induction prove that for every $n$ there exist some $m<n$ such that $A\cap [\frac{m}{n},\frac{m+1}{n}]$ is uncountable, and they form a decreasing chain of sets. Using Cantor's lemma (or simply by compactness) we have that the intersection is non-empty. Then it is easy to show that any point in the intersection of $A$ and all the intervals is non-isolated.

There are many versions of the axiom of choice, from "full blown" global choice (for proper classes, not just sets), to just being able to choose from infinitely many finite sets. When you say non-finite choice it means that you choose from infinitely many infinite sets. If you have a finite collection of non-empty sets you can always choose one from each set. As I said, the axiom of choice is the extension of this finitary process to the case where you have infinitely many sets in your collection.

Edit I:
After a lengthy discussion in the comments, in which I sort of made an ass out of myself I sat to verify with myself that this TonyK and joriki are very much correct and the original proof james gave does not use the axiom of choice.

In addition, I decided to expand the proof I gave a bit - as I skipped over some details and some of them are not 100% accurate (I tend to have a problem with the details).

I am referring, of course, to the closed intervals. After spending a few minutes correcting the inductive definition of the intervals, I came to realize a huge irony that it is only simple to prove that the point in the intersection is also in $A$ if one assumes the axiom of choice (or at least countable choice).

I spent twenty minutes or so thinking about it and came to the conclusion that the proof I gave, while true with the axiom of choice, is probably not as useful as I was hoping for it to be. Any insight on how to fix it is appreciated.

One more last remark about the axiom of choice:
Despite my double fail above, I do want to add one last bit of insight about choice that I mentioned in the later comments below - namely the uniformity of the choice.

Suppose $I$ is a collection of nonempty set. If there is some definable element in every $i\in I$ that is definable by the same formula then there is a choice function on $I$.

For example, if $I$ is a collection of groups we can always define the function to choose the identity element.

If one cannot formulate such property then things are trickier. As I wrote above - choosing out of finitely many sets is always possible, simply by $\bigwedge_{i<n}\exists x_i (x_i\in I)$ as a defining formula.

If there are infinitely many sets we cannot write $\bigwedge_{i\in I} \exists x_i(x_i\in I)$, as first order logic does not allow infinitary conjunctions.

If, however, we have a formula $\varphi(x,i)$ such that for every $j\in I$ there is only a single $y\in i$ such that $\varphi(y,j)$ holds then we can define our choice function.

Notice that these things are equivalent, if there is a choice function then one can fix that function and trivially create $\varphi$, and if $\varphi$ exists then it defines a choice function.

-
Thank you, this was especially enlightening! I suppose it just struck me that I never actually think about when I'm applying the AC, so it was a bit unsettling at first. Also, your proof is quite intuitive (and it even uses something they just covered!), so perhaps I will use that one to prove it! – james Mar 19 '11 at 8:55
@james: That would be awesome. – Asaf Karagila Mar 19 '11 at 9:08
@james @Asaf: I believe @TonyK is right that you don't need choice to pick a rational, since the rationals can be well-ordered. This is also a good point about the axiom of choice, so you might want to stick with your original proof and explain why it doesn't require choice. For more on TonyK's "trick", see en.wikipedia.org/wiki/Axiom_of_Choice#Usage. – joriki Mar 19 '11 at 10:45
@james: Also, although it's true that there's a greatest real $\alpha$ such that the ball contains no other points, to be rigorous you'd have to prove that; you can avoid that complication, too, by just picking the "least" (in some fixed enumeration) rational $\alpha$ with that property. – joriki Mar 19 '11 at 10:55
But Asaf, there's nothing to choose! Pick the first rational in the list. – TonyK Mar 19 '11 at 12:00

You don't need the Axiom of Choice here to pick a rational in each $(a-\frac{\alpha}{2}, a+\frac{\alpha}{2})$. You can fix an enumeration $(q_r)$ of the rationals and just pick the rational $q_i \in (a-\frac{\alpha}{2}, a+\frac{\alpha}{2})$ with the smallest index $i$.

-

As I mentioned recently in another answer, this problem comes down to two simple facts:

1) A subspace of a topological space admitting a countable base (i.e., a second countable space) again admits a countable base: just intersect every element of a countable base with the subspace.

2) A discrete space has a countable base if and only if it is countable.

In particular there is no choice going on here.

(I should note that the notion of "base for a topology" is more commonly encountered in a first topology course than an undergraduate real analysis course. I can see some merits to the more explicit approach given in the question. But for those who know the smallest (nonzero!) amount of general topology, this approach seems to me to be much cleaner and simpler.)

-
Don't you need the axiom of choice to show that there is a smallest nonzero amount of general topology? ;-) – joriki Mar 21 '11 at 5:44