Mathematical Proof and the Principles of Mathematics/Sets/Pairs

From Wikibooks, open books for an open world
Jump to navigation Jump to search

So far, the only set we've actually proved to exist is ∅. The next axiom allows us to create new sets from existing sets, so starting with ∅ we can build up an infinite number of new sets.

Unordered pairs[edit]

The Axiom of Pairs basically says that if we have two sets, x and y, then we can form the new set {x. y}. You may be wondering why we don't start with singletons, but since {x, x} = {x}, the axiom also forms singletons at the same time. As with the Axiom of Existence, the Axiom of Pairs really only says that there is some set whose elements are x and y, but we need to prove uniqueness before defining the notation.

Informally, the axiom states:

If x and y are sets (not necessarily distinct) then there exists a set z such that for all u, iff or .

In more precise logical form:

Axiom S3 (Axiom of pairs): For all 'x' and 'y', for some z, for all u,
iff or .

Definition Given two sets and we define the unordered pair of and to be the set containing precisely and . We denote it .

The pair axiom doesn't state that and have to be distinct. Consider the unordered pair . The Axiom of Extensionality tells us that this is equal to the set .

Example Let . Then the axiom says that there is a set containing and . This is the set .

The set in the example is distinct from the empty set, since is empty, whilst contains the empty set as an element. Thus the two sets contain different elements.

Of course we can continue to create new sets using the pair axiom. For example is a set distinct from both the empty set and the set , and so on.

In fact we can create infinitely many different sets using this process. However, each such set contains either one or two elements.

Ordered pairs[edit]

If sets are always unordered, one might wonder how one defines ordered mathematical objects in terms of sets. The following ingenious definition of an ordered pair is due to Kuratowski.

Definition Given a set and , the ordered pair of and , denoted , is the set .

The following theorem shows that ordered pairs have the properties we expect them to have.

Theorem We have that if and only if and .

Proof Clearly if and then






To show the converse, suppose that (1) holds.

Let us deal first with the case where . In this case, and so , otherwise and we would have from (1) that , which would be a contradiction.

But if then and so for the elements to be the same on both sides of (1), we must have and . But the first of these implies that . Thus . As , this implies .

Now we deal with the case where . In this case

Thus . Thus .

In both cases, and .

Ordered tuples[edit]

We can use Kuratowski's definition of an ordered pair to define an ordered triple.

Definition We define the ordered triple to be .

Obviously we can extend the definition to -tuples for any .

Definition We define the ordered -tuple to be .


  • Show how to generate infinitely many distinct sets having just one element. Do the same for sets with two elements.
  • Suppose . Show that .
  • Show that if one defines ordered pairs by as Wiener did, then if and only if and , just as for Kuratowski's definition.
  • Given Kuratowski's definition of an ordered pair, show that an ordered triple as defined above is a set containing either one or two elements.

Sets elements and subsets · Union and intersection