Best known upper and lower bounds for $\omega_1$

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.

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.

Solution 1:

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$.

Solution 2:

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.

Solution 3:

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.$