Question

Let f: X-->X be a function from a nonempty set X into itself. Show that the relation R = {(x,y) in X x X : f(x) = f(y)} is an equivalence relation on X.

Answer 1

@phi

Answer 2

@myininaya

Answer 3

So we need to show the following:
1reflexive
2symmetric
3transitive

Answer 4

Have you tried any of the 3?

Answer 5

No, I didn't know where to start on this one.

Answer 6

To show something is an equivalence relation we need to show those 3 parts.

Answer 7

http://www.math.vt.edu/people/elder/Math3034/book/3034Chap5.pdf

This looks cute.
Look at page 2.

Answer 8

It sorta gives you an outline on how to prove these things.

Answer 9

So R is a relation
We want to prove this is an equivalence relation.
Let a be in X.
This means (a,a) is in X x X and we know f(a)=f(a)
So it is reflexive.

You try to look at the symmetry part.
This part requires 2 elements not just one.

Answer 10

Like I started out with saying a is in X.
Try letting two elements be in X.

Answer 11

Alright so,

Let a and b be arbitrary elements in X where (a,b) is in X x X and f(a)=f(b)
Not sure how to expand from there.

Answer 12

we also have (b,a) is in X x X and f(b)=f(a)

Answer 13

ah ok

Answer 14

Now for the final part.
we need three elements

Answer 15

so the proof would go like

Let a and b be arbitrary elements in X where (a,b) is in X x X and f(a)=f(b) and (b, a) is in X x X and f(b)=f(a)

Answer 16

And then the outline says to Expand and give an argument which concludes that b is symmetric to a

Answer 17

That part is for symmetry...
Yep.

Answer 18

Well...Ummm no sorta

Answer 19

We have (a,b) and (b,a) in R.
Since (a,b)R(b,a) we are done.

Answer 20

Because (a,b) implies f(a)=f(b)
and (b,a) implies f(b)=f(a)

Answer 21

we are already done

Answer 22

for the symmetry part

Answer 23

So is what you have above just a simpler way to write out the proof?

Answer 24

Like we got to assume on part.

Like assume (a,b) is in R then f(a)=f(b)
But since f(b)=f(a) then (b,a) is in R as well.

Answer 25

And since a,b are in X.

Answer 26

Like you could say something like this.
Let a,b be in X.
(a,b) and (b,a) are in R since f(a)=f(b) implies f(b)=f(a)

I think that is fine.

Answer 27

ah ok, awesome :)

Answer 28

so for the transitive part I need a b and c

Answer 29

So we want to show since (a,b) and (b,c) is in R then (a,c) is in R.

Answer 30

So start with,

Let a,b, and c be in X

Answer 31

yes.

Answer 32

(a,b) and (b, c) are in R since f(a)=f(b) implies f(b)=f(c)

Answer 33

would that be right so far?

Answer 34

Well we get to assume (a,b) is in R which means f(a)=f(b)
and we get to assume (b,c) is in R which means f(b)=f(c)

Like Since both of them R it doesn't necessarily imply that one equality implies the other.

Answer 35

them are in R*

Answer 36

Like (r,s) could be in R just because f(r)=f(s)
and (j, t) could be in R just because f(j)=f(t) where r,s,j,t are elements of X
But f(r)=f(s) doesn't imply f(j)=f(t)

Answer 37

Back to:
Maybe I should edit myselt:
"Like you could say something like this.
Let a,b be in X.
(a,b) and (b,a) are in R since f(a)=f(b) implies f(b)=f(a)"

---

Let a,b be in X.
Since (a,b) is in R then f(a)=f(b).
Since f(a)=f(b) implies f(b)=f(a) and a,b are in X, then (b,a) is in R.
So R is symmetrical.

Answer 38

Of course that first since is you assuming that (a,b) is in R

Answer 39

ah I see, looks good.

Answer 40

Ok so maybe that was my bad. lol.

Answer 41

Let a,b,c be in X.
So anyways, we get to assume that (a,b) and (b,c) is in R.
Show (a,c) is in R.

This proof isn't terrible.

Answer 42

So I need to show (a,c) is in R?

Answer 43

Or was that the proof right there?

Answer 44

Yep show (a,c) is in R.

Answer 45

Um, because a is in R and c is in R then (a,c) is in R?

Answer 46

Oh no. you are suppose to have ordered pairs in R

Answer 47

ah right

Answer 48

You can do this since (a,b) is in R
What does this imply?

Answer 49

(b,a) is in R

Answer 50

Well you are going back to the symmetric thing. And yes it is symmetric.

But what I'm looking for is that f(a)=f(b).
Or you could have wrote f(b)=f(a) since we have the relation is symmetric.

Now you also have (b,c) in R which implies?

Answer 51

f(b)=f(c) so since f(a)=f(b) and f(b)=f(c) then f(a)=f(c)?

Answer 52

yep which implies (a,c) in R since a,c are elements of X.

Answer 53

Reflexive:
Let a be in X.
(a,a) is in X x X
Since f(a)=f(a) then (a,a) is in R.
Symmetric:
Let a,b be in X.
(a,b) is in X x X and (b,a) is in X x X.
Assume (a,b) is in R. This means f(a)=f(b).
Since f(b)=f(a) then (b,a) is in R.
Transitive:
Let a,b,c be in X.
(a,b) is in X x X , (b,c) in X x X, and (a,c) in X x X.
Assume (a,b) in (b,c) is in R.
This means f(a)=f(b) and f(b)=f(c).
Since f(a)=f(b) and f(b)=f(c), then f(a)=f(c) which means (a,c) is in R.
---

Like you know what A x B means?

Like if A={1,2,3} and B={a,b}, then
A x B ={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)}
A={1,2,3} , A={1,2,3}
A x A ={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}

Answer 54

Wow, thank you! Looks great.

Yeah, I know how to do A x B

Answer 55

Great.

Answer 56

Does the proof make sense to you?

Answer 57

Yes I think I'm finally understanding it now :)

Answer 58

Great stuff.