3
$\begingroup$

Does there exist an infinite set of cardinality such that it can never be reached by taking power sets of a set with cardinality aleph-null. Please prove your answer, or include a link to a proof. I apologize for any excessively loose terminology, I am new to this subject of different infinities.

$\endgroup$
  • $\begingroup$ Do you know about taking powersets? $\endgroup$ – user59083 May 23 '14 at 1:11
  • $\begingroup$ So many duplicates, I don't know which one to choose from! :( $\endgroup$ – Asaf Karagila May 23 '14 at 1:13
  • $\begingroup$ There is no limit. Given any collection of sets, the power set of its union is a set of size strictly larger than that of all sets in the collection. Of course, we can always say that the class of all ordinals is the limit, or something silly like that. $\endgroup$ – Andrés E. Caicedo May 23 '14 at 1:13
  • $\begingroup$ math.stackexchange.com/questions/linked/5378 $\endgroup$ – Asaf Karagila May 23 '14 at 1:14
  • $\begingroup$ @AndresCaicedo: that argument does not exactly hold when it comes to natural numbers and the successor function: certainly the successor of a number is greater than itself, and yet infinity is still the limit approached. $\endgroup$ – Platonix May 23 '14 at 1:18
6
$\begingroup$

The answer to the question in the title is no: There is no highest cardinality: Given any set, its power set is always larger. In fact, given any collection $I$ of sets, if we take their union and then the power set of the result, we get a set of cardinality larger than that of any set in $I$.

The answer to the question in the body is yes: We need a definition. The hierarchy of beth ($\beth$) numbers is defined by transfinite recursion: First, $\beth_0=\aleph_0$ is the size of the natural numbers. Given $\beth_\alpha$, we define $\beth_{\alpha+1}$ as the size of its power set. Finally, given a limit ordinal $\lambda$, we define $\beth_\lambda$ as the supremum of the $\beth_\beta$ for $\beta<\alpha$, that is, as the size of the union of the set $\{\beth_\beta\mid \beta<\alpha\}$. (Here I am identifying cardinals with sets of ordinals, so for any cardinal $\kappa$, the set $\kappa$ itself has indeed cardinality $\kappa$.) For example, $\omega=\omega_0$ is the smallest (infinite) limit ordinal, and $\beth_\omega=\sup\{\beth_n\mid n\in\mathbb N\}=\bigcup_n\beth_n$.

In terms of this hierarchy, a set has size that cannot be reached by taking repeated power sets of $\mathbb N$ iff its cardinality is $\beth_\omega$ or larger: A set has size not reachable by taking repeated power sets of $\mathbb N$ iff its size is larger than $\beth_0=|\mathbb N|$, $\beth_1=|\mathcal P(\mathbb N)|$, $\beth_2=|\mathcal P(\mathcal P(\mathbb N))|$, etc, that is, iff its size is at least the supremum of the $\beth_n$ (which is precisely what $\beth_\omega$ is). Of course, any larger cardinality (such as $\beth_\omega^+$, $\beth_{\omega+1}$, etc.) is not reached either.

The proof that sets of this size exist requires a modicum of attention: By the axiom of replacement, we can show that the set $\{\beth_n\mid n\in\mathbb N\}$ exists, since this is the image of $\mathbb N$ under the definable map $n\mapsto|\mathcal P^n(\mathbb N)|$. The union axiom ensures now that $\bigcup_n \beth_n$ exists, and this is exactly $\beth_\omega$. The use of replacement is essential, since $V_{\omega+\omega}$ is a model of the theory $\mathsf{ZC}$, Zermelo-Fraenkel without replacement, and in this model any set has size bounded by some iterated power set $\mathcal P^n(\mathbb N)$.

Just about any standard text in set theory should have a proof of this result. I suggest Moschovakis's Notes on set theory. The book also discusses the cumulative hierarchy of the $V_\alpha$, to which the set $V_{\omega+\omega}$ of the previous paragraph belongs. This hierarchy is defined by setting $V_0=\emptyset$, $V_{\alpha+1}=\mathcal P(V_\alpha)$ for all ordinals $\alpha$, and $V_\lambda=\bigcup_{\beta<\lambda}V_\beta$ for all limit ordinals $\lambda$.

Of course, we could change the question and allow instead transfinite iterations of the power set function, so we look not just at $\mathbb N,\mathcal P(\mathbb N),\dots,\mathcal P^n(\mathbb N),\dots$, but we continue the sequence by looking at $\mathcal P^\omega(\mathbb N)=\bigcup_n\mathcal P^n(\mathbb N), \mathcal P^{\omega+1}(\mathbb N)=\mathcal P(\mathcal P^\omega(\mathbb N)),\dots,\mathcal P^\alpha(\mathbb N),\dots$ where the sequence extends over all ordinals $\alpha$. Now the answer to the question is again no: Note that $|\mathcal P^\alpha(\mathbb N)|=\beth_\alpha$. Any set has size bounded by some $\beth_\alpha$. Again, any standard text should explain why this is the case.

$\endgroup$

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.