You are here
Homeproduct of posets
Primary tabs
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}$, 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<k$ 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
(a) $a_{j}=b_{j}$ for all $j<k$ and $a_{k}\leq b_{k}$, and
(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<k$ and $a_{k}<b_{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}}<a_{{\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}<b_{k}=b_{{\ell}}<a_{{\ell}}=a_{k}$, another contradiction. Therefore $(a_{i})=(b_{i})$.
This completes the proof. ∎
Mathematics Subject Classification
06A06 no label found06A99 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections