The preorder of countable order types

573 Views Asked by At

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

There are 1 best solutions below

5
On BEST ANSWER

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.