Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 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 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 at 17:18
    
@Paze, it's just a different ordered pair –  GPerez Jan 13 at 17:18
3  
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 at 17:28

4 Answers 4

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.

share|improve this answer
    
You are quite correct. Without Regularity, the alternate ordered pair definition may fail. –  Cameron Buie Jan 13 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 at 17:45
1  
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 at 19:18
1  
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 at 21:20
1  
@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 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).

share|improve this answer

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.

share|improve this answer

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."

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.