What are the Axiom of Choice and Axiom of Determinacy?

Would someone please explain:

  • What does the Axiom of Choice mean, intuitively?
  • What does the Axiom of Determinancy mean, intuitively, and how does it contradict the Axiom of Choice?

as simple words as possible?

From what I’ve gathered from the Wikipedia page, my understanding is that the Axiom of Choice pretty much lets you make a completely random decision, i.e. equal probability for everything. I don’t, however, understand what they’re talking about regarding the sets of sets (is it more than what I just described?), and I further don’t understand the Axiom of Determinancy.

Info on those would be appreciated. 🙂

Answer

The axiom of choice is an axiom of set theory, and it is used when implicitly assuming that the universe consists of sets, and sets alone. That is – everything is a set.

For example, 0=\emptyset and 1=\{\emptyset\}. Since everything is a set, consider a set X and all its elements are non-empty sets themselves. Formally \forall y(y\in X\rightarrow \exists z(z\in y)).

The axiom of choice asserts the existence of a function whose domain is X and its range is \{z\mid\exists y(y\in X\land z\in y)\} (often denoted \bigcup X). The function has a very special property, namely f(y)\in y. It chooses someone from every element of X.

Some examples (which do not require the axiom of choice) are, X=\mathcal P(\mathbb N)\setminus\{\emptyset\} that is all the non-empty subsets of natural numbers.

We can have f(A)=\min A, that is the least element of A is returned. We can require something slightly more peculiar f(A) = \min\{a\in A\mid a\text{ is even}\} if such a exists, or \min A otherwise.

These are two examples which do not require the axiom of choice since we are able to specify in a uniform formula who do we want to pick from every A.

A useful equivalence of the axiom of choice is Zorn’s lemma. This lemma is somewhat complicated, but it asserts that if (A,<) is a partially ordered set, and every linearly ordered subset of A has an upper bound, then there exists a maximal element.

To elaborate on that, if A is a non-empty set, and < defines a partial order on A, if every C\subseteq A which has the property \forall a\forall b(a<b\lor b<a\lor a=b) has some x\in A such that \forall a(a\in C\rightarrow a<x) then there exists a maximal element - some x\in A for which the property \forall a(a\neq x\rightarrow a<x) is true.

Zorn's lemma is very useful in algebra, and used in the proof that every field has an algebraic closure; every vector space has a basis; and every ideal can be extended to a maximal ideal (and many many many other uses).

The proof uses heavily the axiom of choice (not surprisingly, since the two are equivalent) and in a nutshell we take one element, then \{a_0\} is linearly ordered, therefore if a_0 is not maximal in A we can extend it. That is the set \{b\in A\mid a<b\land a\neq b\} is non-empty, and we can choose from it. We choose from non-empty subsets of A until we either "find" a maximal element, or derive contradiction to one property or another.

I use "find" because many times the maximal element is one we cannot describe nicely by a sentence (and in fact without the axiom of choice there are vector spaces without basis, fields without algebraic closures and so on).


To understand the axiom of determinacy first we need to understand what there is to be determined.

Take A\subseteq\mathbb N^\mathbb N, that is a set of infinite sequences of natural numbers.

Now we play a game, I will be Player I (P-I) and you will be Player I (P-II). I will choose some n\in\mathbb N, and then you will choose another. The game is infinitely long and will have another round for every finite number of rounds.

Note that in the n-th round we have x_n and y_n (I chose x's and you choose y's). This defines a sequence:
a_n =\begin{cases}x_k & n=2k\\ y_k & n=2k+1\end{cases}

We say that I win the game if \langle a_0,a_1\ldots\rangle\in A, otherwise you win the game. If there is a strategy assuring victory for either one of us then we say that the game is determined. This is to say there is a function from \mathbb N to \mathbb N that given the current state of the game will give me a possible tail segment which assures one of the player's victory. (Note that there are usually a lot of possible strategies).

For example A will be all the sequences which are constants a_n=k for some k. Clearly you have a winning strategy. Whatever I chose at first, choose something else and I have no chance of winning.

Another example is A will be the set of sequences that a_n is even whenever n is even (a_n=n, for example). All I have to do is choose even numbers in my turn, and I cannot lose.

The Axiom of determinacy asserts: Every game is determined. That is, if we play this sort of game then regardless to which set of sequences we have chosen, one of us can win.

The conflict with the axiom of choice is a bit technical for this post (and the part about determinacy could surely be phrased better by someone else), the idea is as such. If we assume the axiom of determinacy, then every game is determined. We will define A by a transfinite induction. Since at each step during the game the collection of winning strategies is non-empty. We simply choose such winning strategy and ensure that it will not work by adding a sequence to A, repeating the process "enough" times we ensured that no strategy exists to determine the winner after any finite number of turns. This contradicts the assumption that every game is determined.

Determinacy is somewhat of a technical axiom, and while it was very natural to postulate this axiom in some parts of set theory (namely descriptive set theory), the mainstream mathematics has been made very comfortable with the axiom of choice, and as Theo points out in the comments some pathologies which we are used to are gone when assuming the axiom of determinacy.

This makes the axiom of choice more common in modern mathematics than determinacy. Things can change, though... things can change.


Added:

To understand the need for the axiom of choice, we return to Bertrand Russell's wonderful analogy. Given infinitely many pairs of shoes, you can always choose one from each pair, but to choose a sock from infinitely many pairs of socks you need the axiom of choice.

What does that mean? Well, given shoes you can easily say "Pick all the left shoes", and regardless of how many pairs are given in each pair there is exactly one left shoe. This defines a function which chooses an element of each pair. On the other hand socks are indistinguishable and you cannot say which one is the left and which one is the right.

What does that mean indistinguishable? Well, given one pair of socks \{a,b\} we can always say "Oh, this is a and this is b", even if our assignment of a was arbitrary. Every time we are given three pairs of socks we can ad-hoc assign each pair as a_i, b_i and pick the ones we assigned as a_i. However if there are infinitely many pairs of socks, can we always make such assignment? Well, only if we assume the axiom of choice holds.

The point is that a pair of socks has two elements in it. These are always distinct and we can always examine the pair by itself and distinguish between the two socks. We can always distinguish between three, four and five socks at once; as well ten or fifteen pairs of socks. We simply assign each collection of socks with different names to be able and temporarily tell which sock is which, then we can choose the names we would like.

Mathematically speaking if we are given a finite collection of non-empty sets, if we do not actually care about the choice of elements, as long as we choose exactly one from each set, it is always doable. First we need to understand that "not caring" means that we only require f(A)\in A which is of course doable since A is non-empty. However, in mathematics it is not enough to claim things, one has to prove them as well. In this case, we can simply write the following statment (assuming A_1,\ldots, A_n are our non-empty sets):

\exists x_1\ldots\exists x_n(x_1\in A_1\land x_2\in A_2\land\ldots\land x_n\in A_n\bigwedge f(A_1)=x_1\land f(A_2)=x_2\land\ldots\land f(A_n)=x_n)

That is to describe exactly (I am somewhat cheating here, I did not describe it exactly, but I gave a close enough approximation) how f looks like, it is the function (however a function may be defined set theoretically) that after fixing x_i\in A_i simply returns x_i as the choice from A_i. Since this is a finite collection of pairs we can describe this sort of choice.

If we have one pair then this sentence is very short, as we keep on adding pairs we will write longer and longer sentences. If we finally have infinitely many pairs then we cannot write this sort of sentence. We need to find a different formulation. This is where the ability to uniformly distinguish some unique element in each A_i comes to help. Suppose \varphi(x) is the property of being a left shoe. Let B=\{B_n\mid n\in\mathbb N\} be a collection of infinitely many pairs of shoes. If we want to choose from each pair, we can simply do it as such:

\forall X(X\in B\rightarrow \varphi(f(X)))

Since there exists exactly one element, a in every X for which \varphi(a) is true (i.e. there is exactly one left shoe in each pair of shoes) this implies the function f is nicely defined, in a finite (and even short) sentence.

Now we return to the socks. There is no property \varphi(x) such that in every pair of socks there is exactly one sock for which \varphi is true. This means that we cannot write a very nice sentence as above, to choose one sock from each pair!

This is the (with a capital "the") key of the issue here. In a finite collection you can always distinguish every element from every other element. When looking at an infinite collection you may not be able to have this luxury.

What does that mean mathematically? It means that you may not be able to write a finite sentence to help you choose from infinitely many pairs without the axiom of choice - which asserts this sort of choice exists (it may not be computable or even definable except for knowing it exists somewhere in your universe, and therefore you can take an arbitrary one and use it for a while).

Attribution
Source : Link , Question Author : user541686 , Answer Author : Asaf Karagila

Leave a Comment