Lecture notes · Math for Computer Science · Lecture 11

Relations, Partial Orders, and Scheduling

MIT 6.042J Mathematics for Computer Science, lecture 11, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part explains what a relation is, how to draw one as a directed graph, and three properties (reflexive, symmetric, antisymmetric) that relations can have.

Key ideas

A relation from set A to set B is a set of pairs. The first item in each pair comes from A, and the second comes from B. For example, pairs of students and the classes they take. 1:15
A relation on one set can be drawn as a directed graph. Each item is a dot (vertex), and each related pair is an arrow (edge) from the first item to the second. 6:11
A relation is reflexive when every item is related to itself. In the lesson's example, it is not reflexive because Julie and Rob do not like themselves. 8:16
A relation is symmetric when any time x is related to y, y is also related to x. If Julie likes Rob, then Rob must like Julie. 8:39
A relation is antisymmetric when two items cannot relate to each other in both directions unless they are the same item. Antisymmetric is the opposite of symmetric. 9:36

Words to know

relation: A set of pairs that shows which items are linked to which. Think of a list of 'who likes whom' pairs.
cross product: All the possible pairs you can make by taking one item from the first set and one item from the second set.
reflexive: A relation where every item is linked to itself. Everyone in the group has to like themselves.
antisymmetric: A relation where, if x links to y and y links back to x, then x and y must be the same thing. Two different items cannot link to each other both ways.

Example

Imagine a group of friends where an arrow means 'likes.' If Julie likes Bill but Bill does not like Julie, the arrow only goes one way, so this relation is not symmetric. Drawing the arrows makes it easy to see which properties hold and which do not.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part teaches three ways a relation can behave (transitive, symmetric, antisymmetric) and uses them to define equivalence relations and equivalence classes.

Key ideas

A relation is transitive if, when x relates to y and y relates to z, then x also relates to z. For example, if 2 is congruent to 7 and 7 is congruent to 12 (mod 5), then 2 is congruent to 12. 10:00
Congruence modulo 5 is reflexive, symmetric, and transitive, but not antisymmetric. Two different numbers such as 7 and 2 can be congruent to each other in both directions. 11:33
Divisibility is reflexive, antisymmetric, and transitive, but not symmetric. For example, 3 divides 9, but 9 does not divide 3. 14:14
An equivalence relation is a relation that is reflexive, symmetric, and transitive. Equality and congruence modulo n are both examples. 16:54
The equivalence class of an element x is the set of all elements in the set that are related to x. Everything in that class is related to the others in it. 18:29

Words to know

transitive: A relation is transitive if passing through a middle step carries the link across. If x links to y and y links to z, then x links to z.
symmetric: A relation is symmetric if it works in both directions. If x links to y, then y also links to x.
antisymmetric: A relation is antisymmetric if the only way a link works both ways is when the two items are the same. If x links to y and y links to x, then x and y must be equal.
equivalence class: A group made of every item that is related to a chosen item. All items in the group count as the same in the rule being used.

Example

Think of the rule 'was born in the same month as.' If Ana and Ben share a birth month, then Ben and Ana do too, so the rule works both ways. If Ana and Ben share a month and Ben and Cara share a month, then Ana and Cara share one too. Anyone is also in the same month as themselves, so the rule has all three properties and groups people into twelve equivalence classes.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part explains how equivalence relations split a set into groups, and introduces partial orders and posets, which rank items.

Key ideas

An equivalence class is a group of items that are all related to one another under an equivalence relation. For example, the numbers that leave remainder 2 when divided by 5 form one class: minus 3, 2, 7, 12, and so on. 20:18
A partition of a set is a collection of non-empty subsets whose union is the whole set. Every item ends up in exactly one piece. 21:05
The lesson states that the equivalence classes of any equivalence relation on a set A form a partition of A. The lesson leaves the proof for the viewer to work out. 23:54
A weak partial order is a relation that is reflexive, antisymmetric, and transitive. Unlike an equivalence relation, it is not symmetric, so it gives a ranking rather than groups. 25:56
A partially ordered set, or poset, is a set paired with a partial order. It can be drawn as a directed graph, with the set's items as vertices and the ordering pairs as edges. 29:37

Words to know

equivalence class: A group of items that are all treated as the same under a rule, such as all numbers that give the same remainder when divided by 5.
partition: A way of splitting a whole set into separate pieces, where every item belongs to exactly one piece.
partial order: A rule for ranking items, like less than or equal to, that is reflexive, antisymmetric, and transitive. Not every pair of items has to be comparable.
poset: Short for partially ordered set: a set of items together with a partial order rule.

Example

Think of sorting a pile of coins into piles so that every coin goes into exactly one pile and no coin is left out. Each pile is like an equivalence class, and all the piles together make a partition. The lesson does this with whole numbers, grouping them by their remainder when divided by 5.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part explains how a partial order, a set of 'must come before' rules, can be drawn as a simpler picture called a Hesse diagram.

Key ideas

A partial order can be drawn as a directed graph, where each arrow shows that one item must come before another. A Hesse diagram is a simpler picture of the same idea. 30:14
The getting-dressed example shows the idea: underwear must come before pants, and pants must come before a belt. Some items have no required order between them, so not every pair is connected. 31:24
The lesson checks three properties of this partial order. It is reflexive (each item is related to itself), transitive (a chain of rules gives a new rule), and antisymmetric (two items cannot each have to come before the other). 33:45
A full directed graph would need many extra arrows, because of transitivity and self loops. That makes the picture messy. 35:28
A Hesse diagram keeps the same items as vertices but removes the self loops and the arrows that transitivity already implies. This leaves a cleaner picture of the order. 37:52

Words to know

Hesse diagram: A simple picture of a partial order, drawn as a directed graph with the self loops and the transitivity arrows left out.
partial order: A set of rules saying which items must come before others. Some pairs may be unordered.
transitivity: If A comes before B, and B comes before C, then A comes before C, even if nobody drew that arrow.
closure: The full set of arrows you get after adding every arrow that transitivity forces. The lesson uses it to describe the complete, messy graph.

Example

Think about getting dressed for a formal event. Your underwear must go on before your pants, and your pants must go on before your belt, so you also know underwear comes before the belt. A Hesse diagram shows just the key steps like these, and you can work out the rest by following the chain.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–50:00

This part explains why a partial order cannot loop back on itself, which lets us rank its elements, and why some pairs of elements still cannot be compared.

Key ideas

A poset (a set with a partial order, meaning a 'is related to' rule) has no directed cycles, apart from self loops. A directed cycle is a path of arrows that leads back to where it started. 40:19
The lecturer proves this by contradiction: assume a cycle exists, then use transitivity (if a is related to b and b to c, then a is related to c) to show a1 is related to an. Antisymmetry then forces a1 to equal an, which contradicts the assumption that they are distinct. 45:22
Because there are no cycles, the elements can be given a ranking, so one element can be called less than another. An element cannot be ranked less than another and also be ranked less than the first. 46:06
Some pairs of elements are incomparable, meaning neither is related to the other. The sock and underwear example shows that transitivity cannot connect them either. 47:46
A total order is a special partial order in which every pair of elements is comparable. This is the kind of consistent ranking the lecturer is working toward. 49:28

Words to know

poset: A set of items with a rule that says which items are related to which, where the rule follows the partial order rules (reflexive, antisymmetric, and transitive).
directed cycle: A chain of arrows, each pointing to the next, that starts at one item and comes back to that same item.
transitive: A rule where if a is related to b, and b is related to c, then a is also related to c.
incomparable: Two items where neither one is related to the other, so you cannot say which comes first.

Example

Think of a family tree where each person is related to their parents and grandparents. You can never be your own ancestor, so the arrows never loop back. Some pairs of cousins are not directly linked in the way you might expect, so they cannot be ranked against each other in that one way.

3 checked practice questions for this part are in the app.

Part 6 · 50:00–1:00:00

This part explains how a partial order (where some items can't be compared) can be stretched into a total order (a full ranking), and why every finite set of that kind can be ranked this way.

Key ideas

A total order is one where every pair of items can be compared, so they line up in a single ranking. Its diagram is a straight line. 51:26
A topological sort takes a partial order and extends it into a total order. The new ranking keeps every rule from the original order, and it ranks all the items. 52:07
The lecturer says every finite poset has a topological sort, and he plans to prove it. 55:18
A minimal element is an item with no other item below it. Infinite sets like the integers can lack one, but a finite poset always has one. 56:35
The proof plan is to take out one minimal element, sort the smaller set that remains, and then add the element back at the front. This is a proof by induction, which builds up from smaller cases. 56:13

Words to know

poset: A set of items with a partial order, meaning a rule that says some items come before others, but not every pair can be compared.
topological sort: A full ranking of all the items that still follows every 'comes before' rule from the original partial order.
minimal element: An item with no other item in the set that is smaller than it.
chain: A list of different items where each one is related to the next, like a step-by-step line going up the order.

Example

Think of getting dressed. Socks must go on before shoes, and underwear must go on before pants, but socks and a shirt have no required order between them. A topological sort is one complete line-up of all the steps that still respects every must-come-before rule.

3 checked practice questions for this part are in the app.

Part 7 · 1:00:00–1:03:55

This part proves that in a finite set with an ordering, the start of a longest chain is a minimal element, meaning nothing in the set is smaller than it.

Key ideas

The plan is to take the longest chain, a1 related to a2 and so on up to an, and show that its first element a1 is minimal. 1:00:00
A longest chain must exist because the set is finite. A chain can be no longer than the number of elements, so there is always a biggest possible length. The lecturer says a formal proof would use the well-ordering principle, but he skips it here. 1:00:55
Case one: if some element a is less than a1 and is not in the chain, you could put a at the front and make a longer chain. That contradicts the chain being the longest, so this case is impossible. 1:01:19
Case two: if a is already in the chain and a is less than or equal to a1, you get a cycle. A poset has no cycles, so this is also impossible. 1:02:48
Since no element in the set is less than a1, a1 meets the definition of a minimal element. The lecturer first says he has shown a minimum element exists, but the argument he gives shows a1 is minimal. 1:03:14

Words to know

chain: a list of elements where each one is related to the next, like a line of people where each stands behind the one before.
cycle: a loop that goes around and comes back to where it started, like walking in a circle. A poset does not allow one.
contradiction: a statement that cannot be true, because it clashes with something already known. Proofs reach a contradiction to show an assumption is wrong.
minimal element: an element with nothing in the set that is smaller than it.

Example

Imagine a line of people standing one behind another, as long as possible. If someone outside the line could step to the front and still fit the order, the line was not the longest possible. That is the same logic the proof uses: a longer chain would break the assumption that the chain was the longest.

3 checked practice questions for this part are in the app.

← Lecture 10: Graph Theory III · Lecture 13: Sums and Asymptotics →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York