PROFESSOR: Partial orders are another way to talk about digraphs and they offer to us an interesting lesson in the idea of axiomatizing a mathematical structure and mathematical ideas.
So let's begin by discussing some of the properties that we're going to use to axiomatize partial orders and digraphs. So if we think about walks in a digraph, the basic property of walks is that if you have a walk from u to v and you have a walk from v to w, then you put the two walks together and you wind up with a walk from u to w. Expressed in terms of the positive walk relation in G, what this is saying is that if u G plus v and v G plus w, then u G plus w. And that abstract property-- which I'm highlighting with the magenta box-- when you apply it to an arbitrary relation is called a transitivity property.
So a relation R on a set-- that is, R is relating-- the domain and co-domain of R are the same-- is that u R v and v R w implies u R w. And a relation that has that property is said to be transitive. And, of course, what we've just seen is the positive path relation of any graph G is transitive.
Another way to say transitivity is to read u R v as saying there's an edge from u to v. And what this says is that if there's an edge from u to v and an edge from v to w, there's an edge from u to w. Or, in other words, if there's a path of length 2, there's a path of length 1. And then by easy induction it follows that if there's a path of any length between-- of any positive lengths between two vertices, then in fact there's a path of length 1. That is, an edge between them.
OK, so the basic theorem that we have to begin with is what is transitivity capturing as a property of a relation. And a relation R is transitive if and only if, in fact, R is equal to the positive walk relation for some digraph G. The proof of this is basically trivial because you could let the relation R be the digraph that it's the positive path relation of.
If we look now at directed acyclic graphs, then what we have is that if there's a positive length path from a vertex u to a vertex v, then since there's no cycles in a directed acyclic graph, there can't be a path back from v to u, and that property is called asymmetry. So D plus, which is the positive path relation, in a DAG has this asymmetry property. Namely, if u can get to v by a positive length path and it's not possible for v to get back to u by a positive length path.
So, abstracted, u R v implies not v R u. That's the asymmetry property of an arbitrary relation R. And by definition of acyclic, D plus is asymmetric in a graph without cycles. OK.
A strict partial order is simply a relation that has these two properties of being transitive and asymmetric. And some examples of strict partial orders are the proper containment relation on sets, which we've previously commented can be viewed as a DAG, but now it satisfies transitivity. And the fact that if one set's properly contained in another, the second one can't be properly contained in the first because proper means you have something extra.
The indirect prerequisite relation on MIT subjects would be another example of a strict prerequisite. If I'm a prerequisite of you, you can't be a prerequisite of me. And finally, the less than relation on real numbers. These are all examples of strict partial orders.
And putting together the previous reasoning, what we can say is that a relation R is a strict partial order if and only if R is the positive path relation for some DAG, D. So the axioms that define strict partial order, namely transitivity and asymmetry, can be said to abstractly capture the property of a relation that it comes from a DAG.
Another important property of partial orders is the idea of being path-total, or linear as some authors call it. And the simple definition of path-total is that given any two elements, one is going to be bigger than the other with respect to the relation.
Most familiar example of that would be the less than relation of a less than or equal to relational on the reals given any two distinct real numbers-- x and y. Either x is less than y or y is less than x. And we take that property for granted.
Now, the formal definition then is simply that if x is not equal to y, then either x R y or y R x, and relation R that has that property is called path-total. Another way to say it is that there are no incomparable elements under R. And I've, again, highlighted with a magenta box this property, which is called path-totality.
Another way to say that a path-total is that the whole order looks like a chain. If you give me a bunch of elements, there's going to have to be a biggest one and then a next biggest one and so on, assuming you've given me any finite set of elements. So the basic example, again, of path-total would be number properties of bigger than. And a basic example of something that would typically not be path-total would be, let's say, subset containment where you can perfectly well have two sets, neither of which is contained in the other.
So a weak partial order is a small variation of a strict partial order. That is another familiar concept where we take the strict property, which guarantees that nothing's related to itself, and we relax it. So a strict partial order is just like a weak partial order except that the condition that there's no positive length path between an element in itself is relaxed. So, in fact, it's not only relaxed, but it's completely denied. In a weak partial order, we insist that every element is related to itself.
An example of that would be the less than or equal to relation. Sorry, the improper containment relation. The ordinary subset relation on sets where now a is a subset with a bar under it. a is just a subset of a, not necessarily a strict subset or a proper subset means that, in fact, a is a subset of a. And then less than or equal, and you put the little bar under the less than sign to indicate that equality is also a possibility, you get a weak partial order on the real numbers.
So the property that distinguishes the weak from the strict is this property of reflexivity. A relation R on a set is reflexive if every element is related to itself, if and only if a R a for all little a in the domain capital A. And what we can observe immediately is that the path of the walk relation-- G star-- which includes walks of length zero is reflexive because, by definition, there is a length zero walk from any vertex to itself.
So if you're going to play with axioms, then you can reformulate asymmetry-- the idea of asymmetry except for elements being related to themselves. It's called antisymmetry, and it says that a relation R is antisymmetric if and only if it's asymmetric except for the a R a case. And more precisely, the difference between asymmetry and antisymmetry is that in asymmetry a R a is never allowed, and in antisymmetry a R a is a possibility. It's not disallowed.
So an antisymmetric relation on R stated abstractly is that u R v implies not v R u for u not equal to v. So the first line is exactly the statement of asymmetry, and then I add this proviso that it only has to hold when the u and the v are not equal. That's the formal way of saying antisymmetry is the same as asymmetry except for a R a. And the walk relation in a digraph, which includes length zero walks, is antisymmetric.
So weak partial orders-- just what you get when you put these things together-- weak partial order is transitive, antisymmetric, and reflexive. So in a weak partial order, we insist that every element be related to itself.
So there's a-- just a quick remark. Asymmetric implies nothing's related to itself. Reflexive implies everything is related to itself.
And it's possible that there be some graph in which some elements are related to themselves and some not. That would be something that was neither a strict nor a weak partial order. It would just be transitive and antisymmetric. Those don't come up much and so we don't bother to give them a name or talk about them.
And, finally, the theorem that summarizes up this whole story is that R is a weak partial order if and only if R is equal to the walk relation for some DAG, including length zero walks.