The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+8 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.
asked in Set Theory & Algebra by Veteran (59.5k points)
edited by | 490 views

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

answered 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?
+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.

answered by Loyal (6.7k 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

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

39,750 questions
46,765 answers
58,515 users