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 pairs

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, $(u\in z)$ iff $(u=x$ or $u=y)$.

In more precise logical form:

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

$(u\in z)$ iff $(u=x$ or $u=y)$.

Definition Given two sets $A$ and $B$ we define the unordered pair of $A$ and $B$ to be the set containing precisely $A$ and $B$. We denote it $\{A,B\}$.

The pair axiom doesn't state that $A$ and $B$ have to be distinct. Consider the unordered pair $\{A,A\}$. The Axiom of Extensionality tells us that this is equal to the set $\{A\}$.

Example Let $A=B=\emptyset$. Then the axiom says that there is a set containing $A$ and $B$. This is the set $S=\{\emptyset ,\emptyset \}=\{\emptyset \}$. $\square$

The set $S$ in the example is distinct from the empty set, since $\emptyset$ is empty, whilst $S$ 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 $T=\{S,\emptyset \}=\{\{\emptyset \},\emptyset \}$ is a set distinct from both the empty set and the set $S$, 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

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 $A$ and $a,b\in A$, the ordered pair of $a$ and $b$, denoted $(a,b)$, is the set $\{\{a\},\{a,b\}\}$.

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

Theorem We have that $(a,b)=(c,d)$ if and only if $a=c$ and $b=d$.

Proof Clearly if $a=c$ and $b=d$ then

$\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}.$

(1)

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

Let us deal first with the case where $a\neq b$. In this case, $\{a\}\neq \{a,b\}$ and so $c\neq d$, otherwise $\{\{c\},\{c,d\}\}=\{\{c\},\{c,c\}\}=\{\{c\},\{c\}\}=\{\{c\}\}$ and we would have from (1) that $\{a\}=\{c\}=\{a,b\}$, which would be a contradiction.

But if $c\neq d$ then $\{c,d\}\neq \{a\}$ and so for the elements to be the same on both sides of (1), we must have $\{a\}=\{c\}$ and $\{a,b\}=\{c,d\}$. But the first of these implies that $a=c$. Thus $\{a,b\}=\{c,d\}=\{a,d\}$. As $a\neq b$, this implies $b=d$.

Now we deal with the case where $a=b$. In this case $\{\{a\},\{a,b\}\}=\{\{a\},\{a\}\}=\{\{a\}\}.$

Thus $\{c\}=\{a\}=\{c,d\}$. Thus $a=b=c=d$.

In both cases, $a=c$ and $b=d$. $\square$

Ordered tuples

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

Definition We define the ordered triple $(a,b,c)$ to be $(a,(b,c))$.

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

Definition We define the ordered $n$-tuple $(a_{1},a_{2},\ldots ,a_{n})$ to be $(a_{1},(a_{2},a_{3},\ldots ,a_{n}))$.

Exercises

• Show how to generate infinitely many distinct sets having just one element. Do the same for sets with two elements.
• Suppose $\{a\}=\{b,c\}$. Show that $b=c$.
• Show that if one defines ordered pairs by $(a,b)=\{\{\{a\},\emptyset \},\{\{b\}\}\}$ as Wiener did, then $(a,b)=(c,d)$ if and only if $a=b$ and $c=d$, 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.