Axiom of choice, non-measurable sets, countable unions

Question

I have been looking through several mathoverflow posts, especially these ones https://mathoverflow.net/questions/32720/non-borel-sets-without-axiom-of-choice , https://mathoverflow.net/questions/73902/axiom-of-choice-and-non-measurable-set and there still are many questions I would like to ask:

1) According to the first answer of the first post "It is consistent with ZF without choice that the reals are the countable union of countable sets" (and therefore all sets are borel, and hence measurable), however this seems in contrast with the answer to the second post which states that "the existence of a non-Lebesgue measurable set does not imply the axiom of choice" (and therefore it is possible to construct a ZF model without choice where there exists a non-Lebesgue-measurable set). How can these two statements be both right?

2) I can't understand why the axiom of (countable) choice is necessary to prove that a countable union of countable sets is countable. By saying that the sets are countable, I have already assumed the existence of a bijection from every set to the set of natural numbers, in other words, I have indexed the elements of each set. So what is the problem in chosing elements from each set? This relates to the above topic in that if the AC weren't necessary to prove that countable union of countable sets is countable, then "It is consistent with ZF without choice that the reals are the countable union of countable sets" can no longer be correct, since this would imply that in ZF without choice the reals are countable.

I am only a third year math student with no background in set theory (only naive), so please excuse the ignorance. I hope someone can answer me, thank you!

Answer 1

For the first question, let us consider the following statement:

$x\in\mathbb R$ and $x\ge 0$. It is consistent with this statement that:

1. $x=0$,
2. $x=1$,
3. $x>4301$,
4. $x\in (2345235,45237911+\frac{1}{2345235})$

This list can go on indefinitely. Of course if $x=0$ then none of the other options are possible. However if we say that $x>4301$ then the fourth option is still possible.

The same is here. If all sets are measurable then it contradicts the axiom of choice; however the fact that some set is unmeasurable does not imply the axiom of choice since it is possible to contradict the axiom of choice in other ways. It is perfectly possible that the universe of set theory behave "as if it has the axiom of choice" up to some rank which is so much beyond the real numbers that everything you can think of about real numbers is as though the axiom of choice holds; however in the large universe itself there are sets which you cannot well order. Things do not end after the continuum.

That been said, of course the two statements "$\mathbb R$ is countable union of countable sets and "There are non-measurable sets" are incompatible: if $\Bbb R$ is a countable union of countable sets, then there is no meaningful way in which we can have a measure which is both $\sigma$-additive and gives intervals a measure equals to their length; whereas stating that there exists a set which is non-measurable we implicitly state that there is a meaningful way that we can actually measure sets of reals. However this is the meaning of it is consistent relatively to ZF. It means that each of those can exist with the rest of the axioms of ZF without adding contradictions (as we do not know that ZF itself is contradiction-free to begin with.)

As for the second question, of course each set is countable and thus has a bijection with $\mathbb N$. From this the union of finitely many countable sets is also countable.

However in order to say that the union of countably many countable sets is countable one must fix a bijection of each set with $\mathbb N$. This is exactly where the axiom of choice comes into play.

There are models in which a countable union of pairs is not only not countable, but in fact has no countable subset whatsoever!

Assuming the axiom of countable choice we can do the following:

Let $\{A_i\mid i\in\mathbb N\}$ be a countable family of disjoint countable sets. For each $i$ let $F_i$ be the set of injections of $A_i$ into $\mathbb N$. Since we can choose from a countable family, let $f_i\in F_i$.

Now define $f\colon\bigcup A_i\to\mathbb N\times\mathbb N$ defined by: $f(a)= f_i(a)$, this is well defined as there is a unique $i$ such that $a\in A_i$. From Cantor's pairing function we know that $\mathbb N\times\mathbb N$ is countable, and so we are done.

Answer 2

For Question $1$, the assertion "the existence of a non-Lebesgue measurable set does not imply the axiom of choice" means that we cannot prove the full Axiom of Choice from the existence of a non-Lebesgue measurable set. Similarly, we cannot prove the full Axiom of Choice from the assumption of Countable Choice. But we cannot prove Countable Choice in ZF (here I should insert "if ZF is consistent," but won't bother).

There are many assertions that cannot be proved in ZF, can be proved in ZFC, but do not imply the full Axiom of Choice, that is, are strictly weaker than the full Axiom of Choice. The existence of a non-Lebesgue measurable set is just one of them. So you can think of an axiom that asserts the existence of a non-measurable set as intermediate in strength between making no "choice" assumptions at all, and asserting the full Axiom of choice.

Added: The following Wikipedia aricle has a nice list of assertions that are equivalent to the Axiom of Choice, and also a nice list of assertions that cannot be proved in ZF, can be proved in ZFC, but do not imply the Axiom of Choice.

Answer 3

(1) The statement

It is consistent with ZF without choice that the reals are the countable union of countable sets

does not mean that in ZF without choice, all subsets of $\mathbb R$ must be measurable. It just says that in that case, "all sets are measurable" is one possibility, possibly among many. Therefore it does not conflict with

the existence of a non-Lebesgue measurable set does not imply the axiom of choice

Taken together, these two statements just means that in ZF without choice there can either be nonmeasurable sets, or not be any nonmeasurable sets. Both possibilities are consistent.

(2) If you have a countable family of countable sets, all you know that for each set in the family there exist one or more bijections between that set and the natural numbers. As long as you're only looking at one of them, you can just choose one of these bijections. However, if you want to prove that the union of the family is countable, you need to choose a particular bijection for each of the sets simultaneously, and you need (countable) choice to do that.

Answer 4

On countable choice and countable unions of countable sets. Let $ C$ be a countably infinite family of countable sets. Then there exists a bijection $F$ with domain $\Bbb N$ such that $C=\{f(n):n\in \Bbb N\}$ and that for each $n\in \Bbb N$ the set $G(n)$ of injections from $f(n)$ into $\Bbb N$ is not empty.

The problem with "choosing" elements from $\cup C$ is that in general $G(n)$ has more than one member, and we need a way to specify an infinite sequence $(g_n)_{n\in \Bbb N}$ where each $g_n\in G(n).$

With Countable Choice we can assert the exists a function $H:\Bbb N\to \cup_{n\in \Bbb N}G(n)$ such that $H(n)\in G(n)$ for each $n\in \Bbb N.$ For any such $H$ the sequence $(H(n))_{n\in \Bbb N}=(g_n)_{n\in \Bbb N}$ exists and we can use it to make selections from $\cup C.$ But without Countable Choice we are stuck.

One very counter-intuitive violation of Countable Choice, that is still consistent with $ZF,$ is that there is a countably infinite $C$ where each member of $C$ has exactly $2$ members, and no infinite subset of $\cup C$ can be well-ordered, and therefore $\cup C$ and $\Bbb N$ are cardinally non-comparable.

A set $\cup C$ that cannot be well-ordered, where $C$ is a countable family of $2$-member sets, is called a sock set, or a Russell sock set. Bertrand Russell said "The axiom of choice is needed for socks but not for shoes." For matched pairs of shoes we can define a sequence $(g_n)_n$: Let $g_n(P)$ be the left shoe of the pair $P. $