Perhaps the most intuitive definition of finiteness as a property of sets is that a set is finite if and only if its cardinality is a natural number. Unfortunately, the most intuitive definition of the natural numbers, at least to me, is that the natural numbers are the cardinalities of finite sets. Therefore, in order to define both of these notions properly, one of these definitions must be altered. I think the most natural one to alter is the definition of finiteness, since, at least to me, finiteness seems like a more fundamental notion than the notion of the natural numbers.
The alternative definition which I’m most satisfied with is Kuratowski’s, given below. The essential idea behind it is that finite sets are sets that can be formed from the empty set by making a finite number of adjoinments (i.e. additions of a single object). The formal statement may seem a little peculiar if you haven’t seen this kind of definition before.
Definition 1 For every set , is Kuratowski finite if and only if it is a member of every family of sets such that and for every member of and every object , .
The key thing to notice here is that it immediately follows from the definition that a variant of mathematical induction can be performed on Kuratowski finite sets. Suppose you wish to prove that every Kuratowski finite set has a certain property. Well, if you let be the family of all sets with the property, you can see from the definition that one way to do this is to show that has the property (i.e. ) and that if you adjoin an object to a set with the property, it will still have the property (i.e. for every member of and every object , ). Definitions similar to the one above turn up in quite a few places in mathematics, and they are always associated with a principle of induction. For example, consider the definition of the subgroup generated by a subset of a group . The intuitive definition of this subgroup is that it is the set of all objects of the form , where is a natural number and , , … and are members of or inverses of members of . However, this definition can be awkward to work with and it is complex to state as a logical formula (it involves a quantification over all finite sets). Alternatively, one can define this subgroup as the intersection of all subgroups of such that . The corresponding principle of induction is that if every member of has a certain property, and the set of all members of the group with the property is a subgroup of , then every member of the subgroup generated by has the property too.
I should note that this definition is not possible in ZF: must be allowed to range over proper classes as well as sets, because for every possible value of , we have that for every object , , so is a superclass of the class of all singletons, which is proper by the axiom of replacement, since is an injection. Quantifiers can only range over sets in ZF. However, a minor amendment makes the definition possible in ZF: we can just require to be a member of . It can be proven that this amended definition (definition 2) is equivalent to the definition as stated above (definition 1).
Proof: Suppose is a finite set by definition 2 and is a family of sets such that and for every member of and every object , . Every member of is an object, so for every member of , , which means is a member of (by definition 2). Therefore, is finite by definition 1 as well.
As for the converse, well, is clearly finite by definition 2. Now, suppose is a finite set by definition 2, is an object and is a family of sets such that and for every member of and every member of , . Since is finite by definition 2, , and since is a member of , that means . Therefore, is finite by definition 2 as well. It follows by the principle of induction on finite sets by definition 1 that every set which is finite by definition 1 is finite by definition 2 as well.
The reason I’ve chosen definition 1 is that it is easier to see the idea behind the definition.
Of course, we must ensure that Kuratowski finiteness is actually equivalent to ordinary finiteness. Since we can induct over natural numbers and we can induct over Kuratowski finite sets, the proof is straightforward.
Proof: . Suppose is a finite set, and is an object. What is ? Well, there is a bijection from to , and it is easy to see that the extension of to such that is a bijection onto . Therefore, is . This completes the proof that the cardinality of every Kuratowski finite set is a natural number, i.e., every Kuratowski finite set is finite.
The only set whose cardinality is 0 is , which is Kuratowski finite. Suppose is a natural number, every set whose cardinality is is Kuratowski finite, is a set and . Then there is a bijection from to . Let be . It is easy to see that the restriction of to is a bijection onto , so . Therefore, is Kuratowski finite. It follows that is Kuratowski finite as well. This completes the proof that every finite set is Kuratowski finite.
The other commonly-seen definition of finiteness is due to Dedekind. The main advantage of this definition is that it is somewhat simpler to state than Kuratowski’s.
Definition 2 For every set , is Dedekind finite if and only if for every proper subset of , .
It is probably possible to prove that every finite set is Dedekind finite by induction, but an easer way to prove this is to prove the contrapositive, that every Dedekind infinite set is infinite. This proof uses the fact that for every set , is infinite if ( is the cardinality of ), since for every natural number , so .
Proof: Suppose is a Dedekind infinite set, so there is a proper subset of such that . Since , there is a member of ; since , there is a bijection from to . Consider the infinite sequence , , , … We can show by induction that this sequence is an injection, so , and therefore, since is infinite, is infinite.
- For every positive integer , , so , which means since .
- Suppose is an integer and for every integer such that , . Then for every integer such that , , so , which means , since is bijective.
Now, if the converse of the fact we used holds, i.e. for every infinite set , , then we can prove the converse: that every infinite set is Dedekind infinite. The proof relies on the fact that has the same cardinality as its proper subset .
Proof: Suppose is an infinite set. Then , so there is an injection from to . Let be the image of under . Then , so is infinite, but is a proper subset of , since .
The problem with Dedekind’s definition is that one runs into trouble when one tries to prove that for every infinite set , , in ZF. The proof can be done easily using the axiom of choice.
Proof: Suppose is an infinite set. If the axiom of choice holds, there is a function on such that for every non-empty subset of , . Let be the sequence such that for every natural number , (this is always defined, because if , , so , which means is finite). It is clear that is an injection into , so .
This doesn’t necessarily mean that the statement is independent of ZF, but certainly it suggests the possibility, since there is no obvious way to amend this proof so that it does not require the axiom of choice.
Perhaps there is another way we could prove that every infinite set is Dedekind infinite? Unfortunately there isn’t, because if every finite set is Dedekind infinite, then for every infinite set , there is a proper subset of such that , so there is a member of , and is infinite too, so there is a proper subset of such that , so there is a member of , and so on. This allows us to construct an injective sequence of members of , so .
Ideally, I would finish off here with a proof that the statement is independent. Unfortunately, I don’t know how to do this. It may be possible to derive the axiom of choice from the fact that every infinite set is Dedekind infinite, in which case this fact cannot be a theorem of ZF (otherwise the axiom of choice would be a theorem of ZF, and the axiom of choice is known to be independent of ZF). On the other hand, this may not be true, in which case I’m not sure what the best way to prove independence would be. The most straightforward way would be to construct a model of ZF in which there are Dedekind finite infinite sets, but I don’t know how you might go about doing that.