5
$\begingroup$

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

$\endgroup$
0

3 Answers 3

10
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ is there any good reference on poset theory ? $\endgroup$ Sep 30, 2014 at 19:56
  • $\begingroup$ I'm sorry that I don't have a reference specifically on posets, although they appear interspersed in many set theory texts. $\endgroup$ Oct 1, 2014 at 9:01
4
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Also, for countable dense linear orders I think the result is that each is isomorphic to $(S,\lt_{\mathbb{Q}})$ for some subset $S \subseteq \mathbb{Q}.$ For example the rationals $[0,1] \cup (2,3].$ $\endgroup$ Sep 30, 2014 at 1:56
  • $\begingroup$ Bjørn, although not phrased that way, the question is about posets such that, whenever two points are comparable, then there are infinitely many points in between. $\endgroup$ Sep 30, 2014 at 2:29
  • 6
    $\begingroup$ @bof Stone soup. Of the two interpretations, one is interesting, the other is not. So, let's go with the interesting one. $\endgroup$ Sep 30, 2014 at 5:37
  • $\begingroup$ @Andres: Speaking of stone soup... $\endgroup$
    – Asaf Karagila
    Sep 30, 2014 at 6:18
  • $\begingroup$ @AsafKaragila Yes, thank you. I figured someone would find the link and add it. $\endgroup$ Sep 30, 2014 at 6:20
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ +1, I agree. This argument provides a Borel reduction from the isomorphism relation on countable graphs to the isomorphism relation on countable dense partial orders. We know in general that isomorphisms-of-graphs is Borel bireducible to isomorphisms-of-groups and to isomorphisms-of-partial-orders and so on for many different kinds of structures. So the classification problems for all these structures are all Borel reducible to one another, and in this sense they are equally hard. In particular, the language of Borel reducibility allows us to make precise statements about such things. $\endgroup$ Oct 2, 2014 at 9:29
  • $\begingroup$ You say that you have a 'dummies' version, but isn't the construction of $\mathbb{P}_L$ in my argument also simple? I just replace every node in $L$ with a copy of $\mathbb{Q}$ and added a few more copies of $\mathbb{Q}$ pointing at the centers of those copies. $\endgroup$ Oct 2, 2014 at 9:34
  • 1
    $\begingroup$ @JoelDavidHamkins I guess so. I have to confess that your answer was TLDR for me, so I skipped to the last paragraph, where you say that a countable dense poset can encode an arbitrary countable poset. That's fine if you already know that all that other stuff is reducible to countable posets. I thought it was better to reduce countable digraphs directly to countable dense posets, because even dummies like me know how complicated countable digraphs can be, e.g., models of set theory. You see, I don't know very much about this stuff. Thanks for your comments and the upvote. $\endgroup$
    – bof
    Oct 2, 2014 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.