Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Ordered pair

  1. Jan 8, 2006 #1
    I freely admit that I am notationally challenged, so please help me out with this:
    (from Enderton, A Mathematical Introduction to Logic)
    I'm baffled. Since
    [tex]\{x,y\} = \{y,x\}[/tex]
    how does [itex]<x,y> = \{\{x\},\{x,y\}\} [/itex] define the ordered pair [itex]<x,y>[/itex]?
    Last edited: Jan 8, 2006
  2. jcsd
  3. Jan 8, 2006 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Because {{x}, {x, y}} = {{u}, {u, v}} iff x = u and y = v.
  4. Jan 8, 2006 #3


    User Avatar
    Science Advisor

    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).
  5. Jan 8, 2006 #4
    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: Jan 8, 2006
  6. Jan 8, 2006 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Because this definition satisfies the properties we ascribe to ordered pairs.

    For example,
    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)
  7. Jan 8, 2006 #6
    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
  8. Jan 8, 2006 #7
    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}
    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:
    (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: Jan 9, 2006
  9. Jan 8, 2006 #8


    User Avatar
    Science Advisor
    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).
  10. Jan 8, 2006 #9


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.

    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}}?
  11. Jan 9, 2006 #10
    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.
    In a word, no. Do you consider this (from Wikipedia) to be accurate:
    If so, how does ∀ Y ∈ p : x ∈Y convey the idea of "firstness"?
  12. Jan 9, 2006 #11
    Obviously I agree with this
    and with this
    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?
  13. Jan 9, 2006 #12


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    An ordered pair is a set of the form {{x}, {x,y}}. :tongue2:
  14. Jan 9, 2006 #13
    :rofl: :rofl: :rofl:
  15. Jan 9, 2006 #14
    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}
    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: Jan 9, 2006
  16. Jan 9, 2006 #15

    matt grime

    User Avatar
    Science Advisor
    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?
  17. Jan 9, 2006 #16


    User Avatar
    Staff Emeritus
    Science Advisor
    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:
    [tex]\forall \phi: \phi = \langle \mathrm{first}(\phi), \mathrm{second}(\phi) \rangle[/tex]
    [tex]\forall x, y, u, v: \langle x, y\rangle = \langle u, v \rangle \iff x = u \wedge y = v[/tex]

    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! :smile:

    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: Jan 9, 2006
  18. Jan 9, 2006 #17
    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?
  19. Jan 9, 2006 #18

    matt grime

    User Avatar
    Science Advisor
    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.
  20. Jan 9, 2006 #19
    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?
  21. Jan 9, 2006 #20

    matt grime

    User Avatar
    Science Advisor
    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: Jan 9, 2006
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook