7

There is an old result due to Mycielski and Sierpiński, and popularized in a Monthly article by Taylor and Wagon (A Paradox Arising from the Elimination of a Paradox; see also this MO answer), that can be stated as follows: in Solovay's model, one can partition $2^\omega$ into more than $2^\omega$ nonempty disjoint sets. Or if we let LM denote the axiom that “all subsets of $\mathbb{R}$ are Lebesgue-measurable,” then we can state this: ZF + LM proves $|\mathbb{R}| < |\mathbb{R}/\mathbb{Q}|$. Taylor and Wagon refer to this phenomenon as the division paradox.

This result is sometimes used as an argument in favor of the axiom of choice and against LM, but something bothers me about drawing this conclusion. If $A$ and $B$ are sets, then standardly we have the following definition.

We say that $|A|<|B|$ if there is an injection from $A$ to $B$ but no bijection from $A$ to $B$.

But suppose we make the following definition.

W say that $B$ outnumbers $A$ if there is an injection from $A$ to $B$ but no surjection from $A$ to $B$.

In the presence of the axiom of choice, $B$ outnumbers $A$ if and only if $|A|<|B|$, but without the axiom of choice they are not equivalent. As a sanity check on whether outnumbering is a reasonable concept, note that it can be shown that if $C$ outnumbers $B$ and $B$ outnumbers $A$, then $C$ outnumbers $A$. The question I have is this:

In Solovay's model, let $B$ be a partition of $A$ into nonempty disjoint sets. Can $B$ outnumber $A$?

If the answer is no, then I would be inclined to interpret the division paradox as telling us that in the absence of the axiom of choice, our intuitions about cardinalities are unreliable, and we should be using the concept of outnumbering to compare sizes of sets. In particular, the division paradox gives us no compelling reason to reject Solovay's model.

Timothy Chow
  • 78,129

1 Answers1

11

Well, by definition (more or less), if $B$ is a partition of $A$, then there is a surjection from $A$ onto $B$. So it is impossible, in general, for a partition of a set to outnumber that set.

The Division Paradox tells us that our intuition, which usually tells us that injections and surjections tell "the same story" with regards to cardinality, is really reliant on the axiom of choice, in a very significant way.

Note that you don't need to go as far as Mycielski and Sierpinski and the Solovay model, by the way, to get "big partitions" of the real numbers. Given any model of $\sf ZFC$ there is a symmetric extension given by adding Cohen real in which there is a "paradoxical partition" of the reals. (See http://karagila.org/2020/countable-sets-of-reals/ for details.)

bof
  • 11,631
Asaf Karagila
  • 38,140
  • But the real question should be: In Solovay's model, if $A$ is uncountable, is there a partition of $A$ into more than $A$ pieces? (Don't know whether this would be easier to answer if instead of Solovay's model one looks at $L(\mathbb R)$ assuming $\mathsf{AD}$. I would be curious to know, in any case.) – Andrés E. Caicedo Dec 13 '22 at 22:27
  • @Sam As far as I know, it is still open whether the failure of choice implies the existence of sets $A$ admitting a partition into more than $A$ pieces. – Andrés E. Caicedo Dec 13 '22 at 22:28
  • @Sam: Presumably you want to refine that question, since any constant function will do the trick. Presumably you want to say that $f$ lifts to an injective function on $A/{\sim}$ somehow? (But probably that is "too strong" here.) – Asaf Karagila Dec 13 '22 at 22:38
  • 1
    @SamHopkins Just to clarify, I'm not trying to demonstrate that there is something really paradoxical about denying AC. It's almost the opposite. I'm trying to undermine a specific argument that there is something really paradoxical about denying AC. – Timothy Chow Dec 13 '22 at 22:47
  • @TimothyChow: To my understanding, part of the motivation behind the Taylor & Wagon paper was my blog post about how the Division Paradox is an anti-anti-Banach–Tarski-based-anti-AC argument. – Asaf Karagila Dec 13 '22 at 22:49
  • @AsafKaragila What do you mean that "part of the motivation ... was my blog post"? Do you mean that Taylor & Wagon were motivated in part by the desire to respond to your blog post? But your blog post appears to be dated later than the Taylor & Wagon paper, if you're referring to the blog post linked in this answer of yours. – Timothy Chow Dec 13 '22 at 22:59
  • 1
    @TimothyChow: I was told that Stan was following my blog. And I am referring to a much earlier post, probably around 2014 or 2015. Specifically, this and that. – Asaf Karagila Dec 13 '22 at 23:33
  • 1
    @AsafKaragila Got it. So I guess I'm proposing an anti-anti-anti-Banach-Tarski argument here? – Timothy Chow Dec 14 '22 at 01:16
  • 1
    @AndrésE.Caicedo If $A$ is wellorderable, it cannot be partitioned into more than $|A|$ pieces. I guess you meant to ask whether a nonwellorderable uncountable set has such a "paradoxical" partition. I think it is not too hard to give a positive answer in the $L(\mathbb R)$ case for sets that are the surjective image of $\mathbb R$ using the fact that $\mathbb R$ injects into such a set and $\mathbb R$ surjects onto a strictly larger set. – Gabe Goldberg Dec 14 '22 at 02:10
  • @Gabe Oops. Yes, of course, non-well-orderable. – Andrés E. Caicedo Dec 14 '22 at 23:13