The preorder of countable order types

Question

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}}$?

Answer 1

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.

Answer 2

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