Alternate proof

of the Schroeder-Bernstein theorem

PlanetMath's standard proof

Wikipedia's standard proof

Draft 2   The following proof of the Schroeder-Bernstein theorem is, as far as I know, new as of April 2006. The standard proof can be found at the links above.   Notation:  "cardA" denotes the cardinal number of a set A. "<=" means "less than or equal to." "~" means "equinumerous to." 

Schroeder-Bernstein theorem: If, and only if, A and B are sets such that card A <= cardB and card B <= card A, then cardA = cardB.

Proof:

Remark: We grant that the transitivity of subsets is established from axioms. That is, A Í B Í C implies A Í C. Further, for nonempty sets, we accept that if A Ì B, then B Ì A is false. This follows from the definition of subset: for all x, x element of X implies x element of Y. But, if A is a proper subset of A, then, for some b, b element of B implies b is not an element of A. Hence B does not fit the definition of subset of A.

We rewrite cardA <= cardB and card B <= card A, thus:

A ~ C Í B and B ~ D Í A

If

Suppose A ~ C = B. Then we are done. Likewise for B ~ D = A. So we test the situation for nonempty sets with: A ~ C Ì B and B ~ D Ì A. (We note that if C ~ D, then A ~ B, spoiling our interim hypothesis. So we assume C is not equinumerous to D.)

We now form the sets A U C and B U D, permitting us to write (A U C) Ì (A U B) and (B U D) Ì (A U B).

We now have two options:

i) (A U C) Ì (A U B) Ì (B U D) Ì (A U B)

This is a contradiction since A U B cannot be a proper subset of itself.

ii) (A U C) Ì (A U B) É (B U D) Ì (A U B)

Also a contradiction, since B U D cannot be a proper subset of A U B and also properly contain A U B.

Only if

We let B = C and D = A.

---

This proof, like the standard modern proof, does not rely on the Axiom of Choice.

---