Set Equivalence an Equivalence Relation

From ProofWiki

Jump to: navigation, search

Theorem

For two sets to be equivalent, there needs to exist a bijection between them.

In the following, let $\phi$, $\phi_1$, $\phi_2$ etc. be understood to be bijections.

The identity mapping $I_S: S \to S$ is the required bijection.

Thus there exists a bijection from $S$ to itself and $S$ is therefore equivalent to itself.

Therefore set equivalence is reflexive.

$\displaystyle $	$\displaystyle $		$\displaystyle S \sim T$	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle \exists \phi: S \to T$	$\displaystyle $	Definition of Set Equivalence
$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle \exists \phi^{-1}: T \to S$	$\displaystyle $	$\phi$ is a bijection, therefore so is its inverse
$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle T \sim S$	$\displaystyle $	Definition of Set Equivalence - $\phi^{-1}$ is also a bijection

Therefore set equivalence is symmetric.

$\displaystyle $	$\displaystyle $		$\displaystyle S_1 \sim S_2 \land S_2 \sim S_3$	$\displaystyle $
$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle \exists \phi_1: S_1 \to S_2 \land \exists \phi_2: S_2 \to S_3$	$\displaystyle $	Definition of Set Equivalence
$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle \exists \phi_2 \circ \phi_1: S_1 \to S_3$	$\displaystyle $	By Composite of Bijections, $\phi_2 \circ \phi_1$ is a bijection
$\displaystyle $	$\displaystyle $	$\implies$	$\displaystyle S_1 \sim S_3$	$\displaystyle $	Definition of Set Equivalence

Therefore set equivalence is transitive.

$\blacksquare$

\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle S \sim T\)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \exists \phi: S \to T\)	\(\displaystyle \)	Definition of Set Equivalence
\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \exists \phi^{-1}: T \to S\)	\(\displaystyle \)	$\phi$ is a bijection, therefore so is its inverse
\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle T \sim S\)	\(\displaystyle \)	Definition of Set Equivalence - $\phi^{-1}$ is also a bijection

\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle S_1 \sim S_2 \land S_2 \sim S_3\)	\(\displaystyle \)
\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \exists \phi_1: S_1 \to S_2 \land \exists \phi_2: S_2 \to S_3\)	\(\displaystyle \)	Definition of Set Equivalence
\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \exists \phi_2 \circ \phi_1: S_1 \to S_3\)	\(\displaystyle \)	By Composite of Bijections, $\phi_2 \circ \phi_1$ is a bijection
\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle S_1 \sim S_3\)	\(\displaystyle \)	Definition of Set Equivalence