To show that a given graded function is the height function

103 Views Asked by At

My background in order theory is not very strong, and I'm confused about the following. The definition and theorems are from Lattices and ordered sets by Roman:

Let $(P,\le)$ be a partially ordered set, where $P$ is finite, i.e. $|P|=n$. Then we defined the distance $d(a,b)$ of two elements in $a,b\in P$ as the maximum length of all maximal chains from $a$ to $b$. Where a chain is defined to be a subset $S\subset P$ if $S$ is totally ordered by $\le$. In this finite case, we have just finite chains, which can be written in the form

$$a_1<a_2<\dots<a_n$$

where the length of such a chain is $n-1$. A chain from $a$ to $b$ is a chain in $P$, whose smallest element is $a$ and largest element is $b$. A maximal chain from $a$ to $b$ is a chain, which is not contained in a larger chain, in the sense of set inclusion, from $a$ to $b$. The distance $d(a,b)$ for elements $a,b\in P$ is defined as the maximum length among all maximal chains from $a$ to $b$. The height of a given element $a\in P$ is defined as $d(0,a)$ (we suppose $0\in P$).

I know that in a partially ordered set which contains $0$ it is equivalent to have the Jordan-Dedekind chain property and that $P$ is graded by its height function.

I have the following question: Suppose I know there is a function $g:P\to\mathbb{N}$ such that $a<b\Rightarrow g(a)<g(b)$. Moreover I know that $g(0)=0$. Now I was able to prove that for $a<b$ such that there is no $c$ with $a<c<b$ we have $g(b)=g(a)+1$. So I know that $P$ is graded by $g$. But why does it follow from $g(0)=0$ that $g$ is equal the height function, i.e. $g(a)=d(0,a)$?

1

There are 1 best solutions below

0
On BEST ANSWER

Let $C=(b_1=0,b_2,b_3, \ldots ,b_t=a)$ be a longest-length chain from $0$ to $a$. Then $d(0,a)=t-1$. Then there is no $c$ such that $b_i < c <b_{i+1}$ (otherwise $c$ could be inserted, producing a longer chain), so by the property you have already shown, $g(b_{i+1})=g(b_i)+1$. It follows that $g(b_i)=i-1$ for all $i$, hence $g(a)=t-1=d(0,a)$ and we are done.