![](https://csdnimg.cn/release/download_crawler_static/10733185/bg14.jpg)
could think of a number as a sequence of nested boxes, the last of which is empty. The number of outer
boxes we need to open to reach the empty box is precisely the number n that the given singleton set in the
above sequence represents. Of course, if there are no outer boxes to be opened, we do not have a singleton
set but the empty set ∅, representing 0. This is a perfectly fine model of the natural numbers in set theory,
due to Zermelo (see [47], 199–215). But it has the drawback that in this representation the number n + 1 has
a single element. As we shall see shortly, there is an alternative representation of the natural numbers, due
to John von Neumann,
1
in which the natural number n is a set with exactly n elements. This is of course a
more appealing representation, particularly because it is the basis of a wonderful analogy (and more than
an analogy: a generalization!) between computing with numbers and computing with sets.
What about ordered pairs? For example, in the plane we can describe a point as an ordered pair (x, y)
of real numbers, corresponding to its coordinates. Can pairs of this kind be also represented in set theory?
The answer is yes. Following an idea of Kuratowski, we can define an ordered pair (x, y) as a special kind
of unordered pair by means of the defining equation
(x, y) = {{x}, {x, y}}.
The information that in the pair (x, y) x is the first element of the pair and y the second element is here
encoded by the fact that when x , y we have {x} ∈ (x, y), but {y} < (x, y), since {y} , {x} and we have a
proper inclusion {y} ⊂ {x, y}. Of course, when x = y we have (x, x) = {{x}, {x, x}} = {{x}, {x}} = {{x}}. That
is, the inclusion {y} ⊆ {x, y} becomes an equality iff x = y, and then x is both the first and second element of
the pair (x, x). For example, in the above, Zermelo representation of the natural numbers, the ordered pair
(1, 2) is represented by the unordered pair {{{∅}}, {{∅}, {{∅}}}}, and the ordered pair (1, 1) by the unordered
pair {{{∅}}, {{∅}, {∅}}} = {{{∅}}, {{∅}}} = {{{∅}}}, which is of course a singleton set.
A key property of ordered pairs is a form of extensionality for such pairs, namely, the following
Lemma 1 (Extensionality of Ordered Pairs). For any sets x, x
0
, y, y
0
, the following equivalence holds:
(x, y) = (x
0
, y
0
) ⇔ (x = x
0
∧ y = y
0
).
Proof. The implication (⇐) is obvious. To see the implication (⇒) we can reason by cases. In case x , y
and x
0
, y
0
, we have (x, y) = {{x}, {x, y}} and (x
0
, y
0
) = {{x
0
}, {x
0
, y
0
}}, with the subset inclusions {x} ⊂
{x, y} and {x
0
} ⊂ {x
0
, y
0
}, both strict, so that neither {x, y} nor {x
0
, y
0
} are singleton sets. By extensionality,
(x, y) = (x
0
, y
0
) means that as sets they must have the same elements. This means that the unique singleton
set in (x, y), namely {x}, must coincide with the unique singleton set in (x
0
, y
0
), namely {x
0
}, which by
extensionality applied to such singleton sets forces x = x
0
. As a consequence, we must have {x, y} = {x, y
0
},
which using again extensionality, plus the assumptions that x , y and x , y
0
, forces y = y
0
. The cases
x = y and x
0
, y
0
, or x , y and x
0
= y
0
, are impossible, since in one case the ordered pair has a single
element, which is a singleton set, and in the other it has two different elements. This leaves the case x = y
and x
0
= y
0
, in which case we have (x, x) = {{x}}, and (x
0
, x
0
) = {{x
0
}}. Extensionality applied twice then
forces x = x
0
, as desired.
One could reasonably wish to distinguish between the abstract concept of an ordered pair (x, y), and a
concrete representation of that concept, such as the set {{x}, {x, y}}. Lemma 1 gives strong evidence that this
particular choice of representation faithfully models the abstract notion. But we could choose many other
representations for ordered pairs (for two other early representations of ordered pairs, due to Wiener and to
Hausdorff, see [47] 224–227). One simple alternative representation is discussed in Exercise 3 (1). Further
evidence that the above definition provides a correct set-theoretic representation of ordered pairs, plus a
general way of freeing the abstract notion of ordered pair of any “representation bias,” is given in Exercise
29, and in §5.5 after that exercise.
Exercise 3 Prove the following results:
1. The alternative definition of an ordered pair as:
(x, y) = {{x, y}, {y}}
provides a different, correct representation of ordered pairs, in the sense that it also satisfies the extensionality
property stated in Lemma 1.
1
Yes, the same genius who designed the von Neumann machine architecture! This should be an additional stimulus for computer
scientists to appreciate set theory.
20