Define sequences of sets by iterating $g \circ f$ and $f \circ g$. Let $A_0 = A \setminus g[B]$ (elements of $A$ not in the image of $g$), and recursively:

$A_{n+1} = (g \circ f)[A_n], \quad \text{i.e., } A_{n+1} = g[f[A_n]].$

Let $A^* = \bigcup_{n=0}^{\infty} A_n$. Define the bijection:

$h(a) = \begin{cases} f(a), & \text{if } a \in A^*, \\ g^{-1}(a), & \text{if } a \notin A^*. \end{cases}$

Well-definedness of $g^{-1}$: If $a \notin A^*$, then $a \notin A_0 = A \setminus g[B]$, so $a \in g[B]$, meaning $g^{-1}(a)$ exists and is unique (since $g$ is injective).

Injectivity of $h$: On $A^*$, $h = f$ is injective. On $A \setminus A^*$, $h = g^{-1}$ is injective. If $a \in A^*$ and $a' \notin A^*$ with $h(a) = h(a')$, then $f(a) = g^{-1}(a')$, so $a' = g(f(a)) \in (g \circ f)[A^*]$. Since $a \in A_n$ for some $n$, we get $a' \in A_{n+1} \subseteq A^*$, contradicting $a' \notin A^*$.

Surjectivity of $h$: Let $b \in B$.

• If $b = f(a)$ for some $a \in A^*$: then $h(a) = b$.
• If $b \notin f[A^*]$: Consider $g(b) \in A$. If $g(b) \in A^*$, say $g(b) \in A_n$, then either $n = 0$ (impossible since $g(b) \in g[B]$, not in $A_0$) or $g(b) \in A_n = (g \circ f)[A_{n-1}]$, so $g(b) = g(f(a'))$ for $a' \in A_{n-1}$, giving $b = f(a')$ with $a' \in A^*$, contradicting $b \notin f[A^*]$. So $g(b) \notin A^*$, and $h(g(b)) = g^{-1}(g(b)) = b$. $\blacksquare$