Week 18 - Relations B

9.201 Equivalence relations and equivalence classes

  • Definition of Equivalence Relation
    • Let R be a relation of elements on a set S. R is an equivalence relation if and only if R is reflexive, symmetric and transitive.
  • Example 1
    • Let R be relation of elements in Z:
      • R={(a,b)Z2amod2=bmod2}R = \{ (a, b) \in Z^2 | a \mod 2 = b \mod 2 \}
    • We have already proved that this relation is:
      • Reflexive as a Ra,aZR a, \in a \forall Z
      • Symmetric as if a R b then b R a, \forall a, b \in Z
      • Transitive as if a R b and b R c then a R c, \forall a, b, c \in Z
      • This is an equivalence relationship.
  • Example 2
    • Let R be a relation of elements in Z:
      • R={(a,b)Z2ab}R = \{ (a, b) \in Z^2 | a \leq b \}
      • Already proved relationship is :
        • Reflex as a R a for all a in Z
        • Transitive as if a R ba \ R \ b and b R cb \ R \ c then a R ca \ R \ c, a,b,cZ\forall a, b, c \in Z
        • Not symmetric as 232 \leq 3 but 32,a,bZ3 \not \lt 2, \forall a, b \in Z
      • This is not equivalence.
  • Definition of Equivalence Class
    • Let R be an equivalence relation on a set S. Then, the equivalence class of a \in S is:
      • a subset of S containing all the elements related to a through R.
      • a={x:xS and x R a}|a| = \{x: x \in S \text { and } x \ R \ a\}
  • Example 1
    • Let S={1,2,3,4}S = \{1, 2, 3, 4\} and R be a relation on elements in S:
      • R={(a,b)S2amod2=bmod2}R = \{ (a, b) \in S^2 | a \mod 2 = b \mod 2 \}
    • R is an equivalence relation with 2 equivalence classes:
      • `[1] = [3] = {1, 3}
      • [2] = [4] == {2, 4}
  • Example 2
    • Let Z={1,2,3,4,5}Z = \{1, 2, 3, 4, 5\} and R be relation of elements in Z:
      • R={(a,b)Z2ab is an even number }R = \{ (a, b) \in Z^2 | a - b \text{ is an even number } \}
    • R = { (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (2, 4), (4, 2), (1, 3), (3, 1), (1, 5), (5, 1), (3, 5), (5, 3) }
    • R is an equivalence relation with 2 equivalence classe:
      • [1] = [3] = [5] = {1, 3, 5}
      • [2] = [4] = {2, 4}

9.203 Partial and total order

  • Definition of a Partial Order.
    • Let RR be a relation on elements in set SS. RR is a partial order if and only if RR is:
      • reflexive
      • anti-symmetric
      • transitive.
    • Example 1
      • Let R be a relation of elements in Z:
        • R={(a,b)Z2ab}R = \{ (a, b) \in Z^2 | a \leq b \}
      • It can easily be proved that R is:
        • reflexive as aaa \leq a, aZ\forall a \in Z
        • transitive as if aba \leq b and bcb \leq c then aca \leq c, a,bZ\forall a, b \in Z
        • anti-symmetric as if aba \leq b and bab \leq a then a=ba = b, a,bZ\forall a, b \in Z
      • Therefore, R is a partial order.
    • Example 2
      • Let RR be a relation of elements in Z+:
        • R={(a,b)Z+a divides b}R = \{ (a, b) \in Z+ | a \text{ divides } b \}
      • It can easily be proven that R is:
        • reflexitive as a divides a,aZ+a, \forall a \in Z+
        • transitive as if a divides ba \text{ divides } b and b divides cb \text{ divides } c then a divides ca \text{ divides } c, a,b,cZ+\forall a, b ,c \in Z+
        • anti-symmetric as if a divides ba \text{ divides } b and b divides ab \text{ divides } a then a=ba = b, a,bZ+\forall a, b \in Z+
      • Therefore, R is a partial order.
  • Definition of a Total Order
    • Let R be a relation on elements in a set S.
    • R is a total order if and only if:
      • R is a partial order
      • a,bS\forall a,b \in S we have either a R ba \ R \ b or b R ab \ R \ a.
    • Example 1
      • Let R be a relation of elements in Z:
        • R={(a,b)Z2ab}R = \{ (a, b) \in Z^2 | a \leq b \}
      • It has been shown that R is a partial order.
      • Also, a,bZ\forall a, b \in Z, aba \leq b or bab \leq a is true.
    • Example 2
      • Let R be a relation on elements in Z+:
        • R={(a,b)Z+a divides b}R = \{ (a, b) \in Z+ | a \text{ divides } b \}
      • We proved R is a partial order
      • However, Z* contains elements that are incomparable, such as 5 and 7.
      • R is not totally ordered.

Peer-graded Assignment: 9.207 Relations

Question

Let R be a relation on ZZ given by x R yx \ R \ y if and only if x2y2x^2 - y^2 is divisible by 3. Show that this relation is an equivalence relation and find its corresponding equivalence classes.

Answer

To prove x R yx \ R \ y has an equivalence relationship, we must show it's reflexive, symmetric and transitive.

We know it's reflexive, because for any integer x2x2=0x^2 - x^2 = 0, which is divisible by 3.

We know it's symmetric, because y2x2=(x2y2)y^2 - x^2 = -(x^2 - y^2). If x2y2x^2 - y^2 is divisible by three, (x2y2)-(x^2-y^2) is also divisible by three.

When know it's transitive, where x R yx \ R \ y and y R zy \ R \ z therefore x R yx \ R \ y, because we know (x2y2)+(y2z2)=x2z2(x^2 - y^2) + (y^2 - z^2) = x^2 - z^2, so when x2y2x^2 - y^2 and y2z2y^2 - z^2 are both divisible by 3, x2z2x^2 - z^2 will also be divisible by 3.


To find the corresponding equivalence classes, we must find all integers related to a given xx.

Suppose yy is related to xx, then x2y3x^2 - y^3 is divisible by 3. That means that all means they have the same residual mod 3.

There are 3 residual mods possible: 0, 1, 2.

Therefore we can assign the integers into these equivalence classes:

  • 0={...,6,3,0,3,6,...}0 = \{..., -6, -3, 0, 3, 6, ...\}
  • 1={...,5,2,1,4,7,...}1 = \{..., -5, -2, 1, 4, 7, ...\}
  • 2={...,4,1,2,5,8,...}2 = \{..., -4, -1, 2, 5, 8, ...\}

However, 1 and 2 are the same. So it's only 2 equivalence classes.

Peer Review

Question 1

1. Reflexive

RR is reflexive if xS\forall x \in S, x R xx \ R \ x

Example: Equality is reflexive, but < is not reflexive.

2. Symmetric

RR is symmetric if x,yS\forall x, y \in S, if x R yx \ R \ y then y R xy \ R\ x.

Example: a marriage is symmetric, but is parent of is not symmetric.

3. Anti-symmetric

RR is anti-symmetric if x,yS\forall x, y \in S, if (x R y(x \ R \ y and y R x)y \ R \ x) then x = y

Example: * subset ($\subseteq$) is antisymmetric relation. If x is a subset of y, and y is a subset of x, then by definition x = y. * an ancestor. If x is an ancestor or y, and y is an ancestor of y, they must be the same person.

Counterexample: * marriage from above. a husband is related to his wife, the wife is related to the husband, but they are not the same.

4. Transitive

RR is transitive if x,y,zS\forall x, y, z \in S, if x R yx\ R \ y and y R zy \ R \ z then x R zx \ R \ z

Example: is in immediate family is transitive, is a parent is not.

5. An equivalence relation.

RR is an equivalence relation if it is reflexive, symmetric and transitive.

Example: * is equal to on the set of real number is an equivalence relation. * is less or equal ($\leq$) is not equivalence relation.

6. A partial order.

RR is a partial order if it is reflexive, antisymmetric and transitive

Example:

The relationship divides on the set of positive integers (natural numbers N\mathbf{N}), is reflexive, antisymmetric and transitive. But the same relation applied to the set of integers Z\mathbf{Z} is not antisymmetric since 22-2 | 2 and 222 | -2 but 22-2 \neq 2

Question 2

Let S={a,b,c}S = \{a, b, c\} and A={(c,c),(a,b),(b,b),(b,c),(c,b)}A = \{(c, c), (a, b), (b, b), (b, c), (c, b)\}

Define a relation RR on SS by "$x$ is related to yy whenever (x,y)A(x, y) \in A"

  1. Draw the relationship digraph
  2. The relationship RR is not reflexive. What pair (x, y) should be added to AA to make RR refexive?

(a, a)

Correct

  1. The relationship RR is not symmetric. What pair (x, y) should be added to A to make R symmetric?

(b, a)

Correct

  1. The relation R is not anti-symmetric. What pair (x, y) should be removed to make R anti-symmetric?

(b, c) or (c, b)

Right now b R c and c R b but b != c

Correct

  1. The relation R is not transitive. What pair (x, y) should be added to A to make R transitive?

(a, c)

Correct

Question 3

The following relations are defined on a set S = {a, b, c}

R1R_1 is the relation given by {(a,a),(a,b),(a,c),(b,a),(b,b),(c,a),(c,c)}\{(a, a), (a, b), (a, c), (b, a), (b, b), (c, a), (c, c)\} R2R_2 is given by {(a,a),(a,b),(b,a),(b,b),(c,c)}\{(a, a), (a, b), (b, a), (b, b), (c, c)\} R3R_3 is given by {(a,b),(a,c),(b,a),(b,c),(c,a),(c,b)}\{(a, b), (a, c), (b, a), (b, c), (c, a), (c, b)\} R4R_4 is given by {(a,a),(a,b),(a,c),(b,b),(b,c),(c,c)}\{(a, a), (a, b), (a, c), (b,b), (b, c), (c, c)\}

Reflexive Symmetric Antisymmetric Transitive Equivalence Relation Partial Order
R_1 Y Y N N N N
R_2 Y Y N Y Y N
R_3 N Y N N Y N
R_4 Y N Y Y N Y

Note, that R2R_2 is considered transitive. We have (a, b) and (b, a) therefore we need (a, a) which we have. R3R_3 is not considered transtive. We have (a, b) and (b, a) therefore we need (a, a) to be transitive, which is missing.

R2R_2 is the only equivalence relation. a related to b c related to c only.

So there are T={[a],[c]}T = \{[a], [c]\} equivalence classes.

Question 4

Let S={1,2,3,4,5,6,7,8,9}S = \{1, 2, 3, 4, 5, 6, 7, 8, 9\} and let P be the partition on S given by = {{1,4,7},{2,5,8},{3,6,9}}\{ \{1, 4, 7\}, \{2, 5, 8\}, \{3, 6, 9\}\}

Define RR to be the equivalence relation associated to PP.

  1. Give 2 conditions for PP to be a partition.

  2. Let P1...PNP_1 ... P_N be the subsets of PP. P is a partition as each subset , P1P2P3=PP_1 \cup P_2 \cup P_3 = P

  3. We also know that PP is a partition as P1P2P3=P_1 \cap P_2 \cap P_3 = \emptyset

  4. Draw the relationship digraph.

On paper. It's 3 disjointed graphs.

  1. Write down the equivalence class [5] as a set.

Apparently it's {2, 5, 8}

So the equivalence class refers to the elements that are in the same class?

Question 5

Let S=Z x N+S = \mathbb{Z} \ x \ \mathbb{N}^{+} and let R\mathbb{R} be a relation on S defined as follows:

(a,b) R (c,d)(a, b) \ R \ (c, d) whenever ad=bcad = bc

Show that RR is an equivalence relation.

  • R is reflexive. As (a,b)S\forall (a, b) \in S, (a,b) R (a,b)(a, b) \ R \ (a, b)
  • R is symmetric as (a,b),(c,d)S\forall(a, b), (c, d) \in S if (a,b) R (c,d)(a, b) \ R \ (c, d) then ad = bc AND cb = da then (c,d)R(a,b)(c, d) R (a, b)
  • R is transitive as (a,b),(c,d),(e,f)S\forall (a, b), (c, d), (e, f) \in S. (a,b) R (c,d)(a, b) \ R \ (c, d) and (c,d) R (e,f)(c, d) \ R \ (e, f) => ad = bc and cf = de => cbde = dacf => be = af => (a,b) R (e,f)(a, b) \ R \ (e, f)

Define the equivalence class generated by (a,b)(a, b) for aZa \in \mathbb{Z} and bN+b \in \mathbb{N}^{+}

[(a,b)]={(m,n):(a,b)Z x N+ and ab=mn}[(a, b)] = \{ (m, n): (a, b) \in \mathbb{Z} \ x \ \mathbb{N}^{+} \text{ and } \frac{a}{b} = \frac{m}{n} \}

Question 6

Let A and B be two sets where:

A={ France , Germany , Switzerland , England , Morocco }A = \{ \text{ France }, \text{ Germany }, \text{ Switzerland }, \text{ England }, \text{ Morocco } \} and

B={ French , German , English , Arabic }B = \{ \text{ French }, \text{ German }, \text{ English }, \text{ Arabic } \}.

Let R be a relation defined from A to B, given by a R ba \ R \ b when b is a national language of a.

The national language of each of the countries is as follows:

  • French for France
  • German for Germany
  • English for England
  • Arabic for Morocco
  • Switzerland has 2 national languages, French and German.

Find the logical matrix for the relation R.

French Germany English Arabic
French 1 0 0 0
Germany 0 1 0 0
England 0 0 1 0
Morocco 0 0 0 1
Switzerland 1 1 0 0

Question 7

For each of the following relations on the set of all people, state if it is an equivalence relation. Explain your answer.

  1. R_1 = { (x, y) | x and y are the same height }

R_1 is flexive as every xx is the same height as itself, or: x R xx \ R \ x R_1 is symmetic as x,yS\forall x, y \in S if x R yx \ R \ y then y R xy \ R \ x R_1 is transitive as x,y,zS\forall x, y, z \in S if x R yx \ R \ y and x R zx \ R \ z then x R zx \ R \ z

Therefore, this is an Equivalence Relationship.

Correct

  1. R_2 = { (x, y) | x and y have, at some point, lived in the same country. }

R_2 is reflexive as x R xx \ R \ x. xx lives in the same country as itself. R_2 is symmetric as x,yS\forall x, y \in S if x R yx \ R \ y ie x and y where in the same country, then y R xy \ R \ x, as again, they must be in the same country. R_2 is NOT transitive. If x, y both lived in Australia, and y, z both lived in Malaysia, it does not imply x lived in the same country.

Therefore, it is NOT an Equivalence Relationship.

Correct

  1. R_3 = { (x, y) | x and y have the same first name }

R3R_3 is reflexive. R3R_3 is symmetric. R3R_3 is transitive.

Therefore, R3R_3 is an equivalence relationship.

  1. R_4 = { (x, y) | x is taller than y }

R_4 is not reflexive as x is not taller than x.

Therefore, it it not an equivalence relationship.

  1. R_5 = { (x, y) | x and y have the same colour hair }

R_5 is reflexive. x R x R_5 is symmetric. x R y and y R x R_5 is transitive. x R y and y R z therefore x R y

Therefore, it is an equivalence relationship.

Question 8

Let S = { {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}, {1, 2, 3, 4, 5}}

X is related to Y whenever XYX \subseteq Y

  1. Draw the relationship digraph.

week-18-problem-sheet-relationship-bigraph

  1. Determine whether or not RR is reflexive, symmetric, antisymmetric or transitive. Give a brief justification for each of your answers.

  2. R is reflexive as x R xx \ R \ x, for example {1}{1}\{1\} \subseteq \{1\}

  3. R is NOT symmetric. if x R yx \ R \ y then y R xy \ R \ x is NOT true. For example, {1}{1,2},{2,1}{1,2}\{1\} \subseteq \{1, 2\}, \{2, 1\} \subseteq \{1, 2\}
  4. R is anti-symmetric. if x R yx \ R \ y and y R xy \ R \ x then x=yx = y.
  5. R is transitive. If x R yx \ R \ y and y R zy \ R \ z, then x R zx \ R \ z

  6. State, with reasons, whether or not RR is an equivalence relation, whether or not it is a partial order and whether or not it is a total order.

R is not an equivalence relation as it is NOT symmetric. R is a partial order as it is reflexive, anti-symmetric and transitive. R is a total order, as it is a partial order and every 2 elements are comparable. a,bS\forall a,b \in S we have either a R ba \ R \ b or b R ab \ R \ a.

Question 9

Let S=a,b,c,dS = {a, b, c, d} and let AS x SA \subseteq S \ x \ S be given by:

{(a,a),(a,c),(b,b),(b,d),(c,a),(c,c),(d,b),(d,d)}\{ (a, a), (a, c), (b, b), (b, d), (c, a), (c, c), (d, b), (d, d) \}

A relation RR on SS is defined by:

xx is related to yy whenever (x,y)A(x, y) \in A

  1. Draw the relationship digraph

week-18-problem-sheet-q9-digraph

  1. Determine whether or not RR is reflexive, symmetric, antisymmetric or transitive. Give brief justification of each answer.

  2. RR is reflexive as xS\forall x \in S, x R xx \ R \ x

  3. RR is symmetric as x,yS\forall x, y \in S, if x R yx \ R \ y then y R zy \ R \ z
  4. RR is NOT anti-symmetric as x,yS\forall x, y \in S, if x R yx \ R \ y and y R xy \ R \ x, it DOES NOT imply x=yx = y
  5. RR is transitive. x,y,zS\forall x, y, z \in S, if x R yx \ R \ y and y R zy \ R \ z, then x R zx \ R \ z

RR is a equivalence relationship as it is reflexive, symettric and transitive. RR is not a partial order as it is NOT anti-symmetric. RR is not a total order as it is NOT a partial order.

Question 10

Let RR be a relation from a set AA to a set BB. The inverse of RR, denoted R1R^{-1}, is the relation from BB to AA defined by R1={(y,x):(x,y)R}R^{-1} = \{ (y, x) : (x, y) \in R \}

Given a relation RR from A={2,3,4}A = \{ 2, 3, 4 \} to B={3,4,5,6,7}B = \{ 3, 4, 5, 6, 7 \} defined by (x,y)R(x, y) \in R if xx divides yy.

Elements: (2, 4), (2, 6), (3, 3), (3, 6), (4, 4)

MrM_r of RR

3 4 5 6 7
2 0 1 0 1 0
3 1 0 0 1 0
4 0 1 0 0 0

Elements R1R^{-1}: (4, 2), ( 6, 2), (3, 3), (6, 3), (4, 4)

2 3 4
3 0 1 0
4 1 0 1
5 0 0 0
6 1 1 0
7 0 0 0

Question 11

Let R1R_1 and R2R_2 be the relations on a set S={1,2,3,4}S = \{1, 2, 3, 4\} given by:

R1={(1,1),(1,2),(3,4),(4,2),(2,4)}R_1 = \{ (1, 1), (1, 2), (3, 4), (4, 2), (2, 4) \} R2={(1,1),(3,2),(4,4),(2,2),(4,2)}R_2 = \{(1, 1), (3, 2), (4, 4), (2, 2), (4, 2)\}

  1. Find the matrix representation R1R_1 and that of R2R_2.

MR1MR_1

1 2 3 4
1 1 1 0 0
2 0 0 0 1
3 0 0 0 1
4 0 1 0 0

MR2MR_2

1 2 3 4
1 1 0 0 0
2 0 1 0 0
3 0 1 0 0
4 0 1 0 1
  1. Find the matrix of the intersection of both matrices in (1).
1 2 3 4
1 1 0 0 0
2 0 0 0 0
3 0 0 0 0
4 0 1 0 0
  1. Find the matrix of the union of both matrices in (1).
1 2 3 4
1 1 1 0 0
2 0 1 0 1
3 0 1 0 1
4 0 1 0 1
  1. List the elements of R1R2R_1 \cap R_2

R1R2={(1,1),(4,2)}R_1 \cup R_2 = \{ (1, 1), (4, 2) \}

  1. List the elemnts of R1R2R_1 \cup R_2

R1R2={(1,1),(1,2),(2,2),(2,4)(3,2),(3,4),(4,2),(4,4)}R_1 \cup R_2 = \{ (1, 1), (1, 2), (2, 2), (2, 4) (3, 2), (3, 4), (4, 2), (4, 4) \}

Question 12

Let RR be a relation on set AA.

  1. How can we quickly determine whether a relation R is reflexive by examining the matrix of RR?
  2. How can we quickly determine whether a relation R is symmetrix by examining the matrix of R?
  3. How can we quickly determiner whether a relation R is anti-symmetric by examining the matrix of R?