How does $\neg$AC lead to a partition of the reals with more parts than reals?

Question

I heard a while ago that the negation of the axiom of choice leads to the existence of a partition of the real numbers, into more partitions then there are real numbers.

I found this post which says

You don't want non-measurable sets? This means that you can partition the real numbers into strictly more parts than real numbers, but no part is empty. Yes, let that sink for a moment: you can partition the reals into more parts than numbers!

I looked for a proof of this online, but could only find the result mentioned. A couple referenced this link, but it's locked behind a paywall.

So, why does the axiom of choice lead to this counterintuitive result?

Answer 1

This is called the "Division Paradox". For a nice exposition, see A Paradox Arising from the Elimination of a Paradox by Alan D. Taylor and Stan Wagon. (The link provided here is to a copy of the paper hosted on Stan Wagon's personal website, rather than to the copy behind a paywall in the link in the OP).

It may be helpful to spell out what is meant by the intuitive description "you can partition the real numbers into strictly more parts than real numbers". It means there is a partition $X$ of $\mathbb{R}$ (so the elements of $X$ are non-empty subsets of $\mathbb{R}$ which are pairwise disjoint and whose union is $\mathbb{R}$), such that $|\mathbb{R}|<|X|$. And the cardinal inequality means that there is an injective function $\mathbb{R}\to X$ but no bijective function $\mathbb{R}\to X$.

The approach taken by Taylor and Wagon (which is different from the approach in spaceisdarkgreen's answer) is to show that $|\mathbb{R}|<|\mathbb{R}/\mathbb{Q}|$ in ZF+LM, which is ZF set theory (without choice) plus the assumption that all sets of reals are Lebesgue measurable. Here $\mathbb{R}/\mathbb{Q}$ is the group-theoretic quotient, so the elements of $\mathbb{R}/\mathbb{Q}$ are the additive cosets of $\mathbb{Q}$, which partition $\mathbb{R}$.

The injective function $\mathbb{R}\to \mathbb{R}/\mathbb{Q}$ is nice and explicit. First, put $\mathbb{R}$ into bijection with $(0,1)$. Then map $(0,1)$ into $\mathbb{R}/\mathbb{Q}$ by $.d_1d_2d_3d_4\dots\mapsto .d_1d_1d_2d_1d_2d_3d_1d_2d_3d_4\dots$. The point is the images of distinct reals lie in different cosets of $\mathbb{Q}$, since the difference between their decimal expansions is a non-repeating decimal.

In the other direction, one observes that if there were a bijection $\mathbb{R}\to \mathbb{R}/\mathbb{Q}$, then we could transfer the linear order on $\mathbb{R}$ to a linear order on $\mathbb{R}/\mathbb{Q}$ and use this linear order to extract a non-Lebesgue-measurable subset of $\mathbb{R}$. Like in spaceisdarkgreen's answer, this is the "hard part".

Answer 2

One way to generate the paradox is:

1. $\sf ZF,$ proves that there is a surjection $\mathbb R\to \omega_1$ (take any set of rationals that is well-ordered under the usual ordering to its order type (and anything not well-ordered to zero) and identify $P(\mathbb Q)$ with $\mathbb R$.)
2. It's consistent with $\sf ZF$ that there is no injection $\omega_1\to \mathbb R$ (And thus this implied by certain principles that violate $\sf AC$.. "all sets of reals are Lebesgue-measurable" happens to be an example.)

A surjection $\mathbb R\to \omega_1$ is a partition of $\mathbb R$ into $\omega_1$ sets. By "spliting $\mathbb R$ in half" we can get a surjection $\mathbb R\to \mathbb R\sqcup\omega_1,$ and thus a partition of $\mathbb R$ into $|\mathbb R|+\aleph_1$ sets.

We have $|\mathbb R|\le |\mathbb R|+\aleph_1$, but since $\omega_1$ doesn't inject into $\mathbb R,$ we can't have $|\mathbb R|\ge |\mathbb R|+\aleph_1.$ Thus $|\mathbb R|< |\mathbb R|+\aleph_1$.

So we have partitioned $\mathbb R$ into strictly more sets than $|\mathbb R|.$

The "hard part" for getting to the quoted result - which I've omitted - is to show that if all sets of reals are Lebesgue-measurable, then there is no injection $\omega_1\to \mathbb R.$

(Note: Though this method works fine for showing the division paradox in certain situations where choice is violated (e.g. it follows pretty easily from "the reals are a countable union of countable sets" or even "every set of reals has the perfect set property"), the "hard part" is actually extremely hard for "every set of of reals is Lebesgue-measurable"... the other answers are better for this specific case.)

Answer 3

For a slightly different approach from the other two answers.

Theorem. Suppose that $\{A\subseteq\Bbb R\mid |A|=\aleph_0\}$ can be linearly ordered, then there is a set of real numbers which is not Lebesgue measurable.

First notice that $\Bbb R$ injects into $\{A\subseteq\Bbb R\mid|A|=\aleph_0\}$. If $x\in\Bbb R$ is irrational map it to $\Bbb Q\cup\{x\}$, otherwise map it to $\Bbb Q\setminus\{x\}$. So the set is provably, at least as large as $\Bbb R$.

Now, by cardinal arithmetic, we have that $2^{\aleph_0}=2^{\aleph_0\cdot\aleph_0}=(2^{\aleph_0})^{\aleph_0}$. Therefore the set $\Bbb{R^N}$, of all infinite sequences of real numbers, has the same cardinality as $\Bbb R$. Now, if $f\colon\Bbb{N\to R}$ is any function, if the image of $f$ is infinite, then it is a countably infinite set.

So, we can map $f$ to its image if that image is finite, and if not, just map it to $\Bbb N$ itself. Since $A$ being a countable set means that there is a bijection $f\colon\Bbb N\to A$, the function we have just described is a surjection from $\Bbb R$ onto $\{A\subseteq\Bbb R\mid|A|=\aleph_0\}$, which of course defines a partition of $\Bbb R$.

Finally, if that all sets are Lebesgue measurable, the latter set cannot be linearly ordered. In particular, it is impossible to find an injection from it into the real numbers (since that would allow us to define a linear ordering). So that partition must be strictly larger than $\Bbb R$.