# Ordered pair definition [duplicate]

Why is the ordered pair $(x,y)$ defined to be the set $\{\{x\},\{x,y\}\}$?

My book states that it is simply defined this way and then proceeds to perform a bunch of magic using this definition.

-

## marked as duplicate by Jack D'Aurizio, Shauna, Ian Coley, Michael Albanese, Jeremy RickardFeb 7 '15 at 21:41

For this question to not fall under the category 'too broad, I believe it is important you answer the question: why not? – Git Gud Jan 13 '14 at 17:11
The class I am in must have a prerequisite that I am not aware of. I don't understand what you mean by (x,y)=(x',y'). What is (x',y')? – Paze Jan 13 '14 at 17:16
What he meant with $x'$ is not an operation, it's just a different variable. You can replace $x'$ with $u$ and $y'$ with $v$, if you want. – Git Gud Jan 13 '14 at 17:18
Why didn't you search the site before asking? – Asaf Karagila Jan 13 '14 at 17:26
And a one and a two and a you know what to do and there are at least two more that I can't find in under five seconds, so I'm not going to bother looking for. – Asaf Karagila Jan 13 '14 at 17:28

The details of how ordered pairs are coded isn't important, except that:

1. You have to be able to show, using the axioms, that $(x,y)$ always exists and is unique. In other words, we need to make sure that the formation of ordered pairs is a genuine function.

2. It must be provable that ordered pairs have the following property.

$$(x,y)=(x′,y′) \rightarrow (x=x′∧y=y′).$$

Note that the converse of the above statement is immediate, simply from the fact that $x,y \mapsto (x,y)$ is a function.

The definition given (namely, Kuratowski's) does an admirable job of both 1 and 2, thus it is the standard definition of ordered pair in material set theory.

Now if you're wondering why Kuratowski's definition satisfies condition $2$, I can explain it this way. An unordered pair can be defined as a set $\{x,y\}$. So all that's missing is a distinguished "first" element. So we pick one, call it $x$, and thus "define" that $(x,y)$ equals "$\{x,y\}$ together with $x$."

But what does "together with" mean? After a bit of thought, we see that the smoothest way to formalize this is to define $(x,y) = \{\{x\},\{x,y\}\}$.

Actually, you might try defining $(x,y) = \{x,\{x,y\}\},$ but this turns out to have some technical issues. In particular, to prove that this definition gives us property 2, we need to appeal to a pretty serious axiom, called the Axiom of Regularity. To avoid this technicality, Kuratowski's definition is best.

As a final comment (thanks to MJD), note that the "reverse" convention (whereby we distinguish the second term as opposed to the first) works equally as well. Namely: $$(x,y)=\{\{y\},\{x,y\}\}.$$

It doesn't matter that we've reversed the order, because we've still successfully coded which term comes first, and therefore property 2 can still be proven.

-
You are quite correct. Without Regularity, the alternate ordered pair definition may fail. – Cameron Buie Jan 13 '14 at 17:43
@CameronBuie, thanks! I gave you a +1, by the way, for actually proving that "Condition 2" as I call it follows from Kuratowski's definition. Something I should have done (but it slipped my mind). – goblin Jan 13 '14 at 17:45
It might also be worth mentioning that the definition $(x,y) = \{\{y\}, \{x, y\}\}$ works just as well, or similarly you could use $\{\{\{a\},\varnothing\},\{\{b\}\}\}$ as Norbert Wiener did. – MJD Jan 13 '14 at 19:18
It can be hard to identify something as an ordered pair using this definition, however. For example $(1,1) = \{\{1\}\}$, since $\{\{1\},\{1,1\}\} = \{\{1\},\{1\}\} = \{\{1\}\}$. This is why I think it is more honest to talk about products categorically. – Steven Gubkin Jan 13 '14 at 21:20
@StevenGubkin, yes agreed, and problems like this actually show up, and its really annoying. For example, the free magma on a set $A$ can be described concretely as the least superset $X$ of $A$ such that if $x,y \in X$, then $(x,y) \in X$. The operation is just $xy = (x,y)$. Well, that's what we'd like to say, except that it doesn't really work; because, what if $A=\{a,b\}$ has the property that b=(a,a)? Then $b=a^2$ in the magma $X$, which is not at all what we want! – goblin Jan 13 '14 at 21:28

It is solely to show that for any $x,y,$ a set $(x,y)$ exists meeting the qualities that we want an ordered pair to have: namely, that ordered pairs are equal if and only if their respective components are equal. Once the existence of such pairs is proved, there is no need to adhere to that specific definition any longer. Other definitions are sometimes given, but the Kuratowski ordered pair makes proving existence and the desired properties very simple (only Extensionality and Pairing are necessary), so tends to be used over other options.

Indeed, take any $x,y.$ By Pairing, $\{x,y\}$ exists, as does $\{x,x\}.$ Then by Extensionality, $\{x,x\}=\{x\},$ so again by Pairing, $\bigl\{\{x\},\{x,y\}\bigr\}$ exists.

Now, suppose $\bigl\{\{x\},\{x,y\}\bigr\}=\bigl\{\{u\},\{u,v\}\bigr\}.$ It can be readily shown by Extensionality that $\{x\}=\{x,y\}$ if and only if $x=y.$ In the case $x=y,$ we then have $\bigl\{\{x\}\bigr\}=\bigl\{\{u\},\{u,v\}\bigr\},$ so by Extensionality, $\{u\}=\{x\}$ (so $u=x$ by Extensionality) and $\{u,v\}=\{x\}$ (so $v=x=y$ by Extensionality). In the case $x\ne y,$ we cannot have $\{u\}=\{x,y\}$ (since we cannot have both $u=x$ and $u=y$), so we must have $\{u\}=\{x\}$ (so $u=x$ by Extensionality) and $\{x,y\}=\{u,v\}$ (so $v=y$ by a few applications of Extensionality).

-

This is not a definition, it's a "representation as a set". You can live with unrepresented pairs, like you do in category theory, but then you won't be able also to represents functions and relations, and you will loose all the goodies that come with set theory.

Any representation would be good as long as you can extract "first" and "second" with a function defined in set theory. All that "bunch of magic" would work exactly the same.

-

One goal of set theory was to define all of math in terms of sets (where a set is a primitive notion, i.e., is not defined). As others have pointed out, this definition exists simply to show that it is possible to define an ordered pair, with all the properties that you'd want, in terms of sets. Wiener gave the first definition of an ordered pair in terms of sets, but Kuratowski's is more "elegant."

-

The definition of the ordered pair states that $(x,y)$ is an object with $x$ as its first and $y$ as its second component. Two ordered pairs are considered equal if the following holds:

$$(x,y) = (x',y') \leftrightarrow (x = x' \wedge y = y').$$

In order to show that $\{ \{x\}, \{x,y\}\}$ is an equivalent representation of an ordered pair, it is sufficient to prove that it obeys the above given property.

According to the axiom of pair set, the collection $\{ \{x\}, \{x,y\}\}$ is indeed a set. Two sets are equal iff every element of one set is element of the other set and vice versa: $$\{ \{ x \}, \{ x, y \} \} = \{ \{ x' \}, \{ x', y' \} \} \leftrightarrow (\forall z) \: z \in \{ \{ x \}, \{ x, y \} \} \leftrightarrow z \in \{ \{ x' \}, \{ x', y' \} \}. \text{ (1)}$$ Since $\{ \{ x \}, \{ x, y \} \}$ is, according to the pair set axiom, a set, we also have $$z \in \{ \{ x \}, \{ x, y \} \} \leftrightarrow z = \{ x \} \vee z = \{ x, y \}.$$ Inserting this identity into (1) yields $$(\forall z) \: z = \{ x \} \vee z = \{ x, y \} \leftrightarrow z = \{ x' \} \vee z = \{ x', y' \},$$ or, equivalently, $$(\forall z) \: (z = \{ x \} \vee z = \{ x, y \} \rightarrow z = \{ x' \} \vee z = \{ x', y' \}) \wedge (z = \{ x \} \vee z = \{ x,y \} \leftarrow z = \{ x' \} \vee z = \{ x',y' \}). \text{ (2)}$$ If $x = y$, (1) requires that $$(\forall z) \: z \in \{ \{ x \} \} \leftrightarrow z \in \{ \{ x' \}, \{ x', y' \} \}.$$ In this case the equivalence holds iff $x' = y'$ such that $x = x'$ and $y = y'$.

If $x \neq y$, (2) yields two implications for the 1st clause of the conjunction: $$z = \{ x \} \rightarrow z = \{ x' \} \vee z = \{ x', y' \},$$ $$z = \{ x,y \} \rightarrow z = \{ x' \} \vee z = \{ x', y' \}.$$ Since for two sets to be equal they need to have the same number of elements, the last two implications reduce to $$z = \{ x \} \rightarrow z = \{ x' \}, \text{ (3)}$$ $$z = \{ x,y \} \rightarrow z = \{ x', y' \}. \text{ (4)}$$ From (3) we have that $x = x'$ while (4) requires that $$\{ x,y \} = \{ x', y' \} \stackrel{(3)}{\longrightarrow} \{ x,y \} = \{ x, y' \} \rightarrow y = y'.$$ Summarizing the above yields $$\{ \{ x \}, \{ x, y \} \} = \{ \{ x' \}, \{ x', y' \} \} \leftrightarrow (x = x' \wedge y = y').$$ $\Box$

-