Equivalence Relation Definition Proof

361 Views Asked by At

enter image description here

My Proof: Trivially, if $a = b$, then $a$ and $b$ must have the same equivalence class (by definition). Then if $a$ and $b$ have the same equivalence class, it follows their intersection cannot be empty (as two elements that have the same equivalence class cannot be disjoint). Lastly, if the equivalence classes of $a$ and $b$ are not disjoint, this implies that $a = b$. This holds, because two elements $a$ and $b$ cannot be equivalent if the intersection of their equivalence classes is disjoint. Thus, we have shown that $1 => 2 => 3 => 1$, as desired.

2

There are 2 best solutions below

1
On BEST ANSWER

For the 3$\implies$1 part, I would proceed like follows:

Since $[a]\cap [b] \neq \varnothing$, there is some $c \in [a] \cap [b]$, i.e. $c \sim a$ and $c\sim b$. Hence $a \sim c$ and $c \sim b$ by symmetry, and then $a\sim b$ by transitivity.

0
On

Complete Proof (Credit goes to xbh for providing key step):

If a=b, then a and b must have the same equivalence class (by definition). Then if a and b have the same equivalence class, it follows their intersection cannot be empty (as two elements that have the same equivalence class cannot be disjoint). Lastly, since $[a]\cap [b] \neq \varnothing$, there exists some $c \in [a] \cap [b]$, i.e. $c \sim a$ and $c\sim b$. Hence $a \sim c$ and $c \sim b$ by symmetry, and then $a\sim b$ by transitivity. Thus, we have shown that $1 => 2 => 3 => 1$, as desired.