Bridge to Abstract Mathematics: Mathematical Proof and Structures

286 RELATIONS: FUNCTIONS AND MAPPINGS Chapter 8

(although if you worked through Exercise 18, Article 8.2, you should

find it familiar). Consider an element a E A. This element may be, or

may fail to be, in the image of g. If it is, let b be the element of B such

that a = g(b). Now focus on this b, in connection with the injection f.

Again, we may have either b E im f or b 4 im f. If the former, let a, E A

have the property that b = f(a,). Note then that a = g(b) = g(f(a,)). If

we continue this process (a process often referred to as "tracing the an-

cestry" of a), we find that one of three mutually exclusive possibilities

must occur:

1. The process terminates with either no ancestor for a or an ancestor
   of a lying in A which is not in the image of g, that is, with an even
   number of ancestors for a. Let us say that a E AA in this case.


2. The process terminates with an ancestor of a lying in B which is not
   in the image off, so that a has an odd number of ancestors. Let
   us say that a E A, in this case.


3. The process does not terminate; we denote this circumstance of
   infinite ancestry for a by writing a E A,.
   Clearly the sets A,, A,, and A, are mutually disjoint subsets of A
   whose union equals A; that is, the sets constitute a partition of A having
   at most three cells. Also, we can partition B in a totally analogous man-
   ner, into subsets BA, BB, and B, (an element b E BA, e.g., has an odd
   number of ancestors). Note now that f maps AA onto BA and A, onto
   B, in a one-to-one fashion, while g restricted to B, is a bijection onto
   A, [see Exercise 7(b)]. Hence we may arrive at the desired bijection h
   in the following manner:

Again, for readers familiar with Article 7.4, the results of Exercise qa),
combined with Theorem 6, enable us to conclude that 5 is a partial-ordering
relation between cardinal numbers.
The Schroeder-Bernstein theorem is extremely useful for proving numeri-
cal equivalence of sets. As one example, suppose it is known that any open
interval (a, b) in R is numerically equivalent to R (see Exercise 1). We may
prove easily, using Schroeder-Bernstein, that any subset X of R containing
an open interval is also numerically equivalent to R [note Exercise 7(a)],
no matter how complicated the structure of X might be.
Let us now apply the Schroeder-Bernstein theorem to the problem stated
immediately before Theorem 6.

THEOREM 7

R is numerically equivalent to the power set of N. In terms of cardinal numbers,

we have 2N0 = C.