Question

Question 1. Equivalence Relation 1

Define a relation R on by iff .

1. Prove that R is an equivalence relation, that is, prove that it is reflexive, symmetric, and transitive.

2. Determine the equivalence classes of this relation.

   1. What members are in the class [2]?

   2. How many members do the equivalence classes have? Do they all have the same number of members?

   3. How many equivalence classes are there?

Question 2. Equivalence Relation 2

Consider the relation from last week defined as:

What are the equivalence classes of this relation? How many are there?

Question 3. Relation Proof

Disprove the following: if R and S are transitive relations, must be transitive.

Answer 1

1.R is a relation defined in R×T by (a,b)R(c,d) iff a−c is an integer and b=d.

Let (a,b)∈R×R

∴(a,b)R(a,b), because a−a=0∈Z and b=b

∴ R is reflexive.

Let (a,b)R(c,d).⇒a−c∈Z and b=d

⇒c−a∈Z and d=b

⇒(c,d)R(a,b)⇒R is symmetric.

Let (a,b)R(c,d) and (c,d)R(e,f).

⇒a−c∈Z,b=d,c−e∈Z,d=f

⇒(a−c)+(c−e)∈z,b=f

⇒a−e∈z,b=f⇒(a,b)R(e,f)

⇒R is transitive.

∴R is an equivalence relation.

2. This is an example.

Let A={0,1,2,3,,4} define a relation R on A as follows:

example:R={(0,0),(0,4),(1,1),(1,3),(2,2),(3,1),(3,3),(4,0),(4,4)}.R={(0,0),(0,4),(1,1),(1,3),(2,2),(3,1),(3,3),(4,0),(4,4)}.

Find the distinct equivalence classes of R

ans:The equivalence classes are {0,4},{1,3},{2}

• (0,4)∈R, so 0 and 4 are in the same class;
• (1,3)∈R, so 1 and 3 are in the same class;
• (2,2)∈R and 2 do not occur in any other pairs in R, so 2 is in a class by itself.

3. let A={a,b,c}

then R={(a,a),(a,b),(b,a),(b,b)}

and S={(b,b),(b,c),(c,b),(c,c)} be transitive

Now, (a,b)∈R∪S

Also,(b,c)∈R∪S

But (a,c)∈/S∪S

∴R∪S is not transitive.