Choice vs. countable choice - MathOverflow

Choice vs. countable choice

2010-04-29T14:56:34Z

This question arose after reading the answers (and the comments to the answers) to http://mathoverflow.net/questions/22927/why-worry-about-the-axiom-of-choice.

First things first. In my intuitive conception of the hierarchy of sets, the axiom of choice is obviously true. I mean, how can the product of a family of non-empty sets fail to be non-empty? I simply cannot fathom it. Now, I understand that there are people who disagree with me; a mathematician of a (more) constructive persuasion would reply that mathematical existence is constructive existence. Well, we can agree to disagree. And besides, the distinction between constructive and non-constructive proofs is very much worth having in mind. First, because constructive proofs usually give more information and second, there are many contexts where AC is not available (e.g. topoi).

A second (personal) reason for championing AC is a pragmatic one: it allows us to prove many things. And "many things" include things that physicists use without a blink. Analysis can hardly get off the ground without some form of choice. Countable choice (ACC) or dependent countable choice (ACDC) is enough for most elementary analysis and many constructivists have no problem with ACC or ACDC. For example, ACC and the stronger ACDC are enough to prove that the countable union of countable sets is countable or Baire's theorem but it is not enough to prove Hahn-Banach, Tychonoff or Krein-Milman (please, correct me if I am wrong). And this is where my question comes in. In one of the comments to the post cited above someone wrote (quoting from memory) that the majority of practicing mathematicians views countable choice as "true". I have seen this repeated many times, and the way I read this is that while the majority of practicing mathematicians views ACC as "obviously true", a part of this population harbours, in various degrees, some doubts about full AC. Assuming that I have not misread these statements, why in the minds of some people ACC is "unproblematic" but AC's validity is not? What is the intuitive explanation (or philosophical reason, if you will) why making countably infinite choices is "unproblematic" but making arbitrarily infinite choices is somehow "more suspicious" and "fraught with dangers"? I for one, cannot see any difference, but then again I freely confess my ignorance about these matters. Let me stress once again that I do not think for a moment that denying AC is "wrong" in some absolute sense of the word; I just would like to understand better what is the obstruction (to use a geometric metaphor) from passing from countably infinite choices to arbitrarily infinite ones.

Note: some rewriting and expansion of the original post to address some of the comments.

Answer by John Goodrick for Choice vs. countable choice

2010-04-29T15:22:42Z

I have no idea who these alleged people are who are nervous about using full AC but not countable AC, but perhaps they (as you would put it) cannot fathom the following consequences of ZFC which are unprovable from ZF + countable choice:

-The existence of a nonmeasurable set of real numbers;

-The existence of a set of real numbers without the property of Baire;

-The Banach-Tarski paradox (that the unit ball in R^3 has a finite, pairwise-disjoint decomposition into subsets which can be reassembled, via isometries in R^3, into two identical copies of the original unit ball).

Answer by Emerton for Choice vs. countable choice

2010-04-29T16:04:55Z

It might be relevant that no-one has trouble well-ordering a countable set.

Added in response to the comments: My somewhat flippant answer has gotten me in trouble; let me see if I can extricate myself.

I think that everyone agrees with finite choice: if we have a finite collection of non-empty sets $S_1,\ldots,S_n$, then we can surely choose an element $s_i$ from each $S_i$

Now suppose we have a sequence of non-empty sets $S_i$. Then, if you can imagine the set of natural numbers in its entirety (in my mind it is laid out as a set of stone, one following the other), then you can image passing step by step through the natural numbers, choosing an element from each $S_i$ in turn.

Although personally I don't have any particular objection to full choice, I can see why the consideration of a general infinite process (choosing an element from each of an infinite collection of sets) could seem much more unreasonable then choosing an element from each of a sequence of sets. Although this is not the direct logical relation of well-ordering with the axiom of choice (which involves well-ordering the union of the sets, not the indexing set), I nevertheless maintain that an infinite process seems more reasonable if you can imagine it being taken one step at a time, rather than if you imagine it being indexed by some amorphous, unstructured infinite set.

Answer by Noam Zeilberger for Choice vs. countable choice

2010-04-29T18:06:38Z

On the idea that "The axiom of choice is obviously true", you might be interested in reading Per Martin-Löf's article (unfortunately behind a paywall), "100 years of Zermelo's axiom of choice: What was the problem with it?". In dependent type theory (as with many flavors of constructive mathematics) a version of the axiom of choice is indeed a trivial theorem, but the devil is in the details, and Martin-Löf argues that the problem with Zermelo's axiom only arose in his 1908 reformulation, where it corresponds to what Martin-Löf calls the extensional axiom of choice. See also Russell O'Connor's note on Intensional vs Extensional Choice.

Answer by Pace Nielsen for Choice vs. countable choice

2010-04-29T19:19:01Z

Maybe I'm in the minority, but I don't really view any mathematical axiom as "true" in the sense of "describes reality." That said, I'm the kind of mathematician who uses the axiom of choice on a daily basis (because I work with maximal ideals in rings). For me, the axiom is useful. But that is as far as it goes.

It seems to me that the description "this is obviously true" is more a statement of the person's intuition on structures he/she is used to. The nice thing about logic is that it can tell us when our intuitions are incomplete. We can describe where our intuition is valid, and where it is invalid.

The axiom of choice is "obviously true" in many axiomatic systems, and is "obviously untrue" in others, and is independent is some others. It seems to me that some people (including myself) just don't like working in those universes where AC fails, just like some people don't like working with rings without unity (or with associativity, or commutativity, etc...).

Answer by David Speyer for Choice vs. countable choice

2010-04-29T19:54:36Z

I am a mathematician who finds countable choice more intuitive than arbitrary choice. I'll try to explain my intuition, although I fully admit it is not rigorous.

Let $S_{n}$ be a sequence of nonempty sets, indexed by integers. There is some element $s_1$ in $S_1$. There is some element $s_2$ in $S_2$, so there is an element $(s_1, s_2)$ in $S_1 \times S_2$. There is some element $s_3$ in $S_3$, so there is an element $(s_1, s_2, s_3)$ in $S_1 \times S_2 \times S_3$. For any fixed integer $n$, I can use this logic to write down an element of $S_1 \times S_2 \times \cdots \times S_n$.

My intuition says that I can take the limit of this process as $n \to \infty$. Sure, it becomes an infinite process, but I can just think of that as "keep doing this, forever". I can even think of Achilles choosing an element of $S_i$ in time $2^{-i}$, so that I don't have to imagine infinite time. The axiom of countable choice makes my hazy intuition precise.

Now, suppose that $S_a$ is a family of sets indexed by $a$ in an uncountable set $A$. Then, even after making infinitely many choices, I still have only chosen an representatives from a minute fraction of the $S_a$ from which I must choose. Even if $A$ can be well-ordered, it can't be embedded in $\mathbb{R}$ in a well-ordered way, which means I can't think of my choices taking place at specific times. I find that disquieting.

Answer by Andrej Bauer for Choice vs. countable choice

2010-04-29T21:28:50Z

Here is one explanation of why countable choice is not problematic in constructive mathematics.

For this discussion it is useful to formulate the axiom of choice as follows:

$(\forall x \in X . \exists y \in Y . R(x,y)) \implies \exists f \in Y^X . \forall x \in X . R(x,f(x))$

This says that a total relation $R \subseteq X \times Y$ contains a function. The usual formulation of the axiom of choice is equivalent to the above one. Indeed, if $(S_i)_{i \in I}$ is a family of non-empty sets we take $X = I$, $Y = \bigcup_i S_i$ and $R(i,x) \iff x \in S_i$ to obtain a choice function $f : I \to \bigcup_i S_i$. Conversely, given a total relation $R \subseteq X \times Y$, consider the the family $(S_x)_{x \in X}$ where $S_x = \lbrace y \in Y \mid R(x,y)\rbrace$ and apply the usual axiom of choice.

One way of viewing sets in constructive mathematics is to imagine that they are collections together with given equality, i.e., some sort of "presets" equipped with equivalence relations. This actually makes sense if you think about how we implement abstract sets in computers: each element of the abstract set is represented by a finite sequence of bits, where each element may have many valid representations (and this is unavoidable in general). Let me give two specific examples:

a natural number $n \in \mathbb{N}$ is represented in the usual binary system, and let us allow leadings zeroes, so that $42$ is represented by $101010$ as well as $0101010$, $00101010$, etc.
a (computable) real $x \in \mathbb{R}$ is represented by machine code (a binary string) that computes arbitrarily good approximations of $x$. Specifically, a piece of code $p$ represents $x$ when $p(n)$ outputs a rational number that differs from $x$ by at most $2^{-n}$. Of course we only represent computable reals this way, and every computable real has many different representations.

Let me write $\mathbb{R}$ for the set of computable reals, because those are the only reals relevant to this discussion.

An essential difference between the first and the second example is that there is a computable canonical choice of representatives for elements of $\mathbb{N}$ (chop off the leading zeroes), whereas there is no such canonical choice for $\mathbb{R}$, for if we had it we could decide equality of computable reals and consequently solve the Halting problem.

According to the constructive interpretation of logic, a statement of the form

$\forall x \in X . \exists y \in Y . R(x, y)$

holds if there is a program $p$ which takes as input a representative for $x \in X$ and produces a representative for $y \in Y$, together with a witness for $R(x,y)$. Crucially, $p$ need not respect equality of $X$. For example,

$\forall x \in \mathbb{R} . \exists n \in \mathbb{N} . x < n$

is accepted because we can write a program which takes as input a representative of $x$, namely a program $p$ as described above, and outputs a natural number larger than $x$, for example $round(p(0)) + 1000$. However, the number $n$ will necessarily depend on $p$, and there is no way too make it depend only on $x$ (computably).

Let us have a look at the axiom of choice again:

$(\forall x \in X . \exists y \in Y . R(x,y)) \implies \exists f \in Y^X . \forall x \in X . R(x,f(x))$

We accept this if there is a program which takes as input a $p$ witnessing totality of $R$ and outputs a representative of a choice function $f$, as well as a witness that $\forall x \in X. R(x, f(x))$ holds. This is probematic because $p$ need not respect equality of $X$, whereas a representative for $f$ must respect equality. It is not clear where we could get it from, and in specific examples we can show that there isn't one. Already the following fails:

$(\forall x \in \mathbb{R} . \exists n \in \mathbb{N} . x < n) \implies \exists f \in \mathbb{N}^\mathbb{R} . \forall x \in \mathbb{R} . x < f(x)$.

Indeed, every computable map $f : \mathbb{R} \to \mathbb{N}$ is constant (because a non-constant one would allow us to write a Halting oracle).

However, if we specialize to countable choice

$(\forall n \in \mathbb{N} . \exists y \in Y . R(n,y)) \implies \exists f \in Y^\mathbb{N} . \forall n \in \mathbb{N} . R(n,f(n))$

then we can produce the desired program. Given $p$ that witnesses totality of $R$, define the following program $q$ that represents a choice function: $q$ takes as input a binary representation of a natural number $n$, possibly with leading zeroes, chops of the leading zeroes, and applies $p$. Now, even if $p$ did not respect equality of natural numbers, $q$ does because it applies $p$ to canonically chosen representatives.

In general, we will accept choice for those sets $X$ that have computable canonical representatives for their elements. Ok, this was a bit quick, but I hope I got the idea accross.

Let me finish with a general comment. Most working mathematicians cannot imagine alternative mathematical universes because they were thoroughly trained to think about only one mathemtical universe, namely classical set theory. As a result their mathematical intuition has fallen a victim to classical set theory. The first step towards understanding why someone might call into question a mathematical principle which seems obviously true to them, is to broaden their horizon by studying other mathematical universes. On a smaller scale this is quite obvious: one cannot make sense of non-Euclidean geometry by interpreting points and lines as those of the Euclidean plane. Similarly, you cannot understand in what way the axiom of choice could fail by interpreting it in classical set theory. You must switch to a different universe, even though you think there isn't one... Of course, this takes some effort, but it's a real eye-opener.

Answer by Pete L. Clark for Choice vs. countable choice

2010-04-30T07:28:24Z

I wish to note that in the comment that prompted this question, I was paraphrasing Kaplansky from memory, not quoting him. Since there is now quite a discussion, people may be interested in the exact quote. Here it is, from Set Theory and Metric Spaces, p.21:

[The context is that he has just given the usual "naive" argument that any infinite set has a countably infinite subset.]

"(I can hear many readers snorting that, without any warning, I have sneaked in the countable axiom of choice. My reply is: guilty as charged. In an account of set theory designed for an apprentice mathematician, I think it is out of place to fuss with the countable axiom of choice. Historical evidence is on my side. It was only when the scrutiny of uncountable sets began that the axiom of choice got placed on the agenda.)"

Answer by Andreas Blass for Choice vs. countable choice

2010-07-04T05:09:43Z

I apologize for writing the following from memory, but I don't have (and won't for a while have) access to the book I want to refer to; I trust that others on MO will correct whatever I mess up here. The book is Gregory Moore's "Zermelo's Axiom of Choice: Its origins, development and influence," and the reason I want to refer to it is not Moore's excellent history of the subject but some letters reprinted at the end of the book. The letters contain a discussion of the axiom of choice, not very long after Zermelo introduced it. They were written by Baire, Borel, Hadamard, Lebesgue, and (I think) one other prominent analyst of that period. If I remember correctly, only Hadamard favored the full axiom of choice; the others wanted only countable choice. Why did they consider countable choice more plausible than full choice? A cynical answer would be that countable choice is needed for lots of results in analysis, including the Baire category theorem (in general complete metric spaces) and the countable additivity of Lebesgue measure. But the reasons actually given in the letters were, to the best of my recollection, rather close to what David Speyer wrote in his answer here.