The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+9 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.1k points)
edited by | 728 views
First Part: E is symmetric closure of R.

2 Answers

+5 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 (10.9k 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.


+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 (7.5k 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.

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
49,845 questions
54,764 answers
80,274 users