Are the following conditions necessary and sufficient for the desired partial order isomorphism?

95 Views Asked by At

Before I get to my questions, let me clarify some terminology and notation that I will be using. $\DeclareMathOperator{\pr}{pr}$ $\DeclareMathOperator{\ext}{ext}$ $\DeclareMathOperator{\rank}{rank}$ $\DeclareMathOperator{\lvl}{lvl}$ $\DeclareMathOperator{\alt}{alt}$ $\DeclareMathOperator{\ord}{ord}$

Given a relation $R,$ the reflexive reduction of $R$ is $$R^\neq:=\bigl\{\langle x,y\rangle\in R:x\ne y\bigr\}.$$

We say that a partial order $\langle S,R\rangle$ is well-chained if for each chain $C$ of $\langle S,R\rangle$--that is, each $C\subseteq S$ such that $\langle C,R\rangle$ is a (possibly non-strict) total order--we have that $R^\neq$ well-orders $C$. We say that a partial order $\langle S,R\rangle$ is well-founded if every non-empty subset of $S$ has an $R$-minimal element (though not necessarily an $R$-least element, of course). Note that well-founded partial orders are necessarily well-chained. The converse holds iff $\mathsf{DC}$ holds.

Given a set $S,$ a (possibly strict) partial order relation $R$ on $S,$ and $x\in S,$ we define/denote the set of $R$-predecessors of $x$ in $S$ by $$\pr(x,S,R):=\{s\in S:s\:R\:x,s\ne x\}.$$ Given a well-founded partial order $\langle S,R\rangle,$ we assign each element of $S$ an ordinal rank. For any $x\in S,$ we define $$\rank(x,S,R)=\sup\bigl\{\rank(y,S,R)+1:y\in\pr(x,S,R)\bigr\}.$$ The extent of a well-founded partial order $\langle S,R\rangle$ is the supremum of the ranks of its elements, that is, $$\ext(S,R):=\sup\bigl\{\rank(x,S,R)+1:x\in S\bigr\}.$$ Note that the notion of extent has more in common with the notion of height in the sense of trees than with height in the sense applicable to more general partial orders.

Given an ordinal $\alpha,$ the $\alpha$th level of a well-founded partial order $\langle S,R\rangle$ is the set of elements of $S$ of rank $\alpha$ in $\langle S,R\rangle,$ that is, $$\lvl(\alpha,S,R):=\bigl\{x\in S:\rank(x,S,R)=\alpha\bigr\}.$$

Given a set $S$ and a relation $R$ that well-orders $S,$ the order type of $\langle S,R\rangle$--denoted $\ord(S,R)$--is the unique ordinal $\alpha$ such that $\langle S,R\rangle$ is isomorphic to $\langle\alpha,\in\rangle.$

Finally, given a well-chained partial order $\langle S,R\rangle,$ we assign each element of $S$ and ordinal altitude. For any $x\in S,$ we define $$\alt(x,S,R):=\sup\bigl\{\ord(C,R):C\subseteq\pr(x,S,R)\text{ and }\langle C,R\rangle\text{ is a total order}\bigr\}.$$

My first (side) question regards terminology: are the notions above called "well-chained," "rank," "extent," and "altitude" usually referred to by different names?


My second (primary) question is about the structure $\langle\Bbb N,\preceq\rangle,$ where $\Bbb N$ is either the positive or nonnegative integers, and $\preceq$ is defined by $$m\preceq n\iff m\mid n.$$ Note that the structure has the following characteristics:

  • For any $m,n\in\Bbb N,$ there is a least upper bound and a greatest lower bound (namely, the least common multiple and greatest common divisor).
  • $\langle\Bbb N,\preceq\rangle$ is a well-founded partial order.
  • For all $n\in\Bbb N,$ $\rank(n,\Bbb N,\preceq)=\alt(n,\Bbb N,\preceq).$
  • The $0$th level has a unique element: $1$.
  • The $1$st level has countably-infinitely-many elements: the primes.
  • Given $m,n\in\Bbb N,$ we have $$\rank(m,\Bbb N,\preceq)+\rank(n,\Bbb N,\preceq)=\rank\left(\inf_{\langle\Bbb N,\preceq\rangle}\{m,n\},\Bbb N,\preceq\right)+\rank\left(\sup_{\langle\Bbb N,\preceq\rangle}\{m,n\},\Bbb N,\preceq\right).$$
  • For each $p\in\lvl(1,\Bbb N,\preceq)$ and each finite $1<n<\omega,$ there is a unique $y\in\lvl(n,\Bbb N,\preceq)$ such that $\pr(y,\Bbb N,\preceq)$ is a chain of $\langle\Bbb N,\preceq\rangle$ and $p\in\pr(y,\Bbb N,\preceq).$ (In particular, $y=p^n$.)
  • Since $\lvl(n,\Bbb N,\preceq)$ is non-empty for all $n<\omega,$ then $\ext(\Bbb N,\preceq)\ge\omega.$
  • Both the width of $\langle\Bbb N,\preceq\rangle$ and the cardinality of $\Bbb N$ are of course $\aleph_0.$
  • In the case that $0\notin\Bbb N,$ we also have $\lvl(\alpha,\Bbb N,\preceq)=\emptyset$ for $\alpha\ge\omega,$ so $\ext(\Bbb N,\preceq)=\omega.$ In the case that $0\in\Bbb N,$ we instead have that $0$ is the unique element of altitude $\omega,$ and $\ext(\Bbb N,\preceq)=\omega+1.$

It seems that the characteristics listed above make $\langle\Bbb N,\preceq\rangle$ (in either version of $\Bbb N$) unique up to isomorphism of partial orders. If they are sufficient, are any of them extraneous? If they aren't sufficient, is there a list of characteristics that is both necessary and sufficient?