# The preorder of countable order types

Consider the set $\mathcal{O}$ of order types corresponding to all posets of cardinality at most $\aleph_0$. The set $\mathcal{O}$ is a preorder under embeddability of its elements (note that some order types are mutually embeddable, e.g. order types of an open and closed intervals in $\mathbb{Q}$). Transform the preorder $\mathcal{O}$ to the poset $\bar{\mathcal{O}}$ by grouping its elements into equivalence classes under mutual embeddability.

• Is the structure of $\bar{\mathcal{O}}$ well understood?
• What are the cardinality and height (the least ordinal not embeddable to a poset) of $\bar{\mathcal{O}}$?
• What are cardinalities of maximal chains and antichains in $\bar{\mathcal{O}}$?

## 2 Answers

Warning: This anwer should be treated with caution. For further information see the comments.

As a partial anwer consider the set $\mathcal L$ of order types of linear orders. Then $\bar{\mathcal L}$ is bounded by the class of $\mathbb Q$ on top and by the chain of the finite intervals at the bottom. Between them you have as structure of arbitrary stackings of up to countable infinitely many copies of $\omega$ and ${}^*\omega$. All of them are different. That means that $\mathcal L$ has cardinality of at least $2^{\aleph_0}$.

That estimation can be shown in the following way. Let $(M,≤)$ be a countable linearly ordered set. Then we can define an equivalence relation $≈$ such that two elements $a,b∈M$ are equivalent iff the order interval between them is finite. This provides a partition of $M$ in a way that elements are in different classes if they are separated by an infinite interval. Now we can assign a number to each of its equivalence classes: $$φ([x]) = \begin{cases}-1, \text{ iff [x] has a maximal element,}\\ 0,\text{ iff [x] has neither a maximal nor a minimal element, und}\\ 1,\text{ iff [x] has a minimal element.} \end{cases}$$

The result is a character sequence in which $1$ cannot follow directly after $-1$ A class $[x]$ can be embedded into a class $[y]$ iff either $φ([x]) = φ([y])$ or $φ([y])=0$. That means that $[x]$ and $[y]$ belong to the same class of $\bar{\mathcal L}$ iff they get the same number assigned. That means two orders are equvalent iff their $≈$-classes generate the same number sequences. On the other hand the countable union of countable sets is also countable. For each countable number sequence that does not contain a number $1$ directly following $-1$ we get a different linear order. There are at least $2^{\aleph_0}$ such sequences (consider only $0$ and $1$) and at most $3^{\aleph_0}=2^{\aleph_0}$.

For the general case know that a countable set has at most $|\mathfrak{P}(\mathbb N\times\mathbb N)| = |\mathfrak{P}(\mathbb N)| =2^{\aleph_0}$ binary relations. Thus we have found the cardinality.

If two nonisomorphic orders are embeddable into each other then we can chain the embeddings and get an endomorphism form each of the ordered sets into a proper subset of itself. That means that you don't have to consider finite ordered sets too hard: They are all different in $\bar{\mathcal O}$.

If embedding does not imply isomorphic embedding, then the rationals $\mathbb Q$ form the top element of $\bar{\mathcal O}$ as each order is the intersection of linear orders.

• I think something is wrong. In fact, $\mathcal{L}$ can be stratified using the Hausdorff rank in $\omega_1$ levels $\mathcal{L}_\alpha$. In addition if $Q$ is qo, remember that $Q^\omega$ is quasi-ordered by letting for $f,g:\omega\to Q$, $f\leq g$ iff there exists an increasing injective $h:\omega\to\omega$ s.t. $f(n)\leq g(h(n))$ for all $n$. One can show that if $Q$ is a countable better quasi-order (bqo), then the partial order quotient of $Q^\omega$ is a countable bqo too. – Yann Pequignot Jul 2 '14 at 20:06
• Then by induction, one can show that the cardinality of $\mathcal{L}_\alpha$ is countable for every $\alpha<\omega_1$, and thus the cardinality of $\mathcal{L}$ is (at most) $\omega_1$. This is done in Lemmas 10 and 11 of On the Quasi-Ordering of Borel Linear Orders Under Embeddability by Louveau and Saint-Raymond. – Yann Pequignot Jul 2 '14 at 20:12
• Thanks for that link. You are right, I forgot to handle the case where two orders are equivalent, but both embeddings have to skip certain levels. On the other hand I also overlooked the case of levels that have finite cardinality. But what I don't understand is, how $Q^\omega$ can describe our situation with an injective mapping $h$. As we consider all suborders of $Q^\omega$ up to equivalence, I would think we must accept that $h$ is non-injective. But maybe there is something I'm missing. – Keinstein Aug 6 '14 at 18:29
• All details are to be found in the paper by Louveau and Saint-Raymond. The idea is to stratify the countable scattered linear orders $\text{SCAT}$ into $\omega_1$ levels $\text{SCAT}_\xi$ in such a way that a member $S$ of $\text{SCAT}_\xi$ is naturally seen as a sum over $\mathbb{Z}$ of members $S_x$, $x\in\mathbb{Z}$, of $\text{SCAT}_{<\xi}=\bigcup_{\alpha<\xi}\text{SCAT}_\alpha$. Then use the fact that $\text{SCAT}_{<\xi}$ is bqo, and countable (up to equivalence) by induction hypothesis, so that $(\text{SCAT}_{<\xi})^\mathbb{Z}$ is a countable bqo up to equivalence. – Yann Pequignot Aug 20 '14 at 7:36
• Notice that if $(S_x)_{x\in\mathbb{Z}}\leq (T_x)_{x\in\mathbb{Z}}$ in $(\text{SCAT}_{<\xi})^\mathbb{Z}$ then $S$ embeds into $T$. The order in $(\text{SCAT}_{<\xi})^\mathbb{Z}$ is of course $(S_x)_{x\in\mathbb{Z}}\leq (T_x)_{x\in\mathbb{Z}}$ iff there exists an embedding $\varphi:\mathbb{Z}\to \mathbb{Z}$ such that $S_x$ embeds into $T_{\varphi(x)}$ for all $x$. This allows you to show that there are $\aleph_1$ countable scattered linear orders up to bi-embeddability. – Yann Pequignot Aug 20 '14 at 7:40

In Theory of Relations by Roland Fraïssé, section 5.11, p. 164 (see here), if I am not mistaken, the following is proved. The set $\mathcal{P}$ of infinite subsets of $\omega$ quasi-ordered by inclusion modulo finite, i.e. $A\subseteq_\text{fin}B$ iff $A\setminus B$ is finite, (or its partial order quotient) embeds into $\mathcal{O}$, the class of countable partial orders with embeddability.

The idea is due to K. Kunen and A. Miller and relies on the finite partial orders $C_n$ called 'crowns', see my other post. For the record, the crowns $C_n$ form an infinite antichain of finite partial orders.

First for every infinite subset $A$ of $\omega$, let $P_A$ be the partial order obtained by adding to the disjoint union of the crowns $C_n$, for $n\in A$, a minimum element. Notice that $P_A$ embeds into $P_B$ iff $A\subseteq B$.

Then for a (countable) equivalence class $\mathcal{A}$ for the modulo finite equivalence relation, we define the partial order $P_\mathcal{A}$ to be the disjoint union of the $P_A$'s for $A\in\mathcal{A}$.

Then $\mathcal{A}\mapsto P_\mathcal{A}$ is indeed an embedding.

Clearly, if $P_\mathcal{A}$ embeds into $P_\mathcal{B}$, then for all $A\in\mathcal{A}$ there exists $B\in\mathcal{B}$ with $A\subseteq B$, and so $\mathcal{A}\subseteq_\text{fin} \mathcal{B}$.

Conversely, it is enough to notice that if $\mathcal{A}\subset_\text{fin}\mathcal{B}$ then there is an injective map $i:\mathcal{A}\to\mathcal{B}$ with $A\subseteq i(A)$ for all $A\in\mathcal{A}$. To see this fix $A\in \mathcal{A}$ and choose $B\in\mathcal{B}$ with $A\subseteq B$. Since $\mathcal{A}\subset_\text{fin}\mathcal{B}$, $B\setminus A$ is infinite and so we can assign to every pair $(F,G)$ of finite subsets of $\omega$ a number $n_{(F,G)}\in B\setminus A$ with $n_{(F,G)}>\max G$ in a one-to-one manner. Then for every $A'\in\mathcal{A}$ there exists a unique pair $(F,G)$ of finite subsets of $\omega$ with $F\subseteq A$, $G\cap A=\emptyset$ and $A'=G\cup( A\setminus F)$, and we let $i(A')=G\cup B\setminus\{n_{(F,G)}\}$.

Finally by Parovicenko's theorem, every partial order of size $\aleph_1$ embeds into $\mathcal{P}$ and therefore into $\mathcal{O}$.