3
$\begingroup$

Natural numbers have an operation of incrementation defined on them. For every natural number $n+1$ is a bigger number. Also we can obtain all natural numbers from 0 by way of incrementation.

Similarly for infinite cardinals starting with $\aleph_0$ we have the power-set. Power-set of a set has a greater cardinality creating an "infinity of infinites".

My question is: are there cardinalities which cannot be obtained from the power-set operation?

$\endgroup$
  • $\begingroup$ See: Ordinal numbers $\endgroup$ – Don Larynx Nov 22 '13 at 6:22
  • $\begingroup$ Generally the $n{+}{+}$ syntax from programming is not used in mathematics. $\endgroup$ – Asaf Karagila Nov 22 '13 at 9:43
  • $\begingroup$ I have seen it in Terrence Tao´s book Analysis I. (Which by the way is very good.) $\endgroup$ – Adam Nov 22 '13 at 12:28
  • $\begingroup$ Also, while I understand that it might not be standard practice, I would advocate to use it in preference to n+1 as being different from addition it makes clear that incrementation is a more fundamental operation than addition. $\endgroup$ – Adam Nov 22 '13 at 12:38
7
$\begingroup$

Yes!

First and foremost, although the power set operation gives a larger cardinality, it need not give the next larger cardinality (I'm assuming that the cardinals are well-ordered here, which follows from ZFC). This is the heart of the Continuum Hypothesis: the reals are essentially the power set of the naturals, are there sets of reals of intermediate cardinality?

Second of all, we have the notion of limit cardinals. The following is a chain of sets of increasing cardinality:

$$\aleph_0, \mathcal{P}(\aleph_0), \mathcal{P}(\mathcal{P}(\aleph_0)), \dots$$

But what's the cardinality of their union? It's bigger than all of them, but it's not equinumerous with the power set of anything smaller than it. (Can you see why?)

The remaining question is, can we climb up past all the cardinals via repeated applications of power set and union? This leads to the notion of inaccessible cardinals. These are cardinals $\kappa$ which are larger than the power set of anything smaller cardinal $\lambda < \kappa$, and larger than any union of less than $\kappa$ many sets each of which has cardinality less than $\kappa$. That is:

  • If $\lambda < \kappa$ and $\mu_i < \kappa, \forall i < \lambda$, then $\left|\bigcup_{i<\lambda}\mu_i\right| < \kappa$

The existence of such inaccessible cardinals is not provable from ZFC (unless ZFC is inconsistent). In fact, the hypothesis "there exists inaccessible cardinals" is so strong that ZFC + "there exist inaccessibles" implies the consistency of ZFC! This is of course strictly stronger, because ZFC alone cannot prove its own consistency, a la Godel. Inaccessible cardinals are one type of the famed large cardinals.

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

Yes. If you start with any set $A$, and consider the sequence $A,\mathcal P(A),\mathcal P(\mathcal P(A)),\dots$, its union $$ \bigcup_n\mathcal P^n(A) $$ is an infinite set whose cardinality is not the size of any power set. This is true even if $A$ is finite, in which case the resulting set has the same size as the natural numbers. If $A=\mathbb N$, the size of the resulting set is denoted $\beth_\omega$.

One way of checking that these sets do not have the size of power sets is to note that they have cofinality $\omega$, meaning that they are the union of countably many pieces of smaller size. A theorem of König tells us that for such any cardinality $\kappa$ made up of countably many smaller pieces, $\kappa^{\aleph_0}>\kappa$. But the cardinality $2^\tau$ of a infinite power set always satisfies $(2^\tau)^{\aleph_0}=2^\tau$.

One can avoid using König's result, as follows: If $B$ is larger than all $\mathcal P^n(A)$, then $B$ is at least as large as their union $U$, so if $B$ is strictly smaller than the union (if, for example, $U$ has the same size as $\mathcal P(B)$), then $B$ must be less than or equal in size to some $\mathcal P^n(A)$, and therefore $\mathcal P(B)$ has size at most the size of $\mathcal P^{n+1}(A)$, which is strictly smaller than $U$.

Still, this uses choice (in the form: Any two cardinalities are comparable). It would be nice(r) to find an argument that avoided any use of choice.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I thought, you could argue like this: suppose our union of sets is a power set of a smaller set, then this power set must be in our list A,P(A),P(P(A)),... and consequently we arrive at a nonsensical result that that a union of a set A and infinitely many other sets is equal to A. Is there anything wrong with this deduction? $\endgroup$ – Adam Nov 22 '13 at 18:28
  • $\begingroup$ This does not quite work, because $A,\mathcal P(A),\dots$ is not necessarily an exhaustive list of the cardinalities below their union, even if we restrict to cardinalities larger than $A$. What you have is that if $B$ has size strictly smaller than $\bigcup_n\mathcal P^n(A)$, then for some $n$, $B$ has size less than or equal to $\mathcal P^n(A)$ (but this needs some argument), so $\mathcal P(B)$ is strictly smaller than the union. [Of course, all of this is easy since choice gives us that any two cardinals are comparable.] $\endgroup$ – Andrés E. Caicedo Nov 22 '13 at 18:52
  • $\begingroup$ You rang? :-) I'm not quite what you mean by the use of choice. Have we passed to cardinals, or are we still talking about $\aleph$ numbers? $\endgroup$ – Asaf Karagila Nov 23 '13 at 9:26
  • $\begingroup$ @AsafKaragila Arbitrary cardinalities. A question is: Can it ever be the case that $\bigcup_n\mathcal P^n(A)$ is equipotent to a power set? (And if so, is it possible if in addition each $\mathcal P^n(A)$ is well-orderable?) $\endgroup$ – Andrés E. Caicedo Nov 23 '13 at 16:24
  • $\begingroup$ @Andres: I have some thoughts on the topic, but they are so premature that I would probably want to work them a little bit first. But I'll send you an email later this week. $\endgroup$ – Asaf Karagila Nov 23 '13 at 17:17
2
$\begingroup$

Yes. Here is an argument that does not require cofinality.

Suppose that the Generalized Continuum Hypothesis holds true. In that case, $\aleph_{\alpha+1}=2^{\aleph_\alpha}$. Thus, in particular, $\aleph_{n+1}=2^{\aleph_n}$ for each $n\in \omega$. Now consider $\aleph_\omega$. Clearly it cannot be a 2 to some cardinal that came before it, because we know that each of those were another aleph with subscript natural number.

On the other hand, if the generalized continuum hypothesis is false, there is some least cardinal $\alpha_\alpha$ such that $\aleph_{\alpha+1}\neq 2^{\aleph_\alpha}$. But since $\aleph_\alpha$ is the smallest such cardinal, every cardinal before it with an immediate predecessor is the power of that immediate predecessor. Thus, $\aleph_{\alpha+1}$ is not a power.

Thus, no matter whether the Generalized Continuum hypothesis holds or not, we find that there are such cardinals.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ There is a distinction between 'weak' inaccessible cardinals and 'strong' inaccessible cardinals. In the first case, a weakly inaccessible cardinal is one that cannot be reached by repeated successions, i.e. $\aleph_\omega$. To be strongly inaccessible is defined as being unreachable by taking power sets. However, this is in the sense that for all $\lambda<\kappa$, $2^\lambda <\kappa$. Thus, it is not equivalent to $\kappa$ to being equal to a power set. However, if $\kappa$ is a strongly inaccessible cardinal, then it is indeed not a power set of some smaller cardinal. $\endgroup$ – Hayden Nov 22 '13 at 6:45
  • $\begingroup$ Hayden, you are talking about limit cardinals versus strong limit cardinals. Inaccessibility is something else. $\endgroup$ – Andrés E. Caicedo Nov 22 '13 at 7:53
  • $\begingroup$ I was under the impression that inaccessibility was about the existence of uncountable regular cardinals that were either weak limit cardinals or strong limit cardinals. I suppose I forgot to mention the 'uncountable regular' part. $\endgroup$ – Hayden Nov 22 '13 at 7:58

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.