3  Unordered Pairs

For all that has been said so far, we might have been operating in a vacuum. To give the discussion some substance, let us now officially assume that

\[ \mathit{there\ exists\ a\ set.} \]

Since later on we shall formulate a deeper and more useful existential assumption, this assumption plays a temporary role only. One consequence of this innocuous seeming assumption is that there exists a set without any elements at all. Indeed, if \(A\) is a set, apply the axiom of specification to \(A\) with the sentence “\(x \neq x\)” (or, for that matter, with any other universally false sentence). The result is the set \(\{x \in A: x \neq x\}\), and that set, clearly, has no elements. The axiom of extension implies that there can be only one set with no elements. The usual symbol for that set is

\[ \emptyset; \]

the set is called the empty set.

The empty set is a subset of every set, or, in other words, \(\emptyset \subset A\) for every \(A\). To establish this, we might argue as follows. It is to be proved that every element in \(\emptyset\) belongs to \(A\); since there are no elements in \(\emptyset\), the condition is automatically fulfilled. The reasoning is correct but perhaps unsatisfying. Since it is a typical example of a frequent phenomenon, a condition holding in the “vacuous” sense, a word of advice to the inexperienced reader might be in order. To prove that something is true about the empty set, prove that it cannot be false. How, for instance, could it be false that \(\emptyset \subset A\)? It could be false only if \(\emptyset\) had an element that did not belong to \(A\). Since \(\emptyset\) has no elements at all, this is absurd. Conclusion: \(\emptyset \subset A\) is not false, and therefore \(\emptyset \subset A\) for every \(A\).

The set theory developed so far is still a pretty poor thing; for all we know there is only one set and that one is empty. Are there enough sets to ensure that every set is an element of some set? Is it true that for any two sets there is a third one that they both belong to? What about three sets, or four, or any number? We need a new principle of set construction to resolve such questions. The following principle is a good beginning.

Axiom 3.1 (Axiom of pairing) For any two sets there exists a set that they both belong to.

Note that this is just the affirmative answer to the second question above.

To reassure worriers, let us hasten to observe that words such as “two,” “three,” and “four,” used above, do not refer to the mathematical concepts bearing those names, which will be defined later; at present such words are merely the ordinary linguistic abbreviations for “something and then something else” repeated an appropriate number of times. Thus, for instance, the axiom of pairing, in unabbreviated form, says that if \(a\) and \(b\) are sets, then there exists a set \(A\) such that \(a \in A\) and \(b \in A\).

One consequence (in fact an equivalent formulation) of the axiom of pairing is that for any two sets there exists a set that contains both of them and nothing else. Indeed, if \(a\) and \(b\) are sets, and if \(A\) is a set such that \(a \in A\) and \(b \in A\), then we can apply the axiom of specification to \(A\) with the sentence “\(x = a \mathit{\ or\ } x = b\).” Conclusion:

\[ \{ x \in A: x = a \mathit{\ or\ } x = b \}, \]

and that set, clearly, contains just \(a\) and \(b\). The axiom of extension implies that there can be only one set with this property. The usual symbol for that set is

\[ \{ a, b \}; \]

the set is called the pair (or, by way of emphatic comparison with a subsequent concept, the unordered pair) formed by \(a\) and \(b\).

If, temporarily, we refer to the sentence “\(x = a \mathit{\ or\ } x = b\)” as \(S(x)\) , we may express the axiom of pairing by saying that there exists a set \(B\) such that

\[ x \in B \text{ \textit{if and only if} } S(x). \tag{3.1}\]

The axiom of specification, applied to a set \(A\), asserts the existence of a set \(B\) such that

\[ x \in B \mathit{\ if\ and\ only\ if\ } (x \in A \mathit{\ and\ } S(x)). \tag{3.2}\]

The relation between Equation 3.1 and Equation 3.2 typifies something that occurs quite frequently. All the remaining principles of set construction are pseudo-special cases of the axiom of specification in the sense in which Equation 3.1 is a pseudo-special case of Equation 3.2. They all assert the existence of a set specified by a certain condition; if it were known in advance that there exists a set containing all the specified elements, then the existence of a set containing just them would indeed follow as a special case of the axiom of specification.

If \(a\) is a set, we may form the unordered pairs \(\{a, a\}\). That unordered pair is denoted by

\[ \{ a \} \]

and is called the singleton of \(a\); it is uniquely characterized by the statement that it has \(a\) as its only element. Thus, for instance, \(\emptyset\) and \(\{ \emptyset \}\) are very different sets; the former has no elements, whereas the latter has the unique element \(\emptyset\). To say that \(a \in A\) is equivalent to saying that \(\{a\} \subset A\).

The axiom of pairing ensures that every set is an element of some set and that any two sets are simultaneously elements of some one and the same set. (The corresponding questions for three and four and more sets will be answered later.) Another pertinent comment is that from the assumptions we have made so far we can infer the existence of very many sets indeed. For examples consider the sets \(\emptyset, \{ \emptyset \}, \{ \{ \emptyset \} \}, \{ \{ \{ \emptyset \} \} \}\), etc.; consider the pairs, such as \(\{ \emptyset, \{ \emptyset \} \}\), formed by any two of them; consider the pairs formed by any two such pairs, or else the mixed pairs formed by any singleton and any pair; proceed so on ad infinitum.

Exercise 3.1 Are all the sets obtained in this way distinct from one another?

Before continuing our study of set theory, we pause for a moment to discuss a notational matter. It seems natural to denote the set \(B\) described in Equation 3.1 by \(\{x: S(x)\}\); in the special case that was there considered

\[ \{ x : x = a \mathit{\ or\ } x = b \} = \{ a,b \}. \]

We shall use this symbolism whenever it is convenient and permissible to do so. If, that is, \(S(x)\) is a condition on \(x\) such that the \(x\)’s that \(S(x)\) specifies constitute a set, then we may denote that set by

\[ \{ x : S(x) \}. \]

In case \(A\) is a set and \(S(x)\) is \((x \in A)\), then it is permissible to form \(\{x: S(x)\}\); in fact

\[ \{ x : x \in A \} = A. \]

If \(A\) is a set and \(S(x)\) is an arbitrary sentence, it is permissible to form \(\{ x : x \in A \mathit{\ and\ } S(x) \}\); this set is the same as \(\{x \in A: S(x) \}\). As further examples, we note that

\[ \{ x : x \neq x \} = \emptyset \]

and

\[ \{ x : x = a \} = \{ a \}. \]

In case \(S(x)\) is \((x \notin x)\), or in case \(S(x)\) is \((x = x)\), the specified \(x\)’s do not constitute a set.

Despite the maxim about never getting something for nothing, it seems a little harsh to be told that certain sets are not really sets and even their names must never be mentioned. Some approaches to set theory try to soften the blow by making systematic use of such illegal sets but just not calling them sets; the customary word is “class”. A precise explanation of what classes really are and how they are used is irrelevant in the present approach. Roughly speaking, class may be identified with a condition (sentence), or, rather, with the “extension” of a condition.