length of Lattices

• Oct 4th 2011, 11:28 PM
Goku
length of Lattices
Prove that

length(P x Q) = length(P) + length(Q)

where P, Q are ordered sets of finite length.

Any ideas of where to start...
• Oct 5th 2011, 11:21 AM
emakarov
Re: length of Lattices
What is the definition of the length of an ordered set? Are we talking about partial or total orders?
• Oct 5th 2011, 01:37 PM
Goku
Re: length of Lattices
partially ordered sets, where the length is the the size of the longest chain in the poset.
• Oct 5th 2011, 02:10 PM
emakarov
Re: length of Lattices
If \$\displaystyle a_1,\dots,a_n\$ and \$\displaystyle b_1,\dots,b_m\$ are chains in P and Q, respectively, then \$\displaystyle (a_1,b_1),(a_2,b_1),\dots,(a_n,b_1),\$\$\displaystyle (a_n,b_2),\dots,(a_n,b_m)\$ is a chain in P x Q, so length(P x Q) >= length(P) + length(Q). Conversely, if you have a chain \$\displaystyle (a_1,b_1)>\dots>(a_n,b_n)\$ in P x Q, then for each \$\displaystyle i\$ you have \$\displaystyle a_{i+1}>a_i\$ or \$\displaystyle b_{i+1}>b_i\$ (or both). So, you can construct chains in P and Q whose total length is >= n. This means that length(P) + length(Q) >= length(P x Q).