# Lamport claims there is an error in Kelley's proof of the Schroeder-Bernstein theorem. What is it?

In section 4.1 of his note How to write a proof, Leslie Lamport mentions an error in Kelley's exposition of the Schroeder-Bernstein theorem:

Some twenty years ago, I decided to write a proof of the Schroeder-Bernstein theorem for an introductory mathematics class. The simplest proof I could find was in Kelley’s classic general topology text [4, page 28]. Since Kelley was writing for a more sophisticated audience, I had to add a great deal of explanation to his half-page proof. I had written five pages when I realized that Kelley’s proof was wrong. Recently, I wanted to illustrate a lecture on my proof style with a convincing incorrect proof, so I turned to Kelley. I could find nothing wrong with his proof; it seemed obviously correct! Read- ing and rereading the proof convinced me that either my memory had failed, or else I was very stupid twenty years ago. Still, Kelley’s proof was short and would serve as a nice example, so I started rewriting it as a structured proof. Within minutes, I rediscovered the error.

However, Lamport doesn't explain what this error is. I looked at Kelley's proof and stared at it for a long time, but I was unable to spot the mistake. Could somebody please explain to me what this alleged mistake might be?

Here's Kelley's proof (which he attributes to Birkhoff and Mac Lane) in its entirety (Kelley, General Topology, page 28):

Theorem If there is a one-to-one function on a set $A$ to a subset of a set $B$ and there is also a one-to-one function on $B$ to a subset of $A$, then $A$ and $B$ are equipollent.

Proof Suppose that $f$ is a one-to-one map of $A$ into $B$ and $g$ is one to one on $B$ to $A$. It may be supposed that $A$ and $B$ are disjoint. The proof of the theorem is accomplished by decomposing $A$ and $B$ into classes which are most easily described in terms of parthenogenesis. A point $x$ (of either $A$ or $B$) is an ancestor of a point $y$ iff $y$ can be obtained from $x$ by successive application of $f$ and $g$ (or $g$ and $f$). Now decompose $A$ into three sets: let $A_E$ consist of all points of $A$ which have an even number of ancestors, let $A_O$ consist of points which have an odd number of ancestors, and let $A_I$ consist of points with infinitely many ancestors. Decompose $B$ similarly and observe: $f$ maps $A_E$ onto $B_O$ and $A_I$ onto $B_I$, and $g^{-1}$ maps $A_O$ onto $B_E$. Hence the function which agrees with $f$ on $A_{E} \cup A_{I}$ and agrees with $g^{-1}$ on $A_{O}$ is a one-to-one map of $A$ onto $B$.

I suspected that the error might lie with the edge-cases (the points in $A_E$ and $B_{E}$ with no ancestor), but there the argument seems to work.

-
"I looked at Kelley's proof and stared at it for a long time, but I was unable to spot the mistake." Note that Lamport didn't say that he found it in reading the proof, but in trying to reconstruct it and explain it to others. To borrow a term from the programming community, did you go beyond "staring at the proof" and try to explain it to the duck? –  Joshua Taylor Jul 8 '14 at 2:14

Suppose there's a cycle, such that $g(f(a))=a$ for some $a$. Then $a$ and $f(a)$ will both count as having an even number of ancestors, namely $\{a,f(a)\}$.

This contradicts the claim that $f$ maps $A_E$ (on)to $B_O$.

-
Awesome! Thank you so much! –  Marion Jul 7 '14 at 13:32
Would the proof be correct if we counted the (in)finiteness of ancestral sequences, instead of their cardinality? That is, count cycles as infinite sequences. –  Petr Pudlák Jul 8 '14 at 17:31
@Petr: Yes, that would fix the proof, at the cost of adding some complexity because instead of just sets of ancestors, one needs to work with sets of possible ancestral distances. –  Henning Makholm Jul 8 '14 at 17:36

Suppose that $f$ is a one-to-one map of $A$ into $B$ and $g$ is one to one on $B$ to $A$.

This is allowed by the given conditions.

It may be supposed that A and B are disjoint.

Indeed, otherwise let $B'=\{A\}\times B$, which is disjoint to $A$ and in obvious bijection to $B$, thus allowing the definitions of maps $A\to B'$, $B'\to A$ accordingly.

The proof of the theorem is accomplished by decomposing $A$ and $B$ into classes which are most easily described in terms of parthenogenesis. A point $x$ (of either $A$ or $B$) is an ancestor of a point $y$ iff $y$ can be obtained from $x$ by successive application of $f$ and $g$ (or $g$ and $f$).

This defines a (transitive) relation on $A\cup B$.

Now decompose $A$ into three sets: let $A_E$ consist of all points of $A$ which have an even number of ancestors, let $A_O$ consist of points which have an odd number of ancestors, and let $A_I$ consist of points with infinitely many ancestors.

No problem here. The cardinality of a set is either odd or even or infinite.

Decompose $B$ similarly and observe: $f$ maps $A_E$ onto $B_O$ and $A_I$ onto $B_I$,

We need to be careful here: The set of ancestors of $f(a)$ is the set of ancestors of $a$, together with $a$. Thus if the first set is infinite, so is the second. And if the first set is even, then the second is odd provided the first does not contain $a$. One might see a sloppy definition here as finite but cyclic ancestor sequences should still be counted to $A_I$ and $B_I$, respectively.

and $g^{−1}$ maps $A_O$ onto $B_E$.

We can apply $g^{-1}$ to $A_O$ because each element has at least one ancestor. However, the same caveats about cyclic cases applies.

Hence the function which agrees with $f$ on $A_E\cup A_I$ and agrees with $g^{−1}$ on $A_O$ is a one-to-one map of $A$ onto $B$.

This is fine.

-
Thank you very much for this detailed analysis and for explaining how to fix the argument. –  Marion Jul 7 '14 at 13:38
Yeah, so if we start with a $y_0$ in one of the sets, that point may or may not have a direct ancestor (wrt. the relevant inverse image). If it has a direct ancestor, call it $y_1$ (since it is unique by the injectivty of the relevant map). Then $y_1$ may or may not have a direct ancestor $y_2$. The sequence so produced can be an infinite sequence (direct ancestor can be found forever) or the process can stop after a finite number of steps. But the case where $y_0,y_1,y_2,\ldots$ is well-defined as an infinite sequence, cannot be described as the case where $\{ y_i\}$ is infinite as a set. –  Jeppe Stig Nielsen Jul 7 '14 at 22:13