|
|
|
|
height of an element in a poset
|
(Definition)
|
|
|
Let $P$ be a poset. Given any $a\in P$ , the lower set $\down a$ of $a$ is a subposet of $P$ . Call the height of $\down a$ less 1 the height of $a$ . Let's denote $h(a)$ the height of $a$ , so $$h(a)=\operatorname{height}(\down a)-1.$$ From this definition, we see that $h(a)=0$ iff $a$ is minimal and $h(a)=1$ iff $a$ is an atom. Also, $h$ partitions $P$ into equivalence classes, so that $a$ is equivalent to $b$ in $P$ iff $h(a)=h(b)$ . Two distinct elements in the same equivalence class are necessarily incomparable. In other words, the equivalence classes are antichains. Furthermore, given any two equivalence classes $[a],[b]$ , set $[a]\le[b]$ iff $h(a)\le h(b)$ , then the set of equivalence classes form a chain.
The height function of a poset $P$ looks remarkably like the rank function of a graded poset: $h$ is constant on the set of all minimal elements, and $h$ is isotone (preserves order). When is $h$ a rank function (the additional condition being the preservation of the covering relation)? The answer is given by a chain condition imposed on $P$ , called the Jordan-Dedekind chain condition:
(*) In a poset, the cardinalities of two maximal chains between common end points must be the same.
Suppose for each $a\in P$ , $h(a)$ is finite and $P$ has a unique minimal element $0$ . Then $P$ can be graded by $h$ iff (*) is satisfied. More generally, if we drop the assumption of the uniqueness of a minimal element, then $P$ can be graded by $h$ iff any two maximal chains ending at the same end point have the same length.
|
"height of an element in a poset" is owned by CWoo.
|
|
(view preamble | get metadata)
See Also: graded poset
| Also defines: |
Jordan-Dedekind chain condition |
This object's parent.
|
|
Cross-references: length, end point, finite, end points, cardinalities, chain condition, relation, covering, order, preserves, minimal elements, graded poset, rank function, height function, chain, antichains, incomparable, equivalent, equivalence classes, partitions, atom, minimal, iff, height, lower set, poset
This is version 7 of height of an element in a poset, born on 2006-12-31, modified 2007-01-09.
Object id is 8705, canonical name is HeightOfAnElementInAPoset.
Accessed 1763 times total.
Classification:
| AMS MSC: | 06A06 (Order, lattices, ordered algebraic structures :: Ordered sets :: Partial order, general) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|