Suppose I have a non-empty set $A$.

How do I choose an element $x\in A$?

More precisely, I believe I would like to find a formula $P(x,y)$ of ZF such that for every non-empty set $y$ there is exactly one $x\in y$ such that $P(x,y)$ is true.

I have thought about this for a while without success and I am beginning to doubt such a formula is even possible. But in mathematical proofs it is quite common to "choose a fixed element" from a non-empty set. So how exactly do we achieve such a thing? Am I missing something?

Thank you in advance.

  • 7
    $\begingroup$ When authors say "choose an element $x \in A$", they could just as well say "let $x$ be any element of $A$". Thus, no active choice actually needs to be made. The point is that whatever claim you are making will be valid for any $x$ you happen to be looking at. $\endgroup$ – Austin Mohr Nov 24 '11 at 6:15
  • $\begingroup$ That's a good point. I now remember reading about so called "C-rule" of predicate calculus some time ago, and if I remember correctly, it uses this to "define" a virtual "fixed element" which feels like making an actual choice. Thanks. $\endgroup$ – Dejan Govc Nov 24 '11 at 7:55

When writing a proof we may write axioms, our assumptions and things which can be deduced directly from these.

The assumption that $A$ is not empty is exactly to say that $\exists x(x\in A)$ is a true sentence, so we may pick one element from $A$ and fix it for the proof. If, for example, $A=\{x\}$ then we can also know immediately that there is only one choice of $x$ possible. Often however, this is not the case.

Inductively we can choose from finitely many sets, and we can choose finitely many elements from each set, of course that if we want this choice to be unique then we may be limited by the cardinality of $A$ (as when $A=\{x\}$ there can be only one unique choice of element from $A$).

If however you want to choose from infinitely many nonempty sets at once, then you need the axiom of choice. It is possible to have a model of ZF where you have a set of countably many pairs whose product is empty - that is you cannot choose exactly one element from each set.

Note that it is perfectly possible to choose from infinitely many sets without the axiom of choice under a severe constraint that they have some common characteristic. From infinitely many sets of natural numbers we can choose the minimal in each set; from infinitely many finite sets of real numbers we can choose the maximal element of each set; etc etc.

Lastly, if you want a formula which chooses from all the nonempty sets in the model then you need something stronger than the axiom of choice. You need something called Global Choice, which is to say exactly this. There is a choice function on all nonempty sets in the universe.

| cite | improve this answer | |
  • $\begingroup$ Very nice! I think I now understand the Axiom of Choice a bit better. Finding a formula like the one I wanted would possibly be even stronger than Global Choice or am I mistaken? Since, if I understand correctly, with Global Choice you would still need to choose a particular choice function, but with a formula you don't even have to choose anymore. $\endgroup$ – Dejan Govc Nov 24 '11 at 8:06
  • $\begingroup$ @Dejan: Global choice means that there is a class choice function. This is exactly to say that there is a formula like you want. Note also that if you have a formula for a choice function, and can modify it at certain points. You can even use the original function to choose which points you will change and how. $\endgroup$ – Asaf Karagila Nov 24 '11 at 10:18
  • $\begingroup$ I don't get "global choice." If there's no universal set, what is the domain of our global choice function? $\endgroup$ – Kevin Jul 14 '15 at 14:11
  • $\begingroup$ @Kevin: The proper class of all non-empty sets. $\endgroup$ – Asaf Karagila Jul 14 '15 at 14:16
  • 1
    $\begingroup$ @FrancescoBilotta: Yes, we can use induction to prove that if we can choose from one set, then we can choose from finitely many sets. $\endgroup$ – Asaf Karagila Aug 29 '19 at 9:26

If there were such a formula in general, we wouldn't need the axiom of choice; we could then use the axiom schema of replacement to construct a choice function. In fact, in cases where there is such a function, we can use it to avoid using the axiom of choice. For instance, to choose from a well-ordered set, you can use the formula that picks out the least element.

| cite | improve this answer | |
  • $\begingroup$ Thanks, this is a helpful perspective. $\endgroup$ – Dejan Govc Nov 24 '11 at 8:15

David Hilbert introduced his $\tau$-operator (sometimes called $\epsilon$-operator) to extract such a choice function. Foundationally this is somewhere between choice and global choice. Bourbaki when they developed their own foundations choice to use Hilbert's $\epsilon$, getting them into no end of trouble as described in detail in the writings of Adrian Mathias; see e.g., this article.

| cite | improve this answer | |

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.