Can we recursively define all possible cardinalities of infinite sets?

200 Views Asked by At

Is the cardinality of any possible infinite set equal to the cardinality of some member of the set below?


Set W:

  • Base case: ℕ ∈ W
  • Constructor case: If n is in W, then P(n) is in W.

That is, the base case of W is the set of natural numbers. The constructor case is the power set of a case in W. Yielding the set {N, P(ℕ), P(P(ℕ), ...}


Is there any infinite set whose cardinality would not equal the cardinality of a member of W?

3

There are 3 best solutions below

0
On

Yes. Take the union of all sets in $W$. This set is at least as large as each individual member, and since each member is strictly larger than the last, this new set must be larger than all of them.

What you're describing is the $\beth$ sequence: $\beth_0$ is the cardinality of the set of natural numbers; $\beth_{\alpha + 1}$ is the cardinality of the power set of $\beth_{\alpha}$. But we can define $\beth_{\omega}$ to be the union of $\beth_n$ for $n$ finite, and keep going - $\beth_{\omega + 1}$ is the cardinality of the power set of that, and so on. In fact, for any cardinal $\kappa$, we can define $\beth_{\kappa}$. Even this isn't exhaustive: there's a cardinal $\kappa$ so that $\kappa = \beth_{\kappa}$ (so $\kappa = \beth_{\beth_{\beth\ldots}}$) but there's also a power set of that, which is strictly larger.

Also, the Continuum Hypothesis states that there is no cardinal strictly larger than $\mathbb{N}$ and strictly smaller than its power set; this is independent of the axioms, which means that whether or not it's true depends on which mathematical universe you're working in. So, depending on the situation, it may be that there are also cardinalities in between the ones on your list.

0
On

This is a major reason for adding the Fraenkel/Skolem axiom of replacement to Zermelo set theory (Z), so as to make Zermelo-Fraenkel set theory (ZF).

Without the axiom of replacement, it's possible for the cardinals you listed to be all the possible infinite cardinals (although, in that case, your $W$ would be a proper class rather than a set).

With the axiom of replacement, $W$ can be proven to be a set, and then $\bigcup W$ is a set of larger cardinality than all the ones you listed. At that point, you can go on and find larger cardinals, heading up high into the transfinite.

0
On

As stated, the answer to the question is a definite yes. Your construction yields the beth numbers $\Bbb N = \beth_0, P(\Bbb N)=\beth_1, \ldots$ This only yields the beth numbers with finite subscripts. In set theory, you probably want to iterate over all the ordinals, in which case you need a new constuctor rule when you have a limit ordinal. The common thing, which is probably what you want here is to define a function $f(\alpha)=\begin {cases} \beth_0&\alpha=0\\P(f(\alpha-1))& \alpha \text { a successor}\\ \bigcup_{\beta \lt \alpha}f(\alpha)& \alpha \text { a limit} \end {cases}$ Now you can continue the construction through the transfinite. Your construction could not define anything as large as $\beth_\omega$, so that is an infinite set whose cardinality is not on your list. If you extend the construction this way and making the list of cardinalities $\bigcup_{\alpha \text { ordinal}} \mid f(\alpha) \mid$ the answer is independent of ZFC. In the constructible universe this collection (which is not a set) contains all infinite cardinalities. If the continuum hypothesis fails, there is at least one infinite cardinality between $\beth_0$ and $\beth_1$.