1
$\begingroup$

What should I call a poset with the property that each element has AT MOST ONE predecessor?

(I'm actually interested in the special case in which there are no infinite descending chains.)

CLARIFICATION: I mean each element has a unique immediate predecessor.
As you go higher up there can be branching, but never collapsing. That is, I don't want to allow $a < z$ and $b < z$ with $a$ and $b$ incomparable; but I am happy with $a< y$ and $a< z$ with $y$ and $z$ incomparable.

FURTHER:

  1. The immediate predecessor should be the largest predecessor. If I write $i-1$ for the unique immediate predecessor of $i$, then $i-1 \leq x \leq i$ forces either $x = i-1$ or $x = i$.

  2. I should have said -- and now do say -- that each element has at most one immediate predecessor.

$\endgroup$
2
  • $\begingroup$ But must the immediate predecessor of the node be largest among all predecessors? $\endgroup$ Commented Dec 18, 2010 at 14:16
  • $\begingroup$ The second part of your further comment (1) does not express what you say in the first part. Having a largest predecessor would mean that $x\lt i\implies x\leq i-1$, which is not equivalent to what you wrote. $\endgroup$ Commented Dec 18, 2010 at 15:29

1 Answer 1

6
$\begingroup$

A partial order with no infinite descending chains is said to be well-founded. Every well-founded partial order admits an ordinal ranking function, an assignment of nodes in the order to ordinals, such that higher nodes get larger ordinals. One can therefore speak of the ordinal rank of a node or the height of the whole order. It is common to prove things about such orders using transfinite induction, either on the ordinal ranks or on the partial order directly.

Your other property, about every node having a unique predecessor (do you mean immediate predecessor?), is a discreteness property, which by iterating is clearly incompatible with well-foundedness.

But perhaps you mean that the partial order is well-founded, and every node has at most one immediate predecessor? In this case, the height of the order will be $\omega$, since there will be no node of limit rank. In this case, your partial order is: a well-founded partial order of height at most $\omega$.

But it still depends on what you mean by predecessor, since one could have a node $b$ with an immediate predecessor $a$, and also with an increasing sequence below $b$ to the side of $a$. Would this count for you? If so, then infinite ranks would still be possible.

(The usual meaning of predecessor in a partial order is simply that $a$ is a predecessor of $b$ if and only if $a\lt b$. With this meaning, the only partial order in which every element has a unique predecessor is the empty order, since if $z$ is a node in the order, it has a unique predecessor $y$, which also must have a predecessor $x$, which would also be a predecessor of $z$, a contradiction.)

$\endgroup$
3
  • $\begingroup$ I tried to clarify! Basically, the poset should look like a forest (in the sense of graph theory). $\endgroup$
    – Jeff Strom
    Commented Dec 18, 2010 at 14:16
  • 4
    $\begingroup$ In that case, and in light of the other things you have said, you have a well-founded tree (or forest) of height at most $\omega$. For partial orders, a tree is a partial order in which the predecessors of every node are linearly ordered. Combined with well-foundedness, this means that the predecessors of every node are well-ordered, and so the tree arranges itself naturally into levels. Your immediate predecessor assumption means that every node is on a finite level (so the total height is at most $\omega$). $\endgroup$ Commented Dec 18, 2010 at 15:26
  • $\begingroup$ It's my pleasure. $\endgroup$ Commented Dec 18, 2010 at 23:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .