Next: Countable sets Up: Finiteness09february2012 Previous: The number of elements

## Criteria for finiteness of a set

We relate sets to to decide finiteness.
• (Q)
Let be a non-empty set.
Then is finite if and only if there is an injection , but no surjection .
Suppose that the set is finite with elements, so there is a bijection .

Put .
Then is a composition of injections, so is an injection.

Next suppose that there is a surjection .
Put .
Then is well-defined and is a composition of surjections, so is a surjection.
But this violates the Pigeonhole Principle, theorem (L) above, so the map cannot exist as required.

Conversely, suppose that there is an injection , but no surjection .
We must prove that is finite.
Note that the map induces a bijection with so the set is finite if and only if is finite, so, without loss of generality, replacing by , we may assume that . So we need only prove the result:
• Let .
If there is no surjection from to , then is finite.
Using POW, we define a map from a subset of the integers to the set , recursively, by the formulas:
• , , , , . If now , we stop and .
• If instead , we define , , , , , . If now , we stop and .
• If instead , we define , , , , , , . If now , we stop and .
We continue in this vein as long as possible: the resulting recursion is well-defined and either goes on for ever or terminates at some point.
If the recursion terminates, after steps, we obtain a map , which is injective, since it is increasing.
Also the range of is .
So is a bijection and is finite, with elements.
If the recursion never terminates, we obtain a map , which is injective, since it is increasing.
We claim that is bijective.
Suppose is not surjective.
Then there is some , such that has no solutions, for .
Now , a property of the recursion, so . Also is false by definition of . So .
Let .
Then exists and since is bounded above by and below by . Then we have .
But since , this contradicts the definition of , since , for any , since is increasing, so that , so , so , a contradiction.
So is surjective, so bijective. So is a surjection from to , a contradiction. So the recursion must terminate and is finite, as required. Note that in the last part of this proof, we also proved here the result:
• (R)
If is an injection and if is not finite, then there is a bijection from to .
Next we give the "dual" version:
• (S)
Let be a non-empty set.
Then is finite if and only if there is a surjection , but no injection .
If is finite, with elements, then we may take , without loss of generality and then the map , defined above, gives a surjection from to . If there were also an injection from to , then the composition gives a well-defined map from to , which is an injection, since it is a composition of injections.
This contradicts the Pigeonhole Principle, so cannot exist.
Conversely we have to prove that if and there is a surjection but no injection , then is finite.
We begin by constructing an injection of into .
For any , define .
Then is well-defined by POW and , whence we have . This gives a well-defined map .
Now if for elements and of we have , then we have:

So is injective. By the previous theorem, if is not finite, then there is a bijection , so in particular an injection from to , a contradiction, so is finite and we are done.
Note that the last part of this proof also gives the theorem:
• (T)
Let be a non-empty set.
If there is a surjection and is not finite, then there is a bijection from to .
Finally we have the theorems (corollaries of the Pigeonhole Principle):
• (U)
Let be a non-empty set and , a map, which is an injection, but not a bijection. Then is not finite.
• (V)
Let be a non-empty set and , a map, which is a surjection, but not a bijection. Then is not finite.

Next: Countable sets Up: Finiteness09february2012 Previous: The number of elements
George A. J. Sparling 2012-02-09