Understanding the Definition of an Ordered Pair

[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:

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

 

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

 

[HallsofIvy]

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

 

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

 

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

 

[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

 

[phoenixthoth]

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

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.

 

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

 

[JFo]

Notation?

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 .

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

Thanks in advance - JFo

 

[phoenixthoth]

For the answer to your question, it would behoove you to read the whole thread...

The definition of (x,y) is {x,{x,y}}; so (x,y) is not an element of {x,{x,y}} but is {x,{x,y}}.

 

[JFo]

I see now... the problem I was having was that I didn't truly know the def. of an ordered pair. Thx