Product order
In mathematics, given a partial order [math]\displaystyle{ \preceq }[/math] and [math]\displaystyle{ \sqsubseteq }[/math] on a set [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math], 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 [math]\displaystyle{ \leq }[/math] on the Cartesian product [math]\displaystyle{ A \times B. }[/math] Given two pairs [math]\displaystyle{ \left(a_1, b_1\right) }[/math] and [math]\displaystyle{ \left(a_2, b_2\right) }[/math] in [math]\displaystyle{ A \times B, }[/math] declare that [math]\displaystyle{ \left(a_1, b_1\right) \leq \left(a_2, b_2\right) }[/math] if [math]\displaystyle{ a_1 \preceq a_2 }[/math] and [math]\displaystyle{ b_1 \sqsubseteq b_2. }[/math]
Another possible ordering on [math]\displaystyle{ A \times B }[/math] is the lexicographical order, which is a total ordering. However the product order of two total orders is not in general total; for example, the pairs [math]\displaystyle{ (0, 1) }[/math] and [math]\displaystyle{ (1, 0) }[/math] are incomparable in the product order of the ordering [math]\displaystyle{ 0 \lt 1 }[/math] 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 [math]\displaystyle{ A \neq \varnothing }[/math] is a set and for every [math]\displaystyle{ a \in A, }[/math] [math]\displaystyle{ \left(I_a, \leq\right) }[/math] is a preordered set. Then the product preorder on [math]\displaystyle{ \prod_{a \in A} I_a }[/math] is defined by declaring for any [math]\displaystyle{ i_{\bull} = \left(i_a\right)_{a \in A} }[/math] and [math]\displaystyle{ j_{\bull} = \left(j_a\right)_{a \in A} }[/math] in [math]\displaystyle{ \prod_{a \in A} I_a, }[/math] that
- [math]\displaystyle{ i_{\bull} \leq j_{\bull} }[/math] if and only if [math]\displaystyle{ i_a \leq j_a }[/math] for every [math]\displaystyle{ a \in A. }[/math]
If every [math]\displaystyle{ \left(I_a, \leq\right) }[/math] is a partial order then so is the product preorder.
Furthermore, given a set [math]\displaystyle{ A, }[/math] the product order over the Cartesian product [math]\displaystyle{ \prod_{a \in A} \{0, 1\} }[/math] can be identified with the inclusion ordering of subsets of [math]\displaystyle{ A. }[/math][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, https://books.google.com/books?id=-ip3-wejeR8C&pg=PA64
- ↑ 2.0 2.1 Sudhir R. Ghorpade; Balmohan V. Limaye (2010). A Course in Multivariable Calculus and Analysis. Springer. p. 5. ISBN 978-1-4419-1621-1.
- ↑ 3.0 3.1 3.2 Egbert Harzheim (2006). Ordered Sets. Springer. pp. 86–88. ISBN 978-0-387-24222-4.
- ↑ 4.0 4.1 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.
- ↑ 7.0 7.1 7.2 Paul Taylor (1999). Practical Foundations of Mathematics. Cambridge University Press. pp. 144–145 and 216. ISBN 978-0-521-63107-5.
See also
- 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
 |  |
