Set Equivalence is Equivalence Relation

From ProofWiki
Jump to: navigation, search

Theorem

Set equivalence is an equivalence relation.


Proof

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.


Reflexive

From Identity Mapping is Bijection, 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.

$\Box$


Symmetric

\(\displaystyle \) \(\) \(\displaystyle S \sim T\) $\quad$ $\quad$
\(\displaystyle \) \(\leadsto\) \(\displaystyle \exists \phi: S \to T\) $\quad$ Definition of Set Equivalence $\quad$
\(\displaystyle \) \(\leadsto\) \(\displaystyle \exists \phi^{-1}: T \to S\) $\quad$ Bijection iff Inverse is Bijection $\quad$
\(\displaystyle \) \(\leadsto\) \(\displaystyle T \sim S\) $\quad$ Definition of Set Equivalence: $\phi^{-1}$ is also a bijection $\quad$


Therefore set equivalence is symmetric.

$\Box$


Transitive

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


Therefore set equivalence is transitive.

$\blacksquare$


Also see

The definition of a cardinal of a set as the equivalence class of that set under set equivalence.


Sources