Representing Partial Orders As Subset Relations

Flash and JavaScript are required for this feature.

Download the video from iTunes U or the Internet Archive.

PROFESSOR: So we've seen that partial orders are a set of axioms that capture the positive path relation or the arbitrary path relation in directed acyclic graphs, or DAGs. But there's still another way to understand these axioms that gives a kind of representation theorem for the kind of mathematical objects that are partial orders and that every partial order looks like.

So let's look at that example. I'm interested in the proper subset relation. A is a proper subset of B, which, you remember, means that B has everything in it that A has and something extra. So in particular, since B has something extra, B is not a subset of A, certainly not a proper subset of A.

So let's look at an example of that. Here are seven sets, and the arrows indicate the proper subset relation. Or more precisely, the positive path relation in this graph represents the proper subset relation where edges are understood to be pointing upwards. So I've left out the arrowheads.

This is also known as a Hasse diagram, where the height is an indication of which way the arrows go. So if arrows are pointing up, this is telling me that, for example, this set of two elements, 1 and 5, because there's a path up to the top set, the top set has everything that this lower set has. Namely the top set has 1 and 5, and it's got extra stuff.

The set consisting of just 1 is a proper subset of 1 and 5 because the set has 1 in it, but it has an extra thing, 5. And also, there's a path from 1 up to 1, 2, 5, 10 because 1, 2, 5, 10 has a 1 in it and extra stuff. So that's what the picture is illustrating, the proper subset relation on this particular collection of seven sets.

Now, let's look at a very similar example of the proper divides relation on some number. So proper divides means a properly divides b if a divides b and it's not equal to b. And I'm interested in the proper divides relation on this set of seven numbers, 1, 2, 3, 5, 10, 15, and 20. And now there's a path from 5 to 30 because 5 is a divisor of 30 and it's not equal to 30. It's a proper divisor of 30.

And of course, the point of this picture is to show that the proper divides relation on these seven numbers has exactly the same shape as the proper subset relation on those seven sets. So there's the seven sets and their proper subset relation shown by the picture followed by the proper divides relation on this set of seven numbers.

And the precise notion or sense in which these things have the same shape-- obviously they can be drawn and one superimposed on the other. But abstractly what we care about with partial orders and digraphs in general is when things are isomorphic-- is the technical name for the same shape-- and isomorphic means that all we care about are the connections between corresponding vertices.

Two graphs where the vertices correspond in a way that where there's a connection between two vertices there's also a connection between the corresponding vertices are isomorphic. And the precise definition of isomorphic is that they're isomorphic when there's an edge-preserving matching between their vertices. Matching means bijection.

And the formal definition is G1 is isomorphic to G2 if and only if there's a bijection from V1, the vertices of G1, to V2, the vertices of G2, with the property that if there's an edge between two vertices u and v in the first graph, then there's an edge between the corresponding two vertices f of u and f of v in the second graph.

And that's an if and only if relation. There's an edge between f of u and f of v if and only if there's an edge between u and v in the original graph. And that's the official definition of isomorphism for digraphs.

And the theorem that we illustrated with that example of proper divides and proper subset is that, in fact, every strict partial order is isomorphic to some collection of subsets partially ordered by less than. So this is a kind of a representation theorem. If you want to know what kinds of things are partial orders, the answer is that a strict partial order is something that looks like a bunch of sets under containment. It's isomorphic to a bunch of sets under containment.

And the proof, actually, of this is quite straightforward. What I'm going to do to find an isomorphism is you give me your arbitrary strict partial order R, and I'm going to map an element a in the domain of R to the set of all of the elements that are, quote, "below it," that is, all of the elements that are related to R.

So a is going to map to the set of b's such that bRa or b is equal to a. And that is added for a technical condition. Remember, R restrict, so a is not related to a under R. But I want it to be in the set that a maps to, so I'm throwing that in. Another way to say this is that the mapping f of a is equal to R inverse of a union a. And let's just illustrate that by the example of, how do you turn the divides relation into the subset relation?

Well, the smallest element in the proper divides example was the number 1, and I'm going to map it to the set consisting of 1, which is all of the elements that properly divide 1 along with 1. And then I'm going to map the number 3 to all of the elements that properly divide 3 along with 3, and that is 1 and 3. 5 maps to 1 and 5. 2 maps to 1 and 2.

And at the next level, I'm going to map 15 to all of the numbers that properly divide 15 along with 15. So 1, 3, 5, and 15 are what the number 15 maps to. That's a set. Likewise, 10 maps to 1, 2, 5, 15, and 30 maps to all of the numbers that are below it, including itself.

And this is the general illustration of the way that you take an arbitrary strict partial order and map elements into sets, which are basically their inverse images under the relation. And the sets have exactly the same structure under proper containment as the relation.

So this is, again, a representation theorem that tells us that if we want to understand partial orders, they are doing nothing more than talking about relations with the same structure as the proper subset relation on some collection of sets.

Free Downloads

Video


Caption

  • English-US (SRT)