Next: Relations: partial orders, equivalences Up: Finiteness09february2012 Previous: A surjection: ; the

## Cantor's Bijection Theorem

Cantor's Bijection Theorem is as follows:
• Let and be non-empty sets.
Let and be injections.
Then there is a bijection .
Proof:
We begin by remarking that, without loss of generality, we may assume that and are disjoint sets, since, otherwise, we may replace and by the sets and , respectively and then and there are bijections between and and between and .
• Given , an immediate ancestor for is an element of such that . Then is unique if it exists since is injective.
• Similarly given , an immediate ancestor for is an element of such that . Then is unique if it exists since is injective.
So given any we may form its chain of ancestors, with in and in , so that and , in each case going on for as long as possible. Then we may augment the chain with the recursion: for even and , , for odd and .

Similarly, given any we may form its chain of ancestors, with in and in , so that and . Then we may augment the chain with the recursion: for even and , , for odd and .
In this way every element of belongs to a unique chain, as does every element of .
Note that in such a chain, if we have a repetition, say , for some positive integer , where is as small as possible for the given chain (using POW), then is even and the chain is just a finite cycle consisting of the elements .
In this case every element of the chain has an immediate ancestor (necessarily unique, as usual).
In particular the immediate ancestor of is and the immediate ancestor of is , for . There are then four mutually exclusive possibilities for the chain that an element of may belong to.
• The chain may be a finite cycle, so possibly after relabeling takes the form , where and such that , for odd and for even and . Here belongs to for odd and belongs to for even.
• The chain may go on forever, without repetitions, so (possibly after a relabeling), gives a doubly infinite sequence such that for even and for odd, such that , for even and for odd and all the elements of the chain are distinct.
• The chain may stop at an element or of , for some integer .
This occurs when has no immediate ancestor.
Then after relabeling the sequence, we have an infinite (automatically non-repetitive) sequence , with , such that has no immediate ancestor and such that , for odd and for even.
In this case we say the chain is rooted in .
• The chain may stop at an element or of , for some integer .
This occurs when has no immediate ancestor.
Then after relabeling the sequence, we have an infinite (automatically non-repetitive) sequence , with , such that has no immediate ancestor and such that , for even and for odd.
In this case we say the chain is rooted in .
Then each element of belongs to exactly one of these chains, called the chain of . We are now in a position to define the map , which we want to be a bijection.
We choose to map each chain to itself.
So to check that is a bijection, we just need to construct an inverse for within each chain.
We will call the inverse map .
• If belongs to a chain which is a finite cycle , then for some (unique) integer , with and we define .
Then the inverse for for this chain maps any element of this chain to for .
Clearly and are well-defined and is the inverse of in this chain.
• If belongs to a doubly infinite chain , and , for some (unique) integer , we define .
The inverse then maps in this chain to .
Clearly and are well-defined and is the inverse of in this chain.
• If belongs to a chain rooted in , , then for some (unique) positive integer and we define .
The inverse maps for some positive integer , to .
Clearly and are well-defined and is the inverse of in this chain.
• If belongs to a chain rooted in , , then for some (unique) positive integer and we define .
The inverse maps for some positive integer , to .
Clearly and are well-defined and is the inverse of in this chain.
Putting the maps and together for all the chains, we obtain the desired bijections: and , with the inverse of and Cantor's Bijection Theorem is proved. Given sets and we say that if and only if there is an injection .
We say that if and only if there is a bijection .
Then Cantor's Bijection Theorem may be rephrased as:
• If and , then we have .
Also we have the relations, valid for any sets , , and :
• If and , then .
• If and , then .
• If and and , then
Finally we say that if but is false.
Then we have the properties, valid for any sets , , and :
• If then is false.
• If and , then .
• If and , then .
• If and , then .
• If and and , then

Next: Relations: partial orders, equivalences Up: Finiteness09february2012 Previous: A surjection: ; the
George A. J. Sparling 2012-02-09