CS285 · Chapter 9 · Annotated SlidesRelations
Original
Overview

Relations

Binary relations and how to write them (roster, set-builder, graph, table), relations on a set, reflexive / irreflexive, symmetric / antisymmetric and transitive relations, combining and composing relations, zero-one matrices and digraphs, closures, and equivalence relations.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 93 slides
  1. 1 Slide 1
  2. 2 Slide 2
  3. 3 Section Summary
  4. 4 Binary Relations
  5. 5 Relations and their properties
  6. 6 Relations and their properties
  7. 7 Relations and their properties
  8. 8 Slide 8
  9. 9 Roster notation
  10. 10 Builder notation
  11. 11 Relations can be represented by:
  12. 12 Relations can be represented by:
  13. 13 notation
  14. 14 Table
  15. 15 Example
  16. 16 Example
  17. 17 Relations
  18. 18 Relations on Set
  19. 19 Example
  20. 20 Example
  21. 21 Slide 21
  22. 22 Slide 22
  23. 23 1. Reflexivity & Irreflexivity
  24. 24 1. Reflexivity & Irreflexivity – cont.
  25. 25 Difference between Not Reflexive and Irreflexive
  26. 26 Difference between Not Reflexive and Irreflexive
  27. 27 Reflexive or not? Irreflexive or not?
  28. 28 Reflexive or not? Irreflexive or not?
  29. 29 2. Symmetry & Antisymmetry
  30. 30 2. Symmetry & Antisymmetry
  31. 31 Reflexive or not Irreflexive or not Symmetric or not Antisemmetric or not?
  32. 32 Reflexive or not Irreflexive or not Symmetric or not Antisemmetric or not?
  33. 33 Reflexive or not Irreflexive or not Symmetric or not Antisemmetric or not?
  34. 34 Symmetric or not Antisemmetric or not?
  35. 35 Symmetric or not Antisemmetric or not?
  36. 36 3. Transitivity
  37. 37 Slide 37
  38. 38 Combining Relations
  39. 39 Combining Relations
  40. 40 Composition
  41. 41 Composite Relations
  42. 42 Example
  43. 43 Power
  44. 44 Power
  45. 45 Example
  46. 46 Slide 46
  47. 47 Section Summary
  48. 48 Representing Relations
  49. 49 Using Zero-One Matrices
  50. 50 Using Zero-One Matrices
  51. 51 Using Zero-One Matrices
  52. 52 Zero-One Reflexive, Symmetric
  53. 53 Zero-One Reflexive, Symmetric
  54. 54 Example
  55. 55 and The Boolean Operations 1) join meet
  56. 56 Example
  57. 57 Example
  58. 58 2) Composite
  59. 59 Remember how we did Boolean product!!!!!!!
  60. 60 Remember how we did Boolean product!!!!!!!
  61. 61 Example
  62. 62 Example
  63. 63 Attention
  64. 64 Attention
  65. 65 3) Power
  66. 66 Example
  67. 67 Example
  68. 68 Example
  69. 69 Using Directed Graphs
  70. 70 Using Directed Graphs
  71. 71 Example
  72. 72 Directed graph and relation properties
  73. 73 Directed graph and relation properties. cont
  74. 74 Example
  75. 75 Digraph Reflexive, Symmetric
  76. 76 Slide 76
  77. 77 1) Reflexive Closure
  78. 78 Example 1
  79. 79 Example 2
  80. 80 2) Symmetric closure
  81. 81 Example 1
  82. 82 Example 2
  83. 83 3) Transitive closure
  84. 84 Example 1
  85. 85 Example 1
  86. 86 Slide 86
  87. 87 Slide 87
  88. 88 Slide 88
  89. 89 Slide 89
  90. 90 Example 2
  91. 91 Slide 91
  92. 92 Equivalence Relations
  93. 93 Equivalence Relations
Slide 1 / 93

Slide 1

Slide 1: Slide 1
Slide 2 / 93

Slide 2

Slide 2: Slide 2
Slide 3 / 93

Section Summary

Slide 3: Section Summary
Slide 4 / 93

Binary Relations

Slide 4: Binary Relations
Slide 5 / 93

Relations and their properties

Slide 5: Relations and their properties
Slide 6 / 93

Relations and their properties

Slide 6: Relations and their properties
Slide 7 / 93

Relations and their properties

Slide 7: Relations and their properties
Slide 8 / 93

Slide 8

Slide 8: Slide 8
Slide 9 / 93

Roster notation

Slide 9: Roster notation
Slide 10 / 93

Builder notation

Slide 10: Builder notation
Slide 11 / 93

Relations can be represented by:

Slide 11: Relations can be represented by:
Slide 12 / 93

Relations can be represented by:

Slide 12: Relations can be represented by:
Slide 13 / 93

notation

Slide 13: notation
Slide 14 / 93

Table

Slide 14: Table
Slide 15 / 93

Example

Slide 15: Example
Slide 16 / 93

Example

Slide 16: Example
Slide 17 / 93

Relations

Slide 17: Relations
Slide 18 / 93

Relations on Set

Slide 18: Relations on Set

Notes

  1. A relation on A is a subset of A × A. There are 2^(n²) relations on a set with n elements.

Exam angle

PredictionQ1

How many relations are there on a set with 3 elements?

Slide 19 / 93

Example

Slide 19: Example
Slide 20 / 93

Example

Slide 20: Example
Slide 21 / 93

Slide 21

Slide 21: Slide 21
Slide 22 / 93

Slide 22

Slide 22: Slide 22
Slide 23 / 93

1. Reflexivity & Irreflexivity

Slide 23: 1. Reflexivity & Irreflexivity
Slide 24 / 93

1. Reflexivity & Irreflexivity – cont.

Slide 24: 1. Reflexivity & Irreflexivity – cont.
Slide 25 / 93

Difference between Not Reflexive and Irreflexive

Slide 25: Difference between Not Reflexive and Irreflexive

Notes

  1. Trap Not reflexive just needs ONE missing loop; irreflexive needs ALL loops missing.

Exam angle

PredictionQ1

A relation that is not reflexive must be irreflexive.

Slide 26 / 93

Difference between Not Reflexive and Irreflexive

Slide 26: Difference between Not Reflexive and Irreflexive
Slide 27 / 93

Reflexive or not? Irreflexive or not?

Slide 27: Reflexive or not? Irreflexive or not?
Slide 28 / 93

Reflexive or not? Irreflexive or not?

Slide 28: Reflexive or not? Irreflexive or not?
Slide 29 / 93

2. Symmetry & Antisymmetry

Slide 29: 2. Symmetry & Antisymmetry

Notes

  1. Symmetric: aRb ⇒ bRa. Antisymmetric: aRb and bRa ⇒ a = b.

  2. A relation can be both (e.g. equality) or neither.

Exam angle

PredictionQ1

R = 1,1), (1,2), (2,1 on {1, 2} is:

PredictionQ2

A relation can be both symmetric and antisymmetric.

Slide 30 / 93

2. Symmetry & Antisymmetry

Slide 30: 2. Symmetry & Antisymmetry
Slide 31 / 93

Reflexive or not Irreflexive or not Symmetric or not Antisemmetric or not?

Slide 31: Reflexive or not Irreflexive or not Symmetric or not Antisemmetric or not?
Slide 32 / 93

Reflexive or not Irreflexive or not Symmetric or not Antisemmetric or not?

Slide 32: Reflexive or not Irreflexive or not Symmetric or not Antisemmetric or not?
Slide 33 / 93

Reflexive or not Irreflexive or not Symmetric or not Antisemmetric or not?

Slide 33: Reflexive or not Irreflexive or not Symmetric or not Antisemmetric or not?
Slide 34 / 93

Symmetric or not Antisemmetric or not?

Slide 34: Symmetric or not Antisemmetric or not?
Slide 35 / 93

Symmetric or not Antisemmetric or not?

Slide 35: Symmetric or not Antisemmetric or not?
Slide 36 / 93

3. Transitivity

Slide 36: 3. Transitivity

Notes

  1. Transitive: aRb and bRc ⇒ aRc.

Exam angle

PredictionQ1

R = 1,2), (2,3 on {1, 2, 3} is not transitive because it lacks:

Slide 37 / 93

Slide 37

Slide 37: Slide 37
Slide 38 / 93

Combining Relations

Slide 38: Combining Relations
Slide 39 / 93

Combining Relations

Slide 39: Combining Relations
Slide 40 / 93

Composition

Slide 40: Composition

Notes

  1. Composite S ∘ R = {(a, c) | ∃b: (a, b) ∈ R and (b, c) ∈ S}: R first, then S.

Exam angle

PredictionQ1

R = 1,2, S = 2,3. S ∘ R =

Slide 41 / 93

Composite Relations

Slide 41: Composite Relations
Slide 42 / 93

Example

Slide 42: Example
Slide 43 / 93

Power

Slide 43: Power

Notes

  1. Powers: R¹ = R, Rⁿ⁺¹ = Rⁿ ∘ R. R is transitive iff Rⁿ ⊆ R for all n.

Slide 44 / 93

Power

Slide 44: Power
Slide 45 / 93

Example

Slide 45: Example
Slide 46 / 93

Slide 46

Slide 46: Slide 46
Slide 47 / 93

Section Summary

Slide 47: Section Summary
Slide 48 / 93

Representing Relations

Slide 48: Representing Relations
Slide 49 / 93

Using Zero-One Matrices

Slide 49: Using Zero-One Matrices
Slide 50 / 93

Using Zero-One Matrices

Slide 50: Using Zero-One Matrices
Slide 51 / 93

Using Zero-One Matrices

Slide 51: Using Zero-One Matrices
Slide 52 / 93

Zero-One Reflexive, Symmetric

Slide 52: Zero-One Reflexive, Symmetric

Notes

  1. Reflexive ⇔ all 1s on the diagonal; symmetric ⇔ M = Mᵗ; antisymmetric ⇔ no pair of 1s mirrored off the diagonal.

Exam angle

PredictionQ1

In the matrix of a reflexive relation:

Slide 53 / 93

Zero-One Reflexive, Symmetric

Slide 53: Zero-One Reflexive, Symmetric
Slide 54 / 93

Example

Slide 54: Example
Slide 55 / 93

and The Boolean Operations 1) join meet

Slide 55: and The Boolean Operations 1) join meet
Slide 56 / 93

Example

Slide 56: Example
Slide 57 / 93

Example

Slide 57: Example
Slide 58 / 93

2) Composite

Slide 58: 2) Composite

Notes

  1. M_(S∘R) = M_R ⊙ M_S (Boolean product, R’s matrix on the left).

Slide 59 / 93

Remember how we did Boolean product!!!!!!!

Slide 59: Remember how we did Boolean product!!!!!!!
Slide 60 / 93

Remember how we did Boolean product!!!!!!!

Slide 60: Remember how we did Boolean product!!!!!!!
Slide 61 / 93

Example

Slide 61: Example
Slide 62 / 93

Example

Slide 62: Example
Slide 63 / 93

Attention

Slide 63: Attention
Slide 64 / 93

Attention

Slide 64: Attention
Slide 65 / 93

3) Power

Slide 65: 3) Power

Notes

  1. M_(Rⁿ) = M_R ⊙ … ⊙ M_R (n times).

Slide 66 / 93

Example

Slide 66: Example
Slide 67 / 93

Example

Slide 67: Example
Slide 68 / 93

Example

Slide 68: Example
Slide 69 / 93

Using Directed Graphs

Slide 69: Using Directed Graphs

Notes

  1. Digraph: an edge a → b for each (a, b); a loop at a for (a, a).

Slide 70 / 93

Using Directed Graphs

Slide 70: Using Directed Graphs
Slide 71 / 93

Example

Slide 71: Example
Slide 72 / 93

Directed graph and relation properties

Slide 72: Directed graph and relation properties

Notes

  1. Digraph test: reflexive = loop at every vertex; symmetric = every edge has a reverse edge; antisymmetric = no two-way edges between distinct vertices; transitive = every 2-step path has a shortcut.

Slide 73 / 93

Directed graph and relation properties. cont

Slide 73: Directed graph and relation properties. cont
Slide 74 / 93

Example

Slide 74: Example
Slide 75 / 93

Digraph Reflexive, Symmetric

Slide 75: Digraph Reflexive, Symmetric
Slide 76 / 93

Slide 76

Slide 76: Slide 76
Slide 77 / 93

1) Reflexive Closure

Slide 77: 1) Reflexive Closure

Notes

  1. Reflexive closure: R ∪ Δ (add all missing loops).

Exam angle

PredictionQ1

The reflexive closure of R = 1,2 on {1, 2} is:

Slide 78 / 93

Example 1

Slide 78: Example 1
Slide 79 / 93

Example 2

Slide 79: Example 2
Slide 80 / 93

2) Symmetric closure

Slide 80: 2) Symmetric closure

Notes

  1. Symmetric closure: R ∪ R⁻¹ (add the reverse of every pair).

Slide 81 / 93

Example 1

Slide 81: Example 1
Slide 82 / 93

Example 2

Slide 82: Example 2
Slide 83 / 93

3) Transitive closure

Slide 83: 3) Transitive closure

Notes

  1. Transitive closure R*: R ∪ R² ∪ … ∪ Rⁿ (keep adding shortcuts until nothing changes).

Exam angle

PredictionQ1

Find the transitive closure of R = 1,2), (2,3), (3,4 on {1, 2, 3, 4}.

Compare with the model answer

R ∪ R² ∪ R³ = 1,2), (2,3), (3,4), (1,3), (2,4), (1,4.

Slide 84 / 93

Example 1

Slide 84: Example 1
Slide 85 / 93

Example 1

Slide 85: Example 1
Slide 86 / 93

Slide 86

Slide 86: Slide 86
Slide 87 / 93

Slide 87

Slide 87: Slide 87
Slide 88 / 93

Slide 88

Slide 88: Slide 88
Slide 89 / 93

Slide 89

Slide 89: Slide 89
Slide 90 / 93

Example 2

Slide 90: Example 2
Slide 91 / 93

Slide 91

Slide 91: Slide 91
Slide 92 / 93

Equivalence Relations

Slide 92: Equivalence Relations

Notes

  1. Equivalence relation: reflexive + symmetric + transitive (e.g. congruence mod m). Its equivalence classes partition the set.

  2. Memory trick Equivalence = RST: Reflexive, Symmetric, Transitive.

Exam angle

PredictionQ1

Which is an equivalence relation on ℤ?

PredictionQ2

A partial order is reflexive, transitive and:

Slide 93 / 93

Equivalence Relations

Slide 93: Equivalence Relations