Product order

{\displaystyle \mathbb {N} } — Hasse diagram of the product order on $\mathbb {N}$ × $\mathbb {N}$

In mathematics, given a partial order $\preceq$ and $\sqsubseteq$ on a set $A$ and $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 ordering $\leq$ on the Cartesian product $A\times B.$ Given two pairs $\left(a_{1},b_{1}\right)$ and $\left(a_{2},b_{2}\right)$ in $A\times B,$ declare that $\left(a_{1},b_{1}\right)\leq \left(a_{2},b_{2}\right)$ if $a_{1}\preceq a_{2}$ and $b_{1}\sqsubseteq b_{2}.$

Another possible ordering on $A\times B$ is the lexicographical order. It is a total ordering if both $A$ and $B$ are totally ordered. However the product order of two total orders is not in general total; for example, the pairs $(0,1)$ and $(1,0)$ are incomparable in the product order of the ordering $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 $A\neq \varnothing$ is a set and for every $a\in A,$ $\left(I_{a},\leq \right)$ is a preordered set. Then the product preorder on $\prod _{a\in A}I_{a}$ is defined by declaring for any $i_{\bullet }=\left(i_{a}\right)_{a\in A}$ and $j_{\bullet }=\left(j_{a}\right)_{a\in A}$ in $\prod _{a\in A}I_{a},$ that

i_{\bullet }\leq j_{\bullet }

if and only if

i_{a}\leq j_{a}

for every

a\in A.

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

Furthermore, given a set $A,$ the product order over the Cartesian product $\prod _{a\in A}\{0,1\}$ can be identified with the inclusion ordering of subsets of $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]

References

^ Neggers, J.; Kim, Hee Sik (1998), "4.2 Product Order and Lexicographic Order", Basic Posets, World Scientific, pp. 64–78, ISBN 9789810235895
^ ^a ^b Sudhir R. Ghorpade; Balmohan V. Limaye (2010). A Course in Multivariable Calculus and Analysis. Springer. p. 5. ISBN 978-1-4419-1621-1.
^ ^a ^b ^c Egbert Harzheim (2006). Ordered Sets. Springer. pp. 86–88. ISBN 978-0-387-24222-4.
^ ^a ^b Victor W. Marek (2009). Introduction to Mathematics of Satisfiability. CRC Press. p. 17. ISBN 978-1-4398-0174-1.
^ Davey & Priestley, Introduction to Lattices and Order (Second Edition), 2002, p. 18
^ Alexander Shen; Nikolai Konstantinovich Vereshchagin (2002). Basic Set Theory. American Mathematical Soc. p. 43. ISBN 978-0-8218-2731-4.
^ ^a ^b ^c Paul Taylor (1999). Practical Foundations of Mathematics. Cambridge University Press. pp. 144–145 and 216. ISBN 978-0-521-63107-5.