# Name for a “layered” type of partial order?

I have a partial order $\prec$ over a (finite) set $S$ satisfying the following property:

There exists a function $f:S\rightarrow \mathbb N$ such that $x\prec y \Leftrightarrow 0<f(x)< f(y)$.

That is, each element is given a layer, and two elements are comparable iff they are in different layers, except for elements in layer 0 which are not comparable with any other.

Is there a name for such an order? What if I lift the constraint about layer 0?

Here are equivalent interpretations, in case it rings a bell:

• The order can be seen as a ranking in a competition with ties (there can be several people at each position), where only a subset of the participants is ranked

• Writting $S_i=\{x\mid f(x)=i\}$, the order can be "described" by $S_1 \prec S_2 \prec ....\prec S_k$.

I don't know a name for the exact conditions on your $(S,\prec)$. At first I thought it was just well-foundedness, but, I overlooked your requirement "except for elements in layer 0 which are not comparible [sic] with any other" (despite your boldface). As Brian Scott points out in his comment, your conditions are stronger than well-foundedness.

There are a few ways to characterize well-founded partial orders $(P,<)$, all equivalent in ZFC:

1. every nonempty subset of $P$ has a $<$-minimal element;
2. there are no infinite descending chains in $(P,<)$;
3. there is an order preserving function from $(P,<)$ into the ordinals.

If $(P,<)$ is well-founded then a stronger statement than 3. can be made: $(P,<)$ has a rank function, a function $\rho\colon (P,<)\to \mathsf{Ord}$ into the ordinals whose range has no "gaps" — that is, its range is an ordinal $\beta$, and for every $\alpha < \beta$, $\rho^{-1}(\alpha)$ is nonempty. The elements of $\rho^{-1}(\alpha)$ have rank, or "height", $\alpha$. The rank function is defined by well-founded recursion along $<$: $$\rho(y) = sup_{x < y} (\rho(x) + 1).$$ Elements of rank $0$ are precisely the $<$-minimal elements.

Your $f$ isn't exactly a rank function, even if its range has no gaps: if $x\in S$ is a minimal element that's incomparable with everything in $S$, then $f(x) = 0$, but if $x\in S$ is a minimal element that has a successor, then $f(x) > 0$.

However, that's not the only extra requirement you impose. You also require that for $x,y\in S$, if $f(x) = i < j = f(y)$ then $x\prec y$. This rules out many typical examples of well-founded partial orders, e.g. most trees.

• The stated condition implies but is quite different from well-foundedness. Those $x\in S$ such that $f(x)\le 1$ all have rank $0$, and those such that $f(x)\ge 1$ all have rank $f(x)-1$, but if we exclude $f^{-1}[\{0\}]$, we have $x\prec y$ iff $x$ is of smaller rank than $y$; well-foundedness gives only one of those implications. – Brian M. Scott Apr 13 '16 at 23:58
• @BrianM.Scott It seems I didn't take into account "except for elements in layer 0 which are not comparible with any other", despite the boldface. I'll attempt a fixup. – BrianO Apr 14 '16 at 2:35
• @BrianM.Scott OK see if that works please. – BrianO Apr 14 '16 at 3:04
• Not quite: you’re still missing the iff aspect. Consider the partial order $\{\langle 0,1\rangle,\langle 0,2\rangle,\langle 1,3\rangle,\langle 2,4\rangle\}$ on $\{0,1,2,3,4,5\}$; it’s well founded, and if we set f(5)=0$,$f(0)=1$,$f(1)=f(2)=2$, and$f(3)=f(4)=3$we almost have the OP’s situation, but not quite: for that we’d have to have$\langle 1,4\rangle$and$\langle 2,3\rangle$as well. – Brian M. Scott Apr 14 '16 at 3:10 • @BrianM.Scott I understood that requirement of the OP — if$fx) = i < j = f(y)$then$x\prec y$— but didn't mention it. It's worth mentioning (just did). – BrianO Apr 14 '16 at 4:08 Consider the following posets. If I have understood your question correctly, you're only interested in posets like$P$, and not in posets like$Q$. So rank functions don't quite cut it, because they can't be used to pin down the notion you're interested in. The way I suggest thinking about posets like$P$uses the concept of a linear sum. It works like this: given posets$A$and$B$, write$A + B$for the poset whose underlying set is the disjoint union$A \sqcup B$, where the order on$A \sqcup B$is required to satisfy the following: • The inclusion$\eta_0 : A \rightarrow A+B$is an embedding. • The inclusion$\eta_1 : B \rightarrow A+B$is an embedding. • For all$a \in A$and$b \in B$, we have$\eta_0(a) \leq \eta_1(b)$. Now to each natural number$n$, assign a set$\underline{n} = \{0,\ldots,n-1\}.$Think of$\underline{n}$as a poset whose order relation is just the equality relation (the "discrete poset on$n$generators"). Then the poset$P$can be defined by $$P = \underline{1}+\underline{2}+\underline{2}+\underline{1}.$$ Furthermore, the following is true. Suppose we have a poset$P$and a function$f : P \rightarrow \mathbf{Pos}$that assigns to each element$x \in P$a poset$f(x)$. Then we can define a "linear sum" $$\sum_{x \in P} f(x)$$ in the obvious way. Ignoring the special "level$0$" elements that you mention, the posets you're interested in are precisely those that can be expressed as $$\sum_{n \in \mathbb{N}} \underline{a_n}$$ for some sequence of natural numbers$a$that is eventually$0$. Lets call such things layides for convenience (that's a quick and dirty made-up word). Then the more general concept you're interested in is: call$P$a generalized layide iff$P$can be expressed as$D \sqcup L$, where$D$is a finite discrete poset and$L$is a layide. (And$\sqcup$is the coproduct of posets). As you allude to in your question, it might be more useful to consider the equivalence classes of your set, rather than the set itself.$S/f$has a lot of nice properties: it's totally ordered, etc. By the way, you tagged this as lattice-orders; if this was intentional, you can prove the following little theorem: Theorem: if$S_i$has more than one element, then$S_{i +1}$must have only one element. To see this, just note that$S_i\$ must have not just an upper bound, but a least upper bound.

• My lattice-orderstag was badly chosen (from my bad idea of the definition of a lattice, I thought my order could be one, but in fact it's not necessary). I've edited to the more general order-theory instead. – tarulen Apr 18 '16 at 7:14