# Without axiom of choice, why can't we choose a random element for each set in an infinite collection of sets

If we have an infinite collection of sets, where each set contains two elements, 0 and 1, without using axioms of choice, we can define a choice function that will always pick the element 0 from each set. However, it seems that if we only assume the set contains two elements, without specifying them in detail, we can not show the existence of a choice function without using the axiom of choice.

Since all the sets has a cardinality of two, we can define bijections between the two elements in each set and {0,1}. So regardless of how the bijection is defined, we can always choose the element that maps to 0.

I don't understand the difference between this operation compares to always choosing 0 in each set, but one requires the axiom of choice, while the other doesn't.

I have read many answers on stack exchange about axioms of choice. Like this one. And I saw answers that used the word "uniform" selection. I'm really confused about what "uniform" means in this case, and no questions seem to answer my confusion.

EDIT: The comment section is getting too long. So I posted a new question.

• " define a bijection between each set in the collection and {0,1}" requires the axiom of choice. Commented Oct 10, 2022 at 23:16
• @AnneBauval Thank you. That’s a typo. I’ve fixed it. Clearly the bijection between all the set in the collection and {0,1} does not exist. Commented Oct 10, 2022 at 23:22
• You can find the bijection for any one set, but you can't necessarily find a set of bijections that work for all sets. There are two bijections for any one set, so you are are now just trying to pick one element from each of those $2$-element sets of bijections. Commented Oct 10, 2022 at 23:24
• That was much worse than a typo, and cannot be fixed. Simultaneously "define a bijection between the two elements in each set and {0,1}" requires the axiom of choice. Commented Oct 10, 2022 at 23:25
• In any event, there is nothing in ZF without choice which lets you prove such a choice exists. "Simultaneously" is not a word in formal set theory. There are a lot of things you might want to say in formal systems that you can't say in those systems. The axioms of set theory is designed to allow you to say those things. While we can sometimes do stuff that remotely resembles "simultaneously" doing something, the axiom of choice is the rule that let's us do that in a lot of contexts. The axiom of choice is the codification of your intuitive notion of "simultaneously" making a decision. Commented Oct 11, 2022 at 0:24

Since all the sets has a cardinality of two, we can define bijections between the two elements in each set and {0,1}.

This actually does not help at all, although it's a little subtle to see why: it's true that for each such set, such a bijection exists, but in order to write down a choice function you need to choose a collection of such bijections for each set simultaneously. This means you need a choice function for the collection of bijections! And there are two for each set! So you're in exactly as bad a position as you were before.

To say this more explicitly, suppose $$I$$ is an index set and $$X_i, i \in I$$ is a collection of $$2$$-element sets indexed by $$I$$. You are saying: well, since by hypothesis each $$X_i$$ has cardinality $$2$$, for each $$i$$ there exists a bijection $$X_i \cong \{ 0, 1 \}$$. And yes, that's true. But to write down the choice function you want using these bijections, you need to choose one such bijection for each $$i \in I$$, and there are two. In other words, you need a choice function for the collection of sets $$Y_i = \text{Iso}(X_i, \{ 0, 1 \})$$, each of which also has two elements!

Coming at this from another direction, here is a more-or-less explicit example of a collection of sets of cardinality two where I challenge you to write down an actual choice function: consider the collection of all fields of characteristic $$\neq 2$$ in which $$-1$$ has a square root (if you want to cut this down to a set then take isomorphism classes and place some restriction on the cardinality). There are always exactly two such square roots, one of which is the negative of the other, which in the complex numbers are $$i$$ and $$-i$$. Can you tell me how to choose, for each such field, one of the two square roots of $$-1$$? Note that there are "surprising" examples of such fields, such as the field of $$p$$-adic numbers $$\mathbb{Q}_p$$ for $$p \equiv 1 \bmod 4$$ a prime.

Another example in a similar vein: consider the collection of all connected orientable manifolds. Any such manifold has exactly two orientations, one of which is the negative of the other. Can you tell me how to choose, for each such manifold, one of its two orientations?

• I understand this case now. Previously, I was also thinking about doing existential instantiation for each individual set, can you elaborate on why that doesn’t work as well on an infinite set but does work in finite cases? So I think a choice function has to be constructively in some sense, but is there a general way for us to determine what is a constructive choice? Commented Oct 11, 2022 at 1:49
• Btw, I forgot to add, in the case of the finite axiom of choice, which can be deduced from ZF, the choice function doesn’t have to be chosen constructively. Commented Oct 11, 2022 at 2:56
• @wsz_fantasy: existential instantiation only lets you make one choice at a time, so you can only use it to make finitely many choices (since a proof has finite length). The rest of the ZF axioms, without choice, simply do not let you make infinitely many choices arbitrarily. It takes a little familiarity with what the ZF axioms do and don't let you do to see what kinds of choice functions you can write down; basically they have to be "explicit" or "constructive" or "computable" in some sense. Commented Oct 11, 2022 at 3:54
• I see. I found this (link)[math.stackexchange.com/questions/2687765/… which mentioned the term “finitary rule”, see the paragraph before the last paragraph. Does that mean with the ZF axioms, we can not prove the existence of such a choice function, like the function mentioned in this question and linked post? Nonetheless, are they still by definition choice functions, where we just don’t know whether they exist or not by ZF? Commented Oct 11, 2022 at 4:11
• @wsz_fantasy This is a bit misleading, because the proof of "finite choice" does not actually proceed by doing some requisite finite number of existential instantiations. Rather, it is proven by induction on the size of the finite set, so just invokes existential instantiation once when arguing the induction step (and perhaps once for the base case, depending on how exactly you formulate things). The former approach doesn't actually make any sense when you try to do it in detail... one way to think about it is there's no guarantee a finite set in a model is actually (externally) finite. Commented Oct 11, 2022 at 4:16