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.
Thanks in advance.
Best Answer
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$.