While I fully understand what it means to be an equivalence relation, I have a difficulty establishing proof that $R$ is an equivalence relation without just listing all pairs that $R$ creates and testing them.

However this method is greatly time consuming and is not possible during exams as we usually have only 2 minutes (exam is 120 min long and is out of 120 marks, the question below is worth 2 marks only) to show that R is an equivalence relation.

For the following relation, can someone show me a fast method for proving that $R$ is an equivalence relation?

Let $\mathcal{P}(S)$ be the power set of $S =\{0,1,2,...,9\}$ and define $$R = \{ (A,B) \in \mathcal{P}(S) \times \mathcal{P}(S) : A=S\backslash B \text{ or } A=B\}.$$

I know we can use $A=B$ from the relation definition to assert that it is reflexive, but what about symmetry and transitivity?

If I prove that $xRy$ is the same as $yRx$ for one example, that doesn't prove that all $A$s and $B$s have symmetric relations as there might be a contradiction somewhere, or is just proving one example symmetric enough to assert that all $A$s and $B$s have a symmetric relation?

  • $\begingroup$ Suppose that $(A,B)\in\mathcal{R}$ and suppose nothing further about $(A,B)$ for now. We wish to prove that this implies that $(B,A)\in\mathcal{R}$. So, since $(A,B)\in\mathcal{R}$ this implies that either $A=S\setminus B$ or that $A=B$. From here we break into two cases. In the case that $A=B$, since $=$ is known to be an equivalence relation this implies that $B=A$ and so $(B,A)\in\mathcal{R}$ as desired. In the case that $A\neq B$, this implies instead that $A=S\setminus B$. Now... do you see why this should imply that $B=S\setminus A$? Make sure you can fully explain why. $\endgroup$ – JMoravitz May 14 '18 at 17:07
  • $\begingroup$ Well, think about what the relationship means. In this case either the sets are equal or the first is the complement of the second. That's reflexive as all sets are equal to themselves. More to the point, it's symmetric because If one set is the complement of another than the other is the complement to the first. Transitivity might be case heavy but if $B=C$ or $A=B$ and $ARB;BRC$ then either $ARB=C$ or $A=BRC$ so $ARC$. And if $A\ne B$ and $B\ne C$ then $A = S-B$ so $B=S-A=S-C$ so $A=C$. So transitive. $\endgroup$ – fleablood May 14 '18 at 18:28

You want to try to prove as much as you can for arbitrary elements $(A,B)$, working from the definitions.

For example, let's say you want to prove symmetry. Symmetry means the following: if you assume $(A,B) \in R$, you want to prove $(B,A) \in R$. So assume $(A,B) \in R$. That means, according to the definition of $R$, either $A=B$ or $A=S\setminus B$. So we break down into two cases:

  • Case 1: $A=B$. Then $B=A$, so by definition $(B,A) \in R$. (This basically boils down to reflexivity, which you have already proven.)
  • Case 2: $A = S \setminus B$. Then, by the properties of set subtraction, $B = S \setminus A$ (do you see why?). Thus $(B,A) \in R$ again by definitioin of $R$.

In either case $(B,A) \in R$, so we have proven symmetry.

Transitivity can be done similarly (though you might need to break up into more cases and subcases); I'll leave it for you to tackle.

  • $\begingroup$ +1 for beating me by 41 seconds :) $\endgroup$ – gt6989b May 14 '18 at 17:10
  • $\begingroup$ For transitivity, assuming a,b∈P(S) and a=/=b, then a=S\b.And assuming b,c∈P(S) and b=/=c, then b=S\c. Since b=S\c and a=S\b then a=S(S\c) which is simplifies into a=c. Thus for aRb and bRc, aRc is true. $\endgroup$ – Mohamad Moustafa May 14 '18 at 17:20
  • $\begingroup$ @MohamadMoustafa Looks good to me! $\endgroup$ – BallBoy May 14 '18 at 17:23

Let's try to prove symmetry. You note correctly, that $R$ is symmetric if $aRb \Leftrightarrow bRa$. In your situation, $aRb$ means either $a=b$ or $a=S\backslash b$.

Let $a,b \in P(S)$ such that $aRb$. Then either $a=b$ or $a = S - b$. In the first case, $bRa$ is true. In the second case, $b = S-a$ so $bRa$ is true as well, and so $R$ is symmetric.

Can you examine transitivity by yourself?

  • $\begingroup$ For transitivity, assuming a,b∈P(S) and a=/=b, then a=S\b.And assuming b,c∈P(S) and b=/=c, then b=S\c. Since b=S\c and a=S\b then a=S(S\c) which is simplifies into a=c. Thus for aRb and bRc, aRc is true. $\endgroup$ – Mohamad Moustafa May 14 '18 at 17:21
  • $\begingroup$ @MohamadMoustafa looks good $\endgroup$ – gt6989b May 14 '18 at 18:11

$A$ and $B$ are related iff they are equal or complements.

Reflexivity: For every subset $A$ of $S$ we have $A=A$

Symmetry: If $A$ is related to $B$ then either they are equal or complements, so $B$ is also related to $A$

Transitivity: If $A$ is related to $B$ and $B$ is related to $C$, then either $B=A$ or $B$ is complement of $A$ and either $C=B$ or $C$ is complement of $B$

In either case we have $A=C$ or $C$ is complement of $A$


First think about what the relationship means. In plain english.

In this case $a R b$ means either $a=b$ or $a = b^{c}$.

Then think about the consequences in terms of reflection, symmetry or trasitivity.

Equality is obviously (almost by definition) an equivalence class. And complements are symmetric although not reflexive or transitive... although the symmetry of complements make them a bit of a toggle. ($a = b^c;b=c^c \implies c=b^c = a$.) And in combination we get:


Reflexive: $a=a$ for all $a$ so $a R a$ for all $a$.

Symmetric: $a R b$ means either $a =b$ and $b=a$; or $a = b^c$ and $b= a^c$. So $aRb \implies bRa$.

Transitive: $a Rb$ and $bRc$ means either $a=b$ and so $a = b Rc$; or $b=c$ and so $a R b=c$; or $a = b^c$ and $b = c^c$ so $c = b^c = a$. So $aRb$ and $bRc\implies aRc$.


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.