Next: Definition of finiteness Up: Finiteness09february2012 Previous: Injections into

Surjections from

• (C)
Let a non-empty set be given.
Suppose that there exists, for some a surjection .
Then either is a bijection, or and there exists a surjection .

Proof:
If , then and any map from to any non-empty set has range a single element, so if the map is surjective, must be a one-element set, in which case the map is also injective so is bijective and we are done.
So henceforth we may assume that and that is not a bijection, since otherwise we are done.
Since is not a bijection, is not injective, so there exist and in such that and yet , say, where .
Define the map by the composition .
Then since is a bijection, the map , being a composition of surjections, is a surjection.
Note that we have and , say, where and , since and is injective.
So and .
Now the map obeys and .
Define as the restriction to of the map .
Then since and and , we see that:

So is a surjection and we are done.

Then, by POW, we have the corollary:
• (D)
Let a non-empty set be given.
Suppose that there exists, for some a surjection .
Then either is a bijection, or and there exists a positive integer and a bijection .

Proof:
Here is the least integer such that an surjection exists.
Then is bijective, since otherwise we could lower the integer , by (C).

Next: Definition of finiteness Up: Finiteness09february2012 Previous: Injections into
George A. J. Sparling 2012-02-09