How to demonstrate the finite height of a lattice?

707 Views Asked by At

I would like to ask you for help with a formal demonstration concerning the finite height of a lattice.

My lattice is defined like this: is a lattice of vectors, each with exactly $n$ cells. In each cell can be contained only or $\top$ or V or $\bot$, with $\bot$ $\sqsubset$ V $\sqsubset$ $\top$.

The partial order ($\dot{\sqsubseteq}$) on the vector lattice is component-wise: a vector $v$ of length $n$ is $\dot{\sqsubseteq}$ of a vector $w$ of length $n$ if and only if $\forall$ $i$ ($i$ is an index) $v[i]$ $\sqsubseteq$ $w[i]$

The join $\dot{\sqcup}$ between two vectors (component-wise) $v$ and $w$ returns a vector $z$ such that $\forall$ $i$ $z[i] = $ $v[i] \sqcup w[i]$.

For example if $n$ = 2, we have this lattice: Vector lattice with n=2

For $n$ = 3, the lower vector will be [$\bot$,$\bot$,$\bot$] and the upper vector will be: [$\top$,$\top$,$\top$].

I see that in both cases the (finite) lattice height is always equal to $2n$. I would like to generalize this reasoning formally, and to prove that a lattice with these characteristics, for any $n$ length of the vector, always has finite height $2n$.

Thanks a lot!

1

There are 1 best solutions below

3
On

According to this answer, the height of a poset $h$ satisfies the following property: $$h(L \times K) = h(L) + h(K) - 1.$$

However, what is considered to be the height of a poset there, is the maximum number of elements in one of its chains.
That is not my definition and according to the results you have reached, it isn't yours either.
I (and apparently you) say that the height of a poset is the maximum number of elements in one of its chain minus one.
With this new definition, the above formula is corrected to $$h(L \times K) = h(L) + h(K).$$

Given that the lattice you're interested in is $\mathbf 3^n$, where $\mathbf 3$ is the three-element lattice with three elements $\bot < V < \top$, it's easy to show (using the above formula), by induction on $n$, that $h(\mathbf 3^n) = 2n$.


Added
Given that the author of the linked answer considers the height of a poset as the maximum number of elements of one of its chains, let's call $m(P)$ to that value, for a poset $P$.
So that answers tells us that $$m(P \times Q) = m(P) + m(Q) - 1.$$ Now, we define the height of a poset $P$ to be $h(P) = m(P) - 1$.
So \begin{align} h(P \times Q) &= m(P \times Q) - 1 \\ &= m(P) + m(Q) - 2\\ &= (m(P) - 1) + (m(Q) - 1)\\ &= h(P) + h(Q). \end{align}

Now, for the induction.
Let us see that $h(\mathbf 3^n) = 2n$. Clearly it is true for $n=1$, since $h(\mathbf 3) = 2$.
If $h(\mathbf 3^n)=2n$, then $$h(\mathbf 3^{n+1}) = h(\mathbf 3 \times \mathbf 3^n) = h(\mathbf 3) + h(\mathbf 3^n) = 2 + 2n = 2(n+1).$$