# Existence in ZF of a set with countable power set

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?

-
You probably mean "countably infinite". –  Stefan Smith Sep 27 '12 at 0:52

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.

-
Thanks for the answer. The part I'm not sure about is whether it requires some form of the axiom of choice to prove that any cardinal strictly smaller than $\aleph_0$ is finite. For example, I've heard of the notion of subcountable sets in constructive mathematics; are things like that impossible in standard set theory even without the axiom of choice? –  Daniel Hast Sep 25 '12 at 0:44
Yes. ${}{}{}\:$ –  Ricky Demer Sep 25 '12 at 0:46
I think I understand now. Since the natural numbers are already well-ordered, it doesn't require the axiom of countable choice to prove that any subset of $\mathbb{N}$ is either finite or in bijection with $\mathbb{N}$, right? –  Daniel Hast Sep 25 '12 at 1:00
@Ricky: But this is THE DEFINITION OF BEING FINITE in ZF. I did not say "has no countably infinite subset", and I did not say "does not have a surjective function onto $\omega$". I said equivalent to a finite ordinal. I suggest that you stop thinking for the OP and let the OP think for himself/herself. Your downvote is confusing and if I were a non-expert I would be baffled by this discussion in the comments, especially since both of us (I hope) know that the definition of finite is being equipotent with a finite ordinal. –  Asaf Karagila Sep 25 '12 at 1:00
@Daniel: Yes, exactly. Thank you for showing Ricky that you are capable of reading and understanding mathematical words on your own... –  Asaf Karagila Sep 25 '12 at 1:00

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.

-
There is also a paper by Halbeisen and Shelah extending this result, I believe. –  Asaf Karagila Sep 25 '12 at 5:58
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. –  Andres Caicedo Sep 25 '12 at 6:30