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

 

[matt grime]

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

no, the category of sets.

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

no, it means construct, make, produce a set with the required properties. a lot of proofs in maths show existence wiithout ever actually demonstrating a single example. it is easy to show that almost all numbers are transcendental, and but very hard to actually find many of them.

please define "projection".

exactly what you think it means: the map from AxB to A sending (a,b) to a (and the one defined on B)

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

having these projections. google for category theory and product, because it is best explained by a picture thaht i can't draw here.

finally (and I don't mean this at all in a disparaging way) does mean that you (set-theorists en masse)

I'm definitely not a set theorist; i know next to nothing about set theory; can't stand it in fact

can't define these concepts in words but only by written symbols?

we could use words, we don't since symbols are universal. personally i tihnk set theory over relies on symbols, but if you dont' like symbolic definitions then maths is going to get quite bad since few books bother with wordy descriptions, possibly at their own expense

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

the language used when discussing maths informally and the formal language of books and definitions are not the same.

 

[gnome]

This is like trying to catch a greased pig.
I can appreciate the utility of symbolic representations, but sometimes words are useful too. I can't understand why it is so difficult to get you guys to attach words to this one:
{{a},{a,b}}
You're standing in front of your class, and there's a blind guy named Charlie in the class.
You say: "An ordered pair is defined as ... " and here your voice trails off as you write on the blackboard

{{a},{a,b}}

"this!" you triumphantly pronounce. "Sorry, Charlie, you're out of luck."
Are you going to stick to:
An ordered pair is defined as left bracket left bracket a right bracket comma left bracket a comma b right bracket right bracket
and that's it? Can't you come up with some words to help Charlie out?
------------------------------------------------------------------------------
I wonder why Enderton felt it appropriate to present this definition, with no further discussion, in a "review" chapter (in an introductory logic text) that begins

We assume the reader already has some familiarity with normal everyday set-theoretic apparatus. Nonetheless, we give here a brief summary ...

We don't seem to be dealing in this thread with "normal, everyday" (which I take to be what Matt calls "naive") anything. Well, maybe normal, everyday for set-theorists. Enderton's book is clearly not aimed at set-theorists. We deal with ("naive", I guess) set concepts constantly, in computer science and in many other disciplines, without losing any sleep over whether or not the set of all sets is a set.
I will try to find time to look at Enderton's "Elements of Set Theory". Maybe he sheds more light on this definition there. And I clearly have to look into category theory, which in my ignorance I thought was a branch of set theory. I stand corrected. Maybe you can recommend something for me to read. Is there such a thing as "Categories for Non-mathematicians"? (I'm not, nor have I ever been, a math major -- just trying to get a reasonably clear idea of what you guys find so irresistable.)

 

[matt grime]

Naive is its name, it is not an invention of mine, it is the set theory that is used and used without problem for 99.99999999% of maths.

You want it in words? OK, we define set of ordered pairs of AxB to be the set constructed as follows: we take all the single elements sets whose element is in A, and the collection of all pairs of elements which contain exactly one element of A and one of B, then we take the subset of the combined collection of all these sets where the element of the singeleton set is an element of the pair.Happy?

I can define it in words more simply but not in words that are purely set theoretic since sets do not have orderings!

 

[Hurkyl]

Hrm...

If you were to ask "What are the real numbers?" instead of "What is an ordered pair?", would you be looking for the "The real numbers are a complete, ordered field" answer, or the "Real numbers are equivalence classes of Cauchy sequences" answer?

 

[mathwonk]

an ordered pair is a pair of things, and one of them is designated as the first one.

if you do not believe such things exist, i feel sorry for you.


If you really want to understand how the set theorists have labored to define such an animal within set theory, I can understand your predicament, having once been there myself, as young child.

But by now I have lost all interest in this exercise, as I have never used the concept in the succeeding 42 years.


So have most people. This explains the reluctance to give lengthy answers to such questions, when many other more interesting mathematical questions abound.

I.e. if this were considered cutting edge mathematics, we would have all become real estate agents long ago.

 

[gnome]

Matt: yes that makes me feel happy. Dumb, but happy, thank you very much. Actually, you could have stopped at "we define set[/color] of ordered pairs of AxB[/color] to be" because that in itself made it all clear. You see, I was not reading it as the definition of a set; I was trying to read the definition of a general concept: "An ordered pair is ..." which of course made no sense, and I needed you to hit me over the head with those words to make me see what you meant.

Hurkyl: thank you too, but I know better than to ask that question. Seriously, it would take more time than I can afford in order to really understand either of those answers. For the time being, I'll sleep very well with a 1-to-1 correspondence to the points on an infinite line.

mathwonk: you misunderstand my motivation in all this nonsense. This was not a debate. Until three days ago I was very satisfied with "an ordered pair is a pair of things, and one of them is designated as the first one" (and tomorrow I will again be satisfied with that). Unfortunately, I came across that {{a},{a,b}} definition in Enderton's "Mathematical Introduction to Logic" and foolishly thought that if it was important enough for him to put there, it was important enough for me to try to understand. Hurkyl and Matt were kind enough to waste their time helping me.

 

[Hurkyl]

Hurkyl: thank you too, but I know better than to ask that question. Seriously, it would take more time than I can afford in order to really understand either of those answers.

I only meant it as an analogy. I was trying to give a way for you to clarify what kind of answer you want, by analogy with this other case!

Unfortunately, I came across that {{a},{a,b}} definition in Enderton's "Mathematical Introduction to Logic" and foolishly thought that if it was important enough for him to put there, it was important enough for me to try to understand.

It is!

I think you're trying to get the wrong lesson from it, though: I suspect that (aside from completeness's sake) the point of this is that it's an example of the process of modelling a concept in some theory.



What happens in practice is that a budding mathematician is told "This is how we can define an ordered pair in the language of sets. Now let's just use the notation (a, b) and never speak of this again." (I think we've hinted at this, but I don't remember if we've said it explicitly)

 

[mathwonk]

i know that gnome. I was answering your persistent questions about why people were answering your questions with questions, and generally having to be begged to stay on topic. it just isn't a topic that seems important after grasping it.
nonetheless, it was rude of me, and I apologize.

Like you, I encountered this definition in a book, and assumed it must have some importance since it was given there (Kelley's Continental classroom algebra book? in 1960?).

I remember thinking only slightly sceptically at the time, " so this is really the definition of an ordered pair? Do I need to know this?"

The answer is no, and I think the only reason this was included in the book, was that someone decided at the time of the set theory hysteria that's wept the math ed world in 1960, that it could be done, and showed off by doing it.

However I think Kelley may have honestly remarked there that it could be done that way if desired, implying that ti had limited significance.

I did however work the exercise that {{x}, {x,y}} = {{z},{z,w}} if and only if x=z and y = w.

assume for example that x = y. then the first set contains only {x}. thus the second set which equals it, must contain only one set too, so we must have z = w also. then since {{x}} = {{z}}, we must have x = z.

now suppose x is different from y...

interesting huh?...:zzz:

 

[matt grime]

I can't wait until you come across what a set theorist thinks the natural numbers really are. If you think the ordered pair stuff is unnecessarily fussy wait until you see this.

 

[mathwonk]

yeah, i just reviewed a book on this stuff supposedly written for young math majors learning proofs. the definition of multiplication of integers in there was really off putting.

those guys must have been smoking crack. then the publishers advertised it by saying it was user friendly, and "written in a highly understandable style".

what a joke.

 

[HallsofIvy]

an ordered pair is a pair of things, and one of them is designated as the first one.

The problem with that is that you need to define what "first one" means- in other words, to define "ordered pair" you'd better first define an order!

The definition: "An ordered pair, (a,b), is a set of the form {{a},{a,b}}" avoids that- it doesn't talk about "first" or "second", "left" or "right", "top" or "bottom". It asserts that there are two objects (a and b) and that
(a,b)= {{a},{a,b}} is different from (b,a)= {{b},{a,b}}. You are then free to assume whatever "order" you want. That's all that "ordered pairs" have to say.

 

[Sir_Deenicus]

yeah, i just reviewed a book on this stuff supposedly written for young math majors learning proofs. the definition of multiplication of integers in there was really off putting.
those guys must have been smoking crack. then the publishers advertised it by saying it was user friendly, and "written in a highly understandable style".
what a joke.

Dont worry, the future is not doomed. Most of us with real interest tend to stay away from such trashy books and even have copies of books from those passed away 100 years gone!

 

[Hurkyl]

The problem with that is that you need to define what "first one" means- in other words, to define "ordered pair" you'd better first define an order!

Or, you could take the interpretation that "first" is merely a name for one of the elements, and has nothing to do with any notion of an ordering.

 

[CrankFan]

Unfortunately, I came across that {{a},{a,b}} definition in Enderton's "Mathematical Introduction to Logic" and foolishly thought that if it was important enough for him to put there, it was important enough for me to try to understand. Hurkyl and Matt were kind enough to waste their time helping me.

The concept of translating ordinary mathematical statements into a formal language is relevant to mathematical logic. Enderton could have omitted that brief exercise but if a reader struggles to see how, in principal, the concept of an ordered pair can be expressed set theoretically, then the reader is probably going to struggle with things presented later in the book.

Set theorists & Mathematical Logicians don't study formal theories because they provide a justification or because knowledge of them is required for other branches of mathematics. They study formal theories because they find it interesting. Same reason why number theorists study integers. If you're not interested in formal theories, don't tie yourself up in knots about it -- just stick to subjects that you enjoy.

 

[gnome]

I'm glad I was able to keep you all entertained these past few days.

I can't wait until you come across what a set theorist thinks the natural numbers really are. If you think the ordered pair stuff is unnecessarily fussy wait until you see this.

You'll be the first to know.

They study formal theories because they find it interesting. Same reason why number theorists study integers. If you're not interested in formal theories, don't tie yourself up in knots about it -- just stick to subjects that you enjoy.

As I said, there's no danger that I'll be crowding the ranks of the set-theorists. On the other hand, I don't consider this to have been a waste of time.

For example, this is the first time I've come across this idea of construction of mathemetical objects. Seems like a surprisingly "empirical" activity for mathematicians to be involved in. Personally, I'd rather tinker around under the hood of my TR-7, but I can see how you could find that interesting.

And, all kidding aside, I think the question of how to express the idea of ordering is fascinating. We all have this concept of order in our minds, but it takes so many forms depending on the particular subject to which it's being applied that it seems like a fairly daunting challenge for AI and one certainly worthy of attention.

 

[matt grime]

For example, this is the first time I've come across this idea of construction of mathemetical objects. Seems like a surprisingly "empirical" activity for mathematicians to be involved in.

It is not empirical at all. Think of it like this:

We take a theory of some type, written in some formal language, if you want to think of it like that. Then we make some formal statement about the objects that is not written in the original formal language. The question is if we can write this statement in that original formal language.

If you're interested in the Category theoretic viewpoint then it is occasionally useful to know when the construction we define is in 'the same universe' (which has a strict set theoretic meaning) as the things we first start from.


As a concrete example, consider the set of rational numbers, this is closed under finite sums of rational numbers (as in sums x_1+x_2+...+x_n a finite number of rationals added up). We can define a space of potentially infinite sums, whereby the infinite sums converge if and only if the sequence of finite partial sums is cauchy. This space cannot be the rational numbers, and is indeed the reals. Now suppose we ask the same question again whereby we allow for all infinite sums of reals whose partial sums are cauchy, do we get anything new? No, since the reals are complete.

Another example, that is easier to explain: consider the real numbers, and then ask if we can find all roots of all real coefficient polynomials in the reals. We can't but we can add in i and get the complex numbers. Is C then algebraically closed? Yes, it is.


Now, set theoretically, consider the class of all finite sets, is this closed under arbitrary unions? No, it is not, indeed there is a strict hierarchy, indexed by the cardinals, that indicate the sets one can make after taking different kinds of unions.

 

[gnome]

Just kidding.

I do get your point, and I intend to read more about category theory but I'm juggling too many balls to get involved in that right now.

Another day. Thanks again.

 

[jim mcnamara]

The set theoretic definition of a tuple uses the ordered pair as it's starting point. The result is that an n-tuple is an ordered set of n elements (or objects). -- Under this definition.

However, a tuple in database theory is usually defined as a finite function that maps fields in a relation(database table for instance) to data, and is not necessarily an ordered set of n elements. Another name for it is a "row" in a resultset or a row in a relation.

 

[mathwonk]

halls, surely you jest.

 

[mathwonk]

Aha! Halls you are right! Forgive me, but now I see for the first time, there really is no way to decide which element is "first"
.
For example when a = b, we have the proposed definition of the "ordered pair" (a,b) as the set {{a},{a,a}}. Now since {a} = {a,a}, this is just
{{a},{a}}, which of course is just {{a}}.
Thus there is no first copy of the element a.
Now this is clearly nonsense.
I.e. suppose we define an ordered singleton as a set of form {{a}}.
Then there is a non trivial intersection between the colection of ordered singletons and the collection of ordered pairs!
I.e. then when given the object {{a}}, we have no way of knowing whether it is an ordered singleton or an ordered pair.
This is obviously ridiculous and only someone who never planned to use them, would define them this way.
For instance with this definition, one could not tell the difference between the point (a,a) of the diagonal in the euclidean plane, and the point a on the real line.
So in fact the definition proposed for the ordered pair (a,b), namely {{a},{a,b}}, is a bit odd.
So unless I have made another of my many flagrant errors of thought (which is highly likely, given the huge number of intelligent people who have dutifully repeated this definition in their books), this silly definition is not only unimportant, but has odd properties.
e.g. in R^3, how should we define an ordered triple? perhaps we set (a,b,c) = the ordered pair (a,(b,c))? i.e. {{a},{{a},{b,c}}}.
Oho! We get the following: the "right" silly definition in this tradition, for an ordered singleton is of course not {{a}} but {a}.
then the ordered pair (a,a) is just {{a},{a,a}} = {{a}}.
and the ordered triple (a,a,a) is hmmm... {{a}, {{a}}}, so now R is disjoint from R^2, etc...
wheee... this kind of trivial nonsense is fun, until you wake up and realize you have more important things to do. It is kind of addictive though, like watching television. I fear it is equally harmful, as I am losing time I could be spending thinking about something deeper, like differential equations, or skew symmetric line bundles on curves.