Proving that a relation R is an equivalence relation

Question

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?

Answer 1

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.

Answer 2

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?

Answer 3

$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$

Answer 4

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:

Ergo:

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$.