Lecture Overview L5−P. 1

Relations Operations on Relations Equivalence Relations and Partitions Partial Orders Relations L5−P. 2

Relationship between elements of sets

Binary relation from a set A to a set B is R ⊆ A × B. Or, a ∼_{R} b or aRb instead of (a, b) ∈ R

A binary relation on a set A is a subset R ⊆ A^{2} A relation from A to A.

The relation “is taking a class” as a subset of {students at MIT } × {classes at MIT }. A relation from students to classes Properties of Relations L5−P. 3

reflexive — if for every a ∈ A, a ∼_{R} a. “is living in the same room” {students at MIT } × {students at MIT }

irreflexive — if for every a ∈ A, a ≁_{R} a. “parent”, on the set {people}

transitive — if for every a, b, c ∈ A, a ∼_{R} b and b ∼_{R} c implies a ∼_{R} c. “can drive from first to second city”

symmetric — if for every a, b ∈ A, a ∼_{R} b implies b ∼_{R} a. “is living in the same room”

antisymmetric — if for every a, b ∈ A, a ∼_{R} b and b ∼_{R} a implies a = b. A = ℕ and a ∼_{R} b iff a ≤ b.

asymmetric — if for every a, b ∈ A, a ∼_{R} b implies ¬(b ∼_{R} a). A = ℕ and a ∼_{R} b iff a < b.

Properties of Relations, Ex. L5−P. 4

Relation on computers, “are connected (directly) by wire” symmetric but not transitive

A = ℜ^{2} and define a ∼_{R} b iff d(a, b) = 1. is only symmetric.

“likes” not symmetric, not antisymmetric, not transitive, not (even) reflexive, not irreflexive, not asymmetric.

Representation L5−P. 5

Lists, Matrices, Graphs

List all pairs

Relation from A = {0, 1, 2, 3} to {a, b, c} to be the list: {(0, a), (0, c), (1, c), (2, b), (1, a)}.

Reflexivity — contains all pairs (a, a) Symmetry — contains (a, b) then (b, a) Transitivity — contains (a, b) and (b, c) then also (a, c).

Boolean matrices L5−P. 6

Used for finite sets A, B Rows for elements of A, columns for B. 1 in position if the pair is in the relation, 0 otherwise.

The relation {(0, a), (0, c), (1, c), (2, b), (1, a)}. from {0, 1, 2, 3} to {a, b, c} is represented by the matrix

\begin{aligned}& a & b & c \\ 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 \\ 2 & 0 & 1 & 0 \\ 3 & 0 & 0 & 0 \end{aligned}

Boolean matrices, Cont. L5−P. 7

The divisibility relation over {1, 2, …, 12}

1 2 3 4 5 6 7 8 9 10 11 12
1 1 1 1 1 1 1 1 1 1 1 1 1
2 0 1 0 1 0 1 0 1 0 1 0 1
3 0 0 1 0 0 1 0 0 1 0 0 1
4 0 0 0 1 0 0 0 1 0 0 0 1
5 0 0 0 0 1 0 0 0 0 1 0 0
6 0 0 0 0 0 1 0 0 0 0 0 1
7 0 0 0 0 0 0 1 0 0 0 0 0
8 0 0 0 0 0 0 0 1 0 0 0 0
9 0 0 0 0 0 0 0 0 1 0 0 0
10 0 0 0 0 0 0 0 0 0 1 0 0
11 0 0 0 0 0 0 0 0 0 0 1 0
12 0 0 0 0 0 0 0 0 0 0 0 1

Reflexivity — major diagonal is all 1 Symmetry — matrix symmetric around the major diagonal Directed graphs – Digraphs L5−P. 8

Used for relations where A = B in this case a dot represents an element in A and an arrow for every relation.

Reflexivity: All nodes have self-loops. Symmetry: all edges are bidirectional. Transitivity: Short-circuits, for any sequence of consecutive arrows, there is a single arrow from the first to the last node.

Paths in Directed graphs L5−P. 9

A path in a relation R is a sequence a_{0}, …, a_{k} with k ≥ 0 such that (a_{i}, a_{i+1}) ∈ R for every i < k. We call k the length of the path.

Operations on Relations, Inverse L5−P. 10

If R is a relation on A×B, then R^{−1} is a relation on B ×A given by R^{−1} = {(b, a) | (a, b) ∈ R}. It’s just the relation “turned backwards.”

Inverse of “parent-of” is “child-of.”

Composition of Relations L5−P. 11

The composition of relations R_{1} ⊆ A × B and R_{2} ⊆ B × C is the relation R_{2} ∘ R_{1} = {(a, c) | (∃b)((a, b) ∈ R_{1}) ∧ ((b, c) ∈ R_{2})}.

Examples: Composition of parent-of relation with itself gives grandparent-of.

Composition of relations is equivalent to matrix multiplication, with + replaced by ∨ (Boolean or) and ∗ replaced by ∧.

Ex: Let R_{1} be relation (student in-class class-number):

\begin{aligned}& a & b & c \\ s_{0} & 1 & 0 & 1 \\ s_{1} & 1 & 0 & 1 \\ s_{2} & 0 & 1 & 0 \\ s_{3} & 0 & 0 & 0 \end{aligned}

Let R_{2} be relation (class-number in-class-rooms class-room) from {a, b, c} to {d, e, f} given by:

\begin{aligned}& d & e & f \\ a & 1 & 1 & 1 \\ b & 0 & 1 & 0 \\ c & 0 & 0 & 1 \end{aligned}

Then R_{2} ∘ R_{1} = {(s_{0}, d), ...}, (student in-class-rooms class-room) that is,

\begin{aligned}& d & e & f \\ s_{0} & 1 & 1 & 1 \\ s_{1} & 1 & 1 & 1 \\ s_{2} & 0 & 1 & 0 \\ s_{3} & 0 & 0 & 0 \end{aligned}

Relational composition is associative. Just like matrix multiplication.

\begin{aligned}& a & b & c \\ s_{0} & 1 & 0 & 1 \\ s_{1} & 1 & 0 & 1 \\ s_{2} & 0 & 1 & 0 \\ s_{3} & 0 & 0 & 0 \end{aligned}

Multiply by:

\begin{aligned}& d & e & f \\ a & 1 & 1 & 1 \\ b & 0 & 1 & 0 \\ c & 0 & 0 & 1 \end{aligned}

Composition of Relations R^{k} L5−P. 14

Useful Lemma: ∀k ≥ 1 R^{k} = {(a, b) | there is a length k path from a to b in R}

“Proof” by example, consider the relation R, (a, b), (b, d), (d, e) or:

a b c d e
a 0 1 0 0 0
b 0 0 0 1 0
c 0 0 0 0 0
d 0 0 0 0 1
e 0 0 0 0 0

Or, a → b → d → e and an additional node c

So, R^{2} (according to the relation composition definition) will be (Note that matrix multiplication gives 1st line and 4th column results in 1 2nd line and 5th column results in 1)

a b c d e
a 0 0 0 1 0
b 0 0 0 0 1
c 0 0 0 0 0
d 0 0 0 0 0
e 0 0 0 0 0

Proof: induction on k Base case: k = 1 then we have R Step: assume for R^{k} and prove for R^{k+1}. If there is a path a_{0}, …, a_{k+1} in R then there is a path a_{0}, …, a_{k} in R and a tuple (a_{k}, a_{k+1}) in R. By induction (a_{0}, a_{k}) ∈ R^{k}. By definition of composition of R^{k}∘R (a_{0}, a_{k+1}) ∈ R^{k+1}. Still to show that if (a, b) ∈ R^{k+1} then a path a_{0}, …, a_{k+1} exists in R...

Closure of Relation Reflexive Closure L5−P. 16

The reflexive closure of R is S = R ∪ {(a, a) | a ∈ A}

a b c d e
a 0 1 1 0 0
b 0 0 0 1 0
c 0 0 0 0 0
d 0 0 0 0 1
e 0 0 0 0 0

is changed to:

a b c d e
a 1 1 1 0 0
b 0 1 0 1 0
c 0 0 1 0 0
d 0 0 0 1 1
e 0 0 0 0 1

Closure of Relation Symmetric Closure L5−P. 17

The symmetric closure of R is S = R ∪ R^{−1}.

a b c d e
a 0 1 1 0 0
b 0 0 0 1 0
c 0 0 0 0 0
d 0 0 0 0 1
e 0 0 0 0 0

Is changed to:

a b c d e
a 0 1 1 0 0
b 1 0 0 1 0
c 1 0 0 0 0
d 0 1 0 0 1
e 0 0 0 1 0

Closure of Relation Transitive Closure L5−P. 18

The transitive closure of a relation R is that set: S = {(a, b) | there is a path from a to b in R}.

a b c d e
a 0 1 0 0 0
b 0 0 0 1 0
c 0 0 0 0 0
d 0 0 0 0 1
e 0 0 0 0 0

Or, a → b → d → e and an additional node c Is changed to:

a b c d e
a 0 1 0 1 1
b 0 0 0 1 1
c 0 0 0 0 0
d 0 0 0 0 1
e 0 0 0 0 0

Closure of Relation, Cont. L5−P. 20

Definition: The closure of relation R with respect to property P is the relation S that

(i) contains R, (ii) has property P, and (iii) is contained in any relation satisfying (i) and (ii). That is, S is the “smallest” relation satisfying (i) and (ii). So we need to show:

Lemma: The reflexive closure of R is S = R ∪ {(a, a) | a ∈ A}

Lemma: The symmetric closure of R is S = R ∪ R^{−1}.

Lemma: The transitive closure of a relation R is that set: S = {(a, b) | there is a path from a to b in R}.

We may show that any relation satisfying (i) and (ii) will have at least the ones in our choice of closure matrix.

Computing Transitive Closure L5−P. 21

Recall R^{i}, i ≥ 1 implies there is a path of length i. Transitive closure of R is R ∪ R^{2} ∪ R^{3} · · ·. We only need the first n elements — if there is a path from A to B, there is a path of length at most n from A to B.

Computing Transitive Closure, Cont. L5−P. 22

Consider the shortest path from a to b (well ordering). Suppose k > n then some element of A appears twice in the path (cut the loop) and contradict shortest property.

So we don’t need infinitely many terms. It is enough to take paths of length n, namely R^{1} ∪ R^{2} ⋯ ∪ R^{n}. In fact we may stop earlier.

Equivalence relations and partitions L5−P. 23

Definition: An equivalence relation is a relation that is reflexive, symmetric and transitive.

“roommates”, “married to”, “on same Ethernet hub”

A partition of a set A is a collection of subsets {A_{1}, ⋯, A_{k}} such that any two of them are disjoint (for any i ≠ j, A_{i} ∩ A_{j} = ∅) and such that their union is A.

That is, every element of A is in exactly one subset.

Fix an equivalence relation R on A. For an element a ∈ A, let [a] denote the set {b ∈ A|a ∼_{R} b}. We call this set the equivalence class of a under R. We call a a representative of [a].

Equivalence relations and partitions, Cont. L5−P. 24

Lemma: The sets [a] for a ∈ A constitute a partition of A. That is, for every a, b ∈ A, either [a] = [b] or [a] ∩ [b] = ∅.

[a] ≠ [b] Let c ∈ [b] − [a] (or c ∈ [a] − [b])

[a] ∩ [b] ≠ ∅ Let d ∈ [a] ∩ [b] We aim for a contradiction showing that c ∈ [a] a ∼_{R} d, d ∼_{R} b, b ∼_{R} c d ∼_{R} c a ∼_{R} d and d ∼_{R} c a ∼_{R} c Partitions, Integers modulo m L5−P. 25

integers (positive, negative and 0)

Definition: If a and b are integers, then a = b(mod m) if m|(a − b). or a = b + km for some integer k.

Theorem: Equality modulo m is an equivalence relation

Proof reflexive: m|(a − a) = 0, so a = a (mod m) symmetric: a = b + km then b = a + (−k)m transitive: a = b + k_{1}m, b = c + k_{2}m, so a = c + k_{2}m + k_{1}m Fast Exponentiation L5−P. 26

Lemma: If a = x (mod m) and b = y (mod m) then (a + b) = (x + y) (mod m). Proof: m | (a − x) and m | (b − y) so m | ((a − x) + (b − y)) = (a + b) − (x + y),

The same fact can be proven for multiplication.

Lemma: If a = x (mod m) and b = y (mod m) then (a × b) = (x × y) (mod m).

To compute mod b of x^{a} we may compute x^{2} replace it with y = x^{2}(mod b). Then repeat the same, compute y^{2} replace with z = y^{2}( mod b). Be careful, when a is odd...

Partial Orders L5−P. 27

A type of binary relation (two elements).

A binary relation R ⊆ A × A is a partial order if it is reflexive, transitive, and antisymmetric.

reflexive: aRa transitive: aRb ∧ bRc ⇒ aRc antisymmetric: aRb ∧ bRa ⇒ a = b. i.e., ∀a ≠ b, aRb ⇒ ¬bRa. Means NEVER symmetric!

Ordering relation (a before b then b cannot be before a).

Definition: a set A together with a partial order ⪯ is called a poset (A, ⪯).

Examples of posets: A = N, R =≤, reflexive, transitive, antisymmetric A = N, R =≥, same. A = N, R =<, NOT because not reflexive A = N, R = | (divides), easy to check reflexive, transitive, antisymmetric Directed Acyclic Graph, DAG L5−P. 29

Task graph, A is a set of tasks. aRb means “b cannot be done until a is finished”.

[figure: .; left sock; left shoe; right sock; shirt; underwear; sweater; jacket; belt; pants; right shoe]

We need to find the reflexive and transitive closure in order to have a partial order (resulting in “must be done before”).

No cycles! no path that ends where it started. otherwise we cannot get dressed.

directed acyclic graph — directed graph with no cycles.

The transitive reflexive closure of a DAG is a partial order.

Hasse Diagrams L5−P. 30

Hasse diagram for a poset (A, ⪯) is a graph:

- whose vertices are the elements of A,

- whose edges (arrows) represent pairs (a, b), where a ⪯ b but a ≠ b,

- that contains no “transitive edges”,

- for which all pairs in ⪯ are obtainable by transitivity from edges in the diagram.

(we need to remove the pants → jacket arrow).

[figure: .; left sock; left shoe; right sock; shirt; underwear; sweater; jacket; belt; pants; right shoe]

Partial vs. Total Orders L5−P. 31

a and b are incomparable if neither a ⪯ b nor b ⪯ a.

the shoes in our example

a and b are comparable if a ⪯ b or b ⪯ a

A poset (S, ⪯) is totally ordered if (∀a, b ∈ S)[a ⪯ b ∨ b ⪯ a].

Examples: S = N, ⪯=≤ S = N, ⪯= |, NOT because neither 3|5 nor 5|3 S = P (N), ⪯=⊆, NOT because neither {3} ⊆ {5} nor {5} ⊆ {3} Lexicographic order on pairs of natural numbers, defined by: (a_{1}, a_{2}) ⪯ (b_{1}, b_{2}) if and only if either a_{1} < b_{1}, or else a_{1} = b_{1} and a_{2} ≤ b_{2}.

The Hasse diagram of a total order looks like a line.

Topological Sorting L5−P. 32

Definition: A topological sort of a finite poset (A, ⪯) is a total ordering of all the elements of A, a_{1}, a_{2}, ⋯, a_{n} in such a way that ∀i < j, either a_{i} ≺ a_{j} or a_{i} and a_{j} are incomparable in (A, ⪯) (equivalently, it is not the case that a_{j} ≺ a_{i}).

Lemma: Every finite poset (A, ⪯) has a minimal element.

By induction on the number of elements. n = 1 is clear. Suppose it is true for all size-n posets. Remove an element a from the n + 1 poset. We still have a poset, use induction hypothesis to have the minimal element b. If a ⪯̸ b then b is a minimal element of the poset. Otherwise, a is the minimal element of the poset: assume that there is c ⪯ a then we have c ⪯ b which contradicts the choice of b.