47
$\begingroup$

So I am relatively familiar with the Axiom of Choice and a few of its equivalent forms (Zorn's Lemma, Surjective implies right invertible, etc.) but I have never actually taken a set theory course.

I know there are times when an explicit way of choosing some elements may not be provided, and instead we call upon the Axiom of Choice to do it for us. But one thing has always bothered me.

I have heard that for a finite set we do not need the Axiom of Choice to choose an element. I find this a little confusing. How is choosing an element from a finite set any different than choosing from an infinite set? I have heard before "since the set it finite, there are finitely many orders, so order the set and choose the first element in the order." But how does one choose what order to use? This involves picking an element from a finite set, i.e. it presumes the conclusion.

I'm guessing there is a good reason why everyone keeps insisting that the Axiom of Choice in not needed to choose from finite sets, so could someone please explain it to me?

Edit: There seems to be confusion on what exactly I am asking. I know that we need the Axiom of Choice, sometimes, to make infinitely many choices, from finite or infinite sets. This is not what is confusing me. Allow me to be more precise:

Suppose $S$ is a nonempty finite set. I want to pick one element from $S$. Does choosing one element from $S$ require the Axiom of Choice? If not, how can the choice be made without the Axiom of Choice?

Saying $S$ is not empty, therefore there is an $x \in S$, does not suffice. How do I choose such an $x$? There is one, but how do I describe it without any information about the set, other than the fact that it nonempty and finite?

Another clarification: I am not asking about using "Let ... be given" as a proof technique.

$\endgroup$
7
  • 2
    $\begingroup$ Essentially duplicate: math.stackexchange.com/questions/85153/… $\endgroup$
    – Asaf Karagila
    Apr 16, 2012 at 22:44
  • 11
    $\begingroup$ The matter of the axiom of choice is not to choose among an infinite set, but make an infinity of choice. $\endgroup$
    – Lierre
    Apr 16, 2012 at 22:59
  • $\begingroup$ If the only things you know about a set $A$ are that it is nonempty any finite, how could you possibly hope to choose an element effectively? You don't even know whether $A$ is a set of numbers, or a set of functions, or some other kind of set! $\endgroup$ Apr 17, 2012 at 11:34
  • $\begingroup$ nullUser, can you please provide an example where you are choosing an element from a set which is not in a context of a proposition/proof? (Even if you don't use "Let ... " you are often sit inside a proposition or a proof of a proposition) $\endgroup$
    – Asaf Karagila
    Apr 18, 2012 at 10:36
  • $\begingroup$ "How do I choose such an x?" is often a good question if you're writing a computer program. But in mathematics, if you want to use the existence of $x$ then tautologically you need only a proof that $x$ exists. $\endgroup$
    – Dan Piponi
    Jul 5, 2014 at 5:35

7 Answers 7

74
$\begingroup$

The ability to give a name to some arbitrary element of a nonempty set is known as "existential instantiation". This is an inference rule of the underlying logic, not part of the theory, and so it is included not only in ZFC, but also in ZF, and in appropriate forms it is also included in PA and every other first-order theory.

The intuition is that giving a name to an object does not really require "choosing" an object; if we know that there is an element in a set $A$, and we begin arguing about some "given" element $c \in A$, we do not have to actually make a choice, we can just reason hypothetically ("what if we knew an element $c$ of $A$?"). This reasoning will be sound because $A$ really is nonempty. However, because we don't know which element is chosen, the only properties we know it has are the ones we can prove every element of $A$ has. In particular, we cannot assume that the element we are given is equal to any other object we already have, unless we can prove they are equal. So we need to give a new name that we are not already using for any other object.

The word "choose" is used in several ways in set theory, both in this way (existential instantiation), and in ways corresponding to the axiom of choice, and in ways where there is not really any choice, for example when we have a function $f$ and a set $x$ and we "choose" $y$ such that $f(x) = y$. You have to look at the context to tell what formal proof is being suggested by the informal proof that you read.

You might be thinking that "choosing" a single element from a set would be an algorithmic operation, but this is just not the case. The nonconstructivity of existential instantiation is a direct consequence of the nonconstructive meaning of $\exists$ in classical logic. To get a system where you can effectively choose a witness to any true existential statement, you have to move to constructive mathematics, but then the meaning of $\exists$ changes as well.

$\endgroup$
4
  • 10
    $\begingroup$ I think this is the best answer so far. $\endgroup$
    – Asaf Karagila
    Apr 17, 2012 at 12:02
  • $\begingroup$ This is good information, but I don't see how it answers the OP's question. $\endgroup$
    – tparker
    Sep 20, 2017 at 15:19
  • $\begingroup$ I was trying in particular to answer the question "Suppose S is a nonempty finite set. I want to pick one element from S. Does choosing one element from S require the Axiom of Choice?" Of course it makes no difference if the set is finite, just that the choice is being made from one set. @tparker $\endgroup$ Sep 20, 2017 at 15:32
  • 2
    $\begingroup$ You're right, this does answer the OP's specific question. I thought they were asking the slightly different question "What's different about finite vs. infinite collections of sets that requires a new axiom for the infinite case?", but rereading the OP I see this is not the case. $\endgroup$
    – tparker
    Sep 20, 2017 at 15:49
19
$\begingroup$
Saying S is not empty, therefore there is an x∈S, does not suffice.

Ah, but it does suffice! Knowing that $S$ is non-empty, there do exist such $x$, and so we can declare the symbol $x$ to denote an element of $S$, and the rest of our argument is then a function of $x$.

To put it more formally, a typical proof that chooses an element from $S$ has the form

Let x∈S
...
Therefore P

and constitutes a proof of $\forall x: (x \in S \implies P)$, which in turn implies $P \vee (S = \emptyset)$.

Similarly, if you made two choices $x \in S, y \in T$, you typically prove a statement like $\forall x,y: \left( (x,y) \in S \times T\implies P \right) $.

This makes it clear how the axiom of choice enters the picture; a sequence of infinitely many choices indexed by $I$ of the form described above would be a proof of

$$ \forall x : \left(x \in \prod_{i \in I} S_i \implies P \right)$$

which implies

$$ P \vee \left(\prod_{i \in I} S_i = \emptyset \right) $$

i.e. a proof that $P$ is true or the family $S_i$ does not have a choice function (or both).

$\endgroup$
7
  • 1
    $\begingroup$ One of the forms of the axiom of choice is: Let $I$ a set of indices, and let $(A_i)_{i\in I}$ a family of sets indexed by $I$. If $A_i\neq\emptyset$ for all $i\in I$, then there exist a function $f:I\to \bigcup_{i\in I}A_i$ such that $f(i)\in A_i$ for all $i\in I$. So, what you are saying is the case where the set of indexes have only one element, i.e., as I see, it is a particular case of the axiom of choice. $\endgroup$
    – leo
    Apr 17, 2012 at 5:23
  • $\begingroup$ The axiom of choice does imply that a one-element family has a choice function, but it's certainly not required for that case. We only need ZF (just Z?) to construct the natural bijection $\prod_{i \in \{ * \}} A_i \cong A_*$ $\endgroup$
    – user14972
    Apr 17, 2012 at 8:31
  • $\begingroup$ Think about the product written in the previous comment, over a single index. It is the set of the form $\{\langle\ast,a\rangle\mid a\in A_\ast\}$. This is naturally isomorphic to $A_\ast$ via the projection onto the second coordinate. I think that as joriki remarked in the comments to azarel's answer the question is why can we choose from the family of choice functions, which is essentially answered in the first part here; in my answer below; and in the answer I linked in the comments. $\endgroup$
    – Asaf Karagila
    Apr 17, 2012 at 10:25
  • $\begingroup$ What does this answer have to do with the issue of finite vs. infinite sets? $\endgroup$
    – tparker
    Sep 20, 2017 at 15:15
  • $\begingroup$ I don't think this answer answers the question. The question asked how to show that for any set of finitely many nonempty sets, there is a choice function and not how to show that for any set of one nonempty set, there is a choice function. Maybe it is useful for correcting some people's mistaken intuition that you can't even prove that for any set of one nonempty set, there is a choice function. $\endgroup$
    – Timothy
    Apr 9, 2018 at 2:47
18
$\begingroup$

There are two things. Let $(A_i)_{i\in I}$ be an arbitrary family of nonempty sets. One version of the axiom of choice says that $\prod_i A_i\neq\emptyset$. We cannot prove this without the axiom of choice if we know that for all $i\in I$ the set $A_i$ is finite. What we can show is that the product is nonempty if $I$ is finite!

The proof goes like this: We show that for each $n$, if $I$ has $n$ elements, then the product is nonempty. We do this by induction. Without loss of generality, we let $I=\{1,\ldots,n\}$. If $I$ contains a single element, showing that the product is nonempty amounts to finding an element in the single set $A_1$. That this can be done is simply the meaning of $A_1$ being nonempty. So suppose there exists a choice function $(a_1,\ldots,a_{n-1})$ defined on $I\backslash\{n\}=\{1,\ldots,n-1\}$. Since $A_n$ is nonempty, there is some $a_n\in A_n$. This gives a choice function for $I$ given by $(a_1,\ldots,a_{n-1},a_n)$. And for this, we don't need the axiom of choice.

$\endgroup$
2
  • 2
    $\begingroup$ I like this one... $\endgroup$
    – Troy Woo
    Nov 15, 2014 at 23:40
  • $\begingroup$ Surely you could have started induction at $I = \varnothing$. $\endgroup$ Aug 15, 2023 at 6:16
15
$\begingroup$

The axiom of choice, as said, allows us to choose from infinitely many sets at once (sometimes even when these sets are finite!). If, however, one only wishes to choose from finitely many sets then this can be done without it. It does not even matter if the sets themselves are finite or not.

Choosing an element from $A$ means fixing a particular element from $A$. If we can name it ($0$, for example chosen from the real numbers) then it's fine. If we does not know the name of the element in advance then we have to assign it a name.

We do that using the infamous "let", and from that point we agree that the assigned name refers only to that particular element. e.g.

Let $r\in\mathbb R\setminus\mathbb Q$...

What happens is that since we assume that $A$ is not empty then the proposition $\exists x(x\in A)$ is true. Now writing the rest of the proof we can think of it as a list of formulas that $x$ is one of the free variables in those formulas, let us call them $\varphi_1(x,y_1),\ldots,\varphi_k(x,y_k)$.

When we choose an element from $A$ we say: $$\ldots\exists x(x\in A\land\varphi_1(x,y_1)\ldots\varphi_k(x,y_k))\ldots$$

So we have some previous proposition, some other variables assigned and we have the proof itself in the middle, and we assign it an arbitrary $x$.

(Note that if we require $x$ to have a certain property then we replace $A$ with a subset of $A$ of "all the elements that have the required property in $A$", of course we sometimes need to argue that this set is not-empty!)

If you understand this explanation it shouldn't be hard to see why we can choose finitely many elements from finitely many non-empty sets as well.

$\endgroup$
12
  • $\begingroup$ This is of course all correct, but it pertains to making a finite number of choices, whereas the question is about choosing from finite sets. $\endgroup$
    – joriki
    Apr 16, 2012 at 22:57
  • $\begingroup$ @joriki: I didn't use the fact that the sets are finite. Should I limit the generality of the answer and write "$A$ finite" everywhere instead, and replace $\mathbb R\setminus\mathbb Q$ by a less-describable-finite set? $\endgroup$
    – Asaf Karagila
    Apr 16, 2012 at 23:00
  • $\begingroup$ No, I just think the answer should first and foremost point out that the statement in the question is false and we do need the axiom of choice to choose from finite sets, before going on to show why something that sounds superficially similar, that we don't need it to make finitely many choices, is true. $\endgroup$
    – joriki
    Apr 16, 2012 at 23:02
  • $\begingroup$ @joriki: With that I agree. I have added something to reflect this. $\endgroup$
    – Asaf Karagila
    Apr 16, 2012 at 23:05
  • $\begingroup$ Sorry to perhaps sound a bit nit-picking, but I still feel the answer doesn't clearly point out that the supposition in the question is false. You only point out that it doesn't matter for the possibility of making finitely many choices without AC whether the sets are finite or not, but you don't point out that it also doesn't matter for the impossibility of making infinitely many choices without AC whether the sets are finite or not; whereas the OP thought that it does. $\endgroup$
    – joriki
    Apr 16, 2012 at 23:09
4
$\begingroup$

You do not need to "choose" $x$ (what do you mean by "choosing" $x$?) You only need to prove the at least one $x$ exists, which is actually your assumption (the set is nonempty), so there is nothing to prove.

The Axiom of Choice does not "choose" a choice function, it only says that at least one choice function exists. It can be stated in the following form:

The Cartesian product of a family of nonempty sets is nonempty.

For one set this is obvious.

$\endgroup$
2
  • 1
    $\begingroup$ This doesn't answer the question. $\endgroup$
    – Asaf Karagila
    Jan 20, 2013 at 12:59
  • 2
    $\begingroup$ What do you mean? I was answering the question "How do I choose such an $x$?". I think i have answered the question. $\endgroup$
    – Alexey
    Jan 20, 2013 at 13:39
3
$\begingroup$

If $S$ is non-empty and finite then, by definition, there exists a bijection $f$ with a non-empty initial prefix of the natural numbers. Choose $f(1)$.

$\endgroup$
0
$\begingroup$

One reason AC is not needed for a finite number of arbitrary choices lies in formal logic. In his Introduction to Mathematical Logic, 4th ed., p. 81-83, E. Mendelson shows how a deduction using "Rule C", involving a finite number of arbitrary choices, can be reduced to a formal deduction without such choices. The mathematical practice of making choices is viewed as a shortcut for the formal deduction. Since deductions can only involve a finite number of choices, one needs a new axiom if one wants to make an infinite number of choices within the proof.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .