# Definition of ordered pair

1. Dec 27, 2004

### Perion

This should be so easy but I'm having trouble understanding why {{x},{x,y}} defines an ordered pair (x,y). I'm trying to work through the following problem from the Zakon Series pdf textbook:

Code (Text):
If (x,y) denotes the set {{x},{x,y}} [B]prove that, for any x, y, u, v,
we have (x,y) = (u,v) iff x=u and y=v[/B]. Treat this as a definition of an
ordered pair.

[Hint: Consider separately the two cases (x equals y) and
(x not equal to y), noting that {x,x}={x}]
I'm just learning to do formal proofs so not sure about where to start. Since it's an iff equivalence I assume that I need to show that
1. if (x,y)=(u,v) then x=u and y=v
AND then also show that
2. if x=u and y=v then (x,y)=(u,v).
Is this the correct overall approach for proving the iff biconditional?

I'm OK with #2 since it's trivial to show that {{x},{x,y}}={{u},{u,v}} for x=u and y=v.

#1 also seems pretty simple when x=y but I'm not sure how to go about it for the case when x is not equal to y. Can you help me with this please.

Thank you,
Perion

[This isn't homework - I'm studying free math e-books on my own.]

2. Dec 27, 2004

### matt grime

If {{x},{x,y}} {{u},{u,v}} them by the definition of equality of sets either

{x}={u} and {x,y}={u,v} OR {x}={u,v} and {x,y}={u}

obviously the second can't occur because if two finite sets are equal they have the same number of elements.

Thus {x}={u} ie x=u. Now {x,y}={u,v} so either x=u, and y=v and we are done, or x=v and y=u, but we know that x=u so y=u=x=v and again x=u and y=v.

3. Dec 27, 2004

### HallsofIvy

Staff Emeritus
The whole point if {x,{x,y}} is to be able to distinguish "x" from "y" and so have the "order" (that is, (x,y) is different from (y,x)).

4. Dec 27, 2004

### phoenixthoth

There are two main features of this definition of (x,y).

One is that it is based on sets. Thus you can do a lot of math with sets without having to invent all sorts of new objects that aren't sets. (Not all of math reduces to set theory.)

Two is that although one can define an ordered pair any way one wishes, the spirit of an ordered pair, something that any "reasonable" definiton of an ordered pair should satisfy is that

(x,y)=(a,b) if, and only if, x=a and y=b.

You can check right off the bat that this is not true if you define (x,y) to be {x,y}. But it is true for {{x},{x,y}}. You could define ordered pairs differently, so long as the above iff holds, but this seems to be the simplest definition in which the above iff is maintained.

5. Dec 28, 2004

### slayerchange

First Post .
Also note the following:
AxB={(x,y): x€A and y€B} .
Thus the elements of AxB are of form {x,{x,y}} .
By you can derive , if my memory is still good ,
AxB is a subset of P(P(A union B)) where P denotes the powerset map . :surprised

6. Dec 28, 2004

### Perion

Thanks to each of for the great info. I think I understand now.

BTW - when I need to prove something that takes the logical form p iff q, do I have to go about it by showing that p implies q (assume p to derive q) and then show that q also implies p (assume q to determine p)? I guess what I'm asking is if there is any preferred (or even required) logical structuring that need to be adhered to in presenting the proof? I see some proofs that seem to follow formal logic and others that are kinda loose. Do you know what I mean?

Thanks,
Perion

7. Dec 28, 2004

### phoenixthoth

When proving iff, you can
1. do what you said exactly
2. instead of using if at each step, use iff. For example, often when you prove that x is in Z iff x is in W, you can go
x is in Z iff x is in Z' iff x is in Z'' iff x is in Z''' iff x is in W. That suffices.

When proving three or more 'sentences' are equivalent, it's kind of cool. If there are three, for example, you prove if A then B, then if B then C, and finally if C then A. That proves A iff B iff C.

8. Dec 28, 2004

### mathwonk

matt, in the following argument you seems to assume that x and y are different.

"If {{x},{x,y}} {{u},{u,v}} them by the definition of equality of sets either

{x}={u} and {x,y}={u,v} OR {x}={u,v} and {x,y}={u}

obviously the second can't occur because if two finite sets are equal they have the same number of elements."

i.e. the second case can occur, if x=y=u=v. but then you are done. i.e. you are trying to prove that the first case does occur, rather than proving the second case does not. it is not true that the second case cannot occur, but if it holds, then so does the first.

Last edited: Dec 28, 2004
9. Jan 12, 2005

### JFo

Notation?

Hi, I've studied a little set theory and have seen the definition of the cartesian product of two sets to be:
AxB={(x,y): x€A and y€B}
Can you explain how an element of AXB can be an element of {x, {x,y}}?

Last edited: Jan 12, 2005
10. Jan 12, 2005