edited by
3,807 views
19 votes
19 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.
edited by

4 Answers

Best answer
7 votes
7 votes
  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.
edited by
6 votes
6 votes

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.

edited by
2 votes
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.

edited by
1 votes
1 votes

A brief intuitive explanation… using diagrams.

Related questions

54 votes
54 votes
6 answers
1
Kathleen asked Sep 29, 2014
21,138 views
The number of equivalence relations of the set $\{1,2,3,4\}$ is$15$$16$$24$$4$
42 votes
42 votes
2 answers
4