# Does this construction rely on the axiom of choice?

Let $$X = \{0,1\}$$. We define $$f: \mathbb Z_+ \rightarrow X^\omega$$ as $$f(n) = (\underbrace{0,...0}_{n-1},1,0...)$$ According to my understanding of the choice axiom, $$f$$ shouldn't rely on it. Let us now define another very similar construction. Let $$A = \{\{x_i\}\}_{i \in \mathbb Z_+}$$ be an indexed family, where $$x_i = (\underbrace{0,...,0}_{i-1},1,0...) \in X^\omega$$. Now there exists ($$A$$ is a collection of nonempty sets) a choice function $$c: A \rightarrow \bigcup_{i \in \mathbb Z_+} \{x_i\}$$ where $$c(\{\{x_i\}\}) = x_i, \forall i \in \mathbb Z_+$$. If we now define $$g: \mathbb Z_+ \rightarrow A$$ such that $$g(i) = \{\{x_i\}\}, \forall i \in \mathbb Z_+$$ does $$g \circ c$$ rely on the axiom of choice? Clearly $$g \circ c$$ and $$f$$ are almost the same, but I'm not sure if defining $$A$$ or $$g$$ constitutes as making an arbitrary amount of choices. Note I am just learning to use the axiom of choice so my intuition isn't quite there yet, hence the question.

• No, they don't need choice because you have a distinguished $x_i$ for every $i$. – user10354138 Jun 3 '19 at 5:24
• Ah of course, $x_i$ is not arbitrary. Thanks! – hampster Jun 3 '19 at 5:37
• No need to use axiom choice if you have an indexed the set. The set is already well-ordered by indices. You know, well-ordering implies AC. – Ma Joad Jun 3 '19 at 6:48
• @Jethro: That seems to be a misunderstanding. Without choice it is perfectly possible to have an $\mathbb N$-indexed sequence of nonempty sets such that the sequence has no choice function. – hmakholm left over Monica Jun 3 '19 at 11:08
• @HenningMakholm What you say is true, but the sequence of sets in the question is special: every element in the sequence is a singleton set. I forget to mention it. The index of singleton sets defines a well-ordering on their union. – Ma Joad Jun 3 '19 at 11:34

When you are dealing with singletons there is no room for arbitrary choices. Therefore the axiom of choice is not necessary.

If we have a set of singletons $$A$$, we can easily describe a choice function: $$F(\{a\})=a$$. In other words, if $$u$$ is in $$A$$, then we know that there is a unique $$a$$ such that $$u=\{a\}$$, therefore map $$u$$ to this unique $$a$$.

Now, since you wrote $$A$$ already as the image of a function $$g(i)=\{\{x_i\}\}$$, there was really no involvement of the axiom of choice.

A modicum of intuition about choice.

The axiom of choice is needed when you do not have a uniform way to specify elements from your set. That means that you cannot identify some property that exactly one element from each set will satisfy.

When we say property, we allow it to depend on parameters, or be very complicated such as "if the set is finite and has $$3$$ elements, choose this and that; if the set has infinitely many elements ...", it just needs to provably select a single member from each member of the family.

One example of a "complicated property" can be given when the family is finite. Then we can prove by induction on the size of the family that there is a choice function. This means that we can instantiate a choice function, and define the property as being the chosen element.

But to your case here, where we're only dealing with sets that have exactly one element, then it's easy to uniformly define a single element from each singleton. Well, it's that element.

Another example is if we are given a set with three elements, $$\{a,b,(a,b)\}$$ (where $$(a,b)$$ is the ordered pair $$a,b$$), then I can either choose the ordered pair, or I can choose the left one, or I can choose the right one. Or I can mix them.

• Thank you for the brilliant clarification! This helped me understand the concept much more. – hampster Jun 3 '19 at 9:32
• You're very welcome! – Asaf Karagila Jun 3 '19 at 9:35
• All this is right, of course, but I fear that "a complicated property can be given when the family is finite" is in danger of being misunderstood by the uninitiated. It would be easy to think it means something like that we can, in-universe, construct a finite formula that explicitly picks out our chosen elements one by one, and then feed that formula into the replacement axiom. (Which is, of course, nonsense). – hmakholm left over Monica Jun 3 '19 at 11:18
• @Henning: Quite indeed. I think that as a general rule of thumb, it is good to think about the false argument with "explicit formulas" (i.e., meta-finiteness) for intuition. And this is all that I am trying to give out here. – Asaf Karagila Jun 3 '19 at 12:44
• To the proposer. For each $n\in \Bbb Z_+$ there is a $unique$ $f(n)$ (as defined by you), demonstrable without AC, so by the axioms of Comprehension & Replacement there exists $\{(n,f(n)):n\in \Bbb Z_+\}$ which is the (graph of) the desired function $f$, without using AC. – DanielWainfleet Jun 6 '19 at 10:07