Existence in ZF of a set with countable power set

Solution 1:

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.

Solution 2:

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.