Sets & Equivalence relation Question

TheSetMiner

Question is attached as a .png file.

Basically can anyone explain what the notation means and what is being asked in parts (i) and (ii).

If anyone know how to do this, I would greatly appreciate your help in the form of a hint or solution.

Thanks!

ClovisI

The notation in line 1 means that X is the set of all ordered pairs of natural numbers, like (1,37) or (12,7), but not (-4,7.567).

Line 2 just defines what ~ means (i.e. what it means for the relation ~ to hold between two elements of X).

For (i)
You need prove that the following statements about the binary relation ~:
- For all x in X, x~x.
- For all x and y in X, if x~y then y~x.
- For all x,y and z in X, if x~y and y~z then x~z.

For (ii), (13,6) is one such element. You should be able to find two more.

TheSetMiner

ClovisI wrote: »

The notation in line 1 means that X is the set of all ordered pairs of natural numbers, like (1,37) or (12,7), but not (-4,7.567).

Line 2 just defines what ~ means (i.e. what it means for the relation ~ to hold between two elements of X).

For (i)
You need prove that the following statements about the binary relation ~:
- For all x in X, x~x.
- For all x and y in X, if x~y then y~x.
- For all x,y and z in X, if x~y and y~z then x~z.

For (ii), (13,6) is one such element. You should be able to find two more.

So for part 2; are (6, 1), (7, 2), (8,3) three elements of the equivalence class (12, 7)? There are an infinite amount of elements right? or am I misunderstanding?

edit: just noticed you said (13,6) is an element but I can't tell how. does that mean 13= c and 6 = d because then the relation doesnt hold for 12 + 6 != 7 + 13... shouldnt they equate?

And for part 1 I have no idea how to go about proving those binary relationships. I am still very much confused about the meaning of this symbol: ~
Could you maybe show how you'd go about proving one of those statements?
Thanks

Davidius

TheSetMiner wrote: »

So for part 2; are (6, 1), (7, 2), (8,3) three elements of the equivalence class (12, 7)? There are an infinite amount of elements right? or am I misunderstanding?

edit: just noticed you said (13,6) is an element but I can't tell how. does that mean 13= c and 6 = d because then the relation doesnt hold for 12 + 6 != 7 + 13... shouldnt they equate?

And for part 1 I have no idea how to go about proving those binary relationships. I am still very much confused about the meaning of this symbol: ~
Could you maybe show how you'd go about proving one of those statements?
Thanks

You've got it right. Restating it, the equivalence class of (12,7) is all (b,d) such that b-d=5. Then (b,b-5) is in it for all natural numbers b>=6.

~ is just a generic symbol for equivalence under some condition. You could replace it with "=" as long as it's clear that you don't mean they're equal under the normal definition of =. So (a,b) "=" (c,d) if a+d=c+b, where the second use of = is the standard one (hence why you should avoid using the symbol = so you don't cause confusion)

If you've done any group theory then the generic * operation on a group is a similar idea. Here's an example of an equivalence: Have (a,b) represent a/b, then if a/b = c/d, (a,b) "=" (c,d) even though they may be different points in 2D space. You could rewrite this as (a,b)~(c,d) if a/b = c/d (or ac=bd) (the ~ being different from the one in this problem of course).

For the binary relation ~ to be an equivalence relation on this set you need
(a,b)~(a,b) to be true (think how x=x is always true)
(a,b)~(c,d) implies (c,d)~(a,b) (like how x=y implies y=x)
(a,b)~(c,d) and (c,d)~(p,q) implies (a,b)~(p,q) (like how x=y and y=z implies x=z)

You need to restate what each means: (a,b)~(c,d) if a+d=c+b. For the first we have naturally that a+b=a+b, so (a,b)~(a,b). The rest follows a similar idea.

ClovisI

Oops. My mistake. I misread the question as a+b=c+d. Sorry.
(13,6) is NOT right!

TheSetMiner

Ah OK. It is clearer now.

So for proving these statements;
for the second statement is it sufficient to say that clearly (a,b) "=" (c, d) holds because a-b = c-d?

for the third statement can I say similarly since the above holds, for any case where (c, d) "=" (p, q), clearly (a, b) "=" (p, q) also holds? ie a-b = c-d; c-d = p-q; a-b = p-q... seems like im writing a lot of fancy notation but saying very little!?

Davidius

TheSetMiner wrote: »

Ah OK. It is clearer now.

So for proving these statements;
for the second statement is it sufficient to say that clearly (a,b) "=" (c, d) holds because a-b = c-d?

for the third statement can I say similarly since the above holds, for any case where (c, d) "=" (p, q), clearly (a, b) "=" (p, q) also holds? ie a-b = c-d; c-d = p-q; a-b = p-q... seems like im writing a lot of fancy notation but saying very little!?

If this is a homework assignment or similar it is better to write the symbol they use, like ~ instead of "=" or some other symbol. "=" was more to demonstrate the nature of what ~ represents but it's better to avoid using "=" in anything other people will read.

For the second statement (a,b)~(c,d) is assumed. For absolute clarity it is better to restate this as a+d=c+b, and explicitly note that c+b=a+d (because = is an equivalence relation itself), then explicitly restate it as the definition of (c,d)~(a,b). For the third you do similar, which you basically have done.

Yeah you'll often find yourself writing out very obvious statements. Exercises like these are more to get you used to the concept, and to teach you to avoid writing out anything that you can't justify in formal writing, which is important for anybody who might read your work (including examiners, who want you to demonstrate an understanding of what's being written. Otherwise people might be tempted to rote learn snippets of a proof without an understanding of it). If this is homework I'd avoid writing it as a-b=c-d over a+d=c+b which was the explicit given definition. While the two are clearly equivalent statements you can stand to lose marks for not stating so explicitly (I've lost marks for not stating seemingly obvious statements like that in the past).