# Ordered pair

## Main Question or Discussion Point

(from Enderton, A Mathematical Introduction to Logic)
The ordered pair <x,y> of objects x and y must be defined in such a way that
$$<x,y>=<u,v> \mbox{ iff } x=u \qquad \mbox{ and } \qquad y=v$$
Any definition that has this property will do; the standard one is
$$<x,y> = \{\{x\},\{x,y\}\}.$$
I'm baffled. Since
$$\{x,y\} = \{y,x\}$$
how does $<x,y> = \{\{x\},\{x,y\}\}$ define the ordered pair $<x,y>$?

Last edited:

Related Set Theory, Logic, Probability, Statistics News on Phys.org
Hurkyl
Staff Emeritus
Gold Member
Because {{x}, {x, y}} = {{u}, {u, v}} iff x = u and y = v.

HallsofIvy
Homework Helper
In particular, defining the ordered pair (a,b) to mean the set {{a}, {a,b}} makes it clear that the pair is {a ,b} but that it is different from {{b},{a,b}}. Notice that it is really isn't important that you know which is first and which is second, as long as you know that (a,b) is different from (b,a).

Hurkyl said:
Because {{x}, {x, y}} = {{u}, {u, v}} iff x = u and y = v.
That's clearly true, but I still don't see how that defines an ordered pair. In plain English, an ordered pair is a set containing exactly two elements, and which has the additional characteristic that the order of the elements must be preserved, right? How is that idea conveyed by {{x},{x,y}} which is a set whose elements are themselves sets, one containing one element and the other containing two elements?

Looking at it another way, I don't see how it is even valid to say <x,y> = {{x}, {x, y}} since, on the left side is "something" consisting of two elements (each of which may or may not be a set), and on the right side is a set containing two elements, each of which is explicitly a set.

Last edited:
Hurkyl
Staff Emeritus
Gold Member
How is that idea conveyed by {{x},{x,y}} which is a set whose elements are themselves sets, one containing one element and the other containing two elements?
Because this definition satisfies the properties we ascribe to ordered pairs.

For example,
In plain English, an ordered pair is a set containing exactly two elements, and which has the additional characteristic that the order of the elements must be preserved, right?
for any {{x}, {x,y}}, can you not tell what the two elements make comprise the ordered pair it represents, and which one comes first?

(don't forget the case x=y)

Sorry, I'm trying, but I don't see how that implies any order, since I can also say {{x},{x,y}} = {{v,u},{u}} iff x = u and y = v.
I don't see how it is even valid to say <x,y> = {{x}, {x, y}} since, on the left side is "something" consisting of two elements (each of which may or may not be a set), and on the right side is a set containing two elements, each of which is explicitly a set.
??

Hurkyl said:
...for any {{x}, {x,y}}, can you not tell what the two elements make comprise the ordered pair it represents, and which one comes first?
(don't forget the case x=y)
I must be missing some very fundamental point here. Please try to tell me what it is.
Regarding "(don't forget the case x=y)": I don't see how that applies either. I think that if x=y, then either:
{{x},{x,y}} is an invalid expression because a set should not contain duplicates, as in {x,x}
or
being forgiving, we let {x,x} mean simply {x}, and then {{x},{x}} becomes just {{x}}.
Either way I don't see how that defines the ordered pair <x,x>, although I see nothing wrong with the idea of <x,x> as an ordered pair. (This does, however, show me that my "plain English" definition was wrong too, since I can't call <x,x> a set.)

a little later...
Actually, I think that
<x,y> = <u,v> iff x=u and y=v doesn't define "ordered pair"; it defines the equality relation on ordered pairs.
I'm not trying to be argumentative. I just don't see how ordered pair can be defined as a set of sets.

later still...
At this point I've read more than I want to know about Kuratowski pairs, Wiener pairs, etc. :zzz:
I think I will have to make it through life with a much more intuitive, non-axiomatic-set-theoretic definition like the one Suppes gives:
Intuitively, an ordered couple is simply two objects given in a fixed order...Thus <x,y> is the ordered couple whose first member is x and whose second member is y.
(along with <x,y> = <u,v> iff x=u and y=v to define the equality relation on them).

I'm still curious, though, about this: I read "<x,y> = {[anything in here]}", in English, as "the ordered pair x,y is the set consisting of ..." and already I think we're in trouble because an ordered pair is not a set. Can you help me with that?

Last edited:
shmoe
Homework Helper
An ordered pair is two elements, where one is "1st" the other is "2nd". It's enough to have one labeled as "1st" and the other isn't. actually all you really need is to be able to distinguish one of them somehow.

(note:assume x is not y below)

Trying to define an ordered pair as {x,y} gets you nowhere, there's nothing distinct about either element. Using {{x},{x,y}} however, we have an element that belongs to two elements of this set, both {x} and {x,y}, and one that belongs to only one. We can then distinguish between the two, and call say x "1st" irregardless of how you write this set ({{y,x},{x}}, {{x,y},{x}}, etc).

For the normal concept of an ordered pair, you want (x,y) to not equal (y,x). This is achieved with the set idea, {{x},{x,y}} is certainly different from {{y},{x,y}}.

If x=y, there's no problem with defining (x,x) as the set {{x}} (or rather having your definition collapse to this).

Hurkyl
Staff Emeritus
Gold Member
I must be missing some very fundamental point here. Please try to tell me what it is.
There is a 1-1 correspondence between the things we would like to call ordered pairs, and sets of the form {{x}, {x, y}}. Therefore, sets of this form are adequate for modelling the notion of ordered pair.

Actually, I think that
<x,y> = <u,v> iff x=u and y=v doesn't define "ordered pair"; it defines the equality relation on ordered pairs.
Maybe exploring this further would help all of this sink in -- this tells us when two ordered pairs are equal. The other atomic operations I can imagine on ordered pairs are the "first" and "second" operations, and the operation that takes a pair of objects and turns them into an ordered pair.

Can you see how to define these three operations on sets of the form {{x}, {x, y}}?

Sorry, while you guys were writing answers, I was busy reading other sources and editing my last post.
Still, I don't see how the set-theoretic definition involves any less "hand-waving" than the intuitive definition.
hurkyl said:
Can you see how to define these three operations on sets of the form {{x}, {x, y}}?
In a word, no. Do you consider this (from Wikipedia) to be accurate:
The statement that x is the first element of an ordered pair p can then be formulated as
∀ Y ∈ p : x ∈Y
and that x is the second element of p as
(∃ Y ∈ p : x ∈ Y) ∧ (∀ Y1 ∈ p, ∀ Y2 ∈ p : Y1 ≠ Y2 → (x ∉ Y1 ∨ x ∉ Y2))
If so, how does ∀ Y ∈ p : x ∈Y convey the idea of "firstness"?

Obviously I agree with this
shmoe said:
For the normal concept of an ordered pair, you want (x,y) to not equal (y,x).
and with this
shmoe said:
{{x},{x,y}} is certainly different from {{y},{x,y}}
I just don't see how either {{x,},{x,y}} or {{y},{x,y}} DEFINES an ordered pair. To me a definition is: "An ordered pair is ... "

Can you express {{x},{x,y}} in words beginning with "An ordered pair is ... " that will help me get your (or Kuratowski's) meaning?

Hurkyl
Staff Emeritus
Gold Member
I just don't see how either {{x,},{x,y}} or {{y},{x,y}} DEFINES an ordered pair. To me a definition is: "An ordered pair is ... "
An ordered pair is a set of the form {{x}, {x,y}}. :tongue2:

:rofl: :rofl: :rofl:

Ugh! Let me try this ...
We have a "thing", "p", that looks like this: <x,y>. We name this p an ordered pair. Using the elements x,y from p form the sets {x},{x,y}, {{x},{x,y}}.
Now, using {{x},{x,y}} as a model for p, we define:
first(p) = {a | ∀ Y ∈ p : a ∈Y}
and:
second(p) = (∃ Y ∈ p : b ∈ Y) ∧ (∀ Y1 ∈ p, ∀ Y2 ∈ p : Y1 ≠ Y2 → (b ∉ Y1 ∨ b ∉ Y2))
then first(p) and second(p) satisfy the requirement that <first(p),second(p)> = <first(q),second(q)> iff first(p) = first(q) and second(p) = second(q)
That model business is still a little wishy-washy, isn't it? I think you want me to say <x,y> = p = {{x},{x,y}}, don't you? Guess I'm just too literal.

edit: What if I say, "p" and "the ordered pair <x,y>" are both names for the object {{x},{x,y}} ... is that the idea?

But that's quite different from "two objects given in a fixed order".

Last edited:
matt grime
Homework Helper
What does first mean? Seriously, you've written (a,b) and said that a is the first element. Why? Because it is on the left? That's very Roman of you, an arabic reader may think it silly. Plus the notion of "firstness" as in "being on the left" is not an intrinsic set theoretic one, is it?

Hurkyl
Staff Emeritus
Gold Member
If I were to write down a theory of ordered pairs, it might look like this:

There's a type Thing of "things". (Thing variables will be roman)
There's a type OP of "ordered pairs". (OP variables will be greek)
There are two functions first and second that map OP->Thing.
There's a function < , > that maps ThingxThing->OP

And we have two axioms:
$$\forall \phi: \phi = \langle \mathrm{first}(\phi), \mathrm{second}(\phi) \rangle$$
$$\forall x, y, u, v: \langle x, y\rangle = \langle u, v \rangle \iff x = u \wedge y = v$$

So the goal is simply to define an interpretation of this theory in your set theory.

Foundationally, this isn't very interesting -- you have to have already built up the set theoretic machinery before you can start talking about model theory.

That's sort of the problem you're faced with: you are trying to define notions without all of the convenient machinery we're used to using!

Incidentally, you could define a set theory that leaves things called "sets" and things called "ordered pairs" defined purely axiomatically. But we don't really "like" to do that, since "ordered pairs" can be defined in terms of sets, and by doing so, we've built our foundation on a simpler theory.

Last edited:
matt grime said:
What does first mean?
For that matter, what does order mean? That seems to be the crux of the issue. That's why "two objects, where one is 'first' and the other is 'second'" stills has a hollow ring.

At first I liked Hurkyl's "theory of ordered pairs", because it expressed far better than I could the idea I was trying to convey a couple of posts up. But there seems to be another problem: a function is a relation, a relation is an ordered pair, so how can we use a function to define "ordered pair"?

Are you using another definition of function?

matt grime
Homework Helper
These are all genuine issues, ones whose answers I am ignorant of, but I thought you wanted to know why ordered pairs had the strange definition that they do instead of simple (a,b) with a first b second. That is the intuition we should have, but the formal one used most is {{a},{a,b}} which adequately defines an ordered pair, in that it distinguishes (a,b) from (b,a) modulo some a=b stuff.

So we're back to that ugly thing {{a},{a,b}}.

All I see there is a set whose elements are two sets, and we can distinguish one from the other because one has one element and the other has two.

Is that all there is to it? Then "first" and "second" are reduced to being meaningless labels that can be attached by some arbitrary rule to either the one-element element or the two-element element?

matt grime
Homework Helper
The "correct way to think about them" is as the ordered pair (a,b) that we all know and love, the point is that to obtain a definition (construction really) that is purely given in set theoretic terms we use the {{a},{a,b}} thing since sets do not come with any ordering of their elements. The assignment of first as the 'one on the left' is entirely arbitrary too, by the way since the product AxB is (canonically) isomorphic to BxA. There is a category theoretic definition that the product of two objects satisfies some universal rule. Of course you need to demonstrate that there is some object in SET that has this property, and it is usual to do so by construction.

I mean, what are the real numbers? The set of equivalence classes of cauchy sequences of rationals? The set of dedekind cuts? The unique complete totally ordered field? Yes, each of those is a correct description, though the first two are really models for a complete totally ordered field: the last of those is 'the correct' definition of them,

We don't actually use any of those things in practice do we? No, we use the model of the decimal representations with the operations defined on these things modulo the relation that we identify things like 0.9.... and 1. Which incidentally shows that there is a complete totally ordered field.

The idea that some constructions might not actually exist in some category is also important. Take the category of finite sets. It is closed under finite products (because we can construct the set AxB with the appropriate properties), but infinite products do not exist in this category. They do in the category SET. If R is a ring does mod(R) have a product? What about kernels? Initial objects, terminal objects, coequalizers, all small limits?

Last edited:
Clearly I'm not a set theoretician, and so I wonder why set theoreticians think that everything should, or can, be explained in terms of sets. But I do want to achieve at least some working appreciation of that way of thinking.
But before going off on too much of a tangent, please tell me if what I just said
All I see there is a set whose elements are two sets, and we can distinguish one from the other because one has one element and the other has two.
Is that all there is to it? Then "first" and "second" are reduced to being meaningless labels that can be attached by some arbitrary rule to either the one-element element or the two-element element?
so eloquently is at least a reasonably accurate understanding of what that set definition represents.

Edit: OK, delete the word "meaningless".

(For some strange reason category theory suddenly seems to keep popping up at the edges of my consciousness. Guess I'll have to look into that as well.)

Last edited:
matt grime
Homework Helper
The point is if you want to define things with as few rules as possible you need to use some ingenuity to remove redundant axioms. Plus just because you make some rules up doesn't mean anything satisfies those rules. For instance if you prove amillion results about a simple group of order p^2 where p is a prime then you've done something very silly. How do you even know that there is a well defined set AxB of pairs (a,b) where a is in A and b is in B? Seriously, given two sets A and B how do you know AxB exists? What is it? The way to think of what AxB is is certainly as (a,b) for a in A and b in B but how do you know that is a set, and not something of strictly different kind?

Last edited:
gnome said:
But before going off on too much of a tangent, please tell me if what I just said so eloquently is at least a reasonably accurate understanding of what that set definition represents.
What you wrote does not express understanding of the definition. You failed to mention the most important characteristic of the definition.

Why does everybody answer my questions with questions?
At the risk of going off-topic, isn't "a set of pairs (a,b) where a is in A and b is in B" well-defined by definition, given sets A and B. Isn't a well-defined collection of objects exactly what a set is?

I'm not sure what point you are trying to make there; I think you're telling me I have to learn to be more comfortable with abstractions (and not worry about whether "first" is right, left, up or down), and if so, I agree.

But you and Hurkyl and shmoe and HallsofIvy keep talking around my question. I'm asking for words to define an ordered pair, and all I keep getting from all of you is a picture: "an ordered pair is this ---> {{a},{a,b}}"

So I ask again: by this ---> {{a},{a,b}} do you mean a set whose elements are two sets, s.t. we can distinguish one from the other because one has one element and the other has two or something else?

matt grime
Homework Helper
gnome said:
Why does everybody answer my questions with questions?
At the risk of going off-topic, isn't "a set of pairs (a,b) where a is in A and b is in B" well-defined by definition, given sets A and B. Isn't a well-defined collection of objects exactly what a set is?
No, that is not what a set is, unless you do naive (that is wrong) set theory. Isn't the set of sets that do not contain themselves a well defined set? (No, incidentally, is the answer.)

And the fact that that is not what a set is is the reason why we are asnwering questions with questions. Such elementary things as what a set is are incredibly difficult questions to answer, and indeed not at all relevant to most mathematics.

But you and Hurkyl and shmoe and HallsofIvy keep talking around my question. I'm asking for words to define an ordered pair, and all I keep getting from all of you is a picture: "an ordered pair is this ---> {{a},{a,b}}"
That's because that's how we construct the set AxB in SET. Properly AxB if it exists is a set S with projections to A and B that is universal with this property (for a category theorist). We show it exists by the oh so stupid way of actually constructing the damn thing.

Last edited: