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


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)$?


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.


Your Answer

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