Next: Surjections from Up: Finiteness09february2012 Previous: Preamble; the switching map

## Injections into

We prove the following results:
• (A)
Let a non-empty set be given.
Suppose that there exists an , and an injection .
Then either is a bijection, or and there exists an injection .
Proof:
If , then and any map from a non-empty set to is automatically surjective, so is a bijection and we are done.
So we may assume that and that is not a bijection, since otherwise we are done.
We need to construct the injective map .
Since is not surjective there exists , such that .
Pick such a and define the map by the composition: .
Since is a bijection and an injection, is an injection also.
Since is its own inverse, we have: .
Suppose that some exists such that .
Then we have:

So , a contradiction, so .
So .
So the map restricts to a well-defined map from to and being injective as a map from to is automatically injective also as a map from and we are done.

By the Well Ordering Principle, we have the following corollary:
• (B)
Let be a non-empty set and an injection, for some .
Then either is a bijection, or and there exists , with and a bijection .
Proof:
Here is the least integer such that an injection exists.
Then is bijective, since otherwise we could lower the integer , by (A).

Next: Surjections from Up: Finiteness09february2012 Previous: Preamble; the switching map
George A. J. Sparling 2012-02-09