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
    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?2012-09-25
  • 0
    Yes. ${}{}{}\:$2012-09-25
  • 0
    @Daniel: I have added the needed line, I suppose. I don't know too much about constructive set theory (I do know that it comes in several flavours, none of which I am knowledgeable about). However the **definition** of finite in modern mathematics is being strictly less than $\aleph_0$. Without choice you can have infinite sets without a countably infinite subset, those are called infinite Dedekind-finite sets, but those are not finite in the same sense as we usually mean.2012-09-25
  • 0
    After the edit I changed my upvote to a downvote; finiteness is defined as $\hspace{2 in}$ being equinumerous to a member of $\omega$. $\:$2012-09-25
  • 0
    @Ricky: And... the edit says what? I merely edited to add that being finite is **by definition** being equinumerous to a **finite** cardinal. Allow me to remind you, if $k<\omega$ then $|k|<\aleph_0$ and $k\in\omega$. But hey, do as you like...2012-09-25
  • 0
    The edit says "if $|A| < \aleph_0$ then $A$ is finite _by definition of finite_". $\:$ You should read your edit, since you actually edited to say that being finite is by definition being equinumerous to a cardinal that is smaller than $\omega$. $\;\;$2012-09-25
  • 0
    @Ricky: I don't get your point. Do you mean to say that there are **other** cardinals other than finite ordinals which are smaller than $\omega$? You need to review your set theory basics if you say that... That is the concrete definition of finite. If you wish I can instead use the Tarski definition of finite and prove the equivalence, but this is still not the point. Can you exhibit a proof that I am wrong here?2012-09-25
  • 0
    I mean to say that it's not incredibly obvious that there aren't any such cardinals. $\:$ (In particular, the OP couldn't see how ZF proves that there aren't any.) $\;\;$2012-09-25
  • 3
    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?2012-09-25
  • 3
    @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.2012-09-25
  • 2
    @Daniel: Yes, exactly. Thank you for showing Ricky that you are capable of reading and understanding mathematical words on your own...2012-09-25
  • 0
    @Ricky: You have some excellent questions (both here and on MO) and none of which are "Please feed me with a spoon all the definitions and the proofs", why do you insist that this rather simple observation is too hard for anyone who might be asking this question to make? And if it were, why would you speak for them? I am asking *because* I have quite a respect for you, and not because I belittle you in any way, and this behavior on the comments rather surprises me.2012-09-25
  • 0
    @Asaf re "But this is...": I think by "this" you mean yours (i.e., $|A|<\aleph_0$); in which case I simply disagree. In particular, for weaker systems that don't prove the equivalence (such as intuitionistic set theory; I don't know if Kripke-Platek proves the equivalence), I believe that "equinumerous to a finite ordinal" works better (where the finite ordinals are the members of $\omega$), and that thus that is the definition or finiteness, whereas it is a theorem that being smaller than $\aleph_0$ is equivalent to being finite.2012-09-25
  • 0
    @Asaf re "You have some": I don't, I just see from Daniel's first comment that he _wasn't_ making that observation, and I spoke for him because I thought it might make things go faster. I just removed the downvote in light of your subsequent edit. (I know this wasn't about the reputation points for you.)2012-09-25
  • 0
    @Ricky: This is a matter of principle. I hate it when people downvote for no *good* reason. The fact that the OP can use their own brain and not being spoonfed is a bad reason to downvote, especially after the OP proved this point. Furthermore at no point this answer was *wrong* in any way.2012-09-25
  • 0
    You stated that it is provable in ZF that no set has a power set that's countably infinite and not that it's provable in ZFC. You're right that it's provable in ZF but you didn't actually prove it. You used the assumption that for any two sets, one is the same size as or smaller than the other which in ZF is equivalent to the axiom of choice.2017-12-11
  • 0
    @Timothy: Huh? Where?2017-12-11
  • 0
    You need to axiom of choice to readily show that if A is infinite, its cardinality is greater than or equal to aleph-naught and therefore that the cardinality of its power set is greater than aleph-naught.2017-12-11
  • 0
    @Timothy: Where am I using this?2017-12-11
  • 0
    @Timothy: If you ***ASSUME*** that the power set of $A$ is countable, then $A$ is countable (or finite). You don't need choice to prove that $A$ has an injection into its power set, or that anything with an injection into a countable set is countable (or finite).2017-12-11
  • 0
    Sometimes people write an incomplete proof that the reader can figure out from reading how to complete. In the case of this answer, there is no obvious way to complete the proof in ZF alone that no set has a countably infinite power set without making the answer completely different. Maybe there is a way that I didn't think of. It is provable in ZFC but not in ZF that all infinite sets have a countably infinite subset. It's pretty hard to show that if a set is infinite but doesn't have a countably infinite subset, its power set isn't countably infinite.2017-12-11
  • 0
    @Timothy: It's good that you are lecturing me on set theory, or how to write proofs. The proof is correct, you are absolutely wrong in your comment, but since you're not willing to learn, there's no point in continuing this discussion. You've voted, I've explained your mistake, you don't care, let's move on.2017-12-11
  • 0
    Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/70073/discussion-between-timothy-and-asaf-karagila).2017-12-11
  • 0
    @Timothy: I hate the chat feature here. There should be a room for set theory and logic. Try asking there, maybe someone can help you.2017-12-11
  • 0
    You're right. I finally figured out how to complete the proof in your answer.2017-12-12
  • 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
    There is also a paper by Halbeisen and Shelah extending this result, I believe.2012-09-25
  • 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