If and are nonempty sets, then

, ,

mean which is injective, bijective, or surjective, respectively. We also define

,

to mean that an injection but no bijection, or a surjection but no bijection, from to . These relationships can be extended to the empty set by declaring that

and for all .

**Proposition.** iff .

Proof. : If is injective, pick an arbitrary and define by if , otherwise. Then is surjective.

: If is surjective, the sets are nonempty and disjoint, so any is an injection from to .

**Proposition.** For any sets and , either or .

Proof. Consider the set of all injections from subsets of to . The members of can be regarded as subsets of , so is partially ordered by inclusion. Applying Zorn’s Lemma, then has a maximal element , with domain and range . If and , then can be extended to an injection from to by setting , contradicting maximality. Hence either , in which case , or , in which case is an injection from to and .

**Proposition.** The Schroder-Bernstein Theorem. If and , then .

Proof. Let and be injections. Consider a point If , we form ; if , we form ; and so forth. Either this process can be continued indefinitely, or it terminates with an element of (perhaps itself), or it terminates with an element of . In these three cases we say that is in , , or ; thus is the disjoint union of , , and . In the same way, is the disjoint union of three sets , , and . Clearly maps onto and , whereas maps onto . Therefore, if we define by if and if , then is bijective.

**Proposition.** For any set , .

Proof. On the one hand, the map is an injection from to . On the other, if , let . Then , for if for some , any attempt to answer the question “Is ?” quickly leads to contradiction. Therefore cannot be surjective.

“Friendship with one’s self is all important, because without it one cannot be friends with anyone else in the world.” ~ Eleanor Roosevelt

To be continued tomorrow 🙂

References

1] Gerald B. Folland, *Real Analysis: Modern Techniques and Their Applications*, 2ed, page 6-7.

[2] Purpose Fairy’s 21-Day Happiness Challenge, http://www.jrmstart.com/wordpress/wp-content/uploads/2014/10/Free+eBook+-+PurposeFairys+21-Day+Happiness+Challenge.pdf.

### Like this:

Like Loading...