Cardinality, The Schroder Bernstein Theorem

The Schroder Bernstein Theorem

Every set trivially maps (one to one) into itself, and if S maps into T maps into U then S maps into U. We almost have a partial ordering on cardinal classes. But we're missing one thing: S ≤ T and T ≤ S → S = T. If S maps into T and T maps into S, are they the same size? Is there a bijection that implements the correspondence?

If two finite sets embed in each other then they are the same size. We only need consider infinite sets. So it's ok to use the infinite axiom, and talk about an element's infinite ancestry etc. There is another proof that avoids this, but I think it is less intuitive.

Let f map S into T and g map T into S. These are 1-1 functions of course. For any x in either set, trace the ancestry of x, going backwards through f inverse and g inverse, until we reach a parentless element that is not in the range of f or g. Let S1 be the subset of S whose members have parentless ancestors in S. Let S2 be the subset of S whose members have parentless ancestors in T. Let S3 be the subset of S whose members have infinite ancestry.

Let h = f on S1 and S3, and g inverse on S2. Clearly h is invertible when restricted to S1∪S3, or S2. We need to show h is invertible across all of S. In other words, we don't want h(x) to equal h(y), when x comes from S1∪S3 and y comes from S2.

Let f(x) = g inverse of y. Thus y = g(f(x)). If x is in S3 (infinite ancestry) then so is y. Yet y is in S2, so x is in S1. This means x has a parentless ancestor in S, and the same holds for y, so y should be in S1. That takes care of 1-1.

Finally we need to show that h maps S onto all of T. Select any y in T and first consider the case when, for some x in S, we have f(x) = y. If x is in S1 or S3 we are done, so x has a parentless ancestor in T. Let g(y) = z, and z has a parentless ancestor in T. Thus z is in S2 and h(z) = y.

Now consider the remaining case, when y is not in the image of f. Once again z=g(y) is in S2 and h maps z to y. Therefore h maps onto all of T and both sets have the same cardinality.

This completes antisymmetry, and also completes the proof of the Schroder Bernstein Theorem.

If two sets fit inside each other they are the same size. Cardinal classes are partially ordered. This provides another method for proving cardinal equality. Mapping two sets into each other is often easier than finding a perfect 1-1 correspondence. For instance, the integers map into the rationals in the obvious way, and rationals map into integers by sending the fraction a/b (lowest terms) to 2a3b. (Send -a/b to -2a3b, and send 0 to 0.) That's it. The integers and the rationals are the same size. (Of course it is also not so difficult to write down explicit examples of one to one maps of the integers onto the rationals.)

Are S and T the same size if a function takes S onto all of T, and another function carries T onto S? If S and T are finite then the answer is yes. For infinite sets, if both these functions are one to one then the Schroder Bernstein theorem gives a positive answer. Otherwise we need the well ordering principle.