GATE CSE 1997 | Question: 14

Question

Let $R$ be a reflexive and transitive relation on a set $A$. Define a new relation $E$ on $A$ as

$E=\{(a, b) \mid (a, b) \in R \text{ and } (b, a) \in R \}$

Prove that $E$ is an equivalence relation on $A$.

Define a relation $\leq$ on the equivalence classes of $E$ as $E_1 \leq E_2$ if $\exists a, b$ such that $a \in E_1, b \in E_2 \text{ and } (a, b) \in R$. Prove that $\leq$ is a partial order.

Comments

First Part: E is symmetric closure of R.

---

Let A={1,2,3}

R is a relation on set A which is reflexive and transitive.

R:{(1,1),(2,2),(3,3),(1,2)} → this relation is reflexive and transitive but not symmetric.

Now a new relation E has been defined on set A.

E = {(a, b) | (a, b) ∈ R and (b, a) ∈ R}

E:{(1,1),(2,2),(3,3)} → E will always be a identify relation on set A.

Identify relation is always reflexive, symmetric and transitive.

→ So, E is an equivalence relation on set A.

For second part:

There will be 3 equivalence classes E1, E2, E3.

H={E1,E2,E3}

a relation ≤ on the equivalence classes of E as E1≤E2 if ∃a,b such that a∈E1,b∈E2 and (a,b)∈R. 

E1={1} , E2={2}, E3={3}

∃1,2 such that 1∈E1, 2∈E2, and (1,2)∈R. So, E1≤E2

New relation will be reflexive :

→ ∃1,1 such that 1∈E1, 1∈E1, and (1,1)∈R. So, E1≤E1

→ ∃2,2 such that 2∈E2, 2∈E2, and (2,2)∈R. So, E2≤E2

→ ∃3,3 such that 3∈E3, 3∈E3, and (3,3)∈R. So, E3≤E3

New relation will be antisymmetric and transitive.

So, we can say new relation is a partial order. 

Answer 1

1. Since it is given that relation $R$ is reflexive and transitive, the new defined relation (definition of symmetric) is equivalence.
2. Partial order is a binary relation "≤" over a set $P$ which is reflexive, antisymmetric, and transitive.

• $a ≤ a$ (reflexivity);

• if $a ≤ b$ and $b ≤ a$, then $a = b$ (antisymmetry);

• if $a ≤ b$ and $b ≤ c$, then $a ≤ c$ (transitivity).

Comments

What are the equivalence classes of E here?

---

For proving symmetry in E,

Given that if(a,b)∈R and (b,a)∈R ,then (a,b)∈E.

Now let (a,b) and (b,a) both belong to R then we can include (a,b) and also (b,a) in E. How?

Because for (b,a) to be included in E the condition is (b,a)∈R and (a,b)∈R. We have already assumed that both are there in R.

So conclusion is if (a,b) and (b,a) both are in R then (a,b),(b,a) are in E which maintains symmetry.

Now suppose (a,b)∈ R and (b,a) ∉ R then (a,b) ∉ E.

Similarly (b,a) can't be there in E. 

Symmetric Relation E  means that "if" (a,b)∈E "then" (b,a)∈E.

p->q form where p: (a,b)∈E ; q: (b,a)∈E.

=> if (a,b)∉ E (p=False ) then p->q is (False implies anything is True) True which means symmetry is there.

So if (a,b) itself is not in in E then we don't need to check for (b,a) in E.

 

---

@MiNiPanda

Please correct me if I'm wrong here.

For the second part,

Say E1={a,b}

E2={c,d}

E3={e,f}

are the 3 equivalence classes.

For Reflexive: Clearly, E1$\leq$E1 so it is reflexive.

For anti-symmetry: if E1$\leq$E2 and E2$\leq$E1 then E1=E2.  This is true because we can't have E1$\leq$E2 if E1 and E2 are different equivalence classes in the first place. (Intersection of equivalence classes is NULL)

For transitivity: if E1$\leq$E2 and E2$\leq$E3 then E1$\leq$E3. This is also true because we can't have E1$\leq$E2 provided that they are different equivalence classes.

Hence the relation $\leq$ defined over equivalence classes is a poset. :)

Answer 2

Let's take R as:

R: {(1,1) (2,2) (3,3) (1,2) (2,1) (2,3) (1,3)} R is reflexive and transitive.

Now by the definition of E in the question,

E: {(1,1) (2,2) (3,3) (1,2) (2,1)}

Now, Diagonal elements are all present => E is reflexive

For symmetric, if every pair aRb, the pair bRa should be present. True.=> E is symmetric

For transitive, if pairs aRb and bRc are present, pair aRc should be present. True. =>E is transitive.

==>E is an equivalence relation.

Coming to the second part, the equivalence classes of E are:

[1] : {1,2} (let E1)

[2]:  {1,2} (let E2)

[3]:  {3}    (let E3)

  For the relation ≤ defined on equivalence classes of E,
For reflexivity, E1 ≤ E1
                          E2 ≤ E2
                and   E3 ≤ E3 should hold. For each of these we can find some "a∈E1,b∈E2 and (a,b)∈R" such that it holds.

eg. for E1 ≤ E1, a=1, b=1 and (1,1) ∈ R

For antisymmetric: E1 ≤ E2 and E2 ≤ E1 only if E1 = E2
We can see that E1 ≤ E2 and E2 ≤ E1 both hold and E1 and E2 are indeed equal. (Both equal {1,2}).

For transitivity, if E1 ≤ E2 and E2 ≤ E3 then E1 ≤ E3 should hold.
Here E1 ≤ E2 holds but E2 ≤ E3 does not, so we need not check for E2 ≤ E3. This makes the relation ≤ already transitive.

As the relation ≤ is reflexive, antisymmetric and transitive, it follows that it is a partial order.

Comments

@shashank did you got the answer for why transitivity isn’t applicable?

---

I think $ E2 \le E3 $  holds. 

[1] : {1,2} (let E1)

[2]:  {1,2} (let E2)

[3]:  {3}    (let E3)

$R: {(1,1),  (2,2) , (3,3) , (1,2) , (2,1) , (2,3),  (1,3)}$

$E1 \le E2 =  { (1, 1) , (1, 2), (2, 1), (2, 2) } $

for any $a \in E1 $ and for any $ b \in E2$, $(a, b) \in R$

$E2 \le E3 = (1,3), (2,3)$. Both these pairs belongs to R. 

For transitivity $E1  \le E3 $ should holds. 

$E1 \le E3 = {(1,3), (2,3) }$ which is same as $E2 \le E3$ and these pairs belongs to $R$. So transitivity holds. 

---

Perfect!

Answer 3

for part 1

Since it is given that relation R is reflexive and transitive but we can't say anything about symmetricity of R.In the worst case, R is not symmetric then relation E contains diagonal elements which leads to an equivalence relation.

Comments

Ans b. E1≤E2 if ∃a,b such that a∈E1,b∈E2 and (a,b)∈R says there must be some pair (a,b) such that it is not existing as a SYMMETRIC PAIR in R i.e. (b,a) not ∈R. Only then it is possible that (a,b) ∈R goes into two different equivalence classes of E. 

Simply,  if ∃a,b such that a∈E1,b∈E2 and (a,b)∈R THEN (b,a) not ∈R

---

please give example for (b) part

---

@s.abhishek1992 perfect explanation.

Answer 4

A brief intuitive explanation… using diagrams.

Comments

@HitechGa thank you for this. But I have some doubts. can you please draw in more descriptive and clearly. Thanks.