A lot of proofs start like this

'Let x be some member of the set S, then...'

(If S are the natural numbers, this is especially common)

Do all of those proofs essentially require axiom of choice? Or is it possible to talk about an element of a set without being able to 'pick' it?


The issue with the Axiom of Choice is that "choosing elements" is no different than stating there exists "some function" that chooses for you. Let's show the Axiom of Choice in use and not in use.

"$2^\mathbb{N}=\prod_{\mathbb{N}}\{0,1\}=\{0,1\}\times\{0,1\}\times\cdots$ is non-empty."

Well, $(0,0,0,0,\ldots)$ (that is, assign $0$ to each spot in the vector) is an infinitely long vector that is in the set. Thus, $2^\mathbb{N}$ is non-empty. This proof did not use the Axiom of Choice, simply because I told you the element to pick. The Axiom of Choice is used when you don't know what element to pick.

"Let $A_i$ for $i\in\mathbb{N}$ be a collection of non-empty sets, then $\prod_\mathbb{N} A_i$ is a non-empty set."

Well, I would like to say that $(a_0,a_1,a_2,\ldots)$ is a vector in the set, where $a_i\in A_i$. But stating that such a vector exists is the same as assuming that there is a function that assigns each $A_i$ to the element $a_i$. That is, if $v=(a_0,a_1,a_2,\ldots)$ really does exist then $$f:\{A_0,A_1,\ldots\}\to \{\text{all the elements in }A_i's\}$$ by $$f(A_i)=\text{the }i\text{th entry in vector }v,$$ is a function that must also exist.

And there is the Axiom of Choice being used. There is no reason to assume that such a function exists (or that such a vector exists). If you can't explicitly define the assigning function, then how do you know it exists? The Axiom of Choice is the assumption that there always exists a function that can assign a collection of sets to it's own elements.

We see the Axiom of Choice in even more subtle ways. For example suppose you had a proof like:

"Let $\Omega$ be an arbitrary set. Let $A$ be an infinitely countable subset of $\Omega$ ..."

But wait, if $A$ is infinitely countable then by definition $A$ is subscriptable by the natural numbers like so, $A=\{a_0,a_1,a_2,\ldots\}$ that means there is some function $f:\mathbb{N}\to \Omega$ exists and that $f(\mathbb{N})=A$. How do I know that such a function exists? I can certainly pick an element of $\Omega$ (at random) and assign it to one, I can then pick another element from $\Omega$ and assign it to two. But how do I pick an infinite number of elements and assign them to the Natural Numbers. I can't tell you how to do it, I have to assume that it is possible by The Axiom of Choice. The Axiom of Choice gives us that $\prod_\mathbb{N} \Omega$ is a non-empty set.

Notice the subtlety of the above discuss. Simply picking an infinitely countable subset from an arbitrary set requires the Axiom of Choice. Or for that matter, simply subscripting a set could be using the Axiom of Choice, after all subscripting is another way of assuming that a choice function exists. The Axiom of Choice is abused extensively when dealing with sub-scripting stuff like sequences.

In general, the Axiom of Choice comes into play when you are dealing with arbitrary sets. If you know anything about the sets, then you don't need the Axiom of Choice. For example, "$\cup_{n\in\mathbb{N}} \{0+\frac{1}{n},1+\frac{1}{n},\ldots\}$ is countable" can be proven without the Axiom of Choice, since I can explicitly define the function that shows this is countable. However, "The countable union of countable sets is countable" is not provable without the Axiom of Choice, since we are dealing with arbitrary sets.

The worst thing about the Axiom of Choice is that you can very well assume that it is not true and you won't contradict the other Axioms of ZF. Thus there really is no reason not to assume that there are arbitrary products of non-empty sets that are empty. :-(

Sorry for the long discussion.

| cite | improve this answer | |
  • $\begingroup$ Right, so as long as we know the set is non-empty, we can pick an element. In the cases where we can't pick one, we simply don't know if the set has any elements (even though it seems very likely it does..) $\endgroup$ – Thomas Ahle Jun 5 '13 at 21:42
  • 1
    $\begingroup$ Yes, "picking an element" from a non-empty set requires no axiom. It is more like a built in definition. If $A$ is a non-empty set, then by definition there is an object, which we will denote by $x$, such that the sentence $x\in A$ makes sense. No axiom needed. $\endgroup$ – Bobby Ocean Jun 5 '13 at 21:46
  • $\begingroup$ Do I need aoc to prove that a family of sets where none of them are a subset of each other, has a maximum element? (I'm just trying to see exactly where the distinction goes) $\endgroup$ – Thomas Ahle Jun 6 '13 at 10:47
  • $\begingroup$ Not sure exactly what you mean. The AOC is needed when you don't define a rule for picking an element from each set in a family of sets. For example, if $\Omega$ is a family of sets where each set is a subset of the natural numbers, then I could say "pick the smallest element in each set", no AOC needed; I gave you the rule. But if $\Omega$ is just some arbitrary family of sets and I say "pick an element from each set", then I have implied the existence of a 'picking function' without telling you what the picking function is; this uses the AOC. $\endgroup$ – Bobby Ocean Jun 6 '13 at 18:51

The axiom of finite choice is a theorem of ZF. All you need to be able to pick an element of $S$ is to know that $S$ is non-empty. The axiom of choice is about making infinitely many choices.

| cite | improve this answer | |

This is essentially just a rule of (classical) logic.

If $\phi (x)$ is a formula (with free variable $x$), such that $( \exists x ) ( \phi ( x ) )$ is true, then by existential instantiation picking some symbol $y$ not used in the proof already assert that $\phi (y)$ holds. In the case in question, if $A$ is a nonempty set, then the formula $( \exists x ) ( x \in A )$ is true, and by picking an appropriate symbol $y$ we may assert $x \in A$ (in other words, we pick some $y \in A$).

As Qiaochu mentions in his answer, the Axiom of Choice is for those cases where infinitely many choices are made at once. Even more, it is for those cases where infinitely many choices are made at one without any rule present to uniformly make these choices. For instance, if $\{ A_i : i \in \}$ is a family of finite nonempty subsets of $\mathbb{R}$, then choosing $y_i = \min ( A_i )$ for all $i \in I$ does not require the Axiom of Choice, since each $A_i$ must have a least element.

| cite | improve this answer | |

Actually, no choice is needed at all – not even finite choice. You can read such sentences as, ‘Assume $x$ is a member of $S$ ...’. More formally, what you are doing is introducing a variable, and you can always do that.

The issue with choice is not so much a question of finiteness as it is a problem with rearranging quantifiers. (The axiom of choice is a formula of the form $\forall \exists \to \exists \forall$.) Here's what a naïve “proof” of the axiom of choice might look like:

  1. Suppose, for all $x$ in $S$, there exists a member of $T (x)$.
  2. Let $x$ be a member of $S$.
  3. Let $y (x)$ be a member of $T (x)$.
  4. Then $y$ is a function such that $y(x) \in T (x)$ for all $x$ in $S$.

This is not a valid proof. Let's take a closer look at the variables in play at each step, in the formalism of (dependent) type theory:

  1. No variables.
  2. $x$ is a variable of type $S$.
  3. $x$ is a variable of type $S$, $y (x)$ is a variable of type $T (x)$.
  4. Not well-formed.

A more generous reading of the above would say that, in step 4, we tried to apply $\lambda$-abstraction to the expression $y (x)$; but the only legal $\lambda$-abstraction at that step eliminates the variable $y (x)$ to produce the function $t \mapsto t$. (We can't eliminate the variable $x$ because the type of the variable $y (x)$, namely $T (x)$, depends on $x$.) Even if we could eliminate the variable $x$, the resulting expression would still depend on $y (x)$ – not really what was intended!

| cite | improve this answer | |

As far as I know, saying "Let $x \in S$" does not involve any choice at all. You only need choice when you say "Choose $x \in S$".

| cite | improve this answer | |
  • 2
    $\begingroup$ So when I say "Choose $x\in\Bbb R$ such that $x\notin\Bbb Q$" I am using the axiom of choice? $\endgroup$ – Asaf Karagila Jun 5 '13 at 19:48
  • 1
    $\begingroup$ As part of a formal system, the words you use when describing the action should have no bearing whatsoever in whether you are appealing to the Axiom of Choice or not. (Otherwise we could presumably go to the opposite extreme of @Asaf's comment and proclaim that saying "Let $B$ be a Hamel basis for $\mathbb{R}$ as a vector space over $\mathbb{Q}$" does not require the Axiom of Choice, but by "choosing" instead we must appeal to the Axiom.) $\endgroup$ – user642796 Jun 5 '13 at 20:08
  • $\begingroup$ @Arthur: But first we need to prove that the set $\{A\mid A\text{ is a Hamel basis for }\Bbb R\text{ over }\Bbb Q\}$ is non-empty, and for that we do need the axiom of choice. Of course, you already know that, but this is the subtlety of where we use the axiom of choice: we use it to prove a certain set is non-empty, and not to choose a particular element from it. $\endgroup$ – Asaf Karagila Jun 5 '13 at 20:11
  • $\begingroup$ @AsafKaragila Doesn't "Choose $x \in \mathbb{R}$ such that $x \notin \mathbb{Q}$ require axiom of finite choice as Qiaochu said? $\endgroup$ – user81123 Jun 5 '13 at 20:21
  • 1
    $\begingroup$ @ArthurFischer Well, when I say "Choose $x \in S$", I'll need $S$ to be nonempty, but when I say "Let $x \in S$", it doesn't matter if $S$ is empty or not. $\endgroup$ – user81123 Jun 5 '13 at 20:23

Not the answer you're looking for? Browse other questions tagged or ask your own question.