Week 17 - Relations A

Lesson 9.1 Understanding the concept of relations

9.101 Introduction

  • Relationships between elements of sets occur in many contexts.
  • We deal with relationships in a daily basis:
    • A relationship between a person and a relative.
    • A relationship between an employee and their salary.
    • A relationship between a business and its telephone number.
    • A relationship between a computer language and a valid statement in this language will often arise in computer science.
  • In maths, we study relationships like:
    • the relation between a positive integer and one it divides.
    • relation between a real number and one that is larger than it.
    • relation between a business and its telephone number.
    • relation between a computer language and a valid statement
    • relation between a real number x and the value f(x) where f is a function, and so on.
  • Relations in maths
    • We can define relationship between elements of 2 sets
    • We can also define the relationship between 2 elements of a set.

9.103 Definition of a relation: relation versus function

  • Relation
    • A relation can be defined between elements of set A and elements of another set B.
    • Can also be defined between elements of the same set.
    • We use the letter RR to refer to relation.
    • Let AA and BB be two sets.
    • Let RR be a relation linking elements of set AA to elements of set BB.
    • Let xAx \in A and yBy \in B
      • We say that xx is related to yy with respect to relation RR and we write x R yx \ R \ y
    • A relation can also be between elements of the same set.
    • A relation is a link between two elements of a set
      • For example
        • A person x is a SON OF' a person y.
        • SON OF is a relation that links x to y
      • Usually use the letter RR to refer to a relation:
        • In this case RR = 'SON OF'
        • If xx is SON OF yy we write x R yx \ R \ y
        • If yy is NOT a SON OF xx we write y  xy \ \not R \ x
    • A relation can be defined as a link or connection between elements of set A to set B.
    • Example
      • A is the set of students in a Comp Science class
        • A={Sofia,Samir,Sarah}A = \{Sofia, Samir, Sarah\}
      • B is the courses the department offers
        • B={Maths,Java,Databases,Art}B = \{Maths, Java, Databases, Art\}
      • Let RR be a relation linking students in set AA to classes they are enrolled in: A student is related to the course if the student is enrolled in the course.
      • Examples:
        • Sofia is enrolled in Math and Java
        • Samir is enrolled in Java and Databases
        • Sarah is enrolled in Math and Art
        • Sofia is not enrolled in Art
      • Notations:
        • Sofia RR Maths
        • Sofia RR Java
        • Samir RR Java
        • Samir RR Databases
        • Sarah RR Maths
        • Sarah RR Art
        • Sofia \not R Art
  • Cartesian product
    • Let AA and BB be 2 sets.
    • The Cartesian product A x B is defined by a set of pairs (x, y) such that xAx \in A and yBy \in B
      • A x B={(x,y):xA and yB}A \ x \ B = \{(x, y): x \in A \text{ and } y \in B \}
    • For example:
      • A={a1,a2}A = \{ a_1, a_2 \} and B={b1,b2,b3}B = \{b_1, b_2, b_3\}
      • A x B={(a1,b1),(a1,b2),(a1,b3),(a2,b1),(a2,b2),(a2,b3)}A \ x \ B = \{(a_1, b_1), (a_1, b_2), (a_1, b_3), (a_2, b_1), (a_2, b_2), (a_2, b_3)\}
  • Definition of relation
    • Let AA and BB be two sets.
    • A binary relation from A to B is a subset of a Cartesian product A x BA \ x \ B
      • RA x BR \subseteq A \ x \ B means RR is a set of ordered pairs of the form (x, y) where xAx \in A and yBy \in B.
      • (x,y)R(x, y) \in R means x R yx \ R \ y (x is related to y)
    • For example:
      • A={a,b,c}A = \{a, b, c\} and B={1,2,3}B = \{1, 2, 3\}
      • The following is a relation defined from A to B:
        • R={(a,1),(b,2),(c,3)}R = \{(a, 1), (b, 2), (c, 3)\}
        • This means that: a R 1a\ R \ 1, b R 2b \ R \ 2 and c R 3c \ R \ 3
  • Relations on a set
    • When A = B
    • A relation R on the set A is a relation from A to A
      • RA x AR \subseteq A \ x \ A
    • We will be studying relations of this type.
    • Example
      • A = {1, 2, 3, 4}
      • Let R be a relation on the set A:
        • x,yAx, y \in A, x R yx \ R \ y if and only if x<yx < y
      • We have 1 R 2, 1 R 3, 1 R 4, 2 R 3, 2 R4, 3 R 4
      • R={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}R = \{(1,2), (1,3),(1,4), (2, 3), (2, 4), (3, 4)\}

9.105 Matrix and graph representatins of a relation

  • Relations using matrices
    • Given a relation R from a set A to set B.
    • List the elements of sets A and B in a particular order
    • Let na=An_a = |A| and nb=Bn_b = |B|
    • The matrix of R is an na x nbn_a \ \text{x} \ n_b matrix.
      • Mr=[mij]na x nbM_r = [m_{ij}] n_a \ x \ n_b
    • In matrix store a 1 if (ai,bj)R(a_i, b_j) \in R otherwise, 0
  • Example 1
    • Let A = {Sofia, Samir, Sarah}
    • Let B = {CS100, CS101, CS102, CS103}
    • Consider the relation of who is enrolled in which class
    • R = { (a,b) | person a is enrolled in course b }
CS100 CS101 CS102
Sofia x x
Samir x x
Sarah x x

Mr=[110011101] M_r = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{bmatrix}

  • Example 2
    • Let A = { 1, 2, 3, 4, 5 }
    • Consider a relation: <(x,y)R if and only if x<y< (x, y) \in R \text{ if and only if } x < y
    • Every element is not related to itself (hence the diagonal 0s).

Mr=[0111100111000110000100000] M_r = \begin{bmatrix} 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix}

  • Example 3
    • Let A = { 1, 2, 3, 4, 5 }
    • Consider a relation : (x,y)R\leq (x, y) \in R if and only if xyx \leq y
    • Note the diagonal is all 1s.

Mr=[1111101111001110001100001] M_r = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix}

  • Combining relations
    • Union
      • The Union of 2 relations is a new set that contains all of the pairs of elements that are in at least one of the two relations.
      • The union is written as R U SR \ U \ S or "R or S".
      • R U SR \ U \ S = { (a,b):(a,b)R(a, b): (a, b) \in R or (a,b)S(a, b) \in S }
    • Intersection
      • The intersection of 2 relations is a new set that contains all of the pairs that are in both sets.
      • The intersection is written as RSR \cap S or "R and S"
      • RSR \cap S = { (a,b):(a,b)R(a, b): (a, b) \in R and (a,b)S(a, b) \in S }
    • Combining relations: via Boolean operators
      • Let MR=[101100010]Ms=[101011100]M_{R} = \begin{bmatrix}1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \\ M_{s} = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{bmatrix}
      • Join MRS=MRMS=[101111110]M_{R \cup S} = M_R \vee M_S = \begin{bmatrix}1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 0\end{bmatrix}
      • Meet MRS=MRMS=[101000000]M_{R \cap S} = M_R \land M_S = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}
  • Representing relations using directed graphs
    • When a relation is defined on a set, we can represent with a digraph.
    • Building the digraph
      • First, the elements of A are written down,
      • When (a,b)R(a, b) \in R arrows are drawn from a to b.
    • Example 1
      • A = { 1, 2,3 ,4}
      • Let R be relation on A defined as follows:
        • R = { (x,y)(x, y) | x divides y}
        • R can be represented by this digraph
        • week-17-digraph-relation
          • Each value divides itself, hence the loop at each vertex.
          • One divides all other elements, so it has a link to each elements.
          • 2 only divides into 4
          • So on...
    • Example 2
      • Let A = { 1, 2, 3, 4, 5 }
      • Consider relation: (x,y)R\leq (x, y) \in R if and only if xyx \leq y
      • week-17-digraph-relation-example-2
        • Each element is equal to itself.
        • One is less than or equal to all elements.
        • 5 is greater than all elements except itself.
        • So on.

9.107 The properties of a relation: reflexive, symmetric and anti-symmetric

  • Reflexivity
    • A relation R in a set S is said to be reflexive if and only if x R xx \ R \ x, xS\forall x \in S
      • Or, for all x in the set, if the pairs (x, x) is in the relation, then it's reflexive.
    • Example 1 (reflexive example)
      • Let R be a relation of elements in Z:
        • R={(a,b)Z2ab}R = \{ (a, b) \in Z^2 | a \leq b \}
      • For all x elements of Z, we have xxx \leq x, hence x R xx \ R \ x
      • This implies that R is reflexive.
    • Example 2 (non-reflexive)
      • R={(a,b)Z2a<b}R = \{ (a, b) \in Z^2 | a \lt b \}
    • Digraph of reflexive relation
      • Every element will have a loop.
      • In this example, S = {1, 2, 3, 4} and R is a relation of elements S R={(a,b)S2ab}R = \{ (a, b) \in S^2 | a \leq b \} week-17-digraph-reflexive
    • Matrix of reflexive relation
      • Same example as above.
      • Note that all the values in the diagonal are 1. week-17-reflexive-matrix
  • Definition of Symmetry
    • A relation is said to be symmetric if and only if:
      • a,bS\forall a, b \in S, if a R ba \ R \ b then b R ab \ R \ a.
    • Proof: let a,bZa, b \in Z with a R ba \ R \ b:
      • a mod 2 = b mod 2
      • b mod 2 = a mod 2
      • b R a
    • R is symmetric
  • Diagram of a symmetric relation
  • Example
    • Let S = {1, 2, 3, 4} and R be relation of elements in S
      • R = { (a,b) \in S^2 | a mod 2 = b mod 2 } week-17-symmetric-relation-example
  • Matrix of symmetric relation
    • Example
      • Let S = {1, 2, 3, 4} and let R be relation of elements in S
        • R = { (a, b) \in S^2 | a mod 2 = b mod 2 }
      • MR=[1010010110100101]M_R = \begin{bmatrix}1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1\end{bmatrix}
  • Definition of anti-symmetric
    • A relation R on a set S is said to be anti-symmetric if and only if a,bS\forall a, b \in S, if a R ba \ R \ b and b R ab \ R \ a then a=ba = b
      • In other words, no 2 diff elements are related both ways.
    • Examples
      • Let R be a relation on elements in Z:
        • R={(a,b)Z2ab}R = \{ (a, b) \in Z^2 | a \leq b \}
      • Let a,bZa, b \in Z, a R ba \ R \ b and b R ab \ R \ a
        • aba \leq b and bab \leq a
        • a=ba = b
      • R is anti-symmetric
  • Digraph of anti-symmetric relation
    • Digraph contains no parallel edges between any 2 different vertices.
    • Example
      • Let S = {1, 2, 3, 4} and R be relation on elements in S
        • R={(a,b)S2 a divides b }R = \{ (a, b) \in S^2 | \text{ a divides b } \} week-17-anti-symmetric-graph
  • Matrix of an anti-symmetric relation week-17-matrix-of-anti-symmetric
  • Exercise
  • Let R be the relation defined by the Matrix M_r
    • Mr=[001111001]M_r = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}
  • Is R reflexive? Symmetric? Anti-symmetric?
  • Clearly R is not reflexive: m1,1=0m_{1,1} = 0
  • It is not symmetric because m2,1=1,m1,2=0m_{2,1}=1, m_{1, 2}=0
  • However, it is anti-symmetric.

9.109 Relation properties: transitivity

  • Definition of transitivty
    • A relation RR on a set S is called transitive if and only if:
      • a,b,cS\forall a, b, c \in S, if ($a \ R \ b$ and b R cb \ R \ c) then a R ca \ R \ c
  • Examples of transitive relations
    • R={(x,y)N2xy}R = \{ (x , y) \in N^{2} | x \leq y \}
      • It is transitive as x,y,zN\forall x, y, z \in \mathbf{N} if xyx \leq y and yzy \leq z then xzx \leq z
    • R = { (a, b) | a is an ancestor of b }
      • It is transitive because if a is an acestory of b and b is an ancestor of c, then a is an ancestor of c.
  • Example of non-transitive relations
    • R = { (2, 3), (3, 2), (2, 2) }
      • It is not transitive because 3 R 2 and 2 R 3 but 3 \not R 3
    • week-17-non-transitive-example
      • Not transitive as:
        • a R ca \ R \ c and b R cb \ R \ c, however a  ca \ \not R \ c
        • Also: b R cb \ R \ c and c R dc \ R \ d however b  db \ \not R \ d
    • What edges need to be added to make it transitive?
      • week-17-enhanced-digraph-for-transitive
        • The result enhanced relation is called the "transitive closure of the original relation"