The wikipedia article about partially ordered set describes three of the possible partial orders on the Cartesian product of two partially ordered sets, and mentions that similar constructions can be done on the Cartesian product of more than two sets. However, if there are more than two sets, the constructions can be combined with each other in various ways. If we restrict ourselves to the lexicographic order and the product order, how can we describe the various way in which these orders can be combined?
For three sets, we could define $(a_1, a_2, a_3) \leq(b_1,b_2,b_3)$ via:
- $a_1 < b_1$ or ($a_1=b_1$ and ($a_2 < b_2$ or ($a_2=b_2$ and $a_3 \leq b_3$))) (lexicographical order)
- $a_1 \leq b_1$ and $a_2 \leq b_2$ and $a_3 \leq b_3$ (product order)
- $a_1 < b_1$ or ($a_1=b_1$ and $a_2 \leq b_2$ and $a_3 \leq b_3$) (first lexicographical order, then product order)
- ($a_1 \leq b_1$ and $a_2 \leq b_2$ and ($a_1 < b_1$ or $a_2 < b_2$)) or ($a_1 = b_1$ and $a_2 = b_2$ and $a_3 \leq b_3$) (first product order, then lexicographical order)
- $a_1 \leq b_1$ and ($a_2 < b_2$ or ($a_2=b_2$ and $a_3 \leq b_3$)) (first product order, then …)
- ($a_1 < b_1$ or ($a_1=b_1$ and $a_3 \leq b_3$)) and ($a_2 < b_2$ or ($a_2=b_2$ and $a_3 \leq b_3$)) (first product order, then …)
I think these are all orders I want to consider for three sets (ignoring permutations), but how can I be sure without a systematic way to describe these orders. Is there a systematic way to describe the orders on the Cartesian product of a finite number of partial ordered sets?
Does the description gets easier, if we look at bounded lattices (or semilattices with identity element) instead of partially ordered sets?
Best Answer
You can systematize the various ways of imposing an order structure on the cartesian product of the underlying sets of the given posets. However, why are you interested in enumerating all possible such orders? Thinking categorically, one is usually motivated by constructing orders with particular properties rather than random mixing of possible definitions. For instance, the product order yields a categorical product in the category $Pos$ of posets. It is more natural to think of induced orders in this way, unless of course there is some particular, application driven, reason to consider a particular induced order.