# Definition of an Ordered Pair

"The ordered pair $(a,b)$ is defined to be the set $\{\{a\},\{a,b\}\}$." ~ Hungerford's Algebra (p.6)

I think this is the first time that i've seen this definition. I've read the wiki page. Is it defined this way, as opposed to a definition relating to functions as in a Cartesian product, because this definition is considered more elementary (or foundational) being that it is related directly to sets?

Also, the definition of an ordered $n$-tuple, according to the wiki page seems vague (perhaps i'm misunderstanding it). For an ordered triple it gives the example:

$$(1,2,3) = \{\{(1,2)\},\{(1,2),3\}\}$$

but how do we know this is not the ordered pair $((1,2),3)$? Or is the difference between $(1,2,3)$ and $((1,2),3)$ considered trivial?

Thirdly, and perhaps unrelated, what does it mean for a natural number to be defined

$$2_{\mathbb{N}} = \{\emptyset,\{\emptyset\} \},$$

and is this also done so that we can define $\mathbb{N}$ in terms of sets?

-
You want to define an arbitrary product of sets as some kind of function. You want to define a function as a special kind of relation. You want to define a relation as a subset of the Cartesian product of two sets. You want to define the Cartesian product of two sets as the collection of ordered pairs. So you need to define 'ordered pair' as some kind of set (the only thing there is to begin with). – wildildildlife Mar 8 '11 at 17:36
@wildildildlife Thanks, i wasn't even thinking about how to define a function. It certainly makes no sense to define an ordered pair in terms of functions and turn around and define functions in terms of things which are defined in terms of ordered pairs. – dandiellie Mar 8 '11 at 19:09
A similar question arose on MathOverflow at mathoverflow.net/questions/32181/ambiguity-in-ordered-tuples – JDH Mar 8 '11 at 20:32
@JDH Oh thanks! That is helpful, too! – dandiellie Mar 8 '11 at 21:35
If you defined an ordered pair naively as $\{a, b\}$ you wouldn't be able to distinguish between $(a, b)$ and $(b, a)$ as different ordered pairs, since order isn't important in sets. The definition give above distinguishes $a$ as the first element of the ordered pair, and $b$ as the second element of the ordered pair, as the intersection and symmetric difference between the two sets, respectively. Is that what you're asking? – Uticensis Mar 9 '11 at 4:47

You may be interested in reading Kuratowski's "Set Theory".

Here's what I remember from it:

1. First one defines pairs $\langle a,b\rangle = \{\{a\},\{a,b\}\}$, with this definition one can define $A\times B$ as the set of all pairs $(a,b)$ with $a\in A$ and $b\in B$. However, that's not a good way to proceed, because of the problems you note.
2. With this definition one defines $\prod_{i\in I} X_i$ as the set of functions $f\colon I \to X_i$ such that $f(i)\in X_i$, here $\{X_i \mid i\in I\}$ is a collection of sets (in other words a function $I\to \mathcal P(\cup X_i)$).
3. In particular $A^2$ is the set of functions $2\to A$, where $2 = \{\varnothing, \{\varnothing\}\}$, and $A\times B$ is the set of functions $f\colon 2 \to A\cup B$ where $f(\varnothing)\in A$ and $f(\{\varnothing\})\in B$.
4. Now we forget about that first definition, and proceed with the latter. (Even though we use the former definition to state the latter!) The practical advantage is that now in fact $A\times B\times C$ is actually well-defined, just like any other product, no matter how large the index-set $I$.
5. It is still not true that $(A\times B)\times C = A\times (B\times C)$, and in fact both are still different from $A\times B\times C$. However, there are bijections between these three sets that are so obvious that for all practical purposes one may consider them to be equal.
-
So is this what you're saying? We define an ordered pair in terms of sets so that we have a solid, foundational definition and so that we avoid getting in trouble down the road, but it's not actually the working definition? The more useful definition is the one using functions. – dandiellie Mar 9 '11 at 5:31
@dandiellie Yes, that's about how it works if you want to do everything "by the book". For finite products you could in fact go without the definition as a function, but it's just not as smooth. When doing real mathematics both are similar enough so it wouldn't really matter much anyway. – Myself Mar 9 '11 at 5:39
Ok, thanks. I haven't gotten to real mathematics yet, so imma have to stick with "the book" for now. :p But i understand what you mean. – dandiellie Mar 9 '11 at 5:44
Dear@myself,similarly with fifth point,it's not true that $R[x_1...,x_n]=(R[x_1,...,x_{n-1}])[x_n]$ thay're isomorphism but many people think they're equal. – R Salimi Dec 20 '13 at 13:54

We want to define the most with as little as possible.

That way we only define what sets are, and by that we define ordered pairs, and so on.

The usual way is to define an ordered pair $\langle a,b\rangle = \{\{a\},\{a,b\}\}$. This is just because it's easy to work with.

You can define an ordered pair as the image of a function from the domain which is the power set of the power set of the empty set, the first element is the image of $\emptyset$ and the second is the image of $\{\emptyset\}$. (Yes, functions are usually defined as collections of ordered pairs. I'm talking about existence of a formula with two free variables.)

Again, these are just conventions and we work with that we find comfortable and as clear as possible.

As for the second issue, we only define pairs, but there is a natural identification between $\langle a,\langle b,c\rangle\rangle$ and $\langle a,b,c\rangle$ and of course $\langle\langle a,b\rangle, c\rangle$. So once again we only define as little as possible and somewhat abuse our own notation because we know that the formal backbone exists and is strong.

And lastly, as I said before, we want to define the most with as little as possible. In the world of set theory it's nice to have only sets. So we define $0=\emptyset$, and inductively we can define the natural numbers in terms of sets, so $n=\{0,\ldots,n-1\}$.

-

For your first question, you are correct. An ordered pair defined as "syntactic sugar" for the set construction is more fundamental.

For your second question, when we think about a $k$-tuple, the fundamental property is that we have "projections" from the $k$-tuple to a particular element of the tuple. In other words, all that we essentially require is that we can somehow discern one element from another, and there is an ordering.

With the definition given, $((1,2),3)$ is indeed equivalent to $(1,2,3)$. This is almost like Lisp where (1 2 3) is equivalent to (1 . (2 . (3 . ()))). The principle is the same; we are just making a sort of binary tree. As you might imagine, $(1,2,3,4)$ would be equivalent to $(((1,2),3),4)$ by the definition given.

This is really an unfortunate problem with notation, and not so much the definition of tuples themselves.

For your last question, basically we can give a formal construction to the natural numbers by using more primitive pieces of mathematics. You can think of it as just a particular encoding for natural numbers --- or even a canonical encoding if you want. Another encoding might be a natural number defined as a composition of "successor" functions, etc. But of course they're all isomorphic.

-

As regards your first question, yes, your intuition that this way of defining things is more set-theory-like and foundational is correct.

Since in a set no ordering is defined (i.e., the set $\{a,b\}$ is the same as the set $\{ b, a \}$ ), if you want to express everything just in terms of sets you have to fix a convention to do so. So, in a sense, writing $\{\{a\},\{a,b\}\}$ is a bit like saying, "we are interested in the set $\{a, b\}$, but with $a$ in a distinguished role".

-

The need for an explicit definition of ordered pair comes from the simplicity of he concept of set: there is no order defined in the set axioms - an object is either a member of a set or not.

But it is a convenient mechanism to be able to have the first of a series (and the second also). And the definition of 'ordered pair' allows that. Of course you have to show that, whatever your definition of 'ordered pair' is, you can show that

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

which you can do with the given definition (the notation $\{b,a,d,c\}$ is the same set as $\{a,b,c,d\}$, but $(b,a,d,c)$ is different from $(a,b,c,d)$

To get n-tuples, it should be straightforward that (though not equivalent in underlying set notation) one can say $(a,b,c)$ can be implemented using ordered pairs as $((a,b),c)$ or $(a, (b,c))$ where you can extract the first element easily, but also to get the second element of the triple you get the first element of the $(b,c)$ which is the second element of the pair $(a,(b,c))$.

-

(a,b,c) = {{a},{a,b},{a,b,c}}?

[(a,b,c) = (d,e,f)] <==> [[a=d & b=e] & c=f]

[ [a=d & b=e] & c=f ] ==> [ {{a},{a,b},{a,b,c}} = {{d},{d,e},{d,e,f}} ]

Now suppose instead that [[a=d & b=f] & c=e]:

{{a},{a,b},{a,b,c}} = {{d},{d,f},{d,e,f}}

The set {{d},{d,f},{d,e,f}} is not the same as the set {{d},{d,e},{d,e,f}} because the set {d,f} (which is in {{d},{d,f},{d,e,f}}) is not the same as the set {d,e} (which is in {{d},{d,e},{d,e,f}}).

For example:

{a,b} = {d,e} if a=d & b=e OR if b=d and a=e. However, there is no order ({d,e} or {e,d}, which are the same) in which {d,e} = {d,f}.

From this, {{d},{d,e},{d,e,f}} is not equivalent to {{d},{d,f},{d,e,f}}. If {{a},{a,b,},{a,b,c}} = {{d},{d,f},{d,e,f}}, then {{a},{a,b},{a,b,c}} is not equivalent to {{d},{d,e},{d,e,f}}. So:

[ {{a},{a,b},{a,b,c}} = {{d},{d,e},{d,e,f}} ] <===> [[a=d & b=e] & c=f]

Which means if...

x = {a} y = {a,b} z = {a,b,c}

then...

(x,y,z) = {x,y,z} {x,y,z} = {{a},{a,b},{a,b,c}} {{a},{a,b},{a,b,c}} = {{d},{d,e},{d,e,f}} if and only if a=d, b=e and c=f.

Or something like that, I think. I've only just started learning so forgive me, I'm still mainly thinking in terms of predicate logic.

Also forgive the presentation.

-
Please, use Tex when posting on this site. – user38355 Dec 20 '13 at 11:01
I have no idea how to, though. As I indicated, I'm really only just beginning with set theory, from which it can be more or less easily deduced that I probably haven't been posting on this site for very long and probably don't know how to do so properly. This is also why I mentioned the poor presentation of my post at the end of it, so I'm not sure as to the intentions of your comment. – dionysus Dec 20 '13 at 21:45
My comment was intended as a courteous reminder to please learn the standard way, Tex/MathJax, of posting math equations on this site. – user38355 Dec 21 '13 at 12:13