4
$\begingroup$

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?

$\endgroup$
6
  • 3
    $\begingroup$ 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.) $\endgroup$
    – Noah Schweber
    Feb 15, 2017 at 17:05
  • $\begingroup$ Noah Schweber: I already feel I am not nearly familiar with ZF without choice... $\endgroup$
    – nombre
    Feb 15, 2017 at 17:08
  • 1
    $\begingroup$ @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. :) $\endgroup$
    – Asaf Karagila ♦
    Feb 15, 2017 at 17:09
  • $\begingroup$ @AsafKaragila True, but I find it's still a useful heuristic in many cases (like this one :P). $\endgroup$
    – Noah Schweber
    Feb 15, 2017 at 17:11
  • 1
    $\begingroup$ Oh, I definitely agree about that. I was just being nitpicky... I mean, a mathematician. :P $\endgroup$
    – Asaf Karagila ♦
    Feb 15, 2017 at 17:12

1 Answer 1

Reset to default
5
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ You guys are quick! Thanks, I'll look it up right now. $\endgroup$
    – nombre
    Feb 15, 2017 at 17:09
  • $\begingroup$ 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. $\endgroup$
    – Asaf Karagila ♦
    Feb 15, 2017 at 17:21
  • $\begingroup$ See the paper on Halbeisen's page here. $\endgroup$
    – Asaf Karagila ♦
    Feb 15, 2017 at 17:21
  • 1
    $\begingroup$ It's not we guys, it's @AsafKaragila ;-) I knew the answer (+1) would have been his before opening the post. $\endgroup$
    – Andreas Caranti
    Feb 15, 2017 at 17:23
  • 1
    $\begingroup$ @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. $\endgroup$
    – Asaf Karagila ♦
    Feb 15, 2017 at 17:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .