Proving a statement about equivalence relations.

51 Views Asked by At

enter image description here

Am I doing it correctly? I am not sure about my notations and the way I explain things as this topic is very new to me..

Question 3

a. True

$E_{1}∩E_{2}$

Reflexive:

Since $E_{1}$ is an equivalent relation on A then for every $a ∈ A \ \ (a,a) ∈ E_{1}$.

Since $E_{2}$ is an equivalent relation on A then for every $a ∈ A \ \ (a,a) ∈ E_{2}$.

We can conclude that all elements of $E_{1}∩E_{2}$ are reflexive.

Therefore for every $a ∈ A \ \ (a,a) ∈ E_{1}∩E_{2}$.

Symmetric:

Since $E_{1}$ is an equivalent relation on A then for every $a,b ∈ A$ if $(a,b) ∈ E_{2}$, then $(b,a) ∈ E_{1}$.

Since $E_{2}$ is an equivalent relation on A then for every $a,b ∈ A$ if $(a,b) ∈ E_{2}$, then $(b,a) ∈ E_{2}$.

We can conclude that all elements of $E_{1}∩E_{2}$ are symmetric.

Therefore for every every $a,b ∈ A$ if $(a,b) ∈ E_{1}∩E_{2}$, then $(b,a) ∈ E_{1}∩E_{2}$.

Transitive:

Since $E_{1}$ is an equivalent relation on A then for every $a,b,c ∈ A$ if $(a,b),(b,c) ∈ E_{1}$, then $(a,c) ∈ E_{1}$.

Since $E_{2}$ is an equivalent relation on A then for every $a,b,c ∈ A$ if $(a,b),(b,c) ∈ E_{2}$, then $(a,c) ∈ E_{2}$.

We can conclude that all elements of $E_{1}∩E_{2}$ are transitive.

Therefore for every every $a,b,c ∈ A$ if $(a,b),(b,c) ∈ E_{1}∩E_{2}$, then $(a,c) ∈ E_{1}∩E_{2}$.

b. False.

$E_{1}∪E_{2}$

Counter example:

Let $A = \left\{1,2,3\right\}$

$E_{1} = \left\{\left(1,1\right),\left(1,2\right),\left(2,1\right),\left(2,2\right),\left(3,3\right)\right\}$

$E_{2} = \left\{\left(2,2\right),\left(2,3\right),\left(3,2\right),\left(3,3\right),\left(1,1\right)\right\}$.

Then $E_{1}∪E_{2} = \left\{\left(1,2\right),\left(2,1\right),\left(2,2\right),\left(2,3\right),\left(3,2\right),\left(3,3\right),\left(1,1\right)\right\}$

We can easily notice that $1R2 ∧ 2R3$, but $1R3$ is not part of the relation, which means the relation is not transitive, and therefore not an equivalence relation.