display | more...
An important theorem in set theory that goes toward proving that all cardinals can be arranged in a well-behaved order. This was only conjectured by Cantor and proved by Schröder and Bernstein, so it is sometimes called the Schröder-Bernstein Theorem.

The cardinality of a set is first defined by the equivalence class of which other sets it is equipollent to, that is where there exists a bijective function between the sets. The notion of cardinality at this stage is not further defined, but it is in some sense a measure of size.

A partial order is defined on cardinalities by saying that |A| <= |B| iff there is an injection from A into B. This is then equivalent to there being a bijection from A onto a subset of B.

The hard part is to show that if |A| <= |B| and |B| <= |A| then |A| = |B|. This is actually harder than I'm prepared to try to detail here, since I'd have to re-read my book a few more times to get it right. Informally, if A is the same size as part of B, and B is the same size as part of A, then A and B are the same size.

This only defines a partial order. There may be sets that are incommensurable with other sets in this order. The steps after this are to construct a hierarchy of ordinals, which are well-ordered sets, so we can take a least ordinal of any given cardinality, and call that ordinal a cardinal.

By the Well-Ordering Principle any set can be well-ordered, so every set has a cardinality of some cardinal. Unfortunately this principle is equivalent to the Axiom of Choice. There is no intuitive consensus on whether to accept it, though it does make things a sight easier if you do.

The following assumes that you have defined the concept of the cardinality of a finite set. It's harder than it sounds. One also must have the idea of a set having infinite cardinality, even if one does not have an ordering on different kinds of infinity.

Theorem (Cantor-Schröder-Bernstein): If f: A -> B is an injection and g: B -> A is an injection, then there exists a bijection between A and B.

Proof: For any a in A, we construct the 'ancestors' of a as follows. If a is in g(B), then there exists a unique b1 in B with g(b1) = a. Similarly if b1 is in f(A) then there exists a unique a1 in A with f(a1) = b. This can be continued to produce a set S(a) = {b1, a1, b2, a2, . . . }. We can produce a similar set S(b) for any b in B.

Now we partition A and B based on the cardinalities of S(a) and S(b). Let Ainf = {a in A: |S(a)| is infinite}. Let A0 = {a in A: |S(a)| is even} and A1 = {a in A: |S(a)| is odd}. Similarly define Binf, B0, B1.

Consider the sets Ainf and Binf. Every b in Binf obviously has an inverse under f in Ainf. Therefore f is a bijection from Ainf to Binf. Now consider A0 and B1. By a parity argument, f maps A0 into B1 injectively. Also, as |S(b)| is odd, it must be at least 1, implying that any b in B1 has an inverse in A0. Therefore f is a bijection from A0 to B1 and, by symmetry, g is a bijection from B0 to A1. By combining the three bijections, we can then construct a bijection between A and B.

(Cantor-Schroeder-Bernstein Theorem)

Here's another proof, that's different enough (at least on the surface) from The Numbered One's above to seem worth noding. Hence showing the splendiferous multifacetedness of mathematics, or something similar.

We have f:A->B, g:B->A, both injective (aka 1-1). Let C0 := A \ ran(g), this being the bit of A which g doesn't map onto - the bit which stops g being the desired bijection. The idea is to reflect C0 between A and B via f and g. So define by recursion

Cn+1
:= g[f[Cn]]

Now we define our bijection, h, by

h(x) := f(x) if x \in Cn for some n,
h(x)
:= g-1(x) else

(g is injective, so g-1 is defined on ran(g) - i.e. on all but C0 which is excluded by the first line)

We need to show h is bijective. First, we show it's injective. So suppose x, x' are distinct elements of A. If h is defined in the same way for both, either by f or by g-1, then we have no problem since these functions are injective. The remaining case is when one has h defined by f, the other by g-1. WLOG, suppose x \in Cm, and x' is not in UCn. Then

h(x) = h(x')=> f(x) = g-1(x') => g(f(x)) = g(g-1(x') = x' => x' \in g[f[Cm]] = Cm+1,

contradicting our choice of x'.

So h is injective.

It remains to show that h is surjective (onto). So let b \in B.
First supppose g(b) is not in any of the Cn's. Then h(g(b)) = g-1(g(b)) = b, so b \in ran(h).
Else, say g(b) \in Cm. m can't be 0, since C0 = A \ ran(g). So m-1 >= 0. So g(b) \in Cm = g[f[Cm-1]], so, since g is injective, we have b \in f[Cm] = h[Cm]. So again, b \in ran(h).

So h is surjective, so h is bijective, so A is equinumerous to B.

QED.

Source: Elements of Set Theory - Enderton

Log in or register to write something here or to contact authors.