Understanding Ordered Pairs to Notation and Definitions

[gnome]

I freely admit that I am notationally challenged, so please help me out with this:
(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
&lt;x,y&gt;=&lt;u,v&gt; \mbox{ iff } x=u \qquad \mbox{ and } \qquad y=v
Any definition that has this property will do; the standard one is
&lt;x,y&gt; = \{\{x\},\{x,y\}\}.

I'm baffled. Since
\{x,y\} = \{y,x\}
how does &lt;x,y&gt; = \{\{x\},\{x,y\}\} define the ordered pair &lt;x,y&gt;?

 

[Hurkyl]

Because {{x}, {x, y}} = {{u}, {u, v}} iff x = u and y = v.

 

[HallsofIvy]

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

 

[gnome]

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.

 

[Hurkyl]

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)

 

[gnome]

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.
And what about

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.

??

 

[gnome]

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

 

[shmoe]

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" regardless 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]

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}}?

 

[gnome]

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.

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

 

[gnome]

Obviously I agree with this

For the normal concept of an ordered pair, you want (x,y) to not equal (y,x).

and with this

{{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]

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

 

[gnome]

 

[gnome]

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

 

[matt grime]

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]

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.

 

[gnome]

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]

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.

 

[gnome]

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]

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?

 

[gnome]

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

 

[matt grime]

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?

 

[CrankFan]

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.

 

[gnome]

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}}[/color]"

So I ask again: by this ---> {{a},{a,b}}[/color] 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[/color] or something else?

 

[matt grime]

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}}[/color]"

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.

 

[gnome]

No, that is not what a set is, unless you do naive (that is wrong) set theory.

The fact that I am reading about sets in Chapter 0 of an introductory logic text should give you a pretty good idea of what kind of set theory I do.

Such elementary things as what a set is are incredibly difficult questions to answer, and indeed not at all relevant to most mathematics.

I hesitate to ask, but to what are they relevant?

 

[matt grime]

The fact that I am reading about sets in Chapter 0 of an introductory logic text should give you a pretty good idea of what kind of set theory I do.

I must have missed the post where you said what books you were currently reading

I hesitate to ask, but to what are they relevant?

there are many aspects where the fundamentals of mathematics (and their problems) are an issue, and we also often know that the only such problems are to do with these set theoretic concerns. they are however almost totally irrelevant to the maths that crops up 'in real life'. we can after all assume whatever (not known to be inconsistent) things we want as axioms and deduce whatever follows without any reference to whether the original statements are in any sense absolutely true (whatever that might mean to a mathematician).

we 'know' what functions, set products, ordered pairs, and so on are without having to be aware of the incredibly complicated set theory (which can be thought of as an attempt to axiomatize the system in as few axioms as possible)

 

[gnome]

Well, there's very little danger of my becoming a category- or set-theorist, but it's interesting enough that I will continue prodding you for answers as long as your patience lasts. But let's try to restrict the discussion to what is an ordered pair, (since you brought it up) does AxB exist and, if it does, what is it?

If you're still willing ... in

That's because that's how we construct[/color] the set AxB in SET[/color]. Properly AxB if it exists is a set S with projections[/color] to A and B that is universal with this property[/color] (for a category theorist). We show it exists by the oh so stupid way of actually constructing the damn thing.

you used some terms (and an entire clause) that almost certainly mean different things to you set-theorists than to the rest of us, so ...

by "SET" do you mean the language of set theory?

does "construct" mean something like "represent symbolically"?

please define "projection".

"that is universal with this property": it's not clear to me what "that" refers to, and which property.

finally (and I don't mean this at all in a disparaging way) does

We show it exists by the oh so stupid way of actually constructing the damn thing.

mean that you (set-theorists en masse) can't define these concepts in words but only by written symbols? This has me completely dumbfounded. Are there really no words to say {{a},{a,b}}? When you discuss these things with your colleagues, do you always carry paper along so you can draw these little pictures to flash at each other? (Sorry, couldn't resist that.)

 

[CrankFan]

finally does [that] mean that you (set-theorists en masse) can't define these concepts in words but only by written symbols?

Why do you think that these concepts can't be described in words?

 

[Hurkyl]

People do set theory so other mathematicians don't have to worry about it. (Yes, this is a vastly oversimplified view)

Let's look at something else a moment to see why foundational issues can be important: (I'm going to simplify and be sloppy because I don't remember all of the details)

Once upon a time, Fermat's Last Theorem had not yet been proven -- in fact, it was still relatively fresh. One day, someone had the brilliant thought to study the problem in a ring of algebraic numbers. He used all the basic facts about numbers, and eventually arrived at a proof of FLT.

But, someone discovered the basic facts about numbers weren't quite as basic as once thought! For example, one elementary fact about the integers is that every number can be written essentially uniquely as a product of a unit and some primes. This is also true in many rings of algebraic numbers. (Though the primes of such a ring can be different. For example, 1+i is a prime in the ring Z).

But, as it turns out, this property of being a unique factorization domain is not universal -- there are many cases of FLT where the rings involved are not UFD's, and thus this "proof" of the FLT was invalid in those cases.



One of the purposes of set theory, category theory, and formal logic is to cover these foundational issues -- to make sure that mathematics is done on the "up and up" and not making unwarranted assumptions.


The reason people try to model everything in set theory is to prove relative consistency: when doing mathematics, we're willing to assume that we have a consistent set theory. But, we might also worry if we have a consistent theory of real analysis. The point of finding a set-theoretic model is that we can say "We don't need to make more assumptions: if set theory is consistent, then so is real analysis!"

In fact, I will brazenly assert that the primary importance of set theory is that it is good for modelling things.


Which brings us back to the problem at hand. We could make all sorts of assumptions about ordered pairs. (such as the theory of ordered pairs I presented in post #16) We'd then have to worry if our new assumptions were consistent.

But, lo and behold, we can interpret it all in set theory, so we're saved! Yay!


Incidentally, you can speak about functions and relations without ever speaking about sets. For example, the theory of ordered fields has several functions and relations (e.g. +, *, <), but the notion of a set appears nowhere in that theory.

Do you realize { , } is a function? It takes two things, and produces the pair set containing those things. This is captured purely syntactically, by the following calculus rule:

A is a thing (in ZFC, we only have sets, to "thing" = "set")
B is a thing
-----------
{A, B} is a set

then, you can define entirely syntactically (i.e. by "pushing symbols" around) how to translate a statement involving { , } into a statement that does not involve { , }.

Of course, it is all easier for us humans to just make { , } part of our language and adopt axioms (a.k.a. definitions) about what the notation means. The formalists have already fielded the question about whether the two approaches are "the same".