3
$\begingroup$

I have been mucking round with orders, and this is the order that I found I needed. I would like to know if it is defined somewhere else, it is kind of difficult to search for such things.

*EDIT*

The only application I have used it for at the moment is a totally ordered domain (e.g. '$a,b \in R $'), but I think it would extend to a partially ordered lattice.

Consider two intervals (a,b) (a',b'), if one is clearly better than the other, i.e. b≤a' then a≤b≤a'≤b' it is better. But if the interval has the same least upper bound where b=b', then only the greatest lower bound matters, so a ≤ a'.

The order that this creates is why I defined it. for instance, given 3 reals {1,2,3} we use a function that defines an interval on each where f(1) = [0,2] f(2) = [1,3] and f(3) = [2,4]. Using this order we can then state that f(1) || f(2) and f(2) || f(3) but f(1) < f(3).

The goal of this order is that it should create a lattice as well.

Thanks for your help.

EDIT

I missed a really important part, sorry. This is based on intervals so a ≤ b and a' ≤ b' must be true.

(a,b) ≤ (a',b') iff b ≤ a' or (b' = b and a < a') where a ≤ b AND a' ≤ b'

$\endgroup$
11
  • 2
    $\begingroup$ That 'ordering' is not transitive: (1, 2) < (3, 0), and (3, 0) < (1, 1), but (1, 2) is not less than (1, 1). $\endgroup$
    – Simon Rose
    May 5, 2010 at 21:54
  • 1
    $\begingroup$ This order seems pretty peculiar to me. It isn't reflexive - if $x < y$ then we don't have $(x, y)\le(x,y)$. Are you sure you typed it right? $\endgroup$
    – Tom Smith
    May 5, 2010 at 21:56
  • 1
    $\begingroup$ do you mean "iff b is less than or equal to b'" in the first part? If so, this is called the lexicographic order: en.wikipedia.org/wiki/Lexicographical_order $\endgroup$ May 5, 2010 at 22:00
  • $\begingroup$ Sorry, a <= b and a' <= b'. This is based on intervals. If you take this into consideration then I am pretty sure it works. $\endgroup$ May 5, 2010 at 22:17
  • $\begingroup$ Are you assuming anything about the ambient order? e.g. Is it linear? Are they real numbers, integers? Or is it just some partial order partial? $\endgroup$ May 5, 2010 at 22:32

4 Answers 4

3
$\begingroup$

If the ambient order is a lattice, they your order is indeed a lattice order. To see this, suppose that we have intervals (a,b) and (a',b'), in your sense that $a\le b$ and $a'\le b'$. If $b\lt b'$, then the least upper bound, written $(a,b)\vee(a',b')$, is $(a'\vee b,b')$. If $b=b'$, then $(a,b)\vee(a',b')=(a\vee a',b)$. Similarly, the case $b'\le b$ is symmetric, and so the remaining case is when $b\perp b'$, in which case $(a,b)\vee(a',b')=(b\vee b',b\vee b')$. A symmetric argument shows $(a,b)\wedge(a',b')$ exists, so it is a lattice.

This argument shows that if the ambient order is an upper semi-lattice, then so is your order, and the smae for lower semi-lattice, since we only needed $\vee$ in the underlying order to define $\vee$ in your order, and the same for $\wedge$.

Also, if the underlying order is well-founded, then your order is also well-founded, since any descending sequence must descend infinitely in one of the coordinates. If the rank of the ambient order is $\omega$, then the new rank is also $\omega$, since every pair would have only have finitely many predecessors in your order. But for larger ordinal ranks, it seems to go up, and one could calculate some bounds if this was a case you were interested in.

$\endgroup$
3
  • $\begingroup$ You have no idea how happy I am that you said that, as this is the first order I have created myself and proven to be a lattice. And I have the same answer written down in front of me. I followed the same process as you suggested the other day with lexicographical order, and came up with this. $\endgroup$ May 5, 2010 at 23:42
  • $\begingroup$ But I was hoping that someone might be able to find a similar order, as it would be nice to have a search term rather than an equation to find out if it is something someone else has done, or it is novel. My supervisor says "If it is maths, then it has been published at least 50 years ago", so far he has been right, so I go with this assumption. $\endgroup$ May 5, 2010 at 23:44
  • $\begingroup$ I have not seen this particular order before, but I like it. People have looked at many interval orders, particularly in universal algebra, and so it may have arisen before, but I'm not sure. $\endgroup$ May 5, 2010 at 23:55
1
$\begingroup$

Since $(2,0) \le (2,1)$ and $(2,1) \le (2,0)$, the relation is not antisymmetric. Or am I mistaken?

$\endgroup$
1
  • $\begingroup$ a <= b and a' <= b', I forgot to mention that the order is based on intervals. Fixed it now. $\endgroup$ May 5, 2010 at 22:18
1
$\begingroup$

In the realm of interval orders, it's often convenient to lift the interval [a,b] to the point (a,b) (which necessarily is above the x=y diagonal). Once you do that, lots of questions about interval containment/intersection can be phrased geometrically in terms of regions. Your order has a somewhat unusual, but reasonable-to-represent form. as follows:

Given the interval [a,b] to the point (a,b). Associate with (a,b) the half infinite rectangular region whose lower end is the horizontal line segment (a,b) - (b,b), and which extends upwards to infinity. Then all intervals greater than (a,b) in your order correspond to all points to the right of this rectangle (and above the diagonal) and the line segment (a,b)-(b,b) itself.

While this looks a little weird, it makes sense once you complete the diagram by reflecting this diagram around the normal to (x=y) passing through (a,b). It's a bit hard to explain without a figure, but the region described above is actually one half of two "wedges" (the lower half containing all intervals that are less than (a,b).

So each point is then associated with these two wedges. Questions about the resulting partial order can (I think) be then phrased in terms of unions and intersections of these regions, which should give you a more Boolean-lattice-like structure to work with.

$\endgroup$
1
$\begingroup$

If you are indeed reasoning about intervals, then perhaps Allen's Interval Algebra might provide some guidance: http://en.wikipedia.org/wiki/Allen's_Interval_Algebra . Allen's Interval Algebra is a Boolean Algebra. Using Allen's terminology, you can more concisely state what order you are aiming at, namely that the first interval takes place before the second one or the second interval finishes the first.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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