The Gateway to Computer Science Excellence
+11 votes
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.
in Set Theory & Algebra by Veteran (52.2k points)
edited by | 944 views
First Part: E is symmetric closure of R.

3 Answers

+6 votes
Best answer

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

by Boss (11.1k points)
edited by

@Rajesh Pradhan


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.

Please clear this doubt.


reflexive and transitive does nt mean symmetric ... 

please explain (b) part with example
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.




Please correct me if I'm wrong here.

For the second part,

Say E1={a,b}



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

+2 votes

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.

by Loyal (8k points)
edited by

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.

+1 vote

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

by Active (3.9k points)
edited by
E will not contain (1,2),(2,1). As they are not present in R.


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

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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,313 answers
105,048 users