Try
Imagine two catalogs, A and B, each containing one entry for every nonnegative integer. You can assign each A entry to a distinct B entry using f(n)=n+1. You can also assign each B entry to a distinct A entry using g(n)=n+1. Neither assignment reaches entry zero in its target catalog. Can these two incomplete assignments produce a complete one-to-one pairing?
The answer is yes, but simply choosing f does not work: zero is missing. Simply trying to reverse g everywhere also fails: g has no inverse value at zero. We need to decide which entries use f and which use the reverse of g. That decision must prevent collisions between the two branches, not just within each branch.
Predict
Entry zero in A has no incoming g arrow, so send it forward by f to entry one in B. That B entry has a g arrow to entry two in A. If we sent two backward by g, it would also land at entry one in B. To avoid the collision, send two forward instead. Continue this reasoning. Which A entries are forced into the forward branch?
They are 0, 2, 4, and so on. The resulting map sends each even n to n+1, and each odd n to n−1. It swaps consecutive pairs. Before proceeding, check that every output occurs exactly once. The finite trace below illustrates a construction whose general proof must still handle arbitrary sets.
Experiment
| A input n | Branch | B output h(n) | Reason |
|---|
| 0 | f | 1 | No incoming g arrow |
|---|
| 1 | g inverse | 0 | Outside the even chain |
|---|
| 2 | f | 3 | Reached by g after f from 0 |
|---|
| 3 | g inverse | 2 | Outside the even chain |
|---|
| 4 | f | 5 | Next forward-chain entry |
|---|
| 5 | g inverse | 4 | Outside the even chain |
|---|
Draw alternating arrows A→B→A for the first three forward steps. Then deliberately use the forward branch only at zero. Inputs zero and two now collide at output one. Both component maps are injective, yet their arbitrary mixture is not. The set selecting the branch needs a proof of its own.
Understand
Now let f:A→B and g:B→A be any injections. Define A₀=A∖g(B), the elements with no incoming g arrow. Define A_(n+1)=g(f(A_n)) for every nonnegative integer n, and let C be the union of all A_n. These are subsets of A. The stages need not exhaust A; C contains exactly the elements reached after finitely many forward pairs of arrows starting in A₀.
Images preserve unions, so C=A₀∪g(f(C)). Define h:A→B as follows: use h(a)=f(a) when a belongs to C, and h(a)=g⁻¹(a) otherwise. Here g⁻¹ means the inverse on the image g(B), not on all of A.
First prove this definition is valid. If a is outside C, it is outside A₀, so it belongs to g(B). There is therefore a preimage under g, and injectivity of g makes it unique. The forward branch is valid because f is already a function on A. Both branches produce elements of B.
Next prove injectivity. Two inputs in C cannot collide because f is injective. Two inputs outside C cannot collide because applying g to their equal inverse values recovers equal inputs. For the crucial cross-case, suppose a lies in C, a′ lies outside C, and f(a)=g⁻¹(a′). Applying g gives a′=g(f(a)), which belongs to g(f(C)) and hence C. This contradicts the branch choice. All cases are covered.
Finally prove surjectivity. Fix any b in B. If g(b) is outside C, its inverse-branch image is b. If g(b) is inside C, it cannot be in A₀, since it is in g(B). The union identity then gives g(b)=g(f(a)) for some a in C. Injectivity of g implies b=f(a)=h(a). Thus every element of B has a preimage. This proves the Cantor–Schroeder–Bernstein theorem by constructing a bijection rather than quoting it.
The boundary cases belong to the argument. If A₀ is empty, every stage is empty, g is onto A, and h is simply g⁻¹. If C=A, only the forward branch is used, and the preceding proof shows f is onto. If A is empty, existence of g:B→A forces B empty too. The unique empty map is then the required bijection.
Apply
Change the countable example to f(n)=n and g(n)=n+2. The initial missing entries are zero and one. Repeated application of g∘f adds two, so the generated set contains every nonnegative integer. The resulting bijection is h(n)=n. Explain why the unused inverse branch causes no problem and why this example differs from the alternating branches in the worked table.
For the endpoint-sensitive application, let K=[0,1) and I=(0,1]. Suppose the separate canonical-digit argument has proved an injection J:K×K→K. Reflection ρ(t)=1−t bijects I with K: the included endpoint 1 maps to the included endpoint 0, and the excluded endpoint 0 would map to the excluded endpoint 1. Reflect both coordinates, apply J, then reflect its output. This gives the injection G(x,y)=1−J(1−x,1−y) from I×I into I. Its output is positive and at most 1, as required.
The reverse-direction injection is f(t)=(t,1), whose second coordinate is allowed in I. Apply the proved theorem with A=I, B=I×I and g=G. It produces a bijection I→I×I, so the actual endpoint choice (0,1] is respected. The practice requires the generated sets and both branches, not just the theorem name. Neither J nor G is assumed onto.
The assumption about J matters: an ambiguous digit encoding is not automatically an injection. Conversely, the theorem does not require the supplied injection to be a surjection. Nor does this proof promise a finite algorithm deciding membership in C. An infinite union defines a set even when an effective membership procedure has not been established.
Continue
For each use of two injections, record their domains and codomains, justify both injections independently, then verify inverse existence, same-branch and cross-branch injectivity, and coverage. Finite diagrams help reveal the branch rule; the set identity and general case arguments establish the theorem. A saved explanation is practice evidence, not an automatic certification of the proof.
