Name for a "layered" type of partial order?

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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