1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Brian M. Scott Apr 13 '16 at 23:58
  • $\begingroup$ @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. $\endgroup$ – BrianO Apr 14 '16 at 2:35
  • $\begingroup$ @BrianM.Scott OK see if that works please. $\endgroup$ – BrianO Apr 14 '16 at 3:04
  • $\begingroup$ 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. $\endgroup$ – Brian M. Scott Apr 14 '16 at 3:10
  • 1
    $\begingroup$ @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). $\endgroup$ – BrianO Apr 14 '16 at 4:08
2
$\begingroup$

Consider the following posets.

enter image description here

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – tarulen Apr 18 '16 at 7:14

Your Answer

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

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