[proofplan] We use the standard ancestor-chain construction, but we keep track of which side, $A$ or $B$, each ancestor lies on. The injections $f: A \to B$ and $g: B \to A$ give well-defined partial inverse maps on their images, so each element has a unique backward chain until a required preimage fails to exist, or else an infinite backward chain. This partitions $A$ and $B$ into elements whose chains terminate on the $A$-side, terminate on the $B$-side, or never terminate; on these three parts we use $f$, $g^{-1}$, and $f$ respectively to assemble a bijection $A \to B$. [/proofplan] [step:Define the partial inverse maps that generate ancestor chains] Since $f: A \to B$ and $g: B \to A$ are injections, each element in the image of either map has a unique preimage under that map. Define the partial inverse maps \begin{align*} f^{-1}_{\operatorname{im}}: f(A) &\to A, & b &\mapsto \text{the unique } a \in A \text{ such that } f(a)=b, \\ g^{-1}_{\operatorname{im}}: g(B) &\to B, & a &\mapsto \text{the unique } b \in B \text{ such that } g(b)=a. \end{align*} These maps are well-defined because $f$ and $g$ are injective. For an element $a \in A$, its ancestor chain is the typed sequence obtained as follows. Start at the $A$-side element $a$. From an $A$-side element $x \in A$, move one step backward to the $B$-side element $g^{-1}_{\operatorname{im}}(x)$ if $x \in g(B)$, and stop on the $A$-side if $x \notin g(B)$. From a $B$-side element $y \in B$, move one step backward to the $A$-side element $f^{-1}_{\operatorname{im}}(y)$ if $y \in f(A)$, and stop on the $B$-side if $y \notin f(A)$. Ancestor chains for elements $b \in B$ are defined by the same rule, starting instead at the $B$-side element $b$. [guided] The point of introducing the restricted inverse symbols is to avoid treating $f^{-1}$ or $g^{-1}$ as total functions. Since $f$ is injective, every $b \in f(A)$ has exactly one preimage in $A$, so the map \begin{align*} f^{-1}_{\operatorname{im}}: f(A) &\to A, & b &\mapsto \text{the unique } a \in A \text{ such that } f(a)=b \end{align*} is a genuine [function](/page/Function). Likewise, since $g$ is injective, the map \begin{align*} g^{-1}_{\operatorname{im}}: g(B) &\to B, & a &\mapsto \text{the unique } b \in B \text{ such that } g(b)=a \end{align*} is a genuine function. The ancestor process alternates between the two sides. Starting from $a \in A$, the first possible predecessor is a $B$-element $b$ with $g(b)=a$, namely $g^{-1}_{\operatorname{im}}(a)$, but this exists only when $a \in g(B)$. From that $B$-element, the next possible predecessor is an $A$-element $a_1$ with $f(a_1)=b$, namely $f^{-1}_{\operatorname{im}}(b)$, but this exists only when $b \in f(A)$. We continue this alternating construction until a required preimage does not exist; if this never happens, the ancestor chain is infinite. The same construction applies to an initial point $b \in B$, with the first possible predecessor taken through $f^{-1}_{\operatorname{im}}$. [/guided] [/step] [step:Partition $A$ and $B$ according to the side where the ancestor chain stops] Define subsets of $A$ by \begin{align*} A_A &= \{a \in A : \text{the ancestor chain of } a \text{ stops on the } A\text{-side}\},\\ A_B &= \{a \in A : \text{the ancestor chain of } a \text{ stops on the } B\text{-side}\},\\ A_\infty &= \{a \in A : \text{the ancestor chain of } a \text{ never stops}\}. \end{align*} Define subsets of $B$ by \begin{align*} B_A &= \{b \in B : \text{the ancestor chain of } b \text{ stops on the } A\text{-side}\},\\ B_B &= \{b \in B : \text{the ancestor chain of } b \text{ stops on the } B\text{-side}\},\\ B_\infty &= \{b \in B : \text{the ancestor chain of } b \text{ never stops}\}. \end{align*} For each starting point, exactly one of these three alternatives occurs: the chain stops on the $A$-side, stops on the $B$-side, or never stops. Hence \begin{align*} A &= A_A \cup A_B \cup A_\infty, & B &= B_A \cup B_B \cup B_\infty, \end{align*} and both unions are pairwise disjoint. [/step] [step:Show that $f$ bijects the $A$-terminating and infinite parts] The restriction \begin{align*} f|_{A_A}: A_A &\to B_A \end{align*} is a bijection. If $a \in A_A$, then the ancestor chain of $f(a) \in B$ begins \begin{align*} f(a),\ a,\ \ldots, \end{align*} because $f^{-1}_{\operatorname{im}}(f(a))=a$. After this first step it is exactly the ancestor chain of $a$, so it stops on the $A$-side. Thus $f(a) \in B_A$. Conversely, let $b \in B_A$. Its ancestor chain starts on the $B$-side and stops on the $A$-side, so it cannot stop at its initial $B$-side element. Therefore $b \in f(A)$, and $a := f^{-1}_{\operatorname{im}}(b)$ is defined. The ancestor chain of $a$ is the ancestor chain of $b$ with the initial term $b$ removed, so it stops on the $A$-side. Hence $a \in A_A$ and $f(a)=b$. Since $f$ is injective, $f|_{A_A}$ is injective, and the previous argument proves surjectivity onto $B_A$. The same argument proves that \begin{align*} f|_{A_\infty}: A_\infty &\to B_\infty \end{align*} is a bijection: prepending the initial $B$-side term $f(a)$ neither creates nor removes a stopping point. [guided] We first prove that $f$ carries $A_A$ exactly onto $B_A$. Take $a \in A_A$. Since $f(a) \in f(A)$, the first predecessor of the $B$-side element $f(a)$ exists and is \begin{align*} f^{-1}_{\operatorname{im}}(f(a)) = a. \end{align*} Therefore the ancestor chain of $f(a)$ is obtained by adding one initial $B$-side term in front of the ancestor chain of $a$: \begin{align*} f(a),\ a,\ \ldots . \end{align*} Because the remaining chain is exactly the ancestor chain of $a$, and because $a \in A_A$, this chain stops on the $A$-side. Thus $f(a) \in B_A$. Now take $b \in B_A$. The chain starts on the $B$-side and stops on the $A$-side. If $b \notin f(A)$, then the chain would stop immediately on the $B$-side, contradicting $b \in B_A$. Hence $b \in f(A)$. Define \begin{align*} a := f^{-1}_{\operatorname{im}}(b) \in A. \end{align*} Then $f(a)=b$, and the ancestor chain of $a$ is exactly the ancestor chain of $b$ after deleting the first term $b$. Since deleting this first term does not change the eventual stopping side, the chain of $a$ stops on the $A$-side. Hence $a \in A_A$, and $b=f(a)$ lies in the image of $f|_{A_A}$. The restriction is injective because $f$ is injective on all of $A$, so $f|_{A_A}: A_A \to B_A$ is a bijection. For the infinite part, the same predecessor relation gives the equivalence \begin{align*} a \in A_\infty \quad \Longleftrightarrow \quad f(a) \in B_\infty. \end{align*} Indeed, the ancestor chain of $f(a)$ is the ancestor chain of $a$ with one initial $B$-side term added. Adding or deleting one initial term cannot turn an infinite chain into a finite one, or a finite chain into an infinite one. Thus $f$ maps $A_\infty$ onto $B_\infty$, and injectivity again follows from injectivity of $f$. [/guided] [/step] [step:Show that $g$ bijects the $B$-terminating parts] The restriction \begin{align*} g|_{B_B}: B_B &\to A_B \end{align*} is a bijection. If $b \in B_B$, then the ancestor chain of $g(b) \in A$ begins \begin{align*} g(b),\ b,\ \ldots, \end{align*} because $g^{-1}_{\operatorname{im}}(g(b))=b$. After this first step it is exactly the ancestor chain of $b$, so it stops on the $B$-side. Hence $g(b) \in A_B$. Conversely, let $a \in A_B$. Its ancestor chain starts on the $A$-side and stops on the $B$-side, so it cannot stop at its initial $A$-side element. Therefore $a \in g(B)$, and $b := g^{-1}_{\operatorname{im}}(a)$ is defined. The ancestor chain of $b$ is the ancestor chain of $a$ with the initial term $a$ removed, so it stops on the $B$-side. Hence $b \in B_B$ and $g(b)=a$. Since $g$ is injective, $g|_{B_B}$ is injective, and the previous argument proves surjectivity onto $A_B$. Equivalently, the partial inverse $g^{-1}_{\operatorname{im}}$ restricts to a bijection \begin{align*} g^{-1}_{\operatorname{im}}|_{A_B}: A_B &\to B_B. \end{align*} [/step] [step:Assemble the bijection from the three bijections on the partition] Define the function \begin{align*} h: A &\to B \end{align*} by \begin{align*} h(a)= \begin{cases} f(a), & \text{if } a \in A_A,\\ g^{-1}_{\operatorname{im}}(a), & \text{if } a \in A_B,\\ f(a), & \text{if } a \in A_\infty. \end{cases} \end{align*} This definition is well-defined because $A_A$, $A_B$, and $A_\infty$ are pairwise disjoint and cover $A$, and because every $a \in A_B$ lies in $g(B)$ by the preceding step. By the previous steps, $h$ maps $A_A$ bijectively onto $B_A$, maps $A_B$ bijectively onto $B_B$, and maps $A_\infty$ bijectively onto $B_\infty$. Since $B_A$, $B_B$, and $B_\infty$ are pairwise disjoint and cover $B$, the function $h$ is injective and surjective. Therefore $h: A \to B$ is a [bijection](/page/Bijection), completing the proof. [/step]