Set Equivalence is Equivalence Relation

From ProofWiki
Jump to navigation Jump to 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\)
\(\displaystyle \) \(\leadsto\) \(\displaystyle \exists \phi: S \to T\) Definition of Set Equivalence
\(\displaystyle \) \(\leadsto\) \(\displaystyle \exists \phi^{-1}: T \to S\) Bijection iff Inverse is Bijection
\(\displaystyle \) \(\leadsto\) \(\displaystyle T \sim S\) Definition of Set Equivalence: $\phi^{-1}$ is also a bijection


Therefore set equivalence is symmetric.

$\Box$


Transitive

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


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