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

Solution 1:

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

Solution 2:

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.