Two injections make a bijection

Two collections. Each fits inside the other with nothing landing on top of anything else. Are they the same size?

For finite collections the answer is yes and the reason is counting: if $A$ fits inside $B$ then $A$ is no larger, and if $B$ fits inside $A$ then $B$ is no larger, so they are equal. Take away the counting and the argument goes with it, because fits inside no longer implies no larger in any sense that can be subtracted.

The answer is still yes. The proof is a construction, and the construction is a decision about which of the two maps to follow.

The example that shows what is at stake #

$[0,1]$ contains $(0,1)$, so the inclusion is an injection one way. And $(0,1)$ contains a copy of $[0,1]$ — send $x$ to $(x+1)/3$, which lands in $[1/3, 2/3]$ — so there is an injection the other way. Both are injections and neither is onto.

The two intervals differ by exactly two points. That is as small a difference as a difference can be, and it is enough to make the obvious approach fail: there is no continuous bijection between them, and no bijection that moves only finitely many points, because removing two points from a finite set changes its size and nothing can put them back.

The two intervals are also the same size for a much cruder reason, and it is worth having both in view: both are uncountable, so neither can be listed, and the theorem below is what turns that shared property into an actual matching.

What works is moving infinitely many points a little. Send $0$ to $1/2$; send $1$ to $1/3$; send $1/2$ to $1/4$; send $1/3$ to $1/5$; and in general send $1/n$ to $1/(n+2)$. Everything else stays exactly where it is.

Count what has happened. The sequence $0, 1, 1/2, 1/3, 1/4, \dots$ has been shifted two places along itself, so its first two entries — the two endpoints — have been vacated, and every entry has somewhere to come from. The two extra points were absorbed by an infinite queue shuffling up.

That is the whole trick, and it is Hilbert’s hotel applied to a set with an accumulation point rather than to rooms.

The general theorem #

Cantor–Schröder–Bernstein. If there is an injection $A \to B$ and an injection $B \to A$, there is a bijection between $A$ and $B$.

The theorem is not obvious and it is not deep, and the gap between those two descriptions is where the interest is.

It is not obvious because the two injections have nothing to do with each other. Neither is onto, so neither can simply be inverted; and there is no reason for the compositions to be anything convenient. The proof has to build a third map out of the two.

It is not deep because the construction is short, uses no machinery, and works uniformly.

The chains #

Here is the construction. Draw $A$ and $B$ as two rows, with an arrow from each $a$ to $f(a)$ and from each $b$ to $g(b)$.

Now trace backwards from any element. Who maps to it? Since both maps are injections, the answer is at most one thing, so tracing backwards is deterministic: from $b$ go back to the unique $a$ with $f(a) = b$ if there is one, from $a$ go back to the unique $b$ with $g(b) = a$ if there is one, and stop when there is nothing.

Every element therefore sits on exactly one chain, alternating between the two sides, and each chain is of one of four kinds:

• it starts in $A$, at an element not in the image of $g$;
• it starts in $B$, at an element not in the image of $f$;
• it goes back forever, with no start at all;
• it closes into a cycle.

Now build the bijection chain by chain. On an $A$-starting chain, use $f$. On a $B$-starting chain, use $g$ backwards. On the other two kinds, either works.

That is it. On an $A$-starting chain, $f$ is a bijection between the chain’s $A$-part and its $B$-part, because the chain has no unmatched $B$-element — anything unmatched by $f$ would have been a start. On a $B$-starting chain, $g$ backwards does the same job for the mirror-image reason. Chains partition everything, so the pieces fit together into a bijection on the whole.

Why the chains are needed at all #

A reader may reasonably ask why the bijection cannot simply be $f$, or $g$ backwards, or some patched-together mixture chosen by hand.

$f$ alone fails because it is not onto: the elements of $B$ outside its image are missed. $g$ backwards alone fails for the same reason on the other side. So a mixture is required, and the question is where to switch.

The chains answer that question, and the answer is that the switch has to be decided globally, not locally. Whether to use $f$ at a particular element depends on where the backward trace from it eventually stops, and that can be arbitrarily far away. There is no way to look at an element and its immediate neighbours and decide.

That is the content of the proof, and it is the reason the theorem needs a proof at all. Finite intuition suggests a matching can be built greedily; here it cannot, and the chain decomposition is what replaces greediness with a rule that is guaranteed consistent. The pattern — a local decision that cannot be made locally, resolved by a structure on the whole object — is the same one that makes an infinite tree’s surviving branch impossible to choose one step at a time without a reason to prefer a side.

The chains, on the interval #

The opening example was solved by hand and the general construction was given afterwards, and the two have not yet been introduced. Running the machinery on the intervals is worth doing, because what comes out is a different bijection from the one built by hand — which is the clearest possible statement of what the theorem does and does not promise.

Take the two injections named at the start: $f$ sends $x$ in $[0,1]$ to $(x+1)/3$, landing inside $(0,1)$, and $g$ is the inclusion of $(0,1)$ back into $[0,1]$.

Trace backwards. A point of $[0,1]$ has a predecessor exactly when it lies in the image of the inclusion, which is $(0,1)$ — so the only points with no predecessor are $0$ and $1$. There are exactly two chains starting on the closed side, and they begin at the two endpoints.

Follow them forwards. From $0$: $f$ gives $1/3$, then $(1/3 + 1)/3 = 4/9$, then $13/27$, and so on, closing in on $1/2$. From $1$: $f$ gives $2/3$, then $(2/3+1)/3 = 5/9$, then $16/27$, closing in on $1/2$ from the other side.

Everything else is a chain starting on the open side — a point of $(0,1)$ outside the interval $[1/3, 2/3]$ has no $f$-predecessor — or a chain with no start at all.

Now assemble by the rule. On the two chains that start in the closed interval, use $f$: so $0$ goes to $1/3$, $1$ to $2/3$, $1/3$ to $4/9$, $2/3$ to $5/9$, and each chain shuffles one place along itself. Everywhere else, use the inclusion backwards, which is to say leave the point where it is.

The result is a bijection between $[0,1]$ and $(0,1)$ in which two sequences shuffle and everything else is fixed. Compare it with the hand-made version at the top of this essay, where a single sequence shuffles two places. Both are correct, neither is preferred, and they agree nowhere except on the points they both leave alone.

That is the theorem’s honest character. It converts two injections into a bijection by a rule, and the rule’s output is determined by the injections it was fed. Feed it a different pair — send $x$ to $(x+1)/4$, say — and the chains land in different places and a third bijection comes out. There is no canonical matching between the two intervals, and the construction does not pretend to find one; it finds a matching, which is all the statement claimed.

The mechanism is the same in both versions, and it is the one this essay keeps returning to: the endpoints have nowhere to go, so an infinite sequence is recruited to absorb them, and the theorem’s contribution is deciding which sequence without anybody choosing it.

The four kinds of chain, and where each occurs #

The classification has four cases and the interval example uses two of them, which is worth spelling out because the other two are usually skipped and are where the finite intuition finally breaks.

Chains that start in $A$. They begin at an element nothing maps to from $B$. Here the map to follow is $f$, forwards.

Chains that start in $B$. Mirror image; follow $g$ backwards.

Chains with no start, going back forever. These are the ones a finite picture cannot show. Nothing on such a chain is a beginning, and either map works because neither side has an unmatched element. In the interval example every point not on the shifting sequence is a chain of this kind — a one-element cycle, in fact, since it maps to itself.

Cycles. A chain that closes on itself. These happen when the composition $g \circ f$ has a fixed point, and again either map works.

The reason all four are needed is that the argument is about arbitrary injections and cannot look at them. It is worth noticing that the proof does not have to decide which kind a given chain is in order to be correct — it only has to be the case that each chain is of one of the four kinds, and that the rule for each kind is consistent. Whether the classification could be carried out in practice is a different question, and for a general pair of injections the answer is no.

What it is used for #

The theorem is a labour-saving device and it saves an enormous amount of labour.

Establishing that two infinite sets have the same size directly means constructing a bijection, which is often fiddly and sometimes genuinely hard. Establishing two injections is usually easy, because an injection can waste as much room as it likes.

The reals and the plane. There is an obvious injection from $\mathbb{R}$ into $\mathbb{R}^2$. The other way, interleave the decimal expansions of two coordinates into one number — which is not a bijection, because of the expansion ambiguity, and is an injection with a little care. So the line and the plane have the same size, a fact Cantor found in 1877 and reported to Dedekind with the remark that he could see it and did not believe it.

The reals and the binary sequences. An injection each way is immediate; a bijection directly is annoying, again because of the expansion ambiguity. The theorem removes the annoyance.

Any two intervals, open or closed. All the same size, all by the same two-line argument, with none of the endpoint bookkeeping done by hand.

In every case the theorem converts a construction problem into two much easier ones, which is what a good structural theorem does.

Why finite intuition is the wrong guide #

The statement sounds obvious and the proof is not, and the gap is worth examining because it recurs everywhere in this part of the subject.

For finite sets, injects into implies has at most as many elements as, and sizes are numbers, and numbers are totally ordered and can be subtracted. Two inequalities in opposite directions give equality by arithmetic, and no construction is required — the bijection exists because the counts agree, and one can be built by any greedy matching.

None of that survives. Infinite cardinalities cannot be subtracted: $|A| \le |B|$ and $|B| \le |A|$ cannot be combined by cancelling anything, because there is nothing to cancel. And a bijection is not implied by an abstract equality of sizes; equality of sizes is the existence of a bijection, so the theorem’s conclusion is the thing itself rather than a consequence of it.

So the theorem is doing the work that arithmetic does in the finite case, and it is doing it by construction because there is no arithmetic to appeal to. That is the standard situation once sets are infinite, and it is why so many statements in this area are obvious-sounding and have proofs: the finite version is a calculation and the infinite version is a construction, and the two do not resemble each other.

The name, which is a small piece of history #

The result is attributed to three people and was proved by at least four, in an order that is worth a paragraph.

Cantor stated it in 1887 and his argument relied on the well-ordering of cardinals, which was itself unproved and turned out to need the axiom of choice. That reliance is the kind of gap a formal system makes visible and an informal one hides, and finding it took twenty years. Dedekind had a complete proof in his notebooks in 1887 and did not publish it. Schröder announced a proof in 1896 that was flawed and was corrected later; Bernstein, then a student of Cantor’s, gave a correct one in 1897. Zermelo produced another in 1908, and the chain argument above is essentially Dedekind’s.

The point worth extracting is not the priority dispute. It is that the proof needs no choice at all, and that this was not clear for twenty years. The chains are defined by tracing backwards, which is deterministic; the decision on each chain is determined by the chain’s own type; and nothing anywhere requires selecting one element from each of infinitely many sets. That is unusual for a theorem about arbitrary infinite sets, and it is why the result is available in settings where choice is not — including the ones where a statement’s independence is shown by exhibiting two models that disagree about choice and agree about this.

What the picture can and cannot show #

The two-row drawing is a window on an infinite pair and it is worth being exact about what survives the truncation.

What survives. That both maps are injections, checked pairwise on the window. That every drawn element lies on exactly one chain, computed by tracing back until the trail leaves the window. That the assembled map — following $f$ on chains that start on the left and $g$ backwards on chains that start on the right — is one-to-one on everything drawn. Those are the three facts the proof needs, and all three are checkable on a finite piece.

What does not survive. A chain with no start cannot appear, because in a finite window every backward trace either stops or leaves the picture, and the two are indistinguishable from inside. Nor can a chain be shown to be infinite. So the window shows the rule and cannot show the case analysis it is a rule for.

That is the standing arrangement in this field and it is stated rather than smoothed over. The finite picture is evidence about the mechanism, never about the infinite object, and where a claim needs the infinite object the essay says so in prose and the figure stays quiet.

What it does not give #

Two limits, both worth stating, because the theorem’s strength invites overreading.

It does not compare sizes that are not comparable this way. The theorem says that two injections give a bijection. It says nothing about which sets are the same size as which, and the first genuine answer to that — that a set is never the same size as its own collection of subsets — is the diagonal argument. It does not say that for any two sets, one injects into the other — that statement is equivalent to the axiom of choice, and is a genuinely different and stronger claim.

It is also silent about anything but size. Two structures matched one to one may be wildly unalike in every other respect, and that is the next paragraph’s subject.

It does not make the bijection natural. The map it produces depends on the two injections given, and different pairs give different bijections with nothing preferred among them. In the interval example the resulting map is discontinuous at infinitely many points and could not be otherwise, since a continuous bijection between the two intervals does not exist. Sameness of size is a very coarse relation, and this theorem is a tool for establishing it rather than for producing anything one would want to use.

That coarseness is worth a closing note, because it is what makes the whole subject of cardinality both powerful and limited. It sees only one property — whether a matching exists — and is blind to every structure a matching might have failed to respect. The interval and the square have the same size, and nothing about that fact says they are alike in any other way; the bijection between them destroys distance, order, continuity and dimension, and cardinality does not notice, because cardinality was never looking.

The blindness has a sharp consequence in the other direction too. Because cardinality never inspects structure, a matching it produces may be unusable — and the existence of one is compatible with every constructive scruple failing, which is why a proof that exhibits nothing is treated with suspicion in some readings of logic and accepted without comment here.

That blindness is the point of the notion rather than a defect in it. Size is the coarsest question that can be asked about a collection, and asking it first is what makes the answers so widely applicable — the theorem above holds for sets of numbers, sets of functions, sets of proofs and sets of sets, because it never looks at what the elements are. Every finer question in mathematics is asked against a background of structure that has to be specified; this one is asked against none, and the price of asking a question that cheap is that the answer says almost nothing beyond itself.