# A strong Cantor theorem without choice

Let $X$ be an infinite set. Can one prove in ZF (without choice, and with finiteness defined as being equipotent to a finite ordinal) that the set $\mathfrak{P}_{< \omega}(X)$ of all finite subsets of $X$ cannot be mapped onto the set $\mathfrak{P}(X)$ of all subsets of $X$?

If not, does countable choice suffice?

• An interesting near-miss: if $X$ is amorphous, then two copies of $\mathfrak{P}_{<\omega}(X)$ can map onto $\mathfrak{P}(X)$, since every subset of an amorphous set is either finite or cofinite. (Incidentally, the fact that even amorphous sets don't immediately provide a counterexample suggests to me that this may, surprisingly!, be provable in ZF alone.) Feb 15, 2017 at 17:05
• Noah Schweber: I already feel I am not nearly familiar with ZF without choice... Feb 15, 2017 at 17:08
• @Noah: Indeed, this is a theorem. Although truth be told, not everything that cannot be contradicted by an amorphous set can be provable. For example, every filter on an amorphous set can be extended to an ultrafilter. :) Feb 15, 2017 at 17:09
• @AsafKaragila True, but I find it's still a useful heuristic in many cases (like this one :P). Feb 15, 2017 at 17:11
• Oh, I definitely agree about that. I was just being nitpicky... I mean, a mathematician. :P Feb 15, 2017 at 17:12

## 1 Answer

It is provable that $\mathcal P_\omega(X)$ is strictly smaller than $\mathcal P(X)$, but it is consistent that there is a surjection still.

Lorenz Halbeisen and Saharon Shelah, Consequences of arithmetic for set theory, J. Symbolic Logic 59 (1994), no. 1, 30--40.

• You guys are quick! Thanks, I'll look it up right now. Feb 15, 2017 at 17:09
• Oops! I looked at the wrong paper, and I misread the result. It turns out to be consistent, although the injection-based order is always strict. I've amended my answer. Feb 15, 2017 at 17:21
• See the paper on Halbeisen's page here. Feb 15, 2017 at 17:21
• It's not we guys, it's @AsafKaragila ;-) I knew the answer (+1) would have been his before opening the post. Feb 15, 2017 at 17:23
• @nombre: It's a partial answer, though. The role of countable choice is interesting here. The proof relies heavily on the fact that the construction is "a finite support construction". So doing the same with countable support (hence obtaining countable choice, and in fact DC) might give us that countable subsets can be mapped onto the power set, but not necessarily the finite subsets. So I'm not sure yet whether or not this is actually consistent with countable choice. So I wouldn't hurry to accept it just yet. Feb 15, 2017 at 17:27