Prove an Equivalence Relation R over N x N

  • Thread starter Ceci020
  • Start date
  • #1
11
0

Homework Statement


Given: A relation R over N x N
((x,y), (u,v)) belongs to R. i.e (x, y) ~ (u,v)

If max(x,y) = max(u,v), given that
max(x,y) = x if x >= y
= y if x < y

Prove that R is an equivalence relation


Homework Equations


I know that to prove an equivalence relation, I must prove that the
relation satisfies : reflexivity, symmetry, and transitivity, but I
somehow get confused on how to use the condition: max(x,y) = max(u,v)
in my proof



The Attempt at a Solution


Here are my thoughts about the proof:

To prove
Reflexivity:
Given that (x,y) ~ (u,v)
so max(x,y) = max(u,v) definitely

Symmetry:
My self-question: since (x,y) ~ (u,v). Does (u,v)~(x,y)?
My thought: since max(x,y) = max(u,v), then flip the sides
I have max(u,v) = max(x, y). This is always
true, because (x,y) ~ (u,v)

Transitivity: I get confused the most with this one, and I kind of get
stuck with the proof from here too.

My thought:
Since I'm given ((x,y), (u,v)) belongs to R and (x,y) ~ (u,v)
Can I let another ordered pairs, say (a,b) that also belongs to R
and then use the following sequence:
(x,y) ~ (u,v) and (u,v) ~ (a,b), then (x,y) ~ (a,b)?

My question: how should I introduce (a,b) into the proof? How do I
prove the fact that (u,v) ~ (a,b) is true, so that I can proceed later
steps?

The most important question: are my thoughts, so far, correct? am I
missing something?
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,260
619
The reflexivity isn't going well. Reflexivity says (x,y)~(x,y). Is that always true? Translate that into the max statement. Symmetry seems ok. Transitivity says (x,y)~(u,v) and (u,v)~(w,z) implies (x,y)~(w,z). Can you show that?
 
  • #3
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
14,788
1,375

Homework Statement


Given: A relation R over N x N
((x,y), (u,v)) belongs to R. i.e (x, y) ~ (u,v)

If max(x,y) = max(u,v), given that
max(x,y) = x if x >= y
= y if x < y

Prove that R is an equivalence relation


Homework Equations


I know that to prove an equivalence relation, I must prove that the
relation satisfies : reflexivity, symmetry, and transitivity, but I
somehow get confused on how to use the condition: max(x,y) = max(u,v)
in my proof



The Attempt at a Solution


Here are my thoughts about the proof:

To prove
Reflexivity:
Given that (x,y) ~ (u,v)
so max(x,y) = max(u,v) definitely
To prove reflexivity, you want to show that (x,y) ~ (x,y). No (u,v) at all in this part.
Symmetry:
My self-question: since (x,y) ~ (u,v). Does (u,v)~(x,y)?
My thought: since max(x,y) = max(u,v), then flip the sides
I have max(u,v) = max(x, y). This is always
true, because (x,y) ~ (u,v)
The order is a bit mixed up here.

1. You assume (x,y) ~ (u,v).
2. This means by definition of R that max(x, y) = max(u, v).
3. This implies max(u, v) = max(x,y). (Why?)
4. Therefore...

You need to fill in the last step.
Transitivity: I get confused the most with this one, and I kind of get
stuck with the proof from here too.

My thought:
Since I'm given ((x,y), (u,v)) belongs to R and (x,y) ~ (u,v)
These two things mean the same thing.
Can I let another ordered pairs, say (a,b) that also belongs to R
and then use the following sequence:
(x,y) ~ (u,v) and (u,v) ~ (a,b), then (x,y) ~ (a,b)?
Yes, that's exactly what you do. You assume (x,y) ~ (u,v) and (u,v) ~ (a,b). Then show that this means that (x,y) ~ (a,b).
My question: how should I introduce (a,b) into the proof? How do I
prove the fact that (u,v) ~ (a,b) is true, so that I can proceed later
steps?
You don't need to prove it. It's true by assumption. You want to show that the assumptions lead to the conclusion.
The most important question: are my thoughts, so far, correct? am I
missing something?
 

Related Threads on Prove an Equivalence Relation R over N x N

Replies
3
Views
2K
  • Last Post
Replies
3
Views
9K
Replies
2
Views
896
Replies
4
Views
4K
Replies
3
Views
695
Replies
1
Views
2K
Replies
13
Views
250
Replies
0
Views
3K
  • Last Post
Replies
4
Views
616
Top