I was very careful in the discussion above not to refer to the set of natural numbers, just to natural numbers. We have criteria, at least with the particular representation chosen, for determining whether something is a natural number, whether one natural number is the sum, difference or product of two other natural numbers, etc. Do we have a set of natural numbers though? We can write down a Boolean expression with a single free variable which evaluates to true if and only if a natural number, in our chosen representation, is substituted for all free occurrences of that variable. The Axiom of Separation, though, doesn’t allow us to get sets from Boolean expressions; it only allows us to get subsets of a given set from them. Do we have a set which is large enough to contain at least the natural numbers, so that we then use Separation to find a set with the natural numbers and only the natural numbers?
With the axioms above we have no way to prove the existence of an infinite set. Extensionality doesn’t give us any sets; it just says when two sets are equal. The axiom of elementary sets produces only finite sets, and in fact only sets with at most two elements. Separation gives us subsets of existing sets. We’ve already seen that subsets of finite sets are finite, so this axiom can’t give us an infinite set unless we already have one. We’ve also seen that power sets of finite sets are finite, so that axiom also can’t give us an infinite set unless we already have one. The same is true of the Axiom of Union. Adding the Axiom of Replacement wouldn’t help either since it’s not difficult to show that functions with finite domains are finite.
We have a number of things though which, if they are sets, must be infinite. One is the natural numbers. If the natural numbers are a set then the set pairs \({ ( x , y ) }\) with \({ x ≤ y }\) is a partially ordered set with no greatest element. We’ve already seen that any partial order on a finite set has a greatest element, so the natural numbers can’t be a finite set.
You might object that I’ve used the set of natural numbers in examples. Examples are meant to guide your intuition though so I sometimes presuppose things we don’t yet know to be true. I’ve been careful to confine the natural numbers to examples though and not to use the existence of such a set in proving theorems.
Another set which, if is exits, must be infinite is that set of lists of items in a given non-empty set \({ A }\). Any set which contains all such lists must be infinite, which we can see as follows.
Suppose \({ A }\) is a non-empty set and \({ B }\) is a set which contains all lists whose items are members of \({ A }\). We can write down a Boolean expression which identifies which elements of \({ B }\) are actually lists all of whose items are members of \({ A }\) so we can use Separation to conclude that there is a set \({ C }\) whose members are precisely such lists. \({ A }\) is non-empty, so there is an \({ x ∈ A }\). Let \({ F }\) be the set of pairs of lists \({ ( D , E ) }\) where \({ E }\) is the list obtained by appending \({ x }\) onto \({ D }\). Then \({ F }\) is an injective function from \({ C }\) to itself. It is not surjective because the empty list \({ ∅ }\) is not in its range. But we’ve already shown that every injective function from a finite set to itself is surjective, so \({ C }\) cannot be finite. Subsets of finite sets are finite so \({ B }\) can’t be finite either.
I introduced a notation earlier for the set of such lists. \({ [ L A ] }\) denotes the lists all of whose elements are members of \({ A }\). The existence of a notation for a set doesn’t imply the existence of that set though, in much the same way that having a notation for the difference of two natural numbers doesn’t imply that this difference exists for all pairs of natural numbers.
There are a number of ways to get infinite sets but all of them involve introducing some new axiom. We could just introduce an axiom saying that there is an infinite set. This turns out not to be sufficient to establish the existence of all the infinite sets that we want. The usual procedure is to introduce an axiom establishing the existence of one particular infinite set which is in some sense large enough. We can, for example, use \({ L \{ ∅ \} }\) for this purpose. As we saw, this is essentially the same as the set of natural numbers.
Once we have one infinite set it’s fairly easy to get others, if we have the Axiom of Replacement. We can, for example, show the existence of \({ L A }\) for any set \({ A }\). It’s not terribly difficult to write down a Boolean expression which characterises \({ L A }\) in the sense that it has one free variable and evaluates to true if and only if the thing substituted for that variable is a list all of whose elements are members of \({ A }\). By itself this isn’t enough to show that \({ L A }\) exists since Separation only allows us to construct subsets of a given set from Boolean expressions. What we can do though is to construct another Boolean expression expression the fact that two lists are of equal length. Combining these two expressions we can write down a Boolean expression with two free variables which evaluates to true if and only if the first variable is a member of \({ L \{ ∅ \} }\), i.e. a list all of whose elements are \({ ∅ }\)’s and whose second variable is the set of all lists of members of \({ A }\) of length equal to the list in the first variable. Applying Replacement gives a function from \({ L \{ ∅ \} }\) to the sets of lists of members of \({ A }\) of equal length. As the range of a function this is a set. Applying Union we finally get the set \({ L A }\). This is actually the only time we will apply Replacement.
Motivated by the considerations above we’ll take the following as an axiom: