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...
Printable View
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...
What is the definition of the length of an ordered set? Are we talking about partial or total orders?
partially ordered sets, where the length is the the size of the longest chain in the poset.
Ifand
are chains in P and Q, respectively, then
,(a_2,b_1),\dots,(a_n,b_1),)
is a chain in P x Q, so length(P x Q) >= length(P) + length(Q). Conversely, if you have a chain
in P x Q, then for each
you have
or
(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).