[proofplan] We reduce the problem to finding a subset $P \subseteq A$ that solves a certain self-referential equation, and then produce such a $P$ via the [Knaster–Tarski Fixed-Point Theorem](/theorems/1478). Specifically, if $P \subseteq A$ satisfies $P = A \setminus g(B \setminus f(P))$, then $A$ splits as $A = P \sqcup g(B \setminus f(P))$ and the map that is $f$ on $P$ and $g^{-1}$ on the complement is a bijection $A \to B$. The operator $\Phi(P) := A \setminus g(B \setminus f(P))$ is order-preserving on $\mathcal{P}(A)$, which is a complete lattice under inclusion, so Knaster–Tarski furnishes a fixed point $P$. [/proofplan] [step:Reduce the problem to partitioning $A$ and $B$ compatibly under $f$ and $g$] Suppose we can find a subset $P \subseteq A$ with the following property: writing $Q := A \setminus P$, $R := f(P) \subseteq B$, and $S := B \setminus R$, we have \begin{align*} g(S) = Q. \end{align*} Define \begin{align*} h: A &\to B, \\ h(a) &= \begin{cases} f(a) & \text{if } a \in P, \\ g^{-1}(a) & \text{if } a \in Q. \end{cases} \end{align*} We verify $h$ is well-defined and bijective. **Well-defined.** If $a \in P$, then $f(a) \in B$ is defined because $f: A \to B$. If $a \in Q = g(S)$, then $a = g(b)$ for some $b \in S \subseteq B$; since $g$ is injective, this $b$ is unique, so $g^{-1}(a)$ is unambiguously defined. **Injectivity.** Suppose $h(a_1) = h(a_2)$. If $a_1, a_2 \in P$, then $f(a_1) = f(a_2)$, so $a_1 = a_2$ by injectivity of $f$. If $a_1, a_2 \in Q$, then $g^{-1}(a_1) = g^{-1}(a_2)$; applying $g$ gives $a_1 = a_2$. Finally, if $a_1 \in P$ and $a_2 \in Q$, then $h(a_1) = f(a_1) \in R$ and $h(a_2) = g^{-1}(a_2) \in S$; but $R \cap S = \varnothing$, so $h(a_1) \neq h(a_2)$, contradicting the assumption. Hence injectivity holds. **Surjectivity.** Let $b \in B$. Either $b \in R = f(P)$, in which case $b = f(a) = h(a)$ for some $a \in P$; or $b \in S$, in which case $g(b) \in g(S) = Q$, so $h(g(b)) = g^{-1}(g(b)) = b$. Hence $h$ is surjective. Thus $h: A \to B$ is a bijection, and the theorem reduces to producing $P \subseteq A$ with $g(B \setminus f(P)) = A \setminus P$. [guided] Why begin by looking for a partition? The obstruction to using $f$ alone is that $f(A)$ might miss some points of $B$; the obstruction to using $g^{-1}$ alone is that $g^{-1}$ is only defined on $g(B) \subseteq A$. A natural strategy is to **split $A$ into two pieces**: a region where we use $f$ (call it $P$) and a region where we use $g^{-1}$ (call it $Q := A \setminus P$). For this blueprint to yield a bijection we need: - $f(P)$ and $g^{-1}(Q)$ to tile $B$ exactly — no overlap, no gap. - Every element of $Q$ to be in the domain of $g^{-1}$, i.e., $Q \subseteq g(B)$. Set $R := f(P)$ and $S := B \setminus R$. The partition $B = R \sqcup S$ is automatic. The condition that $g^{-1}(Q) = S$, i.e., $Q = g(S)$, is exactly what is required: \begin{align*} g(S) = Q = A \setminus P. \end{align*} Using $S = B \setminus f(P)$, this rearranges to the self-referential equation \begin{align*} P = A \setminus g(B \setminus f(P)). \end{align*} We verify the proposed $h$ is a bijection. The injectivity of $f$ and $g$ handles injectivity on each piece; the crux is that images don't clash across pieces, which holds because $f(P) = R$ and $g^{-1}(Q) = S$ and $R \cap S = \varnothing$ by construction. Surjectivity follows because $B = R \cup S$: a $b \in R$ is hit from $P$, a $b \in S$ is hit from $g(S) = Q$. The reduction is now complete: we have transformed the bijection question into the existence of a fixed point of the set operator $\Phi(P) := A \setminus g(B \setminus f(P))$. [/guided] [/step] [step:Identify the operator $\Phi$ on $\mathcal{P}(A)$ whose fixed points give the desired partition] Define \begin{align*} \Phi: \mathcal{P}(A) &\to \mathcal{P}(A), \\ P &\mapsto A \setminus g(B \setminus f(P)). \end{align*} By the previous step, any fixed point $P = \Phi(P)$ solves $g(B \setminus f(P)) = A \setminus P$, which is precisely the condition needed. [/step] [step:Show $\Phi$ is order-preserving on $(\mathcal{P}(A), \subseteq)$] Let $P, P' \in \mathcal{P}(A)$ with $P \subseteq P'$. We chase inclusions through each step of the definition of $\Phi$: \begin{align*} P \subseteq P' &\implies f(P) \subseteq f(P') &&\text{(images preserve inclusions)} \\ &\implies B \setminus f(P) \supseteq B \setminus f(P') &&\text{(complement reverses inclusions)} \\ &\implies g(B \setminus f(P)) \supseteq g(B \setminus f(P')) &&\text{(images preserve inclusions)} \\ &\implies A \setminus g(B \setminus f(P)) \subseteq A \setminus g(B \setminus f(P')) &&\text{(complement reverses inclusions)} \end{align*} The final line is $\Phi(P) \subseteq \Phi(P')$. Hence $\Phi$ is order-preserving with respect to set inclusion. [guided] We want to apply Knaster–Tarski to $\Phi$. Knaster–Tarski requires two ingredients: a complete poset and an order-preserving map. The poset $(\mathcal{P}(A), \subseteq)$ is complete (suprema are unions, infima are intersections), so we need only verify $\Phi$ is order-preserving. The trick is to track how inclusions transform under each operation in $\Phi$. There are two kinds of operation: - **Direct images** $X \mapsto f(X)$, $X \mapsto g(X)$: these **preserve** inclusion. If $X \subseteq X'$, then $f(X) \subseteq f(X')$, because every image point $f(x)$ with $x \in X$ is also an image point from $X'$. - **Complements** $X \mapsto A \setminus X$, $X \mapsto B \setminus X$: these **reverse** inclusion. If $X \subseteq X'$, then $A \setminus X \supseteq A \setminus X'$, because more elements are excluded from $A \setminus X'$ than from $A \setminus X$. The operator $\Phi$ is a composition of four such operations: $f$, complement in $B$, $g$, complement in $A$. Each reversing operation flips the direction; each preserving operation leaves it alone. Two reversing operations compose to a preserving one. So $\Phi$ is order-preserving. Tracing through with $P \subseteq P'$: \begin{align*} P \subseteq P' \xrightarrow{f} f(P) \subseteq f(P') \xrightarrow{B \setminus} B \setminus f(P) \supseteq B \setminus f(P') \xrightarrow{g} g(B \setminus f(P)) \supseteq g(B \setminus f(P')) \xrightarrow{A \setminus} A \setminus g(B \setminus f(P)) \subseteq A \setminus g(B \setminus f(P')). \end{align*} The final inclusion is $\Phi(P) \subseteq \Phi(P')$, as required. Note we did **not** use injectivity of $f$ or $g$ in this step — only that images of sets preserve inclusions and complements reverse them. [/guided] [/step] [step:Verify $(\mathcal{P}(A), \subseteq)$ is complete and apply Knaster–Tarski] The power set $\mathcal{P}(A)$ ordered by inclusion is a complete poset: for any family $\{P_i\}_{i \in I} \subseteq \mathcal{P}(A)$, the supremum is $\bigcup_{i \in I} P_i$ and the infimum is $\bigcap_{i \in I} P_i$; the empty family has supremum $\varnothing$ and infimum $A$. By the previous step, $\Phi: \mathcal{P}(A) \to \mathcal{P}(A)$ is order-preserving. The [Knaster–Tarski Fixed-Point Theorem](/theorems/1478) applies and yields a fixed point $P_0 \in \mathcal{P}(A)$ with \begin{align*} P_0 = \Phi(P_0) = A \setminus g(B \setminus f(P_0)). \end{align*} [/step] [step:Assemble the bijection from the fixed point] With $P_0$ from the previous step, set $Q_0 := A \setminus P_0$, $R_0 := f(P_0)$, and $S_0 := B \setminus R_0$. The fixed-point equation gives $Q_0 = A \setminus P_0 = g(B \setminus f(P_0)) = g(S_0)$, which is the partition condition required in Step 1. Applying the construction of that step, the map \begin{align*} h: A &\to B, \\ h(a) &= \begin{cases} f(a) & \text{if } a \in P_0, \\ g^{-1}(a) & \text{if } a \in Q_0 \end{cases} \end{align*} is a bijection. This completes the proof. [/step]