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. :)

Solution 1:

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).

Solution 2:

I have nothing technical to add to Asaf's answer (he's the one who works on the axiom of choice, after all :-), but something from the perspective of someone who wondered for a long time what the axiom of choice is all about and realized in the end that this confusion arose from a deep misunderstanding of the point of axiomatic set theory. If you already have some (philosophical or pre-philosophical) notion of what it means for mathematical objects like sets to "exist", it happens easily that you read statements about the "existence" of a set (which abound in axiomatic set theory, including Asaf's answer) in the light of that pre-existing notion. That naturally tends to lead to reactions such as: "Whaddaya mean, there might not be a choice function? Here's the set of sets, there's the set of their elements, you agree that both of these exist and that their Cartesian product exists, how can you say there might not be a subset of that product containing exactly one pair for each set relating it to one of its elements? It's right there, that's what the Cartesian product is all about!"

The point is that axiomatic set theory intentionally forgets about all such intuitions of what sorts of sets "there are" and deals only with formal statements about the existence of sets that can be deduced from the axioms and/or that hold in certain models (which often bear little resemblance to what you intuitively think of as "the sets that there are or should be"). If you read that "a choice function might not exist", don't interpret this as telling you something you can or can't do or imagine with infinite sets; it simply means that the existence of a choice function cannot be proved from the axioms, or that there is no choice function in the particular model being discussed.

If you stick to this advice, the axiom of choice becomes a lot less mysterious than it may seem. It's actually quite easy to imagine that there are models of certain axioms that don't contain sets that one thinks "should exist" -- after all, they're just models and axioms. If you don't use the axiom of infinity, you can't deduce from the remaining axioms that there's an infinite set, and you can find a model that doesn't contain any infinite sets -- that has nothing to do with whether infinite sets "really exist" in a philosophical sense of the word (if there is one :-).

Related to this is that it's important to clearly distinguish "internal" and "external" statements -- axiomatic set theory is always concerned with a certain universe of sets, and we can always talk about this "from the outside" and talk about sets that "don't exist" inside the universe under consideration. This would obviously not be possible if all statements about "existence" referred to "the actual universe of sets" (whatever that might be) and not to some particular one.

After all this, one might wonder why bother with axiomatic set theory if it's just a formal game with axioms and models. The reason for this is that our intuition about sets can prove quite unreliable, as evidenced by the paradoxes that pop up everywhere in what's now called "naive set theory". We can say something like "the set of all sets that don't contain themselves", and think that we've said something meaningful, whereas in fact we've said something utterly meaningless, since there can be no such thing. Now that doesn't mean that you can't form the collection of all sets that don't contain themselves and think about it, just like you can form the Cartesian product as the collection of all pairs and think about it and come to the obvious conclusion that it contains a choice function; the paradox arises only if you then insist on calling that collection a "set". So axiomatic set theory, in a sense, allows us to define formally and without many of the pitfalls of "naive set theory" what sort of things we want to call a "set" in a given context -- that's no reason to doubt the existence of other collections, or not to call these collections "sets" in a different context (if that happens to be consistent).

Solution 3:

This is only half an answer, since I don't know much about the axiom of determinacy and so cannot explain how it conflicts with the axiom of choice. However, I hope that the exposition below is useful in answering your first question.

Axiom of choice. Let $\{ X_i : i \in I \}$ be a set, with each $X_i$ a non-empty set. Let $X = \bigcup_{i \in I} X_i$, the union of all of them. Then, there is a function $f : I \to X$ such that $f(i) \in X_i$ for each $i$ in $I$.

Intuitively, this is saying that if you give me any collection of non-empty sets, I can ‘choose’ an element from each one. This is obviously true in the case where you only give me finitely many sets. But what if you give me infinitely many? Obviously I can choose an element for an arbitrarily large number of them, given enough time, but it is not at all obvious that I can, in one fell swoop, choose an element from all of them at once. If I can, that must be because I can describe, in a finitistic way, a choice procedure which does so: this is exactly what $f : I \to X$ is in the above axiom, and for this reason it is called a choice function.

The way I have described the problem perhaps predisposes you to believe that the axiom of choice is not true. How could it be that there is a choice procedure for any arbitrary problem? The axiom of choice is non-constructive and merely asserts the existence of choice functions. But most mathematicians believe that the axiom of choice is true, because it is convenient. Indeed, the axiom of choice is equivalent to many other statements, some more obviously ‘correct’ or ‘wrong’ than others. A famous joke, apparently due to Jerry Bona, references this:

The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?

I'll start with some of the less set-theoretic ones, to show how it connects with ‘real’ mathematics.

Equivalent 1. Every non-trivial vector space has at least one basis.

Like the axiom of choice, this seems entirely reasonable in finite settings: for example, a finite-dimensional vector space obviously has a basis (but how would we know it's finite dimensional otherwise?), and similarly, given a finite collection of non-empty sets, it is obviously possible to pick one element from each set.

Equivalent 2. (Krull's theorem) Every non-trivial ring (with identity) has a maximal ideal. This is proven from the axiom of choice using Zorn's lemma.

Equivalent 3. Every surjective function has a right inverse, that is, if $p : X \to Y$ is a surjective function, then there is a function $f : Y \to X$ such that $f(p(y)) = y$ for all $y$ in $Y$. [The function $p$ is surjective just if for every $y$ in $Y$, there is an $x$ in $X$ such that $p(x) = y$.]

It's not hard to see intuitively that this is equivalent to the axiom of choice: after all, what's happening here is that $p$ is partitioning $Y$ into subsets indexed by $X$, and to construct $f$ one needs to pick from each subset one element; conversely, assuming that this is true, given a choice problem, we can reformulate it so as to obtain a solution using this $f$: for convenience, assume that $X_i$ and $X_j$ have no common elements when $i \ne j$, take $X$ as in the axiom, and set $Y = I$, and let $p : X \to I$ be the function which sends $x$ to $i$ if $x \in X_i$. Then any right inverse $f$ is obviously a choice function.

Just to show why this sort of thing might be a little suspect, let's make a tiny tweak to the conditions. Suppose instead that $X$ and $Y$ are topological spaces, and that $p$ is continuous. Then by no means is it guaranteed that there is a continuous right inverse $f$. For example: let $X$ be the real line and $Y$ be the circle. It's obvious that you can wrap $X$ around $Y$ in a continuous way—so there is such a continuous surjective function $p$. But there's no way to take a circle and transform it into a line continuously, so there isn't any continuous right inverse $f$.

Equivalent 4. (Well-ordering principle) Every non-empty set admits a well-ordering. [A well-ordering is an ordering such that every non-empty subset has a unique minimal element.]

Its equivalence with the axiom of choice is also intuitive: if every non-empty set has a well-ordering, then I can just give $I$ a well-ordering, and work through each $X_i$ in order, giving each one a well-ordering and picking a minimal element; conversely, given the axiom of choice, we can just ‘choose’ a well-ordering.

Equivalent 5. Given any two sets $X$ and $Y$, there is either an injection $X \to Y$, or an injection $Y \to X$, or a bijection between the two sets. This basically says that any two cardinal numbers can be compared. [An injection is a function such that different points in the domain get sent to different points in the image, that is, a function $f : X \to Y$ is injective just if $f(x) = f(x')$ implies $x = x'$. A bijection is a function which is both injective and surjective.]

Equivalent 6. Given a family of non-empty sets $\{ X_i : i \in I \}$, their cartesian product $\prod_{i \in I} X_i$ is non-empty. This is really just a reformulation of the axiom of choice, since an element of the cartesian product is precisely a choice function. [The cartesian product of a finite number of sets can be thought of as a set of ordered lists: for example, $X_1 \times X_2$ is the set of pairs $(x_1, x_2)$ where $x_1 \in X_1$ and $x_2 \in X_2$. But such a pair is obviously the same thing as a function from $\{ 1, 2 \}$ to $X_1 \cup X_2$, so that is how we define the cartesian product in the infinite case.]

Equivalent 7. (Tychonoff's theorem) Given a family of (non-empty) compact topological spaces, their cartesian product, equipped with the product topology, is (non-empty and) compact. This is a somewhat advanced bit of mathematics, but I state it here since it is related to the previous example.

Equivalent 8. (Zorn's lemma) Every partially-ordered set with the property that every chain has an upper bound in fact has a maximal element. [A partially-ordered set is a set with a binary relation $\le$ such that $x \le x$ ($\le$ is reflexive); $x \le y$ and $y \le z$ implies $x \le z$ ($\le$ is transitive); and $x \le y$ and $y \le x$ implies $x = y$ ($\le$ is antisymmetric). A chain is a subset which has the additional property that for all $x$ and $y$ in the subset, either $x \le y$ or $y \le x$. A chain $C$ in a partially-ordered set $X$ has an upper bound if there is an element $u$ in $X$ such that $x \le u$ for every $x$ in $C$. A maximal element is an element $m$ such that there do not exist any elements $x$ such that $m \le x$.]

There are also various results which are known to be invalid without the axiom of choice. In other words, these are statements implied by the axiom of choice but which do not themselves imply the axiom of choice, unlike the equivalents listed above. Some of these results are ‘useful’, and others are unpleasant and run counter to intuition.

Consequence 1. Any two bases of a vector space have the same cardinality—in other words, the dimension of a vector space is well-defined and does not depend on the basis. It can be shown (assuming the consistency of certain logical theories) that there is a universe of Zermelo–Fraenkel set theory where the axiom of choice is false (or, for short, ‘a universe without AC’) and in which there is a vector space which have two bases which have different cardinalities.

Consequence 2. Every field has an algebraic closure. [A field $K$ is algebraically closed if every polynomial with coefficients in $K$ also has a root in $K$. The field of complex numbers $\mathbb{C}$ is algebraically closed, for example. An algebraic closure of a field $F$ is a field $K$ which is algebraically closed and contains $F$ as a subfield.] As above, there is a universe without AC which has a field with no algebraic closure.

Consequence 3. Every countable union of countable sets is again countable. [A set $X$ is countable if there is an injection $X \to \mathbb{N}$, where $\mathbb{N}$ is the set of natural numbers.] There is a universe without AC in which the real numbers is a countable union of countable sets, but it can be shown that in any universe which obeys ZF, the real numbers must be uncountable.

Consequence 4. A function is sequentially continuous at a point if and only if it is also continuous at that point. [A function $f$ is sequentially continuous just if for every sequence of points $(x_n)$ converging to $x$, $f(x_n)$ converges to $f(x)$. By continuous here we mean the usual $\epsilon$-$\delta$ definition.] But there is a universe without AC in which there is a function of the real numbers which is sequentially continuous at a point but not continuous there.

Consequence 5. (Vitali set) There is a non-Lebesgue-measurable subset of the real line. [Informally, there is a subset of the real line for which does not admit a meaningful definition of ‘total length’ compatible with the intuitive notion that the unit interval $[0, 1]$ has length $1$.] There is a universe without AC in which every subset of Euclidean space is measurable.

Consequence 6. (Banach–Tarski theorem) There is a partition of the ball into finitely many pieces such that by rigid motions, these pieces can be reassembled into two balls of the same volume as the original. These pieces are, of course, not measurable, so do not exist in the universe mentioned above.

But is the axiom of choice true? That's not really a meaningful question. At best we can only ask whether Zermelo–Fraenkel set theory together with the axiom of choice (or ZFC for short) is logically consistent or not. Unfortunately, the answer to this question is as yet unknown, and quite possibly can never be known. (Gödel's incompleteness theorem is a precise form of the latter claim: it shows that the logical consistency of ZFC cannot be proven from the axioms of ZFC alone.) Personally, I advocate for pluralism in mathematics, so I don't see this as much of a problem. If it turns out that Zermelo–Fraenkel set theory with the axiom of choice is consistent and the Zermelo–Fraenkel set theory with some negation of the axiom of choice (e.g. the axiom of determinacy) is consistent, this is all the better, because it adds to the richness of mathematics. It's also a defence against the extremely unlikely event that someone does demonstrate that ZFC is inconsistent, though I suspect most mathematicians would just move on as if nothing ever happened...