Discrete Mathematics

---------------------------'COMBINATORICS

261

8.9

SCHRODER-BERNSTEIN THEOREM

If

the sizes

of

two sets are each less than

or

equal to the other, then the sets are the same size. In other words,

the "smaller than" relation is symmetric, at least on finite sets. We would not be happy with our interpretation

of

"smaller than" unless it was symmetric on infinite sets as well as finite ones, and it is.

We have been interpreting

"A

is smaller than B"as A inj

B.

So we can formulate the symmetry property

precisely as:

Theorem (Schroder-Bernstein)

[A

inj

Band

B inj

A]

iff

A inj

B.

The direct proof

of

the previous theorem depends heavily on properties ...