The equivalence relation of an injection

For the proof of Cantor's Bijection Theorem, we study the equivalence relation generated by an injection.
So let $\mathbb{C}$ be a non-empty set and let $f: \mathbb{C}\rightarrow \mathbb{C}$ be an injection.
Regard $f$ as a subset of $\mathbb{C}\times \mathbb{C}$, so $f$ is a relation on $\mathbb{C}$ and denote by $\mathbb{R}(f)$ the equivalence relation determined by $f$.

• We have the formula:
  $$\mathbb{R}(f) = \mathbb{I}_{\mathbb{C}} \cup\left(\bigcup_{n \in \mathbb{N}} (f^n \cup (f^n)') \right).$$

Proof:
Write $\mathbb{S}(f) = \mathbb{I}_{\mathbb{C}} \cup\left(\bigcup_{n \in \mathbb{N}} (f^n \cup (f^n)') \right)$.
Then it is clear from the definition of $\mathbb{R}(f)$ that $\mathbb{S}(f) \subset \mathbb{R}(f)$.
Also it is clear that $f \subset \mathbb{S}(f)$.
Since we have that $\mathbb{R}(f)$ is the smallest equivalence relation continuing $f$, we just have to show that $\mathbb{S}(f)$ is itself an equivalence relation.
It is clear that $\mathbb{S}(f)$ is symmetric and reflexive, so we just have to show that $\mathbb{S}(f)$ is transitive.
Since $\mathbb{S}$ is symmetric and reflexive, to prove transitivity, it suffices to show that $(x, y) \in \mathbb{S}(f)$ and $(y, z) \in \mathbb{S}(f)$, whenever $x$, $y$ and $z$ are pairwise distinct elements of $\mathbb{C}$ (i.e. $x \ne y$, $y\ne z$ and $z \ne x$).
So here it suffices to show that if we have $(x, y) \in \bigcup_{n \in \mathbb{N}} (f^n \cup (f^n)')$ and $(y, z) \in \bigcup_{n \in \mathbb{N}} (f^n \cup (f^n)')$, with $x$, $y$ and $z$ pairwise distinct, then $(x, z) \in \mathbb{S}(f)$.
To prove this, first note that $(x, y) \in f^n$ if and only if $y = f^n(x)$, where $f^n$ is the ordinary $n$-fold composition of $f$ with itself; also note that $f^n$ is an injection.
Similarly $(x, y) \in (f^n)'$ if and only if $f^n(y) = x$. So now we have four cases to consider:

• $(x, y) \in f^m$ and $(y, z)\in f^n$, for some $m$ and $n$ in $\mathbb{N}$.
  Then $y = f^m(x)$ and $z = f^n(y) = f^n(f^m(x)) = f^{m + n}(x)$, so we get $(x, z)\in f^{m + n} \subset \mathbb{S}(f)$.
• $(x, y) \in (f^m)'$ and $(y, z)\in (f^n)'$, for some $m$ and $n$ in $\mathbb{N}$.
  Then $x = f^m(y)$ and $y = f^n(z)$, so $x = f^m(f^n(z)) = f^{m + n}(z)$, so we get $(x, z)\in (f^{m + n})' \subset \mathbb{S}(f)$.
• $(x, y) \in f^m$ and $(y, z)\in (f^n)'$, for some $m$ and $n$ in $\mathbb{N}$.
  Then $y = f^m(x)$ and $y = f^n(z)$.
  Also $m\ne n$, since otherwise, by the injectivity of $f^m$ we would get $x = z$, contrary to hypothesis.
  • If $m > n$, then $f^n(z) = y = f^m(x) = f^n(f^{m- n}(x))$, so we get $z = f^{m- n}(x)$, since $f^n$ is injective, so $(x, z) \in f^{m- n} \subset \mathbb{S}(f)$.
  • If $m < n$, then $f^m(x) = y = f^n(z) = f^m(f^{n- m}(z))$, so we get $x = f^{n- m}(z)$, since $f^m$ is injective, so $(x, z) \in (f^{m- n})' \subset \mathbb{S}(f)$.
• $(x, y) \in (f^m)'$ and $(y, z)\in f^m$, for some $m$ and $n$ in $\mathbb{N}$.
  Then $x = f^m(y)$ and $z = f^n(y)$.
  Again we have $m\ne n$, since otherwise $x = z$, contrary to hypothesis.
  • If $m > n$, then $x = f^m(y) = f^{m - n}(f^n(y)) = f^{m- n}(z)$, so we get $(x, z) \in f^{m- n} \subset \mathbb{S}(f)$.
  • If $m < n$, then $z = f^n(y) = f^{n- m}(f^m(y)) = f^{n - m}(x)$, so we get $(x, z) \in (f^{n- m})' \subset \mathbb{S}(f)$.

In all cases we find that $(x, z) \in \mathbb{S}(f)$ and we are done, $\mathbb{S}(f)$ is an equivalence relation, so $\mathbb{R}(f) = \mathbb{S}(f)$.

Now we see that for $x$ and $y$ in $\mathbb{C}$, we have $(x, y) \in \mathbb{R}(f)$ if and only if $(x, y) \in \mathbb{S}(f)$ if and only if either $x = y$, or $f^n(x) = y$, or $x = f^n(y)$, for some integer $n \in\mathbb{N}$.
So we have that the equivalence class of $x \in \mathbb{C}$ is:

$$\mathbb{R}(f)(x) = \{(x, y)\in \mathbb{C}\times \mathbb{C}: x = y... ...e{3pt} f^n(x) = y,\hspace{3pt}\textrm{for some}\hspace{3pt} n \in \mathbb{N}\}.$$

Note that $f(\mathbb{R}(f)(x)) \subset \mathbb{R}(f)(x)$: if $y \in \mathbb{R}(f)(x)$, then $f(y) \in \mathbb{R}(f)(x)$, since:

• If $y = x$, then $f(y) = f(x) \in \mathbb{R}(f)(x)$.
• If $y = f^n(x)$, with $n \in\mathbb{N}$, then $f(y) = f^{n + 1}(x)\in \mathbb{R}(f)(x)$.
• If $x = f^n(y)$, with $n \in\mathbb{N}$, then if $n = 1$, we have $x = f(y)$, so $f(y) \in \mathbb{R}(f)(x)$; alternatively, if $n > 1$ we have $x = f^{n-1}(f(y))$ with $n - 1\in \mathbb{N}$, so $f(y) \in \mathbb{R}(f)(x)$.

Also we have $f^{-1}(\mathbb{R}(f)(x)) \subset \mathbb{R}(f)(x)$: if $f(z) \in \mathbb{R}(f)(x)$, for some $z \in \mathbb{C}$, then $z \in \mathbb{R}(f)(x)$, since:

• If $f(z) = x$, then $x = f(z)$, so $z \in \mathbb{R}(f)(x)$
• If $f(z) = f^n(x)$, for $n \in\mathbb{N}$, then, if $n = 1$, we have $z = x$, since $f$ is injective; alternatively, if $n > 1$, we have $f(z) = f(f^{n - 1}(x))$, so $z = f^{n - 1}(x)$ and $n - 1\in \mathbb{N}$; in either case, we have $z \in \mathbb{R}(f)(x)$.
• If $f^n(f(z)) = x$, for $n \in\mathbb{N}$, then we have $f^{n + 1}(z) = x$, so $z \in \mathbb{R}(f)(x)$.

We now make the following definition:

• A progenitor for an equivalence class $\mathbb{R}(f)(x)$, for $x \in \mathbb{C}$ is an element $c \in \mathbb{C}$, such that no $b \in \mathbb{C}$ exists with $f(b) = c$.

Note that an equivalence class may not have a progenitor.
If an equivalence class $\mathbb{R}(f)(x)$ has a progenitor $c$, either $c = x$, or $x = f^n(c)$, for some $n \in\mathbb{N}$, since $c = f^n(x)$, with $n \in\mathbb{N}$ is impossible (since either $n = 1$, so $c = f(x)$, a contradiction, or $n > 1$, so $c = f(f^{n - 1}(x))$, again a contradiction).
So the equivalence classes with a progenitor $c$ take the form:

$$\mathbb{R}(f)(c) = \{c\} \cup \{f^n(c): n \in \mathbb{N}\}.$$

(In particular the progenitor of any equivalence class is unique, if it exists).
If an equivalence class does not have a progenitor then the restriction of $f$ to the equivalence class is a bijection, since the restriction is both injective and surjective.