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.