What is partial order?

Question

I am reading category theory for programmers from Bartosz Milewski and I did not get the idea of partial order.

I did not get the context of the following sentences:

You can also have a stronger relation, that satisfies an additional condition that, if a <= b and b <= a then a must be the same as b. That’s called a partial order.

Why a must be the same as b? For example, a = 4 and b = 5, so it is not the same at all. If he would mention

....if a = b and b = a....

Then yes, I would agree.

The second part, that I also do not understand:

Finally, you can impose the condition that any two objects are in a relation with each other, one way or another; and that gives you a linear order or total order.

What does he mean?

Answer 1

if a <= b ...

so a = 4 and b = 5 satisfy the first inequality

and b <= a

but they don't satisfy the second inequality. So, your counterexample is invalid.

Let's forget <= because I suspect it's tricking you into thinking about integers or some other set of numbers you're familiar with. So, we'll re-write it with some arbitrary relation, say ¤

if a ¤ b is true

and b ¤ a is true

and this always implies that a is the same entity as b

then we call relation ¤ a "partial order" (over whatever set a, b are drawn from)

All the author is saying is that for some relation, if the given rule is true, then we call that relation a partial order. This is the author's definition of a partial order. If you find some situation where the rule doesn't hold - that just means you found a type of relation that is not a partial order.

Anyway, the reason for defining a partial order is that sometimes we have collections of objects, and we can't compare all of them to each other.

For example, a set of grades for different subjects: perhaps I can decide whether one student is better at English than another, and I can decide whether one student is better at Music than another, but it doesn't make sense to discuss whether one student's English is better than another's Music.

The last quote just means that if we have a relation which is at least a partial order (it satisfies the rule given) and it can be applied to your whole set (say we're only discussing English grades), then we can call it a total order over that set.

---

PS. As it happens the rule does hold for the usual <= with integers: hence, we can call the relation <= a partial order over ℤ. Since it is also defined for every pair of integers, we can also call <= a total order on ℤ.

PPS. Yes, a partial order also requires transitivity: my answer really only addresses the fairly informal definition quoted in the question. You can find more complete definitions at Wolfram MathWorld, Wikipedia or wherever.

Answer 2

The divisibility of a positive natural number by another positive natural number is an example of partial order which is not a total order (x divides y if y/x is a natural number).

1) If x divides y and if y divides z, then x divides z (transitivity).

2) If x divides y and y divides x, then x = y (antisymmetry).

3) x divides x (reflexivity).

These are the three properties of a partial order.

But this is not a total order, because you can find two natural numbers x and y such that x does not divide y and y does not divide x.

Answer 3

To understand the distinction, you need to look at sets other than integers. Consider the complex numbers. A valid preorder on the complex numbers could say z1 <= z2 if and only if real(z1) <= real(z2). Thus, (3, 5) <= (3, 6) and (3, 6) <= (3, 5). This is not a partial order, though, because (3, 5) != (3, 6).

Adding the condition that z1 <= z2 also requires imag(z1) <= imag(z2) makes this a preorder, since now (3, 5) <= (3, 6) but not vice versa. It's still not a total order, because neither (2, 3) <= (3, 2) nor (3, 2) <=(2, 3) is true.

Instead, one could say z1 <= z2 if and only if real(z1) <= real(z2) and abs(z1) <= abs(z2). Now (3, 5) <= (3, 6) is still true, but (3, 6) <= (3, 5) is not because sqrt(3**2 + 6**2) > sqrt(3**2 + 5**2). But we can say that (2, 3) <= (3, 2) because 2 <= 3 and sqrt(13) <= sqrt(13). This makes the <= operator a total order. (Update: checking whether lexicographical ordering on abs and arg -- with arg limited to (-pi,pi] while special casing the 0 -- is a proper total order, is left as an exercise to a reader.)

(Normally, we say the complex numbers are not ordered because there are several ways one could define a total order, but no single "natural" ordering.)

Answer 4

Consider this Directed Acyclic Graph:

If we say that an arrow on this graph stands for the <= relation then we can see that a <= c and c<=d. But it is not the case that b<=c nor does c<=b hold. Hence we have an order, but it is only partial because it only exists for some pairs of items in the domain.

In general a DAG defines a partial order on its members. Even if the arrow from a to e were not included we could still say that a<=c and c<=e, so therefore a<=e.

Bear in mind that we are not interpreting "x <= y" as meaning anything other than "I can get from x to y by following arrows on the diagram". Now suppose we have two letters x and y, and we know that x <= y and y <= x. If x and y are different and you can get from x to y then you can't get from y to x. Hence it is not possible for x and y to be different items, so they must both be the same item.

A total order, on the other hand, exists for all pairs of items. The integers, for instance, have a total order.