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.

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 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. 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.

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 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 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.

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.