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
    $\begingroup$ You probably mean "countably infinite". $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – Daniel Hast Sep 25 '12 at 0:44
  • $\begingroup$ Yes. ${}{}{}\:$ $\endgroup$ – user57159 Sep 25 '12 at 0:46
  • 3
    $\begingroup$ 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? $\endgroup$ – Daniel Hast Sep 25 '12 at 1:00
  • 3
    $\begingroup$ @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. $\endgroup$ – Asaf Karagila Sep 25 '12 at 1:00
  • 2
    $\begingroup$ @Daniel: Yes, exactly. Thank you for showing Ricky that you are capable of reading and understanding mathematical words on your own... $\endgroup$ – 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.

  • $\begingroup$ There is also a paper by Halbeisen and Shelah extending this result, I believe. $\endgroup$ – Asaf Karagila Sep 25 '12 at 5:58
  • $\begingroup$ 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. $\endgroup$ – Andrés E. Caicedo Sep 25 '12 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.