Next: The proof of Cantor's Up: Finiteness09february2012 Previous: Relations: partial orders, equivalences

## The equivalence relation of an injection

For the proof of Cantor's Bijection Theorem, we study the equivalence relation generated by an injection.
So let be a non-empty set and let be an injection.
Regard as a subset of , so is a relation on and denote by the equivalence relation determined by .
• We have the formula:

Proof:
Write .
Then it is clear from the definition of that .
Also it is clear that .
Since we have that is the smallest equivalence relation continuing , we just have to show that is itself an equivalence relation.
It is clear that is symmetric and reflexive, so we just have to show that is transitive.
Since is symmetric and reflexive, to prove transitivity, it suffices to show that and , whenever , and are pairwise distinct elements of (i.e. , and ).
So here it suffices to show that if we have and , with , and pairwise distinct, then .
To prove this, first note that if and only if , where is the ordinary -fold composition of with itself; also note that is an injection.
Similarly if and only if . So now we have four cases to consider:
• and , for some and in .
Then and , so we get .
• and , for some and in .
Then and , so , so we get .
• and , for some and in .
Then and .
Also , since otherwise, by the injectivity of we would get , contrary to hypothesis.
• If , then , so we get , since is injective, so .
• If , then , so we get , since is injective, so .
• and , for some and in .
Then and .
Again we have , since otherwise , contrary to hypothesis.
• If , then , so we get .
• If , then , so we get .
In all cases we find that and we are done, is an equivalence relation, so .

Now we see that for and in , we have if and only if if and only if either , or , or , for some integer .
So we have that the equivalence class of is:

Note that : if , then , since:
• If , then .
• If , with , then .
• If , with , then if , we have , so ; alternatively, if we have with , so .
Also we have : if , for some , then , since:
• If , then , so
• If , for , then, if , we have , since is injective; alternatively, if , we have , so and ; in either case, we have .
• If , for , then we have , so .
We now make the following definition:
• A progenitor for an equivalence class , for is an element , such that no exists with .
Note that an equivalence class may not have a progenitor.
If an equivalence class has a progenitor , either , or , for some , since , with is impossible (since either , so , a contradiction, or , so , again a contradiction).
So the equivalence classes with a progenitor take the form:

(In particular the progenitor of any equivalence class is unique, if it exists).
If an equivalence class does not have a progenitor then the restriction of to the equivalence class is a bijection, since the restriction is both injective and surjective.

Next: The proof of Cantor's Up: Finiteness09february2012 Previous: Relations: partial orders, equivalences
George A. J. Sparling 2012-02-09