CS285 · Annotated SlidesChapter 9 — Relations
Chapter 9 · Annotated slides

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.

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up
Slide 1: Slide 1
Exam weight Low

    Relations and Their Properties

    Section 9.1

    2
    Exam weight Low

      Section Summary

      • Relations and Functions
      • Properties of Relations
        • Reflexive Relations
        • Symmetric and Antisymmetric Relations
        • Transitive Relations
      • Combining Relations
      3
      Exam weight Low
        Slide 4: Binary Relations
        Exam weight Low
        1. A binary relation from A to B is a subset of A × B; (a, b) ∈ R is written aRb.
        Slide 5: Relations and their properties
        Exam weight Low
          Slide 6: Relations and their properties
          Exam weight Low
            Slide 7: Relations and their properties
            Exam weight Low

              8
              Exam weight Low
                Slide 9: Roster notation
                Exam weight Low
                  Slide 10: Builder notation
                  Exam weight Low
                    Slide 11: Relations can be represented by:
                    Exam weight Low
                      Slide 12: Relations can be represented by:
                      Exam weight Low
                        Slide 13: notation
                        Exam weight Low
                          Slide 14: Table
                          Exam weight Low
                            Slide 15: Example
                            Exam weight Low
                              Slide 16: Example
                              Exam weight Low

                                Relations

                                Example: R: A B

                                such that (a>b)

                                Solution:

                                3,2) , (4,2), (4,3

                                Relations
                                17
                                Exam weight Low
                                  Slide 18: Relations on Set
                                  Exam weight High
                                  1. A relation on A is a subset of A × A. There are 2^(n²) relations on a set with n elements.
                                  🎯 How this can come up · 1 question
                                  MCQ

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

                                  Example

                                  • Consider these relations on the set of integers:
                                  • R1 ={(a,b)| a≤b },
                                  • R2 ={(a,b)|a>b},
                                  • R3 ={(a,b)|a=b or a =−b},
                                  • R4 ={(a,b)|a=b},
                                  • R5 ={(a,b)|a=b+1},
                                  • R6 ={(a,b )|a+b≤3}.

                                  Which of these relations contain each of the pairs (1, 1), (1, 2), (2, 1), (1, −1), and (2, 2)?

                                  19
                                  Exam weight Low

                                    Example

                                    Solution:

                                    R1, R3, R4, R6

                                    • (1,1) R1, R6
                                    • (1,2) R2, R5, R6
                                    • (2,1)
                                    • (1,-1) R2, R3, R6
                                    • (2,2) R1, R3, R4 20
                                    20
                                    Exam weight Low
                                      Slide 21: Slide 21
                                      Exam weight Low

                                        22
                                        Exam weight Low
                                          Slide 23: 1. Reflexivity & Irreflexivity
                                          Exam weight Low
                                          1. Reflexive: (a, a) ∈ R for EVERY a. Irreflexive: (a, a) ∉ R for every a.
                                          Slide 24: 1. Reflexivity & Irreflexivity – cont.
                                          Exam weight Low
                                            Slide 25: Difference between Not Reflexive and Irreflexive
                                            Exam weight High
                                            1. "Not reflexive" ≠ "irreflexive": a relation can be neither (some loops but not all).
                                            Exam trapNot reflexive just needs ONE missing loop; irreflexive needs ALL loops missing.
                                            🎯 How this can come up · 1 question
                                            True / False

                                            A relation that is not reflexive must be irreflexive.

                                            Slide 26: Difference between Not Reflexive and Irreflexive
                                            Exam weight Low
                                              Slide 27: Reflexive or not? Irreflexive or not?
                                              Exam weight Low
                                                Slide 28: Reflexive or not? Irreflexive or not?
                                                Exam weight Low
                                                  Slide 29: 2. Symmetry & Antisymmetry
                                                  Exam weight High
                                                  1. Symmetric: aRb ⇒ bRa. Antisymmetric: aRb and bRa ⇒ a = b.
                                                  2. A relation can be both (e.g. equality) or neither.
                                                  🎯 How this can come up · 2 questions
                                                  MCQ

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

                                                  True / False

                                                  A relation can be both symmetric and antisymmetric.

                                                  Slide 30: 2. Symmetry & Antisymmetry
                                                  Exam weight Low
                                                    Slide 31: Reflexive or not Irreflexive or not Symmetric or not Antisemmetric or not?
                                                    Exam weight Low
                                                      Slide 32: Reflexive or not Irreflexive or not Symmetric or not Antisemmetric or not?
                                                      Exam weight Low
                                                        Slide 33: Reflexive or not Irreflexive or not Symmetric or not Antisemmetric or not?
                                                        Exam weight Low
                                                          Slide 34: Symmetric or not Antisemmetric or not?
                                                          Exam weight Low
                                                            Slide 35: Symmetric or not Antisemmetric or not?
                                                            Exam weight Low
                                                              Slide 36: 3. Transitivity
                                                              Exam weight High
                                                              1. Transitive: aRb and bRc ⇒ aRc.
                                                              🎯 How this can come up · 1 question
                                                              MCQ

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

                                                              Slide 37: Slide 37
                                                              Exam weight Low
                                                                Slide 38: Combining Relations
                                                                Exam weight Low
                                                                1. Relations are sets: combine with ∪, ∩, −, ⊕.
                                                                Slide 39: Combining Relations
                                                                Exam weight Low
                                                                  Slide 40: Composition
                                                                  Exam weight High
                                                                  1. Composite S ∘ R = {(a, c) | ∃b: (a, b) ∈ R and (b, c) ∈ S}: R first, then S.
                                                                  🎯 How this can come up · 1 question
                                                                  MCQ

                                                                  R = {(1,2)}, S = {(2,3)}. S ∘ R =

                                                                  Slide 41: Composite Relations
                                                                  Exam weight Low

                                                                    Example

                                                                    42
                                                                    Exam weight Low
                                                                      Slide 43: Power
                                                                      Exam weight Low
                                                                      1. Powers: R¹ = R, Rⁿ⁺¹ = Rⁿ ∘ R. R is transitive iff Rⁿ ⊆ R for all n.
                                                                      Slide 44: Power
                                                                      Exam weight Low
                                                                        Slide 45: Example
                                                                        Exam weight Low

                                                                          Representing Relations

                                                                          Section 9.3

                                                                          46
                                                                          Exam weight Low

                                                                            Section Summary

                                                                            Representing Relations using Matrices Representing Relations using Digraphs

                                                                            47
                                                                            Exam weight Low

                                                                              Representing Relations

                                                                              Some special ways to represent binary relations:

                                                                              • With ordered pairs (section 9.1)
                                                                              • With a table (section 9.1)
                                                                              • With a Zero-one matrix
                                                                              • With a directed graph or diagraph
                                                                              48
                                                                              Exam weight Low
                                                                                Slide 49: Using Zero-One Matrices
                                                                                Exam weight Low
                                                                                1. Zero-one matrix M_R: mᵢⱼ = 1 if (aᵢ, bⱼ) ∈ R.
                                                                                Slide 50: Using Zero-One Matrices
                                                                                Exam weight Low
                                                                                  Slide 51: Using Zero-One Matrices
                                                                                  Exam weight Low
                                                                                    Slide 52: Zero-One Reflexive, Symmetric
                                                                                    Exam weight High
                                                                                    1. Reflexive ⇔ all 1s on the diagonal; symmetric ⇔ M = Mᵗ; antisymmetric ⇔ no pair of 1s mirrored off the diagonal.
                                                                                    🎯 How this can come up · 1 question
                                                                                    MCQ

                                                                                    In the matrix of a reflexive relation:

                                                                                    Slide 53: Zero-One Reflexive, Symmetric
                                                                                    Exam weight Low
                                                                                      Slide 54: Example
                                                                                      Exam weight Low
                                                                                        Slide 55: and The Boolean Operations 1) join meet
                                                                                        Exam weight Low
                                                                                          Slide 56: Example
                                                                                          Exam weight Low
                                                                                            Slide 57: Example
                                                                                            Exam weight Low
                                                                                              Slide 58: 2) Composite
                                                                                              Exam weight Low
                                                                                              1. M_(S∘R) = M_R ⊙ M_S (Boolean product, R’s matrix on the left).
                                                                                              Slide 59: Remember how we did Boolean product!!!!!!!
                                                                                              Exam weight Low
                                                                                                Slide 60: Remember how we did Boolean product!!!!!!!
                                                                                                Exam weight Low
                                                                                                  Slide 61: Example
                                                                                                  Exam weight Low
                                                                                                    Slide 62: Example
                                                                                                    Exam weight Low
                                                                                                      Slide 63: Attention
                                                                                                      Exam weight Low
                                                                                                        Slide 64: Attention
                                                                                                        Exam weight Low
                                                                                                          Slide 65: 3) Power
                                                                                                          Exam weight Low
                                                                                                          1. M_(Rⁿ) = M_R ⊙ … ⊙ M_R (n times).
                                                                                                          Slide 66: Example
                                                                                                          Exam weight Low
                                                                                                            Slide 67: Example
                                                                                                            Exam weight Low
                                                                                                              Slide 68: Example
                                                                                                              Exam weight Low
                                                                                                                Slide 69: Using Directed Graphs
                                                                                                                Exam weight Low
                                                                                                                1. Digraph: an edge a → b for each (a, b); a loop at a for (a, a).
                                                                                                                Slide 70: Using Directed Graphs
                                                                                                                Exam weight Low
                                                                                                                  Slide 71: Example
                                                                                                                  Exam weight Low
                                                                                                                    Slide 72: Directed graph and relation properties
                                                                                                                    Exam weight Medium
                                                                                                                    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: Directed graph and relation properties. cont
                                                                                                                    Exam weight Low
                                                                                                                      Slide 74: Example
                                                                                                                      Exam weight Low
                                                                                                                        Slide 75: Digraph Reflexive, Symmetric
                                                                                                                        Exam weight Low

                                                                                                                          Closure Relations

                                                                                                                          Section 9.4

                                                                                                                          76
                                                                                                                          Exam weight Low
                                                                                                                            Slide 77: 1) Reflexive Closure
                                                                                                                            Exam weight High
                                                                                                                            1. Reflexive closure: R ∪ Δ (add all missing loops).
                                                                                                                            🎯 How this can come up · 1 question
                                                                                                                            MCQ

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

                                                                                                                            Slide 78: Example 1
                                                                                                                            Exam weight Low
                                                                                                                              Slide 79: Example 2
                                                                                                                              Exam weight Low
                                                                                                                                Slide 80: 2) Symmetric closure
                                                                                                                                Exam weight Low
                                                                                                                                1. Symmetric closure: R ∪ R⁻¹ (add the reverse of every pair).
                                                                                                                                Slide 81: Example 1
                                                                                                                                Exam weight Low
                                                                                                                                  Slide 82: Example 2
                                                                                                                                  Exam weight Low
                                                                                                                                    Slide 83: 3) Transitive closure
                                                                                                                                    Exam weight High
                                                                                                                                    1. Transitive closure R*: R ∪ R² ∪ … ∪ Rⁿ (keep adding shortcuts until nothing changes).
                                                                                                                                    🎯 How this can come up · 1 question
                                                                                                                                    Written

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

                                                                                                                                    Slide 84: Example 1
                                                                                                                                    Exam weight Low
                                                                                                                                      Slide 85: Example 1
                                                                                                                                      Exam weight Low
                                                                                                                                        Slide 86: Slide 86
                                                                                                                                        Exam weight Low

                                                                                                                                          87
                                                                                                                                          Exam weight Low
                                                                                                                                            Slide 88: Slide 88
                                                                                                                                            Exam weight Low
                                                                                                                                              Slide 89: Slide 89
                                                                                                                                              Exam weight Low
                                                                                                                                                Slide 90: Example 2
                                                                                                                                                Exam weight Low
                                                                                                                                                  Slide 91: Slide 91
                                                                                                                                                  Exam weight Low
                                                                                                                                                    Slide 92: Equivalence Relations
                                                                                                                                                    Exam weight High
                                                                                                                                                    1. Equivalence relation: reflexive + symmetric + transitive (e.g. congruence mod m). Its equivalence classes partition the set.
                                                                                                                                                    Memory trickEquivalence = RST: Reflexive, Symmetric, Transitive.
                                                                                                                                                    🎯 How this can come up · 2 questions
                                                                                                                                                    MCQ

                                                                                                                                                    Which is an equivalence relation on ℤ?

                                                                                                                                                    MCQ

                                                                                                                                                    A partial order is reflexive, transitive and:

                                                                                                                                                    Slide 93: Equivalence Relations
                                                                                                                                                    Exam weight Low