Question: Given the real numbers as a set, does it require the (non-finite) Axiom of Choice to pick out an arbitrary single element? What about if we wanted to pick out an integer? What about if we wanted to pick out "0"?

Motivation: Those who have seen some of my previous questions here know that I am terrible at picking out when and where to apply the axiom of choice, and when it is being used in a proof. Perhaps slightly motivated by the Bertrand Russell quote

"The Axiom of Choice is necessary to select a set from an infinite number of socks, but not an infinite number of shoes."

and perhaps slightly motivated by an argument I had over the AoC, I wanted to find out how much it is actually being used. The above question is as basic a question as I can think of to test a "lower bound" on the axiom of choice.

  • $\begingroup$ I have also looked at math.stackexchange.com/questions/15668/axiom-of-choice-examples which states the same quote that I do, but I'm unsure of if I am generalizing the argument correctly: in the case of shoes, we can define a function (always picking the left) from each set. In the reals, unless we distinguish an element, there doesn't seem to be a rule we could use to make our choice purely arbitrary. Same for a random integer. For 0, or for any number, there is clearly a choice function (pick that number). I'm unsure if I am stating these correctly, though. $\endgroup$ – user2959 Mar 27 '11 at 22:44
  • $\begingroup$ There's a difference between the probability notion of "random integer" and "select an integer". In probability, to have "random integer" you would need some probability distribution over the integers that makes every integer "equally likely", but that is impossible (each integer would need to have probability zero of being chosen, but selections being independent would make the probability of choosing any integer equal to $0$ as well by $\sigma$-additivity). But this is a probability obstacle, not a set-theoretic one. $\endgroup$ – Arturo Magidin Mar 27 '11 at 22:50
  • $\begingroup$ @james: Note that one does not need AC to show that an arbitrary power of a nonempty set is nonempty (that is, that $X^I$ is nonempty for $X\neq\emptyset$). This regardless of what $X$ is, so long as it is nonempty. $\endgroup$ – Arturo Magidin Mar 27 '11 at 23:23
  • $\begingroup$ Thank you for pointing out the notion of random verses select --- this was not something I had actually thought about. I feel silly asking this, but what do you mean by the power of a nonempty set? $\endgroup$ – user2959 Mar 28 '11 at 1:21
  • $\begingroup$ @james: What I wrote in parenthesis. A "power" of a set $X$ is a product of $X$ with itself. $\endgroup$ – Arturo Magidin Mar 28 '11 at 1:23

Given a finite number of nonempty sets $A_1,\ldots,A_k$, the Axiom of Choice is not needed to show that there are functions $f\colon\{1,\ldots,k\}\to\cup A_i$ such that $f(i)\in A_i$ for each $i$. That is, there is no need for the Axiom of Choice in order to select an element form finitely many nonempty sets.

In particular, you do not need the Axiom of Choice to show that you can choose a real number (a single set).

Simply: since $A_1$ is nonempty, there exists $a_1\in A_1$. Since $A_2$ is nonempty, there exists $a_2\in A_2$. Likewise, we have $a_i\in A_i$, $i=3,\ldots, k$. And we can let $f=\{(i,a_i)\mid i=1,\ldots,k\}$ be the Choice function. We can write all of this down because there are finitely many $A_i$. Apparently there are subtle non-standard-set-theory issues here (thanks to Carl Mummert for the pointer); so instead, let's say that for a family of nonempty sets indexed by a natural number you do not need the Axiom of Choice to get a choice function, and this can be shown by induction on the index set.

The specter of the Axiom of Choice (so to speak) does not even begin to suggest itself until you have to make infinitely many choices. Even then, you may not need it.

Note, however, that using phrases like "arbitrary real number" may make it seem like you are talking about some kind of uniform probability distribution over all the real numbers that makes all "selections" equally likely. This is a completely different thing altogether, but not what you are talking about here. This is likewise the problem that arises when, in the context of probability, we talk about "selecting a random integer." The problem with "selecting a random integer" is that you cannot have a uniform probability distribution on the integers: this would amount to a measure on the power set of the integers that is $\sigma$-additive, for which each integer has equal probability, and for which $\mu(\mathbb{Z})=1$; no such thing exists, because you would need to have $\mu(n)=0$ for each integer $n$, and $\sigma$-additivity would imply $\mu(\mathbb{Z}) = 0$ as well. This is what is behind the statement "you cannot 'choose a random integer'" true in that context; but this is an obstacle in the notion of "randomness", not a set-theoretic obstacle. Likewise, there can be no uniform probability distribution over all the reals, because uniformity would imply that each interval $[n,n+1)$ with $n\in\mathbb{Z}$ would have the same measure, and $\sigma$-additivity together with the fact that the reals have finite total measure implies that each interval must have measure equal to $0$, and so the reals would also have total measure $0$. Again, this is a probability/measure-theoretic obstacle, not an Axiom-of-Choice one.

  • $\begingroup$ Again, thank you --- I feel I was getting confused here, thinking that since every real number is "equally likely" to be chosen, there was some inherent probabilistic thing; of course, this is not the case and it was me pushing probabilistic intuition onto this set. The fact that the set is nonempty means "there exists" an element in the set; without loss of generality, then, we can make this whatever element we know to be in the reals. $\endgroup$ – user2959 Mar 28 '11 at 1:23
  • 1
    $\begingroup$ There is a subtle point in the proof. ZFC does prove the principle in the first sentence of the answer, which means that the principle holds even in nonstandard models where the $k$ is not actually metafinite. In that case the argument of the third paragraph cannot work because you cannot actually write down the specified set. So to prove this in ZFC you need to go by induction on $k$ instead. But the answer is morally correct: the axiom of choice isn't needed to "pick" an element of a nonempty set; that type of choice is just called "existential instantiation". $\endgroup$ – Carl Mummert Mar 28 '11 at 2:48
  • $\begingroup$ @Carl: I don't know what "metafinite" means, alas! But I'll fix the third paragraph. $\endgroup$ – Arturo Magidin Mar 28 '11 at 2:49
  • $\begingroup$ I just mean finite in the metatheory, that is, finite in the standard model rather than "finite" in some arbitrary model. $\endgroup$ – Carl Mummert Mar 28 '11 at 2:58
  • 1
    $\begingroup$ Yes, it's right now, and I voted it up. You just work by induction on $k$ and the argument goes through in ZFC. It's a subtle point that only comes up when you actually try to prove the principle within ZFC itself. $\endgroup$ – Carl Mummert Mar 28 '11 at 3:12

Your Answer

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