Mathematical Proof and the Principles of Mathematics/Sets/Pairs

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 pairsEdit

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 pairsEdit

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

 

 

 

 

 

(1)

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 tuplesEdit

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  .

ExercisesEdit

  • 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