Understanding Set Relations

• A relationship between elements of sets is a key aspect when discussing sets.
• Relations can exist within a single set or among multiple sets.
• Relations are descriptive tools for illustrating relationships between objects.

Examples of Relations

• M = {(x,y)| x is married to y} is a relation on the set of people, e.g., if A = {Dingdong, Mateo, Dennis, Daniel }, B = {Sarah, Jenilyn, Marian, Kathryn }, then M = { (Dingdong, Marian), (Mateo, Sarah), (Dennis, Jenilyn) }.
• R = {(x,y) | language x is available on computer y} showcases the relation between sets of languages and computers.
• G = {(x,y) | x < y} gives a relation of pairs where x is less than y.
• H = {(x,y) | y = x3} represents a relation where y is the cube of x.
• I = {(x,y) | x+y = 7} is a relation where the sum of x and y equals 7.

Binary Relations

• A binary relation R from set A to set B is a subset of R ⊆ A × B.
• A binary relation from A to B is a set R of ordered pairs where the first element of each ordered pair is from A, and the second is from B.
• For example: If A = {0,1,2} and B = {a,b}, then R = {(0, a), (0, b), (1,a), (2, b)} is a relation from A to B.
• Notation:
  • aRb ⇔ (a, b) ∈ R
  • aRb ⇔ (a, b) ∉ R
• If R = {(0, a), (0, b), (1,a), (2, b)}, then (0, a) ∈ R and (1, b) ∉ R.
• Domain of a relation includes all first entries of ordered pairs.
• Range includes all second coordinates.
• Example:
  • If A = {1,2,3} and B = {1,2,3,4}, and G = {(a,b)| a < b}, then G = {(1,2), (1,3), (1,4),(2,3),(2,4), (3,4)}.
  • Dom(G) = {1,2,3}
  • Range(G) = {2,3,4}
• A binary relation R on a set A is a subset of A × A or a relation from A to A.
• Ex: If A = {a,b,c}, then R = {(a,a), (a,b), (a,c)} is a relation on A.
• Ex: If A = {1, 2, 3, 4}, then R = {(a,b) | a divides b} is R = {(1,1), (1, 2), (1,3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.

Relations example

• Consider the following relations on Z:
  • R₁ = { (a, b) | a≤b}
  • R₂ = { (a, b) | a>b }
  • R₃ = { (a, b) | a = b or a = −b }
  • R₄ = { (a, b) | a = b }
  • R₅ = { (a, b) | a = b+1 }
  • R₆ = { (a, b) | a + b ≤ 3 }
• Pair containments for each relation:
  • R₁ contains (1,1), (1,2), (2,2)
  • R₂ contains (2,1), (1,-1)
  • R₃ contains (1,1), (1,-1), (2,2)
  • R₄ contains (1,1), (2,2)
  • R₅ contains (2,1)
  • R₆ contains (1,1), (1,2), (2,1), (1,-1)
• List the ordered pairs in the relation R from A = {0, 1, 2, 3, 4} to B = {0, 1, 2, 3}, where (a, b) ∈ R if and only if of these sets:
  • a = b. R1 = {(0,0),(1,1), (2,2), (3,3)}
  • a + b = 4. R2 = {(1,3),(2,2), (3,1),(4,0)}
  • a > b. R3 = {(1,0), (2,0), (2,1), (3,0),(3,1),(3,2), (4,0),(4,1), (4,2),(4,3)}

Properties of Relations

• Reflexive
• Symmetric
• Antisymmetric
• Transitive

Reflexive Relations

• R is reflexive if and only if (a,a) ∈ R for every element a ∈ A.
• Symbolically: ∀x[x∈A → (x,x) ∈ R]
• R = {(1,1),(2,2), (3,3), (4,4) }
• S= {(Java, Java), (Pascal, Pascal), (C#,C#)}
• Consider the following relations on {1, 2, 3, 4}:
  • R₂ = { (1,1), (1,2), (2,1) }
  • R3 = { (1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4) }
  • R₄ = { (2,1), (3,1), (3,2), (4,1), (4,2), (4,3) }
• R3 is reflexive

Symmetric Relations

• R is symmetric if and only if (b,a) ∈ R whenever (a,b) ∈ R for all (a,b) ∈ A.
• Symbolically: ∀x∀y [(x,y) ∈R → (y,x) ∈ R]
• R = {(1,2), (2,1), (3,4), (4,3), (4,4)}
• S = {printer, ribbon), (ribbon, printer), (pen, paper), (paper, pen)}

Antisymmetric Relations

• A relation R on a set A for all a,b ∈ A, if (a,b) ∈ R and (b,a) ∈ R, then a = b is called antisymmetric.
• Symbolically: ∀x∀y [(x,y) ∈R ∧ (y,x) ∈ R → x = y]
• For all a,b if (a,b)  R and a ≠ b, then (b,a)  R
• R = {(1,2), (5,6), (3,7),(4,9),(2,2)}
• Ex:
  • R₂ = { (1,1), (1,2), (2,1) }
  • R3 = { (1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4) }
  • R₄ = { (1,1), (2,1), (3,1), (3,2), (4,1), (4,2), (4,3) }
• R2 and R3 are symmetric
• R₄ is antisymmetric

Transitive Relations

• A relation R on a set A is transitive if whenever (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R, for all a,b,c ∈ A.
• Symbolically: VxVy Vz[(x,y) ∈R ∧ (y,z) ∈ R → (x,z) ∈ R ]
• Ex: R = {(1,2), (2,3),(1,3), (3,4), (2,4), (1,4) }
• Given a relation on the set {1, 2, 3, 4}, decide whether it is reflexive, whether it is symmetric, whether it is antisymmetric, and whether it is transitive:
  • {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
    • Reflexive because (a, a) is in the relation for all a = 1, 2, 3, 4.
    • Symmetric because for every (a, b), there is (b, a)
    • Not antisymmetric because there is (1, 2) and (2, 1)
    • Transitive because while there are (1, 2) and (2, 1), there is also (1, 1) or (2, 2) in the relation.
• Determine if the relations on the set {1, 2, 3, 4} are reflexive, symmetric, antisymmetric, and transitive:
  • {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}
  • { (2, 4), (4, 2)}
  • {(1, 2), (2,2), (2, 3), (3, 4)}
  • {(1, 1), (2, 2), (2,4), (3,1), (3, 3), (4, 4)}

Combining Relations

• Given two relations R1 and R2, combine them using set operations:
  • R1 ∪ R2
  • R1 ∩ R2
  • R1 − R2
  • R2 − R1
• Ex: A = {1,2,3} and B = {1,2,3,4}
  • R1 = {(1,1),(2,2),(3,3)}
  • R2 = {(1,1),(1,2),(1,3),(1,4)}
  • R1 ∪ R2 ={(1,1), (1,2), (1,3),(1,4),(2,2),(3,3)}
  • R1 ∩ R2 ={(1,1)}
  • R1 − R2 ={(2,2),(3,3)}
  • R2 − R1 ={(1,2), (1,3),(1,4)}

Composition of a Relation

• R is a relation from set A to set B, and S is a relation from B to set C. The composite of R and S has ordered pairs (a, c), where a ∈ A, c ∈ C, and there is an element b ∈ B where (a, b) ∈ R and (b, c) ∈ S. This is denoted S ◦ R.
• Computing the composite of two relations requires finding elements that are the second element of ordered pairs in the first relation and the first element of ordered pairs in the second relation
• Ex: R is the relation from {1, 2, 3} to {1, 2, 3, 4}.
  • R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)}
  • S is the relation from {1, 2, 3, 4} to {0, 1, 2}.
  • S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)}
  • S ○ R = { (1,0), (1,1 ), (2,1), (2,2) , (3,0), (3,1)}

Representing Relations Using

• Digraphs
• Matrices
• A directed graph, or digraph, consists of a set V of vertices (or nodes) together with a set E of ordered pairs of elements of V called edges (or arcs).
  • The vertex a is the initial vertex of the edge (a,b), and the vertex b is the edge’s terminal vertex.
  • An edge of the form (a,a) is called a loop.
• Ex: Draw the directed graph with vertices a, b, c, and d, for relation R = {(a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b)}
• What are the ordered pairs in the relation represented by this directed graph?
  • R = {(1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (3, 3), (4, 1), (4, 3) }

Representing Relations Using Matrices

• A relation between finite sets is represented using a zero-one matrix.
• If R is a relation from A = {a1, a2, …, am} to B = {b1, b2, …, bn}:
  • The elements can be arbitrarily ordered; when A = B, the same ordering is used.
  • The relation R is represented by the m x n matrix MR = [mij], where mij is 1 if (ai, bj) ∈ R, 0 if (ai, bj) ∉ R.
  • The matrix representing R has a 1 as its (i,j) entry when ai is related to bj and a 0 if ai is not related to bj.
• Ex: A = {1,2,3} and B = {1,2}. R is the relation from A to B containing (a,b) if a ∈ A, b ∈ B, and a > b. The matrix representing R (assuming the increasing numerical order) is:
• Let A = {1, 2, 3,} and B = {1,2,3,4,5}. The ordered pairs in the relation R represented by the matrix is: R = { (1,2),(2,1),(2,3),(2,4), (3,1), (3,3), (3,5)}.