Next: Injections into Up: Finiteness09february2012 Previous: Finiteness09february2012

Preamble; the switching map , the maps and

We assume basic properties of the positive integers .
In particular we assume the Well Ordering Principle, POW:
• Let .
Then either , or has a least element.
For , denote by the set:

For the proofs below we need a switching map which will place certain elements of a set into a desired position.
We have need only of the following switching map , which is defined for any and for any and which maps to itself.
Then is given by the formula:

It is clear that is well-defined, and is its own inverse: we have . In particular, is bijective, injective and surjective.
Note that is defined even if , in which case we have , the identity map.
It follows also that if and are maps into , such that , then we have, using the associativity of composition:

Also for the proofs below we need the properties:
• The composition of injections is an injection.
• The composition of surjections is a surjection.
• The composition of bijections is a bijection.
For each positive integer , we can inject into and surject onto as follows (there is no unique way to do this):
• For each , define a map by the formula: , defined for any . Then is well-defined and is an injection.
• For each , define a map by the formula , for any and , for any integer .
Then the map is well-defined and is a surjection.
Note that and , for each .

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