# GATE1997-14

1.6k views
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.

edited
1
First Part: E is symmetric closure of R.

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 reflexiveantisymmetric, and transitive

edited
0

@asu

but the definition of symmetric is :-

${ (a,b) \in R \rightarrow (b,a) \in R}$

Moreover if A = {1,2}

Relation R = {(1,2)} is symmetric, but according to above definition it is not.

0
please explain (b) part with example
0
What are the equivalence classes of E here?
0

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.

0

@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. :)

Let's take 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,2} (let E1)

:  {1,2} (let E2)

:  {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.

edited
0
E will not contain (1,2),(2,1). As they are not present in R.

Right?
0
Corrected.
0

Every element x of X is a member of the equivalence class [x]. Every two equivalence classes [x] and [y] are either equal or disjoint.

your $E_1$ and $E_2$ are not disjoint sets

https://en.wikipedia.org/wiki/Equivalence_class#Properties

0
"Either EQUAL or disjoint". They are not disjoint but thet're equal.
0
ok thanks for pointing out
0

For transitivity,

Why E2 ≤ E3 does not holds?

for a=2, b=3,  2 ∈ E2 , 3 ∈ E3 and (2, 3) ∈ R, so E2 ≤ E3 holds.

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.

edited
5

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

0
please give example for (b) part
0

@s.abhishek1992 perfect explanation.

## Related questions

1
11.9k views
The number of equivalence relations of the set $\{1,2,3,4\}$ is $15$ $16$ $24$ $4$
Let $F$ be the set of one-to-one functions from the set $\{1, 2, \dots, n\}$ to the set $\{1, 2,\dots, m\}$ where $m\geq n\geq1$. How many functions are members of $F$? How many functions $f$ in $F$ satisfy the property $f(i)=1$ for some $i, 1\leq i \leq n$? How many functions $f$ in $F$ satisfy the property $f(i)<f(j)$ for all $i,j \ \ 1\leq i \leq j \leq n$?
A partial order $≤$ is defined on the set $S=\left \{ x, a_1, a_2, \ldots, a_n, y \right \}$ as $x$ $\leq _{i}$ $a_{i}$ for all $i$ and $a_{i}\leq y$ for all $i$, where $n ≥ 1$. The number of total orders on the set S which contain the partial order $≤$ is $n!$ $n+2$ $n$ $1$
A polynomial $p(x)$ is such that $p(0) = 5, p(1) = 4, p(2) = 9$ and $p(3) = 20$. The minimum degree it should have is $1$ $2$ $3$ $4$