Set Equivalence behaves like Equivalence Relation

From ProofWiki
Jump to navigation Jump to search

Theorem

Set equivalence behaves like an equivalence relation.


That is:

  \(\ds \forall S:\) \(\ds S \sim S \)    Reflexivity             
  \(\ds \forall S, T:\) \(\ds S \sim T \implies T \sim S \)    Symmetry             
  \(\ds \forall S_1, S_2, S_3:\) \(\ds S_1 \sim S_2 \land S_2 \sim S_3 \implies S_1 \sim S_3 \)    Transitivity             

where $S, T, S_1, S_2, S_3$ are sets.


Proof

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


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


Reflexive

From Identity Mapping is Bijection, the identity mapping $I_S: S \to S$ is a bijection from $S$ to $S$.

Thus there exists a bijection from $S$ to itself

Hence by definition $S$ is therefore equivalent to itself.


Thus $\sim$ is seen to behave like a reflexive relation.

$\Box$


Symmetric

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


Thus $\sim$ is seen to behave like a symmetric relation.

$\Box$


Transitive

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


Thus $\sim$ is seen to behave like a transitive relation.

$\blacksquare$


Warning

It has been shown that set equivalence exhibits the same properties as an equivalence relation.

However, it is important to note that set equivalence is not strictly speaking a relation.

This is because the collection of all sets is itself specifically not a set, but a class.

Hence it is incorrect to refer to $\sim$ as an equivalence relation, although it is useful to be able to consider it as behaving like an equivalence relation.


Also see

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


Sources