Show that there is a bijection between the set of equivalence relations on a set A and the set of partitions on A.
So far, I know that to prove this, we must prove that the equivalence relations on A and the Partitions on A must be both surjective and injective.
I think we can go from a partition to an equivalence relation by taking the Cartesian product of the partition with itself. This means that the set A is injective. I'm not sure if this is correct though.
I also do not know how to show how the sets are surjective.
Any help is appreciated!
Best Answer
Let $\{A_i\}$ be a partition of $A$, where each $A_i$ is a set. Define $a \sim b$ if and only if $a$ and $b$ lie in the same $A_i$. Show that this is an equivalence relation.
Define $f(\{ A_i\}) = \ \sim$. We will find an inverse function.
Let $ \# $ be an equivalence relation on $A$. I claim produces a partition on $A$. For $a \in A$, let $[a] = \{ b \in A : a \# b\}$. I claim that for any $[a]$ and $[b]$, $[a]$ and $[b]$ are either disjoint or equal.
For the proof, suppose that $a \# b$ are related. Then, if $x \in [a]$, then $ x \# a$, and transitivity and reflexivity implies $x \# b$,, hence $x \in [b]$. Onthe other hand, if $y \in [b]$, then $ y \# b$, and transitivity and reflexivity implies $y \# a$,, hence $y \in [a]$. Together, this proves that $[a] = [b]$.
If $[a]$ and $[b]$ are not related, then they are disjoint. For if $c \in [a]$ and $c \in [b]$,then $c \# a$ and $c \# b$, which by transitivity and reflexivity implies that $a \# b$, which is a contradiction. Hence, $[a]$ is disjoint from $[b]$.
Now, letting $\{[a]\}$ be the set of $[a]$,we observe this is a partition of $A$, because it is a disjoint collection, and every element $e$ of $A$, is in it's own equivalence class $[e]$. Define $g(\#) = \{[a]\}$
That is, every equivalence relation gives a partition and every partition gives an equivalence relation. I leave you to prove that $f$ and $g$ are inverses of each other. This establishes a bijection between the set of partitions and equivalence relations.