Starting from the cardinal $|\Bbb N| = \aleph_0 = \beth_0$, we can generate a larger cardinal in two ways:

  1. Take the set of all subsets, generating the cardinal $\beth_1$
  2. Take the set of all well-order-types (up to isomorphism), generating the cardinal $\aleph_1$

I am wondering if, rather than well-order-types, we can take other order-types (up to isomorphism) to generate different cardinals. Are any of these known?

  1. The set of all total order-types of $\aleph_0$
  2. The set of all partial order-types of $\aleph_0$

  3. The set of all preorder-types of $\aleph_0$

where these are all taken up to isomorphism.

Are the cardinalities of any of these known? Do any lead to another type of cardinal similar to the $\aleph$ or $\beth$ cardinals? How much of AC is required to talk about these?

  • $\begingroup$ Since total orders are special types of partial orders, 2 and 3 are the same. $\endgroup$ – Noah Schweber Feb 9 '19 at 22:36
  • $\begingroup$ Oops, that's from an earlier edit. Removed $\endgroup$ – Mike Battaglia Feb 9 '19 at 22:37

There's an easy construction which lets us show that there are continuum-many countable ordertypes up to isomorphism: given any infinite sequence of natural numbers $f$, consider the order $$A_f=\mathbb{Z}+f(0)+\mathbb{Z}+f(1)+...=\sum_{i\in\mathbb{N}}[\mathbb{Z}+f(i)].$$ It's easy to check that $A_f\cong A_g\iff f=g$. This immediately implies that all the other numbers are also continuum.

And note that we can do this for arbitrary infinite cardinalities: given $f:\kappa\rightarrow\{0,1\}$, let $$A^\kappa_f=\sum_{\eta<\kappa}[\mathbb{Z}+f(\eta)].$$ Again we have $A_f^\kappa\cong A_g^\kappa$ iff $f=g$.

So for every infinite cardinal $\kappa$, there are $2^\kappa$-many isomorphism types of linear orders of size $\kappa$. (And AC was never used at any point in the above.)

| cite | improve this answer | |
  • 2
    $\begingroup$ @MikeBattaglia Not a single number, but a finite linear ordering of length $f(i)$, between copies of Z. $\endgroup$ – Ned Feb 9 '19 at 23:36
  • 1
    $\begingroup$ @MikeBattaglia There is a natural way to view the set of all linear orderings of $\mathbb{N}$ as a Polish space $\mathcal{L}$. In this light, Burgess' theorem says that any analytic equivalence relation on $\mathcal{L}$ has either countably many, $\aleph_1$-many, or continuum-many equivalence classes. What does this have to do with counting orderings of a given type? Well, given a class $C$ of linear orders (e.g. the well-orderings), let $\equiv_C$ be the equivalence relation on $\mathcal{L}$ given by pushing all the "non-$C$" orders together, and being isomorphism otherwise. (cont'd) $\endgroup$ – Noah Schweber Feb 10 '19 at 0:44
  • 2
    $\begingroup$ That is, $A\equiv_CB$ iff (neither $A$ or $B$ is in $C$) or ($A\cong B$). So for example: taking $C$ to be the class of well-orderings, $\mathcal{L}/\equiv_C$ has one element for each countable ordinal, and then one more element for "not well-ordered." So we're just counting the $\equiv_C$-classes, essentially. The point is that Burgess tells us that we can never hope to get anything other than $\le\aleph_0$, $\aleph_1$, or $2^{\aleph_0}$ using any kind of ordering which yields an analytic equivalence relation. For example, $C$=well-orderings does give an analytic equivalence relation. $\endgroup$ – Noah Schweber Feb 10 '19 at 0:47
  • 1
    $\begingroup$ (And Silver's theorem, which is easier, shows that coanalytic equivalence relations are even tamer: they get either countably many or continuum-many classes.) So tentatively, I'd say that you're never going to find a natural way to whip up (say) $\aleph_2$ this way (even after granting the clearly-necessary assumption of $\neg$CH). $\endgroup$ – Noah Schweber Feb 10 '19 at 0:48
  • 1
    $\begingroup$ All this falls into the general descriptive-set-theoretic picture of cardinals in between $\aleph_0$ and continuum being "difficult to exhibit." Incidentally, things get weirder at higher cardinals, but that's a separate issue. $\endgroup$ – Noah Schweber Feb 10 '19 at 0:51

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.