19
$\begingroup$

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?

  • 0
    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.2011-03-19
  • 0
    @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.2011-03-19
  • 0
    @joriki: Well indeed, seems like I was somehow expecting a proof by contradiction even though it isn't. Thanks for enlightening me!2011-03-19
  • 6
    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.2011-03-19

3 Answers 3

6

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

  • 0
    Don't you need the axiom of choice to show that there is a smallest nonzero amount of general topology? ;-)2011-03-21
23

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

8

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

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

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.

  • 0
    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!2011-03-19
  • 0
    @james: That would be awesome.2011-03-19
  • 1
    @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 http://en.wikipedia.org/wiki/Axiom_of_Choice#Usage.2011-03-19
  • 0
    @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.2011-03-19
  • 0
    @joriki: Firstly for the second comment to avoid complications in choice of $\alpha$ one can directly attend to the supremum divided by 2, it is very easy to show that this is a fitting number. As for the choice of rationals, the axiom of choice is a messy beast when not handled with care. It is true that choosing **a** rational from **an** interval does not require the axiom of choice, however I'm not sure if this trick would carry over smoothly. It might, but it might also not work. To give some example of how this can be problematic (cont...)2011-03-19
  • 0
    @joriki: (cont.) consider the usual construction of an Aronszajn tree on $\omega_1$. In this process we take bounded functions from countable ordinals into the rationals, and we do it in such way which gives us an Aronszajn tree. If one could always choose rationals, this construction would carry over without the axiom of choice but in fact not even Dependent Choice (which is strictly weaker) is enough to allow such construction. So it might be that the trick of fixing an enumeration will work here, but generally it is a very delicate issue that requires extra care and verifications.2011-03-19
  • 0
    @Asaf: My choice function is quite explicit here. I don't see your problem.2011-03-19
  • 0
    @TonyK: My problem is that this explicit function seems to me as though it carries over to ZF without AC, which would mean Aronszajn trees can be constructed in any model of ZF, and that is simply not true.2011-03-19
  • 0
    @Asaf: I'm reading up on Aronszajn trees, but in the meantime: This is quite a complicated argument for a comparatively simple issue. Are you saying that in some cases specifying infinitely many elements by specifying a well-defined property which in each case only one particular element has requires an axiom of choice?2011-03-19
  • 0
    TonyK's argument does not require choice; it is similar to the usual "shoes vs. socks" dichotomy. When we have a distinguished element in each set we are choosing from, no choice is needed.2011-03-19
  • 0
    @Asaf: I think I've now understood the construction of an Aronszajn tree described here: http://www.maa.org/devlin/devlin_01_06.html. Is this what you're referring to? If so, I don't think there's any contradiction with @TonyK's argument. There's a step in that construction where you "pick some strictly increasing sequence (m_i : i a natural number) of ordinals less than m". That's more than just picking individual (well-ordered) ordinals. It's not obvious to me that the set of such sequences can be well-ordered; in fact my intuition would be that it can't (without choice).2011-03-19
  • 0
    @joriki: I did not say TonyK's function is wrong, and it is very likely that in the case of Aronszajn trees things are complicated and the usage of choice is hidden somewhere else. Much like how $\bigcup^\infty \mathbb{N}$ need not be countable without AC, I'm saying that the fact we choose *simultaneously* for infinitely many numbers then we **might** be using some choice without noticing.2011-03-19
  • 4
    But Asaf, there's nothing to choose! Pick the first rational in the list.2011-03-19
  • 0
    @Asaf: You say "we choose *simultaneously* for infinitely many numbers". But the point @TonyK and I are making is that we're not choosing at all, neither finitely nor infinitely many times. We're just specifying well-defined unique elements by well-defined properties. By $\bigcup^\infty\mathbb{N}$, do you mean the countable union of "disjoint copies" of $\mathbb{N}$? As it stands, it would just be $\mathbb{N}$, which is obviously countable.2011-03-19
  • 0
    @Asaf: If by $\bigcup^\infty\mathbb{N}$ you mean a countable union of countable sets, the reason why we need choice to show that this union is countable is because we have to choose an infinite number of enumerations, and there might not be any property to pick out a particular enumeration for each copy. That's not related to the present case, since we can fix one enumeration of the rationals once and for all.2011-03-19
  • 0
    @joriki: Of course I mean disjoint copies of $\mathbb{N}$ :-) and once again: I did not claim TonyK's argument was false or badly stated or even required any fixing. I simply stated that unless a detailed proof (or at least pointing to enough theorems I know already in an orderly fashion) is shown - I tend not to trust such construction. This is just me here. I did not have time to sit and verify with myself the proof in question, hopefully later today I will be able to do it. Until then, I remain in my doubts.2011-03-19
  • 0
    @Asaf: I'm not so much interested in whether @TonyK's particular argument is correct (that too) but much more interested in whether my understanding of choice is fundamentally flawed. Quite apart from this particular case, you seem to be saying that specifying unique elements may sometimes require choice. If so, @TonyK, @Steve and I disagree, and we can sort that out independent of this specific argument. If that's not what you're saying, does that mean your doubts arise because you're not sure whether we really are specifying unique elements by well-defined properties in this case?2011-03-19
  • 0
    @Asaf: Concerning the countable union of disjoint copies of $\mathbb{N}$: I don't see how that can fail to be countable. Why can't we enumerate them like this: 1;2,1';3,2',1'';4,3',2'',1''',...? This is different from the case of a countable union of countable sets, where we might not be given a particular enumeration of each of them.2011-03-19
  • 0
    @joriki: I agree that when you can specify a unique element by a uniform formula in all your sets (if you have $I$ your collection of sets and $\varphi(x,i)$ defines a certain element in $a_i$ for all $i\in I$ (e.g. identity element in a group) then this is fine. I'm having doubts about TonyK's specific argument and how it carries over. The question is whether or not a property (or this one, in this case) can be defined uniformly or not.2011-03-19
  • 0
    @Asaf: I'm not sure I fully understand what you mean by "uniformly". If you mean "the same property for all sets you're picking from, without any aspects of the property that would have to be chosen per set", then I don't see what in TonyK's case could prevent the property from being uniform in this sense. To be specific, fix an enumeration $e:\mathbb{N}\rightarrow\mathbb{Q}$ of the rationals, and use the property $\phi(x,i)=x\in\mathbb{Q}\land(\nexists m,n,y\;\;m\in\mathbb{N}\land n\in\mathbb{N}\land y\in i\land e(m)=x\land e(n)=y\land n < m)$.2011-03-19
  • 0
    Asaf, there is nothing difficult in my assertion. I gave you an explicit choice function, so you don't need the Axiom of Choice to provide you with one. That is really simple.2011-03-19
  • 0
    @jorki: Uniformly means that there is one formula that up to a parameter change defines everything you want it to define.2011-03-19
  • 0
    @TonyK: Yes, I thought about it while doing my laundry and came to see the truth in your argument. I will edit my answer to correct my mistakes.2011-03-19
  • 0
    @joriki: Isn't it fun that in just two years I have learned so much about the axiom of choice? I like this thread because it shows me how much I went through! :-)2013-01-08