Product order

In mathematics, given partial orders ${\displaystyle \preceq }${\displaystyle \preceq } and ${\displaystyle \sqsubseteq }${\displaystyle \sqsubseteq } on sets ${\displaystyle A}${\displaystyle A} and ${\displaystyle B}${\displaystyle B}, respectively, the product order^{[1] [2] [3] [4]} (also called the coordinatewise order^{[5] [3] [6]} or componentwise order^{[2] [7]} ) is a partial order ${\displaystyle \leq }${\displaystyle \leq } on the Cartesian product ${\displaystyle A\times B.}${\displaystyle A\times B.} Given two pairs ${\displaystyle \left(a_{1},b_{1}\right)}${\displaystyle \left(a_{1},b_{1}\right)} and ${\displaystyle \left(a_{2},b_{2}\right)}${\displaystyle \left(a_{2},b_{2}\right)} in ${\displaystyle A\times B,}${\displaystyle A\times B,} declare that ${\displaystyle \left(a_{1},b_{1}\right)\leq \left(a_{2},b_{2}\right)}${\displaystyle \left(a_{1},b_{1}\right)\leq \left(a_{2},b_{2}\right)} if ${\displaystyle a_{1}\preceq a_{2}}${\displaystyle a_{1}\preceq a_{2}} and ${\displaystyle b_{1}\sqsubseteq b_{2}.}${\displaystyle b_{1}\sqsubseteq b_{2}.}

Another possible order on ${\displaystyle A\times B}${\displaystyle A\times B} is the lexicographical order. It is a total order if both ${\displaystyle A}${\displaystyle A} and ${\displaystyle B}${\displaystyle B} are totally ordered. However the product order of two total orders is not in general total; for example, the pairs ${\displaystyle (0,1)}${\displaystyle (0,1)} and ${\displaystyle (1,0)}${\displaystyle (1,0)} are incomparable in the product order of the order ${\displaystyle 0<1}${\displaystyle 0<1} with itself. The lexicographic combination of two total orders is a linear extension of their product order, and thus the product order is a subrelation of the lexicographic order.^[3]

The Cartesian product with the product order is the categorical product in the category of partially ordered sets with monotone functions.^[7]

The product order generalizes to arbitrary (possibly infinitary) Cartesian products. Suppose ${\displaystyle A\neq \varnothing }${\displaystyle A\neq \varnothing } is a set and for every ${\displaystyle a\in A,}${\displaystyle a\in A,} ${\displaystyle \left(I_{a},\leq \right)}${\displaystyle \left(I_{a},\leq \right)} is a preordered set. Then the product preorder on ${\displaystyle \prod _{a\in A}I_{a}}${\displaystyle \prod _{a\in A}I_{a}} is defined by declaring for any ${\displaystyle i_{\bullet }=\left(i_{a}\right)_{a\in A}}${\displaystyle i_{\bullet }=\left(i_{a}\right)_{a\in A}} and ${\displaystyle j_{\bullet }=\left(j_{a}\right)_{a\in A}}${\displaystyle j_{\bullet }=\left(j_{a}\right)_{a\in A}} in ${\displaystyle \prod _{a\in A}I_{a},}${\displaystyle \prod _{a\in A}I_{a},} that

${\displaystyle i_{\bullet }\leq j_{\bullet }}${\displaystyle i_{\bullet }\leq j_{\bullet }} if and only if ${\displaystyle i_{a}\leq j_{a}}${\displaystyle i_{a}\leq j_{a}} for every ${\displaystyle a\in A.}${\displaystyle a\in A.}

If every ${\displaystyle \left(I_{a},\leq \right)}${\displaystyle \left(I_{a},\leq \right)} is a partial order then so is the product preorder.

Furthermore, given a set ${\displaystyle A,}${\displaystyle A,} the product order over the Cartesian product ${\displaystyle \prod _{a\in A}\{0,1\}}${\displaystyle \prod _{a\in A}\{0,1\}} can be identified with the inclusion order of subsets of ${\displaystyle A.}${\displaystyle A.}^[4]

The notion applies equally well to preorders. The product order is also the categorical product in a number of richer categories, including lattices and Boolean algebras.^[7]

• Direct product of binary relations
• Examples of partial orders
• Star product, a different way of combining partial orders
• Orders on the Cartesian product of totally ordered sets
• Ordinal sum of partial orders
• Ordered vector space – Vector space with a partial order

• Order theory
• Mathematics stubs

• Articles with short description
• Short description matches Wikidata
• All stub articles