MathB.in - Share Mathematics with LaTeX and Markdown

Lemma: Suppose $\sim$ is an equivalence relation on a set $A$. Given $a,b \in A$. Then exactly one of the following hold either

$$ [a] = [b] $$ or 
$$ [a] \cap [b] = \emptyset$$.

Proof by cases: Suppose ~ is an equivalence relation on a set A. It follows that for any $a,b \in A$ either 
$ a \sim b$ or $ a \not \sim b$. Let $a,b \in A$.

Case 1: Assume $ a \sim b $ and let $ x \in [a] $, observe that 
$$ x \sim a $$ and $$ a \sim b $$ by assumption and definition of $ [a] $.
Now by the transitive property of $ \sim $, $ x \sim b $. Since $x$ was taken to be arbitrary, $ [a] \subseteq [b] $. By symmetry, $b \sim a $ thus $[b] \subseteq [a] $ by above hence $ [a] = [b] $.

Case 2: (Proof by contradiction) Assume $ a \not \sim b$ and $[a] \cap [b] \neq \emptyset$. Then there must exist as least one element in $[a] \cap [b] $ so call it $x$. Thus, 
$$ b \sim x $$ and $$ x \sim a $$ since $ x \in [a] \cap [b]. $ By transitivity, $ a \sim b $ which is a contradiction since $ a \not \sim b $ by assumption. Therefore $ [a] \cap [b] = \emptyset $.

Case 3: Assume $ a \sim b $ and $[a] \cap [b] = \emptyset $. Let $ x \in [a] $. Thus $ x \sim a $ since $[a]$ is an equivalence class and $x \sim b $ by transitivity of $\sim$. Therefore $ x \in [a] \cap [b]$ contradicting our assumption that $[a] \cap [b] = \emptyset $.

Case 4: Assume $ a \not \sim b $ and $[a] = [b]$. Let $x \in [a]$ thus $x \in [b]$ by assumption. Notice that, $ a \sim x$ and $ x \sim b$ therefore $a \sim b$ which contradicts our assumption that $a \not \sim b$.

Taking case 1-4 we have proven the above lemma.

Sat, 01 Sep 2018 22:05 GMT