product of posets

Cartesian Ordering

Let $(P_{1},\leq_{1})$ and $(P_{2},\leq_{2})$ be posets. Let $P=P_{1}\times P_{2}$, the Cartesian product of the underlying sets. Next, define a binary relation $\leq$ on $P$, given by

 $(a,b)\leq(c,d)\qquad\mbox{ iff }\qquad a\leq_{1}c\mbox{ and }b\leq_{2}d.$

Then $\leq$ is a partial order on $P$. $(P,\leq)$ is called the product of posets $(P_{1},\leq_{1})$ and $(P_{2},\leq_{2})$. The ordering $\leq$ is called the Cartesian ordering. As it is customary, we write $P$ to mean $(P,\leq)$.

If $P_{1}$ and $P_{2}$ are antichains, their product is also an antichain. If they are both join semilattices, then their product $P$ is a join semilattice as well. The join of $(a,b)$ and $(c,d)$ are given by

 $(a,b)\vee(c,d)=(a\vee_{1}c,b\vee_{2}d).$

Conversely, if the product $P$ of two posets $P_{1}$ and $P_{2}$ is a join semilattice, then $P_{1}$ and $P_{2}$ are both join semilattices. If $(a,b)\vee(c,d)=(e,f)$, then $e$ is the upper bound of $a$ and $c$. If $g\leq e$ is an upper bound of $a$ and $c$, then $(g,f)$ is an upper bound of $(a,b)$ and $(c,d)$, whence $(g,f)=(e,f)$, or $g=e$. So $g=a\vee_{1}c$. Similarly, $f=b\vee_{2}d$. Dually, $P=P_{1}\times P_{2}$ is a meet semilattice (and consequently, a lattice) iff both $P_{1}$ and $P_{2}$ are. Equivalently, the product of (semi)lattices can be defined purely algebraically (using $\vee$ and $\wedge$ only).

Another simple fact about the product of posets is the following: the product is never a chain unless one of the posets is trivial (a singleton). To see this, let $P=P_{1}\times P_{2}$ and $(a,b),(c,d)\in P$. Then $(a,b)$ and $(c,d)$ are comparable, say $(a,b)\leq(c,d)$, which implies $a\leq_{1}c$ and $b\leq_{2}d$. Also, $(c,b)$ and $(a,d)$ are comparable. But since $b\leq_{2}d$, we must have $(c,b)\leq(a,d)$, which means $c\leq_{1}a$, showing $a=c$, or $P_{1}=\{a\}$.

Remark. The product of two posets can be readily extended to any finite product, countably infinite product, or even arbitrary product of posets. The definition is similar to the one given above and will not be repeated here.

An example of a product of posets is the lattice in $\mathbb{R}^{n}$ (http://planetmath.org/LatticeInMathbbRn), which is defined as the free abelian group over $\mathbb{Z}$ in $n$ generators. But from a poset perspective, it can be viewed as a product of $n$ chains, each order isomorphic to $\mathbb{Z}$. As we have just seen earlier, this product is a lattice, and hence the name “lattice” in $\mathbb{R}^{n}$.

Lexicographic Ordering

Again, let $P_{1}$ and $P_{2}$ be posets. Form the Cartesian product of $P_{1}$ and $P_{2}$ and call it $P$. There is another way to partial order $P$, called the lexicographic order. Specifically,

 $(a,b)\leq(c,d)\quad\mbox{ iff }\quad\begin{cases}a\leq c\mbox{, or }\\ a=c\mbox{ and }b\leq d.\end{cases}$

More generally, if $\{P_{i}\mid i\in I\}$ is a collection of posets indexed by a set $I$ that is linearly ordered, then the Cartesian product $P:=\prod P_{i}$ also has the lexicographic order:

$(a_{i})\leq(b_{i})$ iff there is some $k\in I$ such that $a_{j}=b_{j}$ for all $j and $a_{k}\leq b_{k}$.

We show that this is indeed a partial order on $P$:

Proof.

The three things we need to verify are

• (Reflexivity). Clearly, $(a_{i})\leq(a_{i})$, since $a_{i}\leq a_{i}$ for any $i\in I$.

• (Transitivity). If $(a_{i})\leq(b_{i})$ and $(b_{i})\leq(c_{i})$, then for some $k,\ell\in I$ we have that

1. (a)

$a_{j}=b_{j}$ for all $j and $a_{k}\leq b_{k}$, and

2. (b)

$b_{j}=c_{j}$ for all $j<\ell$ and $b_{\ell}\leq c_{\ell}$.

Since $I$ is a total order, $k$ and $\ell$ are comparable, say $k\leq\ell$, so that $a_{j}=b_{j}=c_{j}$ for all $k<\ell$ and $a_{k}\leq b_{k}\leq c_{k}$. Since $P_{k}$ is partially ordered, $a_{k}\leq c_{k}$ as well. Therefore $(a_{i})\leq(c_{i})$.

• (Antisymmetry). Finally, suppose $(a_{i})\leq(b_{i})$ and $(b_{i})\leq(a_{i})$. If $(a_{i})\neq(b_{i})$, then $(a_{i})\leq(b_{i})$ implies that we can find $k\in I$ such that $a_{j}=b_{j}$ for all $j and $a_{k}. By the same token, $(b_{i})\leq(a_{i})$ implies the existence of $\ell\in I$ with $b_{j}=a_{j}$ for all $j<\ell$ and $b_{\ell}. Since $I$ is linearly ordered, we can again assume that $k\leq\ell$. But then this means that either $k<\ell$, in which case $b_{k}=a_{k}$, a contradiction, or $k=\ell$, in which case we have that $a_{k}, another contradiction. Therefore $(a_{i})=(b_{i})$.

This completes the proof. ∎

Title product of posets ProductOfPosets 2013-03-22 16:33:25 2013-03-22 16:33:25 CWoo (3771) CWoo (3771) 14 CWoo (3771) Definition msc 06A06 msc 06A99 LatticeInMathbbRn product of lattices Cartesian ordering lexicographic ordering