# How can an ordered pair be expressed as a set?

My book says $$(a,b)=\{\{a\},\{a,b\}\}$$

I have been staring at this for a bit and it is not making since to me. I have read several others posts on this, but none made any sense to me.

For example, Definition of an Ordered Pair

Based on how my ignorant brain is viewing this, I don't see why the definition could not be.

$$(a,b)=\{\{a\},\{b\},\{a,b\}\}$$

aka the power set. What is the significance of the {a} in that definition? Please keep things simple if possible. Normally definitions have a valid and clear reason for being defined that way.

Clarification

First, I understand what an ordered pair is. I just don't see how the set notation says that.

Second, $$(a,b) = \{\{a\},\{a,b\}\}=\{\{a,b\},\{a\}\}$$ Sets don't preserve order, but ordered pairs do. How does the third part of the equality apply to the definition?

Third, another issue with the notation that I have starts with the Product Property of Sets

$$\text{Let X and Y be sets} :\ X=\{a,b,c\}\text{ and }Y=\{a,d,e\}.$$ $$\text{Then }X \times Y = \{(a,a),(a,d),(a,e),(b,a),(b,d),(b,e),\dots,(c,e)\}$$ If we look at the first ordered pair and our given definition we have

$$(a,a)=\{\{a\},\{a,a\}\}$$

How can this be so, you can't have duplicates in sets? I guess what I am looking for in an answer, is not a proof or a definition of ordered pairs, but rather something like, "This notation says what it says because...". Except for the second to last point I get the terminology, I just don't get the connection between the two different uses of notation.

-
The important thing here is that $(a,b) \neq (b,a)$ if $a \neq b$. In your proposed definition $(a,b) = \{\{a\},\{b\},\{a,b\}\} = (b,a)$ for all $a$ and $b$. – MartianInvader Sep 8 '11 at 18:48
Hmmm, ignorance is frustrating as hell. So lets forget my definition. If I could only ask my question correctly, I am sure I would get the answer that helped me the most. Let me ponder on what has been said, I will try and rephrase my question in a bit. – Matthew Hoggan Sep 8 '11 at 18:53
It has nothing to do with the answer, but your $(a,b)$ is not the power set. Poor $\emptyset$ has been neglected, an easy thing to do, since it is so small. – André Nicolas Sep 8 '11 at 18:54
@Matthew, since I already gave an answer (and won't be able to edit it soon for quite some time), please do not completely edit away the question. If you are planning on a completely different question, I suggest you may ask a new one. – Asaf Karagila Sep 8 '11 at 19:06
I will not edit the post, I was not planning on editing the post physcially. – Matthew Hoggan Sep 8 '11 at 19:07
show 1 more comment

Whatever it is we define "$(a,b)$" to be as a set, what we really want is the following "defining property":

$(a,b) = (c,d)$ if and only if $a=c$ and $b=d$.

There are many ways to achieve this, but this is what we really want to achieve; once we achieve this via some definition, we want to avoid using the actual "guts" of the definition and stick exclusively to that defining property. (Similar to the points made in this answer and comment about how to represent the real numbers as sets).

One way to achieve this "defining property" is via the Kuratowski definition, by defining $$(a,b) = \Bigl\{ \{a\},\{a,b\}\Bigr\}.$$ We can prove that this is a set, and that this set has the property we want.

There are other ways of achieving the same result; for example, Wiener proposed $$(a,b) = \Bigl\{ \bigl\{ \{a\},\emptyset\bigr\}, \bigl\{\{b\}\bigr\}\Bigr\},$$ which also has the "defining property".

The problem with your proposal is that it does not have the defining property we want for ordered pairs: for example, $\emptyset\neq\{\emptyset\}$, so we want $(\emptyset,\{\emptyset\}) \neq (\{\emptyset\},\emptyset)$. But in your proposal, we have: \begin{align*} (\emptyset,\{\emptyset\}) &= \Bigl\{ \{\emptyset\}, \bigl\{\{\emptyset\}\bigr\}, \bigl\{ \emptyset, \{\emptyset\}\bigr\}\Bigr\},\\ (\{\emptyset\},\emptyset) &= \Bigl\{ \bigl\{ \{\emptyset\}\bigr\}, \{\emptyset\}, \bigl\{ \{\emptyset\},\emptyset\bigr\}\Bigr\}; \end{align*} so that $(\emptyset,\{\emptyset\}) = (\{\emptyset\},\emptyset)$.

So the proposal, while a perfectly fine definition of a set, does not achieve the ultimate purpose of defining the ordered pair, and so it should not be the definition of "ordered pair".

Proof that the Kuratowski definition has the "defining property".

If $a=c$ and $b=d$, then $$(a,b) = \Bigl\{ \{a\}, \{a,b\}\Bigr\} = \Bigl\{ \{c\},\{c,d\}\Bigr\} = (c,d).$$ Assume conversely that $(a,b)=(c,d)$. Then $\bigcap(a,b) = \bigcap(c,d)$. Since $$\bigcap(a,b) = \bigcap\Bigl\{ \{a\},\{a,b\}\Bigr\} = \{a\}\cap\{a,b\} = \{a\}$$ and $$\bigcap(c,d) = \bigcap\Bigr\{ \{c\}, \{c,d\}\Bigr\} = \{c\}\cap\{c,d\} = \{c\},$$ we conclude that $a=c$.

If $b=a$, then $(a,b) = \{\{a\}\} = (c,d) = \{\{c\},\{c,d\}\}$. Therefore, $\{c,d\} \in\{\;\{a\}\;\}$, so $d\in\{a\}$, hence $d=a=b$ and we conclude $d=b$, as desired. Symmetrically, if $c=d$, then $\{a,b\}\in(a,b)=(c,d) = \{\;\{c\}\;\}$, so $\{a,b\}=\{c\}$, hence $b=c=d$ and we again conclude $d=b$ as desired.

If $b\neq a$ and $c\neq d$, then $\bigcup(a,b)-\bigcap(a,b) = \bigcup(c,d)-\bigcap(c,d)$. Since $$\bigcup(a,b)-\bigcap(a,b) = \bigcup\Bigl\{\{a\},\{a,b\}\Bigr\} - \{a\} = \Bigl( \{a\}\cup \{a,b\}\Bigr)-\{a\} = \{a,b\}-\{a\} = \{b\}$$ and $$\bigcup(c,d)-\bigcap(c,d) = \bigcup\Bigl\{\{c\},\{c,d\}\Bigr\} - \{c\} = \Bigl(\{c\}\cup \{c,d\}\Bigr)-\{c\} = \{c,d\}-\{c\} = \{d\}$$ (where we've used that $a\neq b$ to conclude that $\{a,b\}-\{a\}=\{b\}$ and we've used $c\neq d$ to conclude ${c,d}-{c}={d}$), then we have $\{b\}=\{d\}$, hence $b=d$, again as desired.

Thus, if $(a,b)=(c,d)$, then $a=c$ and $b=d$.

This definition is part of a way to try to define a lot of the things that we use in mathematics on the basis of an axiomatic theory; in this case, we start with Axiomatic Set Theory, where the only notions we have (if we are working in Zermelo-Fraenkel Set Theory) are "set" and "is and element of", together with the axioms that tells us properties of sets and things we can do with sets.

We want to have something that works like what we know as "the ordered pair"; but all we have to work with are sets. So we need to find a way of constructing a set that has the properties we want for the ordered pair.

For a metaphor: the ordered pair is like a car; we know how to drive. But in order to actually have a car, there needs to be an engine and gasoline, and the engine has to work. We are trying to construct that engine so that we can later drive it.

So this is not notation, this is a definition of what the ordered pair is in set theory. We are defining an object, which we call "$(a,b)$", to be the given set. It's not merely how we are writing the ordered pair, is what the ordered pair is if you are interested in actually seeing the engine of the car working. We know what we want "ordered pair" to behave like, but we have to actually construct an object that behaves that way. This is a way of defining an object that does behave that way.

There aren't "two notations" here. We define "the ordered pair with first component $a$ and second component $b$" to be the set $$\bigl\{ \{a\}, \{a,b\}\bigr\},$$ (which one can prove is indeed a set using the Axioms of Set Theory, if $a$ and $b$ are already in the theory).

Then we prove that "the ordered pair with first component $a$ and second component $b$" is equal to "the ordered pair with first component $c$ and second component $d$" if and only if $a=c$ and $b=d$.

Then we abbreviate "the ordered pair with first component $a$ and second component $b$" by writing "$(a,b)$" (or sometimes "$\langle a,b\rangle$").

"$(a,b)"$ is notation. The other side is the definition of this set.

The definition is the way it is because it works; that's really all we care about. In fact, we forget about the definition pretty much as soon as we can, and simply use the $(a,b)$ and the "defining property." We can do that, because we know that "under the hood" there actually is an engine that does what we need it to do, even if we don't see it working while we are driving the car.

So, there is only one bit of notation, and it's "$(a,b)$". The other side is the definition of what that notation actually is.

1. The "set notation" doesn't "say" the ordered pair is what you think it is. What we are doing is defining what an ordered pair is, in a theory where the only thing we have are sets and the axioms of set theory. Because sets don't respect order, we cannot rely on simply how we write something; in order to be able to define an ordered pair we need to give a purely set-theoretic definition that actually achieves the purpose we want. Kuratowski's definition of an ordered pair $(a,b)$ to be the set given by $\bigl\{\{a\},\{a,b\}\bigr\}$ achieves this objective, in that the defined object has precisely the property we want an "ordered-pair-whatever-it-may-actually-be" to have. Since this set has that property, we define that set to be what the ordered pair "really is". But we don't actually care about what an ordered pair "really is", we just care about its desired "defining property".

In order for your car to work, there has to be an engine somewhere; but once there is an engine and your car works, you don't need to see the engine working in order to drive the car. The same with the ordered pair: for us to have an "ordered pair" in set theory, we need to be able to construct it somehow using sets. Once we have managed to do that, we don't need to see the actual set, we can just use the fact that there is a set that achieves our desired goal.

2. Yes, two sets are equal if and only if they have the same elements. So $\bigl\{\{a\},\{a,b\}\bigr\} = \bigl\{ \{a,b\}, \{a\}\bigr\}$. This does not matter. What matters is that $\bigl\{ \{a\}, \{a,b\}\bigr\} = \bigl\{ \{c\},\{c,d\}\bigr\}$ if and only if $a=c$ and $b=d$, because that's what we are going for. The definition of ordered pair by Kuratowski is specifically designed so that the end result "encodes" an order and distinguishes between the "first component" and the "second component" of $(a,b)$. The definition actually achieves this, as I proved above.

3. There is no problem with "duplicate elements". It's just that the set $\bigl\{\{a\},\{a\}\bigr\}$ is equal to the set $\bigl\{\{a\}\bigr\}$ by the Axiom of Extension, which says that two sets $A$ and $B$ are equal if and only if for every $x$, $x\in A\leftrightarrow x\in B$. The ordered pair $(a,a)$, as a set, is a set which can be written as $$\bigl\{ \{a\},\{a,a\}\bigr\} \text{ or as }\bigl\{\{a\},\{a\}\bigr\}\text{ or as }\bigl\{ \{a\}\bigr\}.$$ There is no problem with this, because that set has the property that $(c,d)$ is equal to $\bigl\{ \{a\}\bigr\}$ if and only if $c=d=a$, which is exactly what we want.

Again: the whole point of this definition is only that it satisfies the property

$\bigl\{ \{a\},\{a,b\}\bigr\} = \bigl\{ \{c\},\{c,d\}\bigr\}$ if and only if $a=c$ and $b=d$.

Once we have this property, we abbreviate the set $\bigl\{\{a\},\{a,b\}\bigr\}$ as $(a,b)$, and simply use the property listed above.

-
This,to me,is the argument I keep having with people over foundations of mathematics: Axiomatic set theory allows us to be very precise about the ontology of mathematics in a way that category theory without set theory cannot give us. Kuratowski's definition of an ordered pair-and the resulting definition of a function-which was proposed by Giuseppe Peano in a little known paper in 1911-are perfect examples. – Mathemagician1234 Sep 9 '11 at 3:27

You want to be able and "decode" the set $\{\{a\},\{a,b\}\}$ into $\langle a,b\rangle$.

We do this by saying "The right coordinate is the one which appears only in one of the elements in $\{\{a\},\{a,b\}\}$, and the left coordinate is the other one, if exists, else it is $\langle a,a\rangle$ and $a=b$".

Edit: Since an ordered pair is a pair of elements in which the position within the pair matters, we refer to $a$ in $\langle a,b\rangle$ as "The left coordinate" and we refer to $b$ as "The right coordinate". This is a matter of terminology only, to allows us to distinct which elements is in each of the entries of the ordered pair.

-
 Is this definition only to be interpreted based on the (en.wikipedia.org/wiki/Cartesian_coordinate_system)? – Matthew Hoggan Sep 8 '11 at 19:06 @Matthew: I have added to my answer to explain on this question (which I think is very good). – Asaf Karagila Sep 8 '11 at 19:32

You can also think a pair is a set of two elements where the order is specified with identifying the first element.

-