Can I construct a collection of pairs of socks?

Question

A standard example of something that cannot be done without the axiom of choice is choosing one sock from each pair of socks in an infinite collection of pairs of socks. In contrast, it is possible to do a similar thing for shoes with the axiom of replacement, using the functional relation $P(x,y)$ which evaluates to true iff x is a pair of shoes and y is the left shoe from this pair.

Is it possible to construct, in ZF, a collection of pairs whose elements are as indistinguishable as the elements of a pair of socks, so that the axiom of replacement won't help us choose one from each pair? I'm not sure how this would be done without the elements of the pairs actually being equal, which would make them no longer pairs. Any difference between the elements of a pair seems like it would be possible grounds for a functional relation that could circumvent the axiom of choice.

Answer 1

You can't construct such things in ZF (because the ZF world you work in could actually be a ZFC world) -- but they may (or may not) exist all the same.

I'm not sure how this would be done without the elements of the pairs actually being equal, which would make them no longer pairs. Any difference between the elements of a pair seems like it would be possible grounds for a functional relation that could circumvent the axiom of choice.

That is not actually a good intuition.

There are (supposing ZF is consistent) models of ZF in which there is a countable family of pairwise disjoint 2-element sets that has no choice function.

In such a model, if you view any single of the 2-element sets in isolation, you can perfectly well distinguish one of its elements from another. What prevents you from constructing a choice function using Replacement is that you need different properties for distinguishing elements of different pairs -- there is no single formula that is true for exactly one element of each of the pairs.

Answer 2

Let me add to Henning's excellent answer that it is consistent with $\sf ZF$ that every family of finite sets admits a choice function, in particular there are no Russell sets (i.e., sets which can be partitioned into pairs, and do not admit a choice function on any infinite family of these pairs).

In fact, this is consistent with even the failure of countable choice. Namely, it might be that we cannot choose from a countable family of non-empty sets; but we are still able to choose from a countable family of pairs.

So we cannot prove outright from $\sf ZF$ or even $\sf ZF+\lnot AC_\omega$, that such a family of pairs exist.

All that we can say is that due to the work of Cohen (and Fraenkel, Mostowski and Specker to some extent) we know that assuming that such a sequence of pairs exists will not add a contradiction to $\sf ZF$, unless such a contradiction already exists. This is worse, since there are no "natural failures of choice" which can prove the existence of such set, other than assuming it exists.