2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ If I understand your definitions, what you call "levels" will not necessarily be antichains, which seems to conflict with my intuition about that word. Is it on purpose that they're not? $\endgroup$ – Henning Makholm Sep 12 '15 at 22:34
  • $\begingroup$ Also, I think your "well-chained" partial orders are the same ones as are usually called well-founded partial orders. $\endgroup$ – Henning Makholm Sep 12 '15 at 22:40
  • $\begingroup$ @Henning: Are they not? They certainly aren't strong antichains, but I think the elements of a given level will be pairwise incomparable. If $x,y$ are distinct elements of a well-chained partial order $\langle S,R\rangle,$ and if $x\:R\:y,$ then it seems we have $\alt(x,S,R)<\alt(y,S,R),$ unless I'm missing something. $\endgroup$ – Cameron Buie Sep 12 '15 at 22:44
  • $\begingroup$ When I was reading about well-quasi-orders, I read that $\langle\Bbb N,\preceq\rangle$ was not a well partial order due to the existence of an infinite antichain. This disagrees with my usual understanding of well-foundedness. Is this perhaps an error? $\endgroup$ – Cameron Buie Sep 12 '15 at 22:48
  • $\begingroup$ x @Cameron: Consider an order that is the union of separate total orders of all finite lengths, plus a $\star$ element that sits above all of them, plus a $\star'$ element that sits above $\star$. Then every chain that ends at either $\star$ or $\star'$ is finite, so they both have altitude $\omega$. It would be nicer, and perhaps closer to your intention, to work with ranks, defined as $$\operatorname{rank}(x) = \sup_{y<x} (\operatorname{rank}(y)+1) $$ rather than by quantifying over chains. $\endgroup$ – Henning Makholm Sep 12 '15 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.