product of posets

Cartesian Ordering

Let $(P_1,{\le }_1)$ and $(P_2,{\le }_2)$ be posets. Let $P=P_1\times P_2$, the Cartesian product of the underlying sets. Next, define a binary relation $\le$ on $P$, given by

$$(a,b)\le (c,d)\mathit{\hspace{1em}\hspace{1em}}\text{ iff }\mathit{\hspace{1em}\hspace{1em}}a{\le }_{1}c\text{ and }b{\le }_{2}d.$$

Then $\le$ is a partial order on $P$. $(P,\le )$ is called the product of posets $(P_1,{\le }_1)$ and $(P_2,{\le }_2)$. The ordering $\le$ is called the Cartesian ordering. As it is customary, we write $P$ to mean $(P,\le )$.

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\le 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)\le (c,d)$, which implies $a{\le }_{1}c$ and $b{\le }_{2}d$. Also, $(c,b)$ and $(a,d)$ are comparable. But since $b{\le }_{2}d$, we must have $(c,b)\le (a,d)$, which means $c{\le }_{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 ${ℝ}^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 ${ℝ}^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)\le (c,d)\mathit{\hspace{1em}}\text{ iff }\mathit{\hspace{1em}}\{\begin{array}{cc}a\le c\text{, or }\hfill & \\ a=c\text{ and }b\le d.\hfill & \end{array}$$

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)\le (b_i)$ iff there is some $k\in I$ such that $a_j=b_j$ for all and $a_k\le 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)\le (a_i)$, since $a_i\le a_i$ for any $i\in I$.

• (Transitivity). If $(a_i)\le (b_i)$ and $(b_i)\le (c_i)$, then for some $k,\mathrm{\ell }\in I$ we have that

  1. $a_j=b_j$ for all and $a_k\le b_k$, and

  2. $b_j=c_j$ for all and $b_{\mathrm{\ell }}\le c_{\mathrm{\ell }}$.

  Since $I$ is a total order, $k$ and $\mathrm{\ell }$ are comparable, say $k\le \mathrm{\ell }$, so that $a_j=b_j=c_j$ for all and $a_k\le b_k\le c_k$. Since $P_k$ is partially ordered, $a_k\le c_k$ as well. Therefore $(a_i)\le (c_i)$.

• (Antisymmetry). Finally, suppose $(a_i)\le (b_i)$ and $(b_i)\le (a_i)$. If $(a_i)\ne (b_i)$, then $(a_i)\le (b_i)$ implies that we can find $k\in I$ such that $a_j=b_j$ for all and . By the same token, $(b_i)\le (a_i)$ implies the existence of $\mathrm{\ell }\in I$ with $b_j=a_j$ for all and . Since $I$ is linearly ordered, we can again assume that $k\le \mathrm{\ell }$. But then this means that either , in which case $b_k=a_k$, a contradiction, or $k=\mathrm{\ell }$, in which case we have that , another contradiction. Therefore $(a_i)=(b_i)$.

This completes the proof. ∎

Title	product of posets
Canonical name	ProductOfPosets
Date of creation	2013-03-22 16:33:25
Last modified on	2013-03-22 16:33:25
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	14
Author	CWoo (3771)
Entry type	Definition
Classification	msc 06A06
Classification	msc 06A99
Related topic	LatticeInMathbbRn
Defines	product of lattices
Defines	Cartesian ordering
Defines	lexicographic ordering