10
$\begingroup$

Is it consistent with ZF for there to exist a set $S$ such that the power set $P(S)$ is countable? If so, what is the weakest form of the axiom of choice needed to prove that no such set exists?

  • 1
    You probably mean "countably infinite".2012-09-27

2 Answers 2

14

No. It is impossible in already in ZF.

Recall that a set $A$ is finite if and only if there exists a finite ordinal $k$ and a bijection between $A$ and $k$. In turn this implies that a set $A$ is finite if and only if $|A|<\aleph_0$ (namely there exists an injection from $A$ into $\omega$, but there is no bijection between the sets).

Suppose that $A$ is a set such that $P(A)$ is countably infinite. It is trivial that $|A|\leq|P(A)|$, and by Cantor's theorem the inequality is sharp.

However if $|A|<\aleph_0$ then $A$ is finite by definition of finite, and therefore $P(A)$ is finite as well.

  • 0
    @Timothy: The proof *is* complete.2017-12-12
4

Asaf has answered the question. Let me just add that even more is true: Provably in $\mathsf{ZF}$, If $A$ is a set, and $\aleph_0\le|\mathcal P(A)|$, then in fact $|\mathbb R|=2^{\aleph_0}\le|\mathcal P(A)|$. This is a result of Kuratowski. What one proves is that from an injection from $\mathbb N$ into $\mathcal P(A)$, an infinite sequence of pairwise disjoint subsets of $A$ can be obtained (this takes some work), so there is a surjection from $A$ onto $\mathbb N$, and from this we easily get an injection of $\mathcal P(\mathbb N)$ into $\mathcal P(A)$.

It may well be the case that we have an infinite set $A$ such that $\aleph_0\not\le|\mathcal P(A)|$, though we always have $\aleph_0\le|\mathcal P(\mathcal P(A))|$ for $A$ infinite.

  • 0
    Hi @AsafKaragila. Lorenz and Saharon deal with the relation between the sizes of $\mathcal P(A)$, $\mbox{Fin}(A)$, $\mbox{Seq}(A)$ and $\mbox{Seq}^{1\mbox{-}1}(A)$, that is, the power set of $A$, the collection of its finite subsets, the collection of finite sequences from $A$, and the collection of finite injective sequences. It is a nice paper. Part of their results is a direct extension of results of Specker, but they also have to deal with some (finite) combinatorics and number theory. Lorenz has some extensions and variants on his page.2012-09-25