12
$\begingroup$

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.

  • 5
    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.2011-11-24
  • 0
    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.2011-11-24

3 Answers 3

15

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.

  • 0
    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.2011-11-24
  • 0
    @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.2011-11-24
  • 0
    I don't get "global choice." If there's no universal set, what is the domain of our global choice function?2015-07-14
  • 0
    @Kevin: The proper class of all non-empty sets.2015-07-14
  • 0
    Oh, I see; we're not in ZFC, because there's no such thing as a "proper class" in ZFC. It might be helpful to mention that in the answer.2015-07-14
  • 0
    @Kevin: You can still formalize "global choice" in ZFC; or in some cases ZFC+F where F is a binary relation symbol with the axioms stating it is a choice function from every nonempty set.2015-07-14
  • 0
    @Kevin: More specifically, we can prove under the assumption that $V=HOD$ (which is a first-order set theoretic axiom), that there is a formula $\varphi(x,y)$ which defines a global choice function; in slightly more lenient cases we may allow a parameter and we might be able to prove that there exists a parameter for which the formula defines a global choice function. All in ZFC, of course.2015-07-14
  • 0
    But a function is just a set of ordered pairs. I think we can use the axioms of separation + pairing to build the universal set out of a function whose domain is "everything," and from there we can use regularity to get a contradiction.2015-07-14
  • 0
    @Kevin: So in this context a function is not necessarily a set. It's just a class of ordered pairs which satisfies the condition that if $(x,y)$ and $(x,z)$ are in the class, then $y=z$.2015-07-14
  • 0
    Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/25822/discussion-between-kevin-and-asaf-karagila).2015-07-14
4

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.

  • 0
    Thanks, this is a helpful perspective.2011-11-24
2

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.