Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

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.

share|improve this answer
    
I want to systematically describe these orders for posets, because I want to try to characterize those which give me bounded lattices (or semilattices with identity element). The application behind this is to better understand how an efficient data-strucure for a semilattice might look like (especially if I want to use a join-semilattice instead of a tree for representing hierarchies). Perhaps I would be better off thinking about relational representations instead, since this is what databases did when trees were no longer enough. –  Thomas Klimpel Oct 26 '12 at 8:12
up vote 1 down vote accepted

I found the trick required to construct similar orders as the ones I gave as examples. The crucial step is to look at preorders instead of partial orders, and ignore the Cartesian product as much as possible.

For a preorder relation $\leq$, we can define the strict preorder relation $<$ via

  • $a < b$ if and only if $a \leq b$ and not $b \leq a$.

If two preorders $\leq_1$ and $\leq_2$ on the same set $P$ are given, we can define preorder analogs of lexicographical and product orders via

  • $a \leq_L b$ if and only if $a <_1 b$ or ($a \leq_1 b$ and $a \leq_2 b)$.
  • $a \leq_P b$ if and only if $a \leq_1 b$ or ($a \leq_1 b$ and $a \leq_2 b)$.

We can also define the analog of the product of the strict orders

  • $a \leq_S b$ if and only if ($a <_1 b$ and $a <_2 b$) or ($a \leq_1 b$ and $b \leq_1 a$ and $a \leq_2 b$ and $b \leq_2 a$).

The following preorders are canonically defined on the direct product of $n$ partially ordered sets:

  • For $1 \leq i \leq n$: $(a_1,\ldots,a_n) \leq_i (b_1,\ldots,b_n)$ if and only if $a_i \leq b_i$.

The partial orders I gave as example simply arise by successively defining new preorders on the direct product via $\leq_L$ and $\leq_P$ starting from the preorders $\leq_i$. This will give rise to a partial order on the direct product if each $\leq_i$ occurs at least once in the constructed preorder.

Does the description gets easier, if we look at bounded lattices (or semilattices with identity element) instead of partially ordered sets?

My guess would be that in this case, each $\leq_i$ must occur exactly once in the constructed preorder and that $\leq_S$ may not be used, but I haven't checked this yet. I guess the first step would be to define a notion of independent preorders, and then check the behavior of $\leq_L$, $\leq_P$ and $\leq_S$ for (independent) preorder analogs of lattices. I guess the result is that $\leq_S$ doesn't give rise to a preorder analog of lattices, $\leq_L$ will only work for bounded lattices (or semilattices with identity element), and $\leq_P$ will work without restrictions (except that the preorders should be independent).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.