Classification of countable posets?

Question

Is there a classification of countable posets where between each two comparable elements there is a third element between them?

Answer 1

$\newcommand\P{\mathbb{P}} \newcommand\Q{\mathbb{Q}} \newcommand\N{\mathbb{N}}$

Update. I claim that, in a precise sense I shall explain (using the ideas of Borel equivalence relation theory), there can be no explicit classification of the collection of all countable dense partial orders, and the classification problem for these structures is at least as difficult as the problem of classifying all countable groups, all countable graphs or all countable partial orders (which is very difficult indeed). In particular, there can be no Borel way to exhibit one member of each isomorphism class of the countable dense partial orders.

Let me begin by pointing out that in contrast to the case of countable dense linear orders, which have only finitely many isomorphism types (mentioned in Bjorn's answer), for the countable dense partial orders we have continuum many isomorphism types.

To see this, consider any $A\subset\N$ and define the partial order $\P_A$ as follows:

• there is a backbone copy of $\Q$
• For each $n\in\N\subset\Q$ on this backbone, we place another copy of $\Q$ sticking out to the side, above $n$, but incomparable with all $q\in\Q$ having $q>n$.
• For each $n\in A$ on the backbone, we place a second incomparable such copy of $\Q$ sticking out to the side, above $n$ and incomparable with the previous copy.

Like this:

                      .
                     .
                    .
                   /
                 \/
                 /
              \|/
               /
             \/
             /
           \/
           /
        \|/
         /
       \/
       /

This satisfies your density criterion, since whenever $x<y$, there are many points between. But the point now is that every $n\in\N$ on the backbone is definable in $\P_A$, since these are exactly the GLB's of incomparable pairs. And the $n\in A$ are definable among these as the GLB's of an incomparable triple, having no elements of $\N$ between. So $A\neq B$ implies $\P_A\not\cong\P_B$, and we therefore have continuum many isomorphism classes.

Indeed, we have that $A\neq B$ implies $\P_A\not\equiv\P_B$, so the theory of dense partial orders has continuum many completions (as opposed to only finitely many in the linear case). This is because any difference between $A$ and $B$ will be revealed in the theory by means of the definitions of the elements of $A$ and $B$ inside $\N$ as above.

But now, let me claim more, with a different encoding. Consider the collection DPO of all countable dense partial orders as a standard Borel space---just think of the relations as coded on $\N$ in some canonical manner. So we have the isomorphism relation $\cong_{DPO}$ on these (codes for) dense partial orders. The classification problem is the problem of assigning invariants to the equivalence classes of this equivalence relation.

What I claim is that the isomorphism relation on all countable partial orders $\cong_{PO}$ is Borel reducible to the isomorphism relation $\cong_{DPO}$ on countable dense partial orders.

Specifically, given any countable partial order $\langle L,<_L\rangle$, I shall assign a countable dense partial order $\P_L$, in such a way that that the assignment $L\mapsto \P_L$ is a Borel function (on the codes for the orders) and $$L_0\cong_{PO}L_1\iff\P_{L_0}\cong_{DPO}\P_{L_1}.$$ Thus, it is a reduction of $\cong_{PO}$ to $\cong_{DPO}$.

Since $\cong_{PO}$ is known to be $\Sigma^1_1$-complete and furthermore Borel-bireducible with the isomorphism relation on countable graphs, on countable groups and so on, the conclusion is that classifying the countable dense partial orders is at least as hard as classifying these classes of structures. In particular, there can be no Borel way to exhibit one member of each isomorphism class. In this sense, this makes a strongly negative answer to the question.

Now, let's give the reduction $L\mapsto\P_L$. Suppose we are given an arbitrary countable partial order $\langle L,<_L\rangle$. To define $\P_L$, let us replace each element of $L$ with a copy of the rational line $\Q$, defining the new relation so that each element of this copy of $\Q$ acts like the original node it is replacing with respect to the other copies of $\Q$; furthermore, we add a new maximal element $\infty$ at the top of $\P_L$, and place a copy of the rational line going linearly (and incomparably with the other copies) between $\infty$ and the $0$ of each copy of $\Q$ that we added in the first step. And extend the relation by transitivity. This defines $\P_L$. (Can you picture it?)

Note that $\P_L$ is a countable dense partial order, since whenever $x<y$, then in fact there is a copy of $\Q$ between $x$ and $y$.

Furthermore, I claim that $L_0\cong L_1$ just in case $\P_{L_0}\cong\P_{L_1}$. The forward implication is trivial, so consider the reverse. The point is that $\infty$ is definable in $\P_L$, and from $\infty$, we can define the $0$s of the copies of $\Q$ that were added for each node, since these are the places where the linear segments from $\infty$ joint up with the rest of the order. Thus, we can identify the original copy of $L$ inside $\P_L$ as the $0$'s of the added copies of $\Q$, and so $\P_{L_0}\cong \P_{L_1}$ will imply $L_0\cong L_1$, as desired.

So we have a Borel reduction of the isomorphism relation on all countable partial orders to the isomorphism relation on all countable dense partial orders. Since the former is known to be very complicated, it follows that the latter is as well, and so there can be no simple classification.

Answer 2

This answer is to version 1 of the question.

Yes, note that such a poset would have to be linear. Then, a countable dense linear order can have one of the following 6 types:

1. Infinite and having no endpoints
2. Infinite and having both left and right endpoints
3. Infinite and having left endpoint only
4. Infinite and having right endpoint only
5. Cardinality 1.
6. Cardinality 0.

The fact that the endpoints-status is sufficient to determine the isomorphism type is discussed here

Answer 3

Here is the dummies version of why countable dense posets (meaning countable posets in which every maximal chain is densely ordered) are as complicated as countable binary relations in general, so that no reasonable classification of them is to be expected.

To any countable poset $(P,\lt)$ let us associate a countable set $A$ and an irreflexive binary relation $R\subseteq A\times A$ as follows: $A$ is the set of all minimal elements of $P$, and $$R=\{(a,b)\in A\times A:\exists x,y\in P\ (a\lt x\lt y\wedge b\not\lt x\wedge b\lt y)\}.$$ Let's call $(A,R)$ the BRSC of $(P,\lt)$.

Proposition. Given a countable set $A$ and an irreflexive binary relation $R\subseteq A\times A$, we can construct a countable dense poset $(P,\lt)$ such that the BRSC of $(P,\lt)$ is isomorphic to $(A,R)$.

Proof. We assume that $A$ is disjoint from $A\times A\times\mathbb Q$. Let $$P=A\cup\{(a,b,x):(a,b)\in R\wedge x\in\mathbb Q\}.$$ The ordering of $P$ has the following comparisons and no others: $$(a,b,x)\lt(a,b,y)\text{ when }(a,b)\in R\wedge x,y\in\mathbb Q\wedge x\lt y;$$ $$a\lt(a,b,x)\text{ when }a,b\in R\wedge x\in\mathbb Q;$$ $$b\lt(a,b,x)\text{ when }(a,b)\in R\wedge x\in\mathbb Q\wedge x\gt0.$$