I have a vague understanding of the Axiom of Choice, but I've always had trouble with some of the analogies people use to explain it.
Two things that have bugged me for a while:
- why is it usually talked about only in the context of infinite sets? Is there a general trick to building a choice function if all you have are finite sets?
- There's a saying like "you can choose from an infinite set of shoes, but not from an infinite set of socks without AC". Why exactly?
The axiom of choice is about making an infinite number of arbitrary choices simultaneously. If you can specify some rule, this rule is just one choice. Finitely many choices are always fine and don't need the axiom of choice.
If you have a finite set, you can number its elements and make rules by saying "let's take the element with the smallest number having this or that property", so you don't need the axiom of choice when dealing with finite sets.
The point of Russell's shoes versus socks analogy is that shoes are distinguishable while socks aren't:
To choose one shoe from each of an infinite set of pairs of shoes, you can always choose the left shoe, or specify some pattern (so you don't need the axiom of choice), whereas when choosing socks, you have to make an arbitrary choice to select one from each pair (so you do need the axiom of choice).
The main problem is taking a statement about a set ("for every A in X, A is nonempty") to the existence of a set ("there is a function f [which in ZFC is considered to be a set] such that for all A in X, f(A) is in A").
If you are able to create a statement P(A,a) that for every A in X is true for exactly one a in A, then it follows from the axiom of replacement that there is such a choice function. The axiom of choice seems to say that it suffices to make a statement P(A,a) that for every A in X is true for at least one a in A.
The axiom of replacement helps actually construct such a choice function, whereas the axiom of choice just asserts one ought to exist since "at least one" seems good enough.
To use the axiom of replacement, you have to use some structure for A. For instance, with the finite set example, it might be that each A is not just a set, but a set which is in bijective correspondence with a natural number, where there is a distinguished bijection. Then, you could just say that P(A,a) is true exactly when a is the image of 0 under the bijection.
Two things that have bugged me for a while:
- why is it usually talked about only in the context of infinite sets? Is there a general trick to building a choice function if all you have are finite sets?
- There's a saying like "you can choose from an infinite set of shoes, but not from an infinite set of socks without AC". Why exactly?