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

answered by Boss (11k points)
edited by
0

@Rajesh Pradhan

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

Please clear this doubt.

+2

reflexive and transitive does nt mean symmetric ... 

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.

 

+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 (7k points)
edited by
+2

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



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

42,658 questions
48,639 answers
156,224 comments
63,953 users