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?

Solution 1:

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$.

Solution 2:

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.

One last remark about choice:
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.