Is the following a restatement of the axiom of choice?

Given an arbitrary collection $A$ of non empty sets there exists a set $C$ which contains precisely one element from each element of $A$.

According to Munkres, given a collection $\mathbb{B}$ of non empty sets there exists a choice function so that $c(B) \in B$ for each $B \in \mathbb{B}$. So why can’t I define my set to be the set containing $c(B)$ for $B \in \mathbb{B}$?

  • 1
    $\begingroup$ I am 100% sure that this is a duplicate. $\endgroup$ – Asaf Karagila Aug 4 '19 at 19:58

This can't work, for instance $A=P(X)\setminus\{\emptyset\}$ is a collection of non-empty sets but there can't be a set $C$ which contains exactly one element of each: it would have to contain all elements of $X$ because of singletons, so it would be equal to $X$... but it wouldn't contain exactly one element of $X$ which also is in $P(X)$.

On the other hand if you add the hypothesis that two elements of $C$ are always disjoint, you can probably make it work. By the axiom of choice, there would be a function such that $f(a) \in a$ and so you would build $C = \{f(a), a\in A\}$.

Conversely, if your property is true, then for any $A$ you can consider the set $A'=\{\{a\}\times a, a \in A\}$. Elements of $A'$ are clearly disjoint, so you can find $C$ containing exactly one element of each, of the form $(a,x)$. Finally you take $f:a \mapsto x$.

  • $\begingroup$ According to munkres, given a collection $:\mathbb{B}$ of non empty subsets, there exists a choice function c such that c(B) $\in$ $B$ for each B $\in \mathbb{B}$ why isn’t that equivalent to what I said? $\endgroup$ – monoidaltransform Aug 4 '19 at 19:52
  • $\begingroup$ I forgot to mention you in the above comment $\endgroup$ – monoidaltransform Aug 4 '19 at 19:55
  • $\begingroup$ It is not because your assertion is false (cf. my proof). There can't be a set which contains "precisely one element from each element of $A$" in the example I gave (the axiom of choice just implies that there is a choice function $f(a)\in a$, but it might pick elements which also belong to other elements of $A$ as well). $\endgroup$ – FXV Aug 4 '19 at 20:06
  • $\begingroup$ The choice function allows you to pick one element from each set but there's no guarantee that the resulting set formed from these choices will contain only one element from each of the original family of sets. $\endgroup$ – Cheerful Parsnip Aug 4 '19 at 20:10
  • $\begingroup$ @Cheerful Parsnip , What I meant was that for each B, $C \cap B$ contains a single element. That would only work if the sets were disjoint, right? $\endgroup$ – monoidaltransform Aug 4 '19 at 20:12

Here's a corrected version of your attempt to give something equivalent to the axiom of choice: the Cartesian product of any set of non-empty sets is non-empty. (It's the fifth bullet point under "Set theory" here.) Note that (i) we use products rather than a set containing elements of elements because these may repeat and (ii) it must be a set, and not arbitrary collection, of non-empty sets.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.