2
$\begingroup$

Let R be a relation defined by the condition aRba$R_1$ba$R_2$b where $R_1$ and $R_2$ are equivalence relations on a set A. Prove that R is an equivalence relation on A.

Could I just assume that since $R_1$ and $R_2$ are equivalence relations, then they are both reflexive, symmetric, and transitive, therefore the bicondition a$R_1$ba$R_2$b is true and I only need to prove that aRb is reflexive, symmetric, and transitive to prove that R is an equivalence relation.

$\endgroup$
  • 2
    $\begingroup$ "Could I just assume that since $R_1$ and $R_2$ are equivalence relations, then they are both reflexive, symmetric, and transitive, therefore I only need to prove that $R$ is reflexive, symmetric, and transitive to prove that $R$ is an equivalence relation ?" YES $\endgroup$ – Mauro ALLEGRANZA Nov 8 at 14:47
  • 1
    $\begingroup$ You need the bi-conditional, because it is the definition of $R$. $\endgroup$ – Mauro ALLEGRANZA Nov 8 at 14:48
2
$\begingroup$

You seem to believe that you have to prove that aRb is true using the fact that aRb is true iff aR1b & aR2b.

Proving " aRb" for all a, b belonging to A would amount to proving that the relation R is the cartesian product " A cross A", which is not what you have to show.

Your job is to use " aRb <--> aR1b & aR2b " in order to prove that R actually has the 3 properties that define an equivalence relation on A , namely :

(1) for all x belonging to A, the pair (x,x) belongs to R.

(2) for all x, y belonging to A, IF (x,y) belongs to R, THEN (y,x) belongs to R.

(3) for all, x,y,z belonging to A , IF (x,y) and (y,z) belong to R, THEN (x,z) also belongs to R.

Rk. - Using " aRb <--> aR1b & aR2b" requires you

(a) to analyze it as the conjunction of two conditonals:

( aRb --> aR1b & aR2b ) AND ( aR1b & aR2b --> aRb)

(b) ( in proving reflexivity) to transform the second conjunct using contraposition in order to get : ~ aRb --> ~ ( aR1b & aR2b)

(c) ( still in proving reflexivity) to transform this last result, using DeMorgan's law , in order to get :

~ aRb --> ~ aR1b OR ~ aR2b

In order to prove (1) an indirect proof can be used.

In order to prove (2) and (3) , since they are " IF...THEN" statements, suppose that the 'IF part" is realized and show that , in such a situation, the "THEN part " would actually follow.


What is to be proved is that R is an equivalence relation on a set A , that is :

(1) for all x belonging to A, (x,x) belongs to R

(2) if (x,y) belongs to R , then (y,x) belongs to S

(3) if (x,y) and (y,z) belong to R , then (x,z) belongs to R.

(1) Suppose ( in view of refutation) there is some x belonging to A such that (x,x) does not belong to R ( in other words , SUPPOSE that R is NOT reflexive) . It would mean that : (xR1x & xR2x) is false. By DeMorgan’s law, it would imply that xR1x is false OR xR2x is false for some x belonging to A. But neither can be false , since both R1 and R2 are equivalence relations on A, and, therefore, reflexive relations on A ( which means that : for all x belonging to A, both xR1x and xR2 x are true) . Consequently, for all x, (x,x) belongs to R, in other words : R is reflexive on A.

(2) Suppose that : (x,y) belongs to R ( with x and y belonging to A). By definition, it means that (x,y) belongs to R1 and to R2. Since both R1 and R2 are equivalence relations, and therefore symmetric relations, this implies that : (y,x) belongs to R1 and to R2. But belonging both to R1 and R2 is a sufficient condition to belong to R ( if one reads the biconditional that defines R from left to right). . So (y,x) belongs to R. That proves that : R is a symmetric relation on A .

(3) Suppose that (x,y) and (y,z) belong to R. That means that : (x,y) belongs to R1 and to R2; and that (y,z) belongs to R1 and to R2. Since (x,y) and (y,z) belong to R1, (x,z) belongs to R1 ( R1 being an equivalence relation on A , and therefore a transitive relation on A). Since (x,y) and (y,z) belong to R2, (x,z) belongs to R2 ( R2 being an equivalence relation on A , and therefore a transitive relation on A). Now, the fact that (x,z) belongs both to R1 and R2 is a sufficient condition for (x,y) to belong to R. This proves that : R is a transitive relation on A.

$\endgroup$
0
$\begingroup$

A different approach.

For any non-empty $A,$ a partition of $A$ is a family $F$ of pair-wise disjoint subsets of $A$ such that $\cup F=A.$ That is, each $a\in A$ belongs to exactly one member of $F.$

Given a partition $F$ of $A,$ for $a,b\in A$ let $a\sim_F b$ iff $a,b$ belong to the same member of $F.$ It is easy to see that $\sim_F$ is an equivalence relation on $A.$

Given an equivalence relation $\sim$ on $A,$ the set of $\sim$-equivalence classes is $F=A_{/\sim}=\{[a]_{\sim}: a\in A\},$ where $[a]_{\sim}=\{b: a\sim b\}.$ It is easy to see that $F$ is a partition of $A$ and that $\sim_F,$ as defined above, is $\sim.$

It is also easy to see that if $F_1, F_2$ are partitions of $A$ then $\{f_1\cap f_2:f_1\in F_1\land f_2\in F_2\}$ is a partition of $A.$

Given equivalence relations $R_1, R_2$ on $A,$ let $F_i=A_{/R_i}$ for $i\in \{1,2\}$ and let $F=\{f_1\cap f_2: f_1\in F_1\land f_2\in F_2\}.$

Then we have $$aRb\iff$$ $$\iff (aR_1b\land aR_2b)\iff$$ $$\iff \exists f_1\in F_1\,\exists f_2\in F_2 \,(\{a,b\}\subset f_1\cap f_2)\iff$$ $$\iff \exists f\in F \, (\{a,b\}\subset f)\iff$$ $$\iff a\sim_F b. $$

So $R$ is identical to the equivalence relation $\sim_F.$

Remark. Some authors, for convenience, assume $\emptyset \not \in F$ when $A\ne \emptyset$ and $F$ is a partition of $A.$ For my convenience I have not made that assumption.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.