# Prove an Equivalence Relation R over N x N

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

Related Calculus and Beyond Homework Help News on Phys.org
Dick
Homework Helper
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?

vela
Staff Emeritus
Homework Helper

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