The Gateway to Computer Science Excellence
+11 votes
944 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.
in Set Theory & Algebra by Veteran (52.2k points)
edited by | 944 views
+1
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
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.

 

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

+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
+3

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.

+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
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

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
198,349 comments
105,048 users