2
$\begingroup$

What are the best known lower and upper bounds for $\omega_1$? Are there sharper lower bounds than $\varepsilon_0$? And are there any known upper bounds which can be explicitly constructed like $\varepsilon_0$?

Since $\varepsilon_0$ is countable, $\varepsilon_0$ must be less than $\omega_1$. But in all of the 45 books on logic and set theory on my bookshelf, I can find no bounds better than this. I've been trying to find the answer to this for many years, and it's very frustrating that only one of the infinite cardinals has an explicit construction. The uncountable cardinals seem to be only known to exist, but they can't be nailed down explicitly, unless the answer lies in some book which I haven't consulted.

A secondary question is why ordinal numbers are used as "cardinality yardsticks" anyway. Why don't we use the infinite von Neumann universes as cardinality yardsticks instead? For example, $V_\omega$ (which has the same cardinality as $\omega$), $V_{\omega+1}$ which has the cardinality of the continuum, and $V_{\omega+\omega}$ which is reputedly the smallest model of Zermelo set theory. These spaces have the philosophical disadvantage that they don't include any "mediate cardinals". But they include every infinite cardinality which is of practical use in practical mathematics.


Postscript 2015-10-26:
First, sincere thanks to those respondents who understood my question and answered accordingly. Second, to anyone who arrives at this web page, possibly seeking the answer to the same question, I should state now what my current understanding of this issue is. The answers given to this question here have totally changed my understanding of the ordinals, that's for sure.

When I read the Halmos "Naive set theory" chapter on ordinal numbers during undergraduate years, I gained the false impression from the final page of that chapter that the limits, and limits of limits, and so on and so on, of ordinal numbers constituted the complete set of ordinal numbers. I assumed that $\omega_1$ must be in that huge tower of ordinal numbers somewhere. Now from the answers to my question, it has dawned on me that all of those ordinal numbers are countable. (I hope I've understood that correctly now.) Therefore my question was effectively null and void. None of that tower of ordinal numbers, including the $\varepsilon_\alpha$ ordinals, is an upper bound for $\omega_1$ and they are all lower bounds. Different kinds of procedures are required to "get a handle" on $\omega_1$, $\omega_2$ etc.

Third, thanks again to those who gave serious responses.

$\endgroup$
  • 1
    $\begingroup$ How would a "sharper" lower bound be an improvement? Any such number would have to be countable by definition, and so, no "closer" to $\omega_1$ than $\varepsilon_0$. $\endgroup$ – Tim Raczkowski Oct 25 '15 at 3:50
  • 2
    $\begingroup$ I don't really understand the premise of your secondary question. The von Neumann hierarchy is used all the time in set theory for many purposes. I am not sure in what sense $V_{\omega+1}$ is any more "explicit" than $\omega_1$; if you accept that $V_{\omega+1}$ exists then you should accept that (a set of order-type) $\omega_1$ exists, as in my answer. $\endgroup$ – Eric Wofsey Oct 25 '15 at 4:21
  • 2
    $\begingroup$ For the usual von Neumann definition, you can easily say what the elements of $\omega_1$ are. A set $A$ is an element of $\omega_1$ iff it is countable and the element relation $\in$ is a total ordering on $A$. $\endgroup$ – Eric Wofsey Oct 25 '15 at 4:31
  • 2
    $\begingroup$ @AlanU.Kennington What do you mean? $\omega_1$ is the set of all countable ordinals - that's a pretty concrete description! And if you don't think that is concrete, in what sense is $V_{\omega+1}$ concrete? Note that in many precise mathematical senses, $V_{\omega+1}$ is strictly more complicated than $\omega_1$: $\omega_1$ is provably constructible (in the technical sense of "is in $L$"), while $V_{\omega+1}$ consistently isn't. $\endgroup$ – Noah Schweber Oct 25 '15 at 4:31
  • 3
    $\begingroup$ The class of hereditarily countable sets satisfies all the axioms of ZF except the Power Set axiom. Without Power we cannot prove that $\omega_1$ exists. "Power" does not rely on some recursion,but just declares the existence of power sets. else we could derive it in ZF-P. Not surprising that $\omega_1$ can't be defined by recursion from below either. $\endgroup$ – DanielWainfleet Oct 25 '15 at 8:14
8
$\begingroup$

I suspect you want something which just doesn't exist.

Let's start with the basics: for any countable ordinal $\alpha$, $\epsilon_\alpha$ is again countable - so you won't get $\omega_1$ that way.

More generally, $\epsilon$ numbers are defined as fixed points of a certain continuous map on countable ordinals: $\gamma\mapsto\omega^\gamma$. In particular, $\epsilon_0$ is the first fixed point of this map. We could ask: is $\omega_1$ the least fixed point of any continuous map on the countable ordinals? The problem is, the answer is no: any continuous map on the countable ordinals has a countable fixed point. (Note that we can concretely describe truly gigantic ordinals this way, well beyond $\epsilon_0$, which are relevant to e.g. proof theory - but these are still countable!)

OK, let's broaden our search a bit - what if I just want any concrete description of $\omega_1$? Well, this is obviously problematic: what does "concrete" mean? :D But there's a reasonable property concrete descriptions should satisfy: they should be absolute between transitive models of set theory. For instance, the construction of $\epsilon_0$ has this property: if $M\subseteq N$ are transitive models of $ZFC$ with $\alpha\in M$, and $M$ thinks $\alpha$ is (the ordinal which satisfies the definition of) $\epsilon_0$, then $N$ also thinks $\alpha$ is $\epsilon_0$. So maybe $\omega_1$ has a similarly "absolute" definition?

Nope! Let $M$ be a countable transitive model of set theory. Then $M$ contains an ordinal $\alpha$ which it thinks is $\omega_1$. But $\alpha$ is countable, since $M$ is countable and transitive. Oops.

There really isn't any good way to describe $\omega_1$ except as "the least uncountable ordinal." Now, if you are happy with powerset and separation, this isn't too bad: take the set of all well-orderings of $\omega$. Now just "glue these together" in increasing order, and you'll get $\omega_1$! But that's about the best "building from below" that you can do.

OK, what about "finding $\omega_1$ in nature?" Maybe we could describe a well-ordering of a subset of $\mathbb{R}$ which happens to have order type $\omega_1$. Well, this also breaks: in ZFC, we can prove that any such well-ordering must not be Borel (actually we can prove much more). And assuming large cardinals, we can extend this. In fact, consistently with ZF, every well-orderable subset of $\mathbb{R}$ is countable! So this can't happen in a provable way.


By the way, this doesn't address your last paragraph, which is a different question altogether. I don't quite understand what you're asking here, but I feel like you're objecting to the lack of examples of sets of "intermediate" cardinality between e.g. countable and continuum (assuming $\neg CH$ so that this isn't trivial). This is certainly a reasonable gripe; I'm very sad about it too, as I am about our current lack of any natural Turing degree between "computable" and "the halting problem." But we can still be interested in intermediate cardinalities/degrees without any natural examples - they're pretty interesting objects! And, in fact, there are some natural potential examples: https://en.wikipedia.org/wiki/Cardinal_characteristic_of_the_continuum. EDIT: you might consider these upper bounds of $\omega_1$.

$\endgroup$
  • $\begingroup$ So it seems you're saying that it is not possible to construct an ordinal which is uncountable, starting from $\omega$ and progressing by limits and limits of limits and so forth. That comes pretty close to saying that an uncountable ordinal is not constructible. Is that right? $\endgroup$ – Alan U. Kennington Oct 25 '15 at 4:05
  • 2
    $\begingroup$ @AlanU.Kennington What do you mean by "constructible"? Usually the way the term is used in set theory is quite different, and $\omega_1$ - in fact, every ordinal - is constructible. But there is indeed a sense in which $\omega_1$ is really really hard to reach. $\endgroup$ – Noah Schweber Oct 25 '15 at 4:08
  • $\begingroup$ Yes, I realize there are multiple meanings for "constructible". I mean in the sense of a series of limits like we use to get to $\varepsilon_0$, something like that. But from what you've said, I get the impression that no one has been able to write down an explicit uncountable ordinal. $\endgroup$ – Alan U. Kennington Oct 25 '15 at 4:10
  • 1
    $\begingroup$ @AlanU.Kennington Well, I don't know what you mean by "explicit." I would consider the "gluing together" construction pretty explicit! But yes, there are many senses in which $\omega_1$ provably cannot be described nicely. Note that this isn't a matter of "no one has been able to," this is outright provable impossibility! $\endgroup$ – Noah Schweber Oct 25 '15 at 4:11
  • $\begingroup$ I realize this is late, but $\omega_1$ is a limit of smaller ordinals - it's just that any such set has to be uncountable, so the number of smaller ordinals in any such limit is at least $\omega_1$. This observation leads to the notion of the "cofinality" of an ordinal, and to the notion of "regular cardinals" of which $\omega_1 = \aleph_1$ is an example. $\endgroup$ – Daniel Schepler Jul 7 '17 at 20:55
2
$\begingroup$

I'm not quite sure what you're asking for, but maybe this will satisfy you. You can give a reasonably explicit construction of a well-ordered set of order-type $\omega_1$ as follows. Let $S$ be the set of all well-ordered sets $(A,<)$ such that $A$ is a subset of $\mathbb{N}$. Isomorphism of ordered sets gives an equivalence relation on $S$; let $T=S/{\cong}$ be the set of equivalence classes. Order $T$ by saying that $[(A,<_A)]<[(B,<_B)]$ if there exists an isomorphism from $(A,<_A)$ to a proper initial segment of $(B,<_B)$ (this is clearly independent of the representatives of the equivalence classes chosen). Then it can be shown that $<$ is a well-ordering on $T$, and $(T,<)$ has order-type $\omega_1$.

More briefly, $\omega_1$ can be described explicitly as the set of possible lengths of well-orderings of countable sets. This construction also generalizes to higher cardinals: $\omega_2$ is the set of possible lengths of well-orderings of sets of cardinality $\leq\aleph_1$, $\omega_3$ is the set of possible lengths of well-orderings of sets of cardinality $\leq\aleph_2$, and so on.

$\endgroup$
  • 2
    $\begingroup$ @AlanU.Kennington Note that this is pretty much exactly what I describe in my sixth paragraph (but with more details). $\endgroup$ – Noah Schweber Oct 25 '15 at 4:26
  • 2
    $\begingroup$ @AlanU.Kennington Given your analysis background, you might like this: to each real number $r$ I can associate a countable ordinal $\omega_1^r$, the least ordinal which cannot be "computed" (in a precise sense, see en.wikipedia.org/wiki/Church%E2%80%93Kleene_ordinal) from $r$. Then each $\omega_1^r$ is a countable ordinal, and $\omega_1$ is the supremum of the $\omega_1^r$s as $r$ runs through the reals. This is no simpler than the "glue it all together" construction, in fact it's more complicated - but I'm making a wild guess that you might find this somewhat more satisfying. (cont'd) $\endgroup$ – Noah Schweber Oct 25 '15 at 4:42
  • 2
    $\begingroup$ Why? Because each real is "approximating" $\omega_1$ in a way, and the true $\omega_1$ is the limit of these approximations. But if you do find this at all satisfying, you should spend a bit to convince yourself that it is in fact exactly the same as the descriptions already given; I think then you'll be more satisfied with $\omega_1$ in general. $\endgroup$ – Noah Schweber Oct 25 '15 at 4:45
  • 1
    $\begingroup$ @NoahSchweber How is $\omega_1^r$ defined? Your link doesn't actually seem to talk about this. $\endgroup$ – Akiva Weinberger Oct 26 '15 at 21:00
  • 2
    $\begingroup$ @AkivaWeinberger: It is very easy to get such a function. Think of a real as encoding a subset of $\mathbb{N}\times\mathbb{N}$, and map it to its order-type if it is a well-ordering and $0$ otherwise. $\endgroup$ – Eric Wofsey Oct 26 '15 at 23:46
1
$\begingroup$

In ZF without the axioms of power-set nor infinity we have :Every well-order $W$ is order-isomorphic to a unique ordinal $f(W)$. Enter Infinity.Now we get $\omega$ and $\omega \times \omega$. A binary relation on a set $s$ is a subset of $s \times s$.Enter Power. Now we get $T=P(\omega \times \omega)$.By Comprehension we get $U=\{W\in T :W$ is a well-order $\}$. By Replacement and Comprehension (Kunen's version) we get $X=\{f(W) : W\in U\}$ And $X$ is the set of all countable ordinals.That is, $X=\omega_1.$

$\endgroup$
  • $\begingroup$ That puts it very succinctly, and at first it seems totally convincing. But when I think about this a bit more, it seems like it is just a proof of existence, not an identification of where in the recursive series it is "located". But as you say in a comment to the main question, "$\omega_1$ can't be defined by recursion from below", which explains why the answer to my question is not in books. It can't be done that way. The method which you state seems to say only that $\omega_1$ is the smallest uncountable ordinal. It doesn't say what it "is". But knowing it is unknowable is comforting! $\endgroup$ – Alan U. Kennington Oct 25 '15 at 8:52
  • 1
    $\begingroup$ As far as I can tell, we prove that there exists a least uncountable ordinal, and that's what it is. "That depends on what your definition of 'is' is"--Bill Clinton. $\endgroup$ – DanielWainfleet Oct 25 '15 at 8:56
  • 1
    $\begingroup$ Just one little postscript.... Now I am feeling like I was a bit deceived by the Halmos "Naive set theory" book which showed how to get up to $\varepsilon_0$ and beyond using limits, limits of limits etc. This same sequence appears in the original founding paper(s) by Cantor in the late 19th century. I had assumed, perhaps naively, that that was all the ordinals there are. Now I understand, and perhaps should have understood before, this only gets you the countable ordinals. This explains why no author says how far you have to go to get uncountable. The ordinals are much bigger than I thought! $\endgroup$ – Alan U. Kennington Oct 25 '15 at 12:46
  • 1
    $\begingroup$ @AlanU.Kennington Note that "easily-definable" limit processes like this won't even get you past $\omega_1^{CK}$, which is still countable! And then there are even larger countable ordinals which people study, like recursion-theoretic versions of large cardinals, etc. But if you're interested in that sort of limit process, you should read about the Veblen hierarchy (and related ideas): en.wikipedia.org/wiki/Veblen_function and en.wikipedia.org/wiki/Large_countable_ordinal. $\endgroup$ – Noah Schweber Oct 26 '15 at 23:27
  • 1
    $\begingroup$ Well, $\omega_1$ is impossibly bigger than those "large" countable ordinals. $\endgroup$ – Noah Schweber Oct 27 '15 at 2:52

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.