|
|
|
|
|
|
by DominikPeters
3964 days ago
|
|
|
Careful, the axiom of choice doesn't state that non-empty sets contain an element (this is a triviality). Rather (an equivalent of) it states that the Cartesian product of non-empty sets is non-empty. If we take a product of finitely many such sets, then we can prove it, but we need the axiom of choice for the infinite case. The reason is intuitively clear: in order to prove that the infinite product is non-empty, we need to produce an infinitely long vector. Well, since the individual sets are non-empty, we can just for each set choose an element and put it in the vector. But this takes infinitely many steps! and that's not allowed in mathematics. The axiom of choice is a way of collapsing infinitely many steps into 1 invocation of the axiom (so 1 step, so finitely many steps). Not too much to do with excluded middle. |
|
|
But you are right, the devil is in the details, so let me spell it out precisely:
The axiom states that for every set X, there is a function
If you want to restrict yourself to first-order logic, then you have to encode the function \epsilon (e.g. as a functional relation, where relations are in turn encoded as sets of ordered pairs, which are in turn encoded with Kuratowsky's construction). Set theorists like first-order logic and this encoding overhead is the reason why it's not the standard definition, even though it's arguably what the axiom is trying to express(1,2). Apart from that the statements are (classically) equivalent:To go from the higher-order version to the cartesian product, note that the cartesian product of an I-indexed family of sets is a set of functions f from I to the union of all X_i's, such that f(i) \in X_i for all i. Let (X_i)_{i\in I} be an I-indexed family of sets, all of which are non-empty, then (i -> \epsilon(X_i)) is in the cartesian product of the X_i's, where we use \epsilon for the union of all X_i's. The reason we couldn't build that element without AC is precisely that we have no way of selecting exacly one element from each X_i, even though we know that they are non-empty.
In the other direction we can use Zermelo's well-ordering theorem to construct a well-order on X. We define \epsilon to pick out the minimum with respect to this order.
(1) This really is what the axiom of choice was meant to express. If you can read German, you can refer to Zermelo's own work:
Under point 2 in this paper, Zermelo assumes that there is such a choice function on a given set and from this he derives the well-ordering of that set.(2) Another example of the drawbacks of working with a first-order axiomatization is the axiom of regularity. The idea we want to express is that there are no infinitely descending element chains ("every set is well-founded"), but expressing this in first-order logic leads to a convoluted statement which obscures the simple idea... and is also not a correct encoding of this idea in intuitionistic logic!