3
$\begingroup$

Since my last question here about the Alephs was too imprecise and thus went over like a lead balloon, I am trying a new and simpler question which asks what I probably should have asked before.

Under "Beth Numbers" in Wikipedia I read:

"In ZF, for any cardinals $\kappa$ and $\mu$, there is an ordinal $\alpha$ such that:

$\kappa \leq \beth_\alpha(\mu)$."

But under "Inaccessible Cardinals" I read:

"a cardinal $\kappa$ is strongly inaccessible if it is uncountable, it is not a sum of fewer than $\kappa$ cardinals that are less than $\kappa$, and $\alpha < \kappa$ implies $2^\alpha < \kappa$."

These two passages are troubling to me since they seem to be contradictory. The first one seems to imply that for ANY cardinal one can always find a Beth number which exceeds it. While the second one clearly seems to imply that the first inaccesible and any cardinal larger than it, of which there are uncountably many, of course, are all vastly larger than any Beth cardinal generated by even $\omega$ applications of the Power Set operation could ever be.

I assume that I am simply missing something important here, and that both statements from the Wikipedia are actually true. But what exactly am I missing??

$\endgroup$
  • 2
    $\begingroup$ Why are you limiting yourself to only $\omega$ applications of the power set operation? $\endgroup$ – Eric Wofsey Aug 19 at 19:54
  • $\begingroup$ OK, I thought of that and almost said "any number of Power Set operations," but I don't understand what it would be to apply the operation an uncountable number of times, if such is possible at all. $\endgroup$ – Wd Fusroy Aug 19 at 20:02
  • 1
    $\begingroup$ @WdFusroy "I don't understand what it would be to apply the operation an uncountable number of times, if such is possible at all." This is exactly what's going on here. Are you familiar with transfinite recursion? $\endgroup$ – Noah Schweber Aug 19 at 22:21
  • 1
    $\begingroup$ @WdFusroy "no such restriction is placed on the equation in the Beth numbers article." Right, that's what I said. That's why there's no contradiction. If $\kappa$ is strongly inaccessible, then $\beth_\alpha\lt\kappa$ for $\alpha\lt\kappa$, but $\beth_\alpha\ge\kappa$ for $\alpha\ge\kappa$. What's the problem? $\endgroup$ – bof Aug 19 at 23:15
  • 1
    $\begingroup$ An inaccessible cardinal is still an ordinal. $\endgroup$ – Asaf Karagila Aug 20 at 6:37
6
$\begingroup$

It seems like the issue you're having is with understanding what $\beth_\alpha$ means when $\alpha \geq \omega$. The definition is by recursion: $\beth_0 = \aleph_0$, for any ordinal $\alpha$ we define $\beth_{\alpha+1} = 2^{\beth_\alpha}$, and when $\alpha$ is a limit ordinal we have $\beth_\alpha = \sup\{\beth_\beta : \beta < \alpha\}$. This allows us to continue the powerset operation transfinitely.

Notice that, for every $\alpha$, $\aleph_\alpha \leq \beth_\alpha$. Thus, if $\kappa = \aleph_\alpha$, then $\beth_\alpha \geq \aleph_\alpha = \kappa$, so it is indeed true that there is a $\beth$ number larger than $\kappa$ (if you want strictly larger, go for $\beth_{\alpha+1}$).

The reason the previous paragraph doesn't contradict the definition of $\kappa$ being inaccessible is that if $\kappa$ is inaccessible then the $\alpha$ for which $\kappa = \aleph_\alpha$ is $\kappa$ itself, i.e., $\kappa = \aleph_\kappa$. Thus, unlike in the definition of inaccessibility, we're not in the position of calculating $2^{\alpha}$ with $\alpha < \kappa$.

$\endgroup$
  • $\begingroup$ Well, that all sounds very sensible. But I am still troubled by your claim that:"if κ is inaccessible then the α for which κ=ℵα is κ itself, i.e., κ=ℵκ." I have encountered that claim many times before but never been fully comfortable with it since it isn't obvious to me that there could not exist some big cardinal "j" such that there is NO "a," not even j itself, for which j = Aleph[j], or in the case mentioned here, for which j = Beth[j]. More simply put, how can we know, a priori, that many cardinals do not exceed even uncountably infinite recursive Power Set taking altogether? $\endgroup$ – Wd Fusroy Aug 19 at 21:02
  • $\begingroup$ I am also still quite troubled by the idea that it would ever be possible to take an uncountable number of recursive Power Set applications. Since these recursions must always be taken in precise sequence, each one after, and building upon, the previous one, they should always remain countable by some huge, but still denumerable, ordinal index, I think. $\endgroup$ – Wd Fusroy Aug 19 at 21:07
  • $\begingroup$ I should probably also say that I am interested in all of these matters primarily because it has always seemed to me that the Power Set operation is far too "slow" to serve as something like an index of the comparative size of various cardinals, which, I assume, was the general idea behind inventing the Beth Numbers in the first place. There are many other operations, like, say, the tetration operation, i.e. 2 Tet [Super]Beth[n] = [Super]Beth[n+1], which would certainly grow vastly faster than the usual 2 exp Beth[n] = Beth[n+1] But could even that recursion get to any of the inaccessibles?? $\endgroup$ – Wd Fusroy Aug 19 at 21:20
  • 1
    $\begingroup$ There are a few things going on here. The existence of an inaccessible cardinal is something you could reasonably not believe (in the sense that we don't even know that it is consistent, and indeed there are significant barriers to us knowing that, because ZFC+"there is an inaccessible cardinal" implies Con(ZFC)). $\endgroup$ – Chris Eagle Aug 19 at 22:11
  • 2
    $\begingroup$ @WdFusroy "Since these recursions must always be taken in precise sequence, each one after, and building upon, the previous one, they should always remain countable by some huge, but still denumerable, ordinal index, I think." No, that's not necessary. Definition by transfinite recursion makes sense along all the ordinals. $\endgroup$ – Noah Schweber Aug 19 at 22:32
4
$\begingroup$

Your comments indicate that you are dubious about iterating operations on ordinals more than finitely many times, and very dubious about iterating them uncountably many times. This is a fundamental point in set theory. The danger is in thinking of recursive definitions as processes which need to be carried out, in which case our "finitary biases" get in the way. Instead, you should think of a recursive definition as "happening all at once." Essentially, we can show that every recursive description corresponds to a unique function, and what lets us do this is transfinite induction. (It shouldn't be surprising that "we can do recursion for as long as we can do induction.")

Specifically, suppose that $F:Ord\rightarrow Ord$ is a function on ordinals (or rather, class function; for simplicity I'm assuming we're working in a theory like NBG that makes all this much simpler to say). For $\theta>0$ an ordinal, say that a function $G$ iterates $F$ along $\theta$ starting at $\alpha$ iff

  • The domain of $G$ is $\theta$,

  • $G(0)=\alpha$,

  • for $\beta+1<\theta$ we have $G(\beta+1)=F(G(\beta))$, and

  • for $\lambda<\theta$ a limit we have $G(\lambda)=\sup\{G(\beta): \beta<\lambda\}$.

Incidentally, this last condition is really only a natural thing to do if $F$ is nondecreasing, but strictly speaking this works for any $F$.

In principle, there could be many $G$ with this property, or none at all. However, it turns out that there is only ever exactly one:

For every $F:Ord\rightarrow Ord$ (= the function to be iterated), $\theta>0$ (= the iteration length), and $\alpha$ (= the starting value), there is exactly one $G$ which iterates $F$ along $\theta$ starting at $\alpha$.

Moreover, the $G$s "cohere" in the sense that if $G$ iterates $F$ along $\theta$ starting at $\alpha$ and $G'$ iterates $F$ along $\theta'$ starting at $\alpha$, with $\theta<\theta'$, then for each $\eta<\theta$ we have $G(\eta)=G'(\eta)$. So in some sense there is a unique way to iterate $F$ along $Ord$.

The proof is by transfinite induction: fixing an arbitrary $F$ and $\alpha$, consider some $\theta$ such that the claim holds for all iteration lengths $<\theta$. Intuitively, if $\theta=\gamma+1$ we just take the $G$ for $\gamma$ and "stick one more value onto it," and if $\theta$ is a limit we "glue the earlier $G$s together." It's a good exercise to turn this vague hint into an actual proof.

The sequence of $\beth$ numbers can be constructed in this way:

  • $F$ is the map sending an ordinal $\alpha$ to the cardinality of the powerset of $\alpha$ (which, remember, is itself an ordinal - cardinals are just initial ordinals).

  • The starting value $\alpha$ is $\omega$: this amounts to setting $\beth_0=\omega$.

  • To determine what $\beth_\eta$ should be, we set $\theta=\eta+1$ - or really we pick any $\theta>\eta$, by the "coherence" point above it doesn't affect the answer.

$\endgroup$
  • $\begingroup$ Thanks so much for that very complete explanation, Noah. I can't quite grasp everything you have written yet but will work hard on it in the next few days. I find "Essentially, we can show that every recursive description corresponds to a unique function, and what lets us do this is transfinite induction," the crux of the matter, and it strikes me as funny that I have trouble with transfinite recursion of the Beths, when I've never had any problem with the similarly "transfinite" definition of simple functions from R to R! [Still the Beths seem "sequential" in a way the Reals do not.] $\endgroup$ – Wd Fusroy Aug 20 at 15:54
1
$\begingroup$

Say that a natural number $n$ is "large" if for any number $k$ you'd think of in the next 24 hours, $n>10^k$. Let's go bigger, say $n>k\uparrow^k k$, using the Knuth notation.

Pretty much by definition, $n$ is unimaginably large. So large that for the next 24 hours there is no way you can even imagine it. But tomorrow evening, you'd be sitting with a beer and realize that you can imagine an even larger number. Why is that even possible? Because even though this $n$ is large, almost all the other natural numbers are larger.

Inaccessible cardinals are ordinals. They are incredibly large, yes. But at the end of the day, most ordinals are in fact larger. More cardinals are larger.

If $\kappa$ is inaccessible and $\mu<\kappa$, then we can prove that the smallest $\alpha$ for which $\kappa\leq\beth_\alpha(\mu)$ is in fact $\kappa$ itself. Namely, $\kappa\leq\beth_\kappa(\mu)$, and they are in fact equal, and if $\alpha<\kappa$, then $\beth_\alpha(\mu)<\kappa$ as well. But since $\kappa$ is an ordinal, taking $\alpha=\kappa$ is perfectly valid.

So there is no contradiction there. You can move to $\aleph$ fixed points, whose existence is provable in $\sf ZFC$, and replace the $\beth_\alpha(\mu)$ by $\mu^{+\alpha}$, the $\alpha$th successor of $\mu$. If $\kappa=\aleph_\kappa$, and $\mu,\alpha<\kappa$, then $\mu^{+\alpha}<\kappa$. Nevertheless, there is some $\beta$ such that $\mu^{+\beta}\geq\kappa$, in fact a proper class of those $\beta$s. And specifically, $\kappa$ itself works for that.

$\endgroup$
  • $\begingroup$ Thanks so much Asaf! I always prize your answers and try to learn from them. Here I love the way you start out with an analogy from the finite case. I've always thought that the study of the "Large Finites" has been relatively neglected by mathematicians, although in recent years it is starting to develop. I've always found it amazing that if one asks someone to pick any natural number of their choice, however cleverly large, it will still fall in the first INFINTESIMAL segment of the whole set of nat. numbers. And so too with the infinite cardinals, even if it sometimes seems less obvious. $\endgroup$ – Wd Fusroy Aug 20 at 16:09
  • $\begingroup$ The meat of your answer is however this: "If κ is inaccessible and μ<κ, then we can prove that the smallest α for which κ≤ℶα(μ) is in fact κ itself" I have certainly learned that basic fact, but as I do not know the proof it still seems less than apodeictic to me. At the risk of making a fool of myself again, I still don't see why k can't be GREATER than even Beth[k] [mu] in some cases. That would just mean that k is so large there is NO "a," not even k, that will put Beth[a] [mu] beyond what we might call, say, the "recursively inaccessible" k. Why is such an odd thing impossible?? $\endgroup$ – Wd Fusroy Aug 20 at 16:20
  • $\begingroup$ Perhaps my problem here is as simple as not knowing for sure whether Beth[omega] is a limit cardinal. I had always assumed it must be, -- since it doesn't get to the inaccessibles -- but now it seems to me like the limit cardinal for the whole class of Beths must come only much farther out -- whatever exactly that means -- if in fact there IS anything like a limit cardinal for the whole sequence, which the answers here seem strongly to indicate there is not. $\endgroup$ – Wd Fusroy Aug 20 at 16:35
  • 1
    $\begingroup$ I think it would be very good for you to do some basic exercises about cardinals, ordinals, and recursive definitions. Most of the questions you raise in the comments are very easy to answer once you have a firm grasp on the basics. $\endgroup$ – Asaf Karagila Aug 20 at 16:59
  • 1
    $\begingroup$ Do you mean $\beth_{\omega+\omega}$? Or just generally limit cardinals? For the latter case, that is undecided in ZFC, since it is consistent (i.e., GCH) that $\aleph_\alpha=\beth_\alpha$, but it's also consistent that $\beth_{\alpha+2}$ is a limit cardinal for any fixed $\alpha$. $\endgroup$ – Asaf Karagila Sep 19 at 20:48

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.