[proofplan]
We verify the three equivalence-relation axioms directly from the definition of equinumerosity. Reflexivity is witnessed by the identity map. Symmetry is witnessed by the inverse of a bijection, whose function property, injectivity, and surjectivity follow from the inverse identities. Transitivity is witnessed by the composite of two bijections, with injectivity and surjectivity checked explicitly.
[/proofplan]
[step:Use the identity map to prove reflexivity]
Let $A$ be a set. Define the identity map
\begin{align*}
\operatorname{id}_A: A &\to A \\
a &\mapsto a.
\end{align*}
If $a_1,a_2 \in A$ and $\operatorname{id}_A(a_1)=\operatorname{id}_A(a_2)$, then $a_1=a_2$, so $\operatorname{id}_A$ is injective. If $a \in A$, then $a=\operatorname{id}_A(a)$, so $\operatorname{id}_A$ is surjective. Hence $\operatorname{id}_A$ is a bijection $A \to A$, and therefore $A \approx A$.
[/step]
[step:Invert a bijection to prove symmetry]
Let $A$ and $B$ be sets, and assume $A \approx B$. By definition, there exists a bijection
\begin{align*}
f: A &\to B.
\end{align*}
Define the inverse map
\begin{align*}
f^{-1}: B &\to A
\end{align*}
as follows: for $b \in B$, $f^{-1}(b)$ is the unique element $a \in A$ such that $f(a)=b$.
This definition is valid because $f$ is surjective, so such an $a$ exists for every $b \in B$, and because $f$ is injective, such an $a$ is unique. Thus $f^{-1}$ is a function $B \to A$.
For every $a \in A$ and every $b \in B$, the construction gives
\begin{align*}
f^{-1}(f(a)) &= a, \\
f(f^{-1}(b)) &= b.
\end{align*}
If $b_1,b_2 \in B$ and $f^{-1}(b_1)=f^{-1}(b_2)$, then applying $f$ to both sides gives
\begin{align*}
b_1=f(f^{-1}(b_1))=f(f^{-1}(b_2))=b_2,
\end{align*}
so $f^{-1}$ is injective. If $a \in A$, then $a=f^{-1}(f(a))$ and $f(a) \in B$, so $a$ lies in the image of $f^{-1}$. Hence $f^{-1}$ is surjective.
Therefore $f^{-1}: B \to A$ is a bijection, so $B \approx A$.
[guided]
We assume $A \approx B$, which means there is a bijection
\begin{align*}
f: A &\to B.
\end{align*}
To prove $B \approx A$, we need a bijection in the reverse direction. The natural candidate is the inverse of $f$.
Define
\begin{align*}
f^{-1}: B &\to A
\end{align*}
by sending each $b \in B$ to the unique element $a \in A$ satisfying $f(a)=b$. This rule is well-defined for two separate reasons. Surjectivity of $f$ gives existence: for every $b \in B$, there is at least one $a \in A$ with $f(a)=b$. Injectivity of $f$ gives uniqueness: if $f(a_1)=b=f(a_2)$, then $a_1=a_2$.
The defining inverse identities are
\begin{align*}
f^{-1}(f(a)) &= a &&\text{for every } a \in A, \\
f(f^{-1}(b)) &= b &&\text{for every } b \in B.
\end{align*}
We now prove that $f^{-1}$ is bijective. First, suppose $b_1,b_2 \in B$ and $f^{-1}(b_1)=f^{-1}(b_2)$. Applying $f$ to both sides and using the second inverse identity gives
\begin{align*}
b_1=f(f^{-1}(b_1))=f(f^{-1}(b_2))=b_2.
\end{align*}
Thus $f^{-1}$ is injective. Second, let $a \in A$. Since $f(a) \in B$ and $f^{-1}(f(a))=a$, the element $a$ is attained by $f^{-1}$. Thus $f^{-1}$ is surjective.
So $f^{-1}: B \to A$ is a bijection. By the definition of $\approx$, this proves $B \approx A$.
[/guided]
[/step]
[step:Compose bijections to prove transitivity]
Let $A$, $B$, and $C$ be sets, and assume $A \approx B$ and $B \approx C$. By definition, there exist bijections
\begin{align*}
f: A &\to B, \\
g: B &\to C.
\end{align*}
Define the composite map
\begin{align*}
g \circ f: A &\to C \\
a &\mapsto g(f(a)).
\end{align*}
We prove that $g \circ f$ is injective. Let $a_1,a_2 \in A$ and suppose
\begin{align*}
(g \circ f)(a_1)=(g \circ f)(a_2).
\end{align*}
Then $g(f(a_1))=g(f(a_2))$. Since $g$ is injective, $f(a_1)=f(a_2)$. Since $f$ is injective, $a_1=a_2$. Hence $g \circ f$ is injective.
We prove that $g \circ f$ is surjective. Let $c \in C$. Since $g$ is surjective, there exists $b \in B$ such that $g(b)=c$. Since $f$ is surjective, there exists $a \in A$ such that $f(a)=b$. Therefore
\begin{align*}
(g \circ f)(a)=g(f(a))=g(b)=c.
\end{align*}
Thus $g \circ f$ is surjective.
Hence $g \circ f: A \to C$ is a bijection, so $A \approx C$.
[/step]
[step:Conclude that equinumerosity satisfies all equivalence-relation axioms]
The first step proves reflexivity, the second proves symmetry, and the third proves transitivity. Therefore the relation $\approx$ of equinumerosity is an [equivalence relation](/page/Equivalence%20Relation) on sets.
[/step]
