Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Let R be a relation defined by the condition aRb ↔ a$R_1$b ∧ a$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$b ∧ a$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.
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.
