studyhubDiscrete Structures I

Notes / Unit 2 · Module 2 · Midterm

Relations

A relation is just a set of ordered pairs, so every question in this unit comes down to checking which pairs are present. The exam asks you to find domains and ranges, test the four properties pair by pair, read off equivalence classes, draw Hasse diagrams and compose relations in the right order.

2.1Relations, domain and range

A relation R from A to B is any subset of the Cartesian product A × B. Every element of R is an ordered pair (a, b) with a ∈ A and b ∈ B. When A = B, R is a relation on A.

aRb
(a, b) ∈ R: a is related to b. If (a, b) ∉ R, a is not related to b.
Domain, Dom(R)
The set of first elements of the pairs in R.
Range, Ran(R) or Im(R)
The set of second elements of the pairs in R, also called the image.
Co-domain
The whole of B, whether or not every element of it is used.
Empty relation
R = ∅, which contains no pairs.
Full relation
R = A × B, which contains every pair.
Identity relation on A
{(a, a) | a ∈ A}, where every element is related to itself and to nothing else.

Worked example

A = {1, 2, 3, 5}, B = {4, 6, 9}, R = {(a, b) | a − b is odd}

  1. 1Test all 4 × 3 = 12 pairs of A × B. a − b is odd when one of a, b is even and the other odd.
  2. 2R = {(1, 4), (1, 6), (2, 9), (3, 4), (3, 6), (5, 4), (5, 6)}.
  3. 3Domain = {1, 2, 3, 5}, the first elements used.
  4. 4Range = {4, 6, 9}, the second elements used. Co-domain = B = {4, 6, 9}.

Worked example

R = {(1, y), (1, z), (3, y)} from A = {1, 2, 3} to B = {x, y, z}

  1. 1Domain = {1, 3}. The element 2 is in A but starts no pair.
  2. 2Range = {y, z}. The element x is in B but ends no pair.
  3. 3Co-domain = {x, y, z}.

Since |A × B| = |A| · |B|, there are 2^(|A| · |B|) different relations from A to B, one for each subset, ∅ included.

2.2Arrow diagrams, matrices and digraphs

The same relation can be shown three ways. An arrow diagram draws an arrow from a to b whenever aRb. A digraph does the same on a single set of vertices, so a pair (a, a) becomes a loop. A matrix M_R = [mᵢⱼ] lists A down the side and B across the top.

mᵢⱼ = 1 if (aᵢ, bⱼ) ∈ R, mᵢⱼ = 0 if (aᵢ, bⱼ) ∉ R

row i
the first element aᵢ
column j
the second element bⱼ
   1 2 3
1  1 1 1
2  0 1 1
3  0 0 1
R = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)} on A = {1, 2, 3}

Row a lists everything a is related to, and column b lists everything related to b. Transposing the matrix (swapping rows and columns) gives the matrix of the inverse relation, R⁻¹.

2.3Reflexive, symmetric, antisymmetric, transitive

These four properties are defined only for a relation on one set A. Each one is checked pair by pair, and a single counterexample is enough to show that a property fails.

PropertyConditionIn the matrixIn the digraph
Reflexive(a, a) ∈ R for every a ∈ AMain diagonal all 1sA loop at every vertex
Irreflexive(a, a) ∉ R for every a ∈ AMain diagonal all 0sNo loops at all
Symmetric(a, b) ∈ R ⇒ (b, a) ∈ REqual to its transpose (mirror image across the diagonal)Every edge has a partner going back. Loops need none
Antisymmetric(a, b) ∈ R and (b, a) ∈ R ⇒ a = bNever 1 in both mᵢⱼ and mⱼᵢ for i ≠ j. The diagonal can be anythingNo pair of distinct vertices joined both ways
Transitive(a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ RHard to see. Check every chainEvery two-step path a → b → c has a shortcut a → c

Worked example

Rosen's six relations on A = {1, 2, 3, 4}

  1. 1R1 = {(1,1), (1,2), (2,1), (2,2), (3,4), (4,1), (4,4)}, R2 = {(1,1), (1,2), (2,1)}, R3 = {(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4)}.
  2. 2R4 = {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3)}, R5 = {(a, b) | a ≤ b}, R6 = {(3,4)}.
  3. 3Reflexive: R3 and R5. Each of the others lacks (3, 3).
  4. 4Symmetric: R2 and R3. In every other relation some (a, b) has no (b, a).
  5. 5Antisymmetric: R4, R5 and R6. R1, R2 and R3 each contain both (1, 2) and (2, 1).
  6. 6Transitive: R4, R5 and R6. R1 fails on (3, 4), (4, 1) without (3, 1). R2 fails on (2, 1), (1, 2) without (2, 2). R3 fails on (4, 1), (1, 2) without (4, 2).

Worked example

Transitivity on A = {1, 2, 3}

  1. 1R1 = {(1, 2), (2, 3), (1, 3)}. The only chain is (1, 2), (2, 3), and (1, 3) is present, so R1 is transitive.
  2. 2R2 = {(1, 2), (2, 1)}. The chain (1, 2), (2, 1) demands (1, 1), which is missing, so R2 is not transitive.
  3. 3R3 = A × A contains every pair, so it is transitive.

2.4Equivalence relations and classes

A relation on A is an equivalence relation when it is reflexive, symmetric and transitive. It groups elements that are "the same" in some respect, such as the same remainder or the same length.

Equivalence class [a]
{b ∈ A | aRb}, every element related to a. Because R is reflexive, a ∈ [a].
Partition of A
Non-empty blocks that do not overlap and together cover A.
Congruence mod m
a ≡ b (mod m) when m divides a − b. Its classes are the m possible remainders.

Any two classes are either equal or disjoint, so the distinct classes form a partition of A. In the other direction, every partition defines an equivalence relation: relate two elements exactly when they share a block.

Worked example

Which is an equivalence relation on A = {1, 2, 3}?

  1. 1R1 = A × A. It is reflexive, symmetric and transitive, so it is an equivalence relation with one class, [1] = {1, 2, 3}.
  2. 2R2 = {(1, 1), (1, 3), (2, 1), (3, 1)}. It is not reflexive, since (2, 2) is missing, so it is not an equivalence relation.
  3. 3R2 is not symmetric either: (2, 1) has no (1, 2). Nor is it transitive: (3, 1) and (1, 3) demand (3, 3).

Worked example

Classes of a ≡ b (mod 3) on A = {0, 1, …, 8}

  1. 1[0] = {0, 3, 6}, [1] = {1, 4, 7}, [2] = {2, 5, 8}.
  2. 2[4] = [1], because 4 leaves remainder 1. Naming a class by a different member does not give a new class.
  3. 3The partition is {{0, 3, 6}, {1, 4, 7}, {2, 5, 8}}.

2.5Partial orders

A relation on A is a partial order when it is reflexive, antisymmetric and transitive. A set together with a partial order is a poset, written (A, ⪯). Examples are ≤ on numbers, divisibility on positive integers and ⊆ on sets.

Comparable
a ⪯ b or b ⪯ a. In divisibility, 2 and 3 are incomparable.
Total order
A partial order in which every two elements are comparable, such as ≤.
Minimal element
No other element is below it. There can be several.
Maximal element
No other element is above it. There can be several.
Least / greatest element
Below or above every other element. There is at most one of each, and there may be none.

Worked example

Which is a partial order on A = {1, 2, 3}?

  1. 1R1 = {(1,1), (2,2), (3,3), (1,2), (2,1)}. It is not antisymmetric, since (1, 2) and (2, 1) are both present.
  2. 2R2 = {(1,1), (2,2), (3,3), (1,3), (2,3)}. It is reflexive and antisymmetric, and its only chains, (1,3),(3,3) and (2,3),(3,3), close up. So it is a partial order.
  3. 3R3 = A × A. It is not antisymmetric, so it is not a partial order (although it is an equivalence relation).

2.6Hasse diagrams

A Hasse diagram is a trimmed digraph of a partial order. Reflexivity and transitivity can always be read back in, so it draws only the covering pairs. b covers a when a ⪯ b, a ≠ b, and nothing lies strictly between them.

  1. Start from the digraph of the partial order.
  2. Remove every loop (a, a).
  3. Remove every edge (a, c) that is implied by a path a → b → c.
  4. Place each b above everything it covers and drop the arrowheads, since every edge now points upward.

Worked example

Divisibility on A = {1, 2, 3, 4, 6, 12}

  1. 1Covering pairs: 1–2, 1–3, 2–4, 2–6, 3–6, 4–12, 6–12. These seven are the lines.
  2. 2(1, 4) is not drawn, because 1 | 2 | 4. Nor is (2, 12), because 2 | 4 | 12. Neither is any loop.
  3. 3Minimal element: 1, at the bottom. Maximal element: 12, at the top. Here they are also the least and greatest elements.
  4. 4To recover the order, a ⪯ b exactly when you can climb from a to b along lines, or a = b.

2.7Inverse relations

R⁻¹ = {(b, a) | (a, b) ∈ R}

If R goes from A to B, then R⁻¹ goes from B to A.

  • (R⁻¹)⁻¹ = R.
  • Dom(R⁻¹) = Ran(R) and Ran(R⁻¹) = Dom(R).
  • If R is a relation on A, so is R⁻¹. Its matrix is the transpose of M_R.
  • R is symmetric exactly when R = R⁻¹.

Worked example

R = {(1, q), (2, r), (3, q), (4, p)} from A = {1, 2, 3, 4} to B = {p, q, r}

  1. 1Reverse every pair: R⁻¹ = {(p, 4), (q, 1), (q, 3), (r, 2)}.
  2. 2Dom(R⁻¹) = {p, q, r} and Ran(R⁻¹) = {1, 2, 3, 4}.
  3. 3(R⁻¹)⁻¹ = {(1, q), (2, r), (3, q), (4, p)} = R.

2.8Composition of relations

Let R be a relation from A to B and S a relation from B to C. Their composition S ∘ R goes from A to C, and it follows R first, then S.

S ∘ R = {(a, c) ∈ A × C | (a, b) ∈ R and (b, c) ∈ S for some b ∈ B}

This is the course's convention, the same as for functions: the relation written on the right acts first.

Worked example

R = {(1, a), (2, d), (3, a), (3, b), (3, d)}, S = {(b, x), (b, z), (c, y), (d, z)}

  1. 1For each pair of R, look for pairs of S that start where it ends.
  2. 2(1, a) and (3, a): S has nothing starting at a, so these give nothing.
  3. 3(2, d) then (d, z) gives (2, z). (3, b) then (b, x) and (b, z) gives (3, x) and (3, z). (3, d) then (d, z) gives (3, z) again.
  4. 4S ∘ R = {(2, z), (3, x), (3, z)}.

Worked example

On A = {2, 4, 7, 9}: R = {(2,2), (4,7), (7,4), (9,2)}, S = {(2,9), (7,4), (4,2), (7,9)}

  1. 1R ∘ S (S first): (2,9) then (9,2) gives (2,2). (7,4) then (4,7) gives (7,7). (4,2) then (2,2) gives (4,2). (7,9) then (9,2) gives (7,2).
  2. 2R ∘ S = {(2, 2), (4, 2), (7, 2), (7, 7)}.
  3. 3S ∘ R (R first): (2,2) then (2,9) gives (2,9). (4,7) then (7,4) and (7,9) gives (4,4) and (4,9). (7,4) then (4,2) gives (7,2). (9,2) then (2,9) gives (9,9).
  4. 4S ∘ R = {(2, 9), (4, 4), (4, 9), (7, 2), (9, 9)}, which is a different relation.

R ∘ R is written R². A relation is transitive exactly when R² ⊆ R. In matrix form, M_{S∘R} is the Boolean product of M_R and M_S (R's matrix on the left), which uses AND for multiplication and OR for addition.

Check yourself

Answer these out loud, without scrolling up. Any you can't, reread that section — then let the drill mark you.

  1. 1.R = {(1, y), (3, y), (3, z)} goes from A = {1, 2, 3} to B = {x, y, z}. What are its domain, range and co-domain?
  2. 2.Give a relation on {1, 2, 3} that is both symmetric and antisymmetric, and one that is neither.
  3. 3.How does each of reflexive, symmetric and antisymmetric show up in the matrix of a relation?
  4. 4.Why are two equivalence classes always either equal or disjoint?
  5. 5.Draw the Hasse diagram of divisibility on {2, 3, 4, 6, 12, 18}, and name its minimal and maximal elements.
  6. 6.In S ∘ R, which relation is applied first? Compute S ∘ R and R ∘ S for R = {(1, 2), (2, 3)} and S = {(2, 1), (3, 3)} on {1, 2, 3}.