# Set relation with a biconditional definition.

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.

• "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 – Mauro ALLEGRANZA Nov 8 at 14:47
• You need the bi-conditional, because it is the definition of $R$. – Mauro ALLEGRANZA Nov 8 at 14:48

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.

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.