Countable sets of reals

One of the classic results of Sierpinski is that if there are as many countable sets of reals as there are reals, then there is a set which is not Lebesgue measurable. (You can find a wonderful discussion on MathOverflow.)

This is fact is used in the paradoxical decomposition theorems (which I often enjoy bringing up as a counter-argument to bad arguments that the Banach–Tarski paradox implies we need to accept that all sets are measurable as an axiom):

Theorem. If all sets of reals are Lebesgue measurable, then there is a partition of the real numbers into more sets than real numbers.

Proof. There is a bijection between \(\RR\) and \(\RR^\omega\), and there is a surjection from \(\RR^\omega\) onto \([\RR]^\omega\), given by mapping each sequence to its range (or to \(\QQ\) if the range is finite). If all sets of reals are Lebesgue measurable, then by Sierpinski's theorem it has to be that \([\RR]^\omega\) must have a strictly larger cardinality than \(\RR\). To see that, note that \(\RR\) maps into \([\RR]^\omega\) by mapping \(r\) to \(\{r\}\cup\QQ\) if \(r\) is irrational, or to \(\QQ\setminus\{r\}\) otherwise. So the cardinality of \([\RR]^\omega\) is at least as large as that of \(\RR\).

The surjection, composed onto the bijection between \(\RR\) and \(\RR^\omega\) induces a partition of \(\RR\) into more parts than real numbers, as wanted. \(\ \square\)

Okay, that's great. We also get from this that the Partition Principle implies the existence of non-measurable sets. And I'd like to remind you, in case you're not my three usual readers who are familiar with \(\Par\), that it is the statement that if we partition a set \(A\), then the partition can be mapped into \(A\). In other words, if \(f\colon A\to B\) is a surjective function, then there is an injective function from \(B\) into \(A\).

In fact, we can write the following hierarchy of principles:

1. The Axiom of Choice: if \(f\colon A\to B\) is a surjection, then there is an injective \(g\colon B\to A\) such that \(f\circ g=\id_B\).
2. The Partition Principle: if \(f\colon A\to B\) is a surjection, then there is an injective \(g\colon B\to A\).
3. The dual Cantor–Bernstein Theorem: if \(f\colon A\to B\) and \(g\colon B\to A\) are surjective functions, then there is \(h\colon A\to B\) which is a bijection.
4. The Weak Partition Principle: if \(f\colon A\to B\) is a surjection and \(g\colon A\to B\) is an injection, then there is \(h\colon A\to B\) which is a bijection.

Easily (1) implies (2), and easily (2) implies (3), since we can replace the surjections by injections and appeal to the usual Cantor–Bernstein (whose proof requires no use of choice, at all). And of course that (3) implies (4), since the injection, \(g\), can be reversed to a surjection in the other direction. All the reverse implications are open, by the way. We know absolutely nothing about these things.

Okay, why are we talking about this now? Well, there is an injection from \(\RR\) into \([\RR]^\omega\), and there is a surjection from \(\RR\) onto \([\RR]^\omega\). So in fact, we found a counterexample to the Weak Partition Principle, or rather, we proved that \(\axiom{WPP}\) implies the existence of a non-measurable set.

That's great. And we use these examples a lot as off-the-cuff strangeness. But having all sets Lebesgue measurable means that there is an inaccessible cardinal, or that we gave up on \(\DC\). Worse: sometimes people appeal to \(\AD\) for this sort of result. But why? There's no reason to do that. I mean, not if you want to talk about surjections and injections, anyway.

Theorem. Suppose that \(V\models\ZFC\). There is a symmetric extension given by a Cohen forcing, in which \(\DC\) holds, and there is no bijection between \(\RR\) and \([\RR]^\omega\).

Proof. Let \(\kappa\) denote \((2^{\aleph_0})^V\), and if simplicity is your game, you might as well assume \(\kappa=\aleph_1\), although this is strictly unnecessary. The idea is that we are going to add real numbers such that there is a surjection from \(\RR\) onto \(\kappa^+\), or in fact onto any ordinal your heart desires, such that every fiber is countable, and there is no injection from \(\kappa^+\) into \(\RR\).

This will ensure that \(\kappa^+<[\RR]^\omega\), but \(\kappa^+\nleq\RR\), which therefore implies the cardinality of \([\RR]^\omega\) is strictly greater. As a bonus, we also get to preserve \(\DC\), and in fact \(\DC_\kappa\).

Let \(\PP\) be \(\Add(\omega,\kappa^+\times\omega)\), that is, add a \(\kappa^+\)-sequence of countable sets of Cohen reals. Our automorphisms are going to be induced by permutations of \(\kappa^+\times\omega\) which do not change the \(\kappa^+\)th coordinate. That is, each countable fiber gets permuted independently, and the \(\kappa^+\)-sequence is fixed (not just the set!).

For \(E\subseteq\kappa^+\) let \(\fix(E)\) denote the group of permutations (having the above property) such that \(\pi\restriction E\times\omega=\id\). We will generate our filter of subgroups from \(\{\fix(E)\mid \sup E<\kappa^+\}\). We can also think about this as a product of symmetric systems, with finite support, where each one is \(\Add(\omega,\omega)\), with the full permutation group of \(\omega\) acting on the coordinate, and the improper filter of subgroups; with the filter generated by bounded supports.

This filter is \(\kappa^+\)-complete, and \(\PP\) is ccc, so \(\DC_\kappa\) is preserved. In the more general case, we add \(\lambda\) Cohen reals (or rather, a \(\lambda\)-sequence of countable sets of Cohen reals), then we get \(\DC_{<\cf(\lambda)}\).

It is a standard argument to verify that all the new reals are symmetric (indeed, not just the Cohen reals, all the new reals), and that the same holds for the countable sets and the sequence. But suppose that there was a symmetric name \(\dot f\) for an injection from \(\kappa^+\) to \(\RR\).

Well, such injection defines, trivially, a set of ordinals. By homogeneity arguments, if \(\dot A\) is this set of ordinals, and \(E\) is a bounded subset of \(\kappa^+\) such that \(\fix(E)\subseteq\sym(\dot A)\), then \(p\forces\check\xi\in\dot A\) if and only if \(p\restriction E\forces\check\xi\in\dot A\). But by decoding argument, this means that values (including the reals themselves) of the function \(\dot f\) are decided by conditions whose domains are subsets of \(E\times\omega\).

By cardinality arguments, that means there is some condition which decides \(\kappa^+\) different values. But this is impossible, as that implies that \(\RR^{V[G\restriction E]}\) has size \(\kappa^+\). \(\ \square\)

And so this finishes this proof. But now we can ask, what happens when we only add a \(\kappa\)-sequence of countable sets (with bounded supports, of course)? In this case it is easy to check that choice fails since the surjection defined using this new sequence does not split. But there is an injection from \(\kappa\) into \(\RR\). So, does the Weak Partition Principle for \(\RR\) holds?

Who knows...