• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Difficulty proving a relation is an equivalence relation

1. Homework Statement

Screenshot 2016-11-06 15.36.00.png


2. Homework Equations

I don't think there are any in this case

3. The Attempt at a Solution

I know that in order to prove R is an equivalence relation, I'd have to show that it is Reflexive, Symmetric, and Transitive. I'm not sure why, but I'm finding this a bit difficult in this case, possibly because the "elements" in question are now sets instead of just regular elements.

Here's what I've thought up so far:

For Reflexivity, I have to demonstrate that ##\forall S\in A((S,S) \in R)##. Since ##A## is the class of all possible sets, of course ##S \in A##, which gets the first requirement out of the way.

As for ##[\exists f : S \rightarrow S \space\ bijective function]##... I can think of one possible example for such a function, namely the identity function ##f(x) = x##; since N maps into itself, the identity function should be both injective (each element in the domain outputs itself in the codomain) and surjective (each element in the codomain is output by itself).

I'm not sure if this is right, though.

I'm not sure how to demonstrate symmetry here. By definition I'd have to show ##\forall S \forall Q ((S,Q) \in R \rightarrow (Q,S) \in R)##, which really just boils down to showing that ##[\exists f : (S \rightarrow Q \space\ bijective function) \rightarrow (Q \rightarrow S \space\ bijective function) ]##, if I'm not mistaken?


However, in this case, S and Q are two different functions, so I can't just use the identity function like with reflexivity... and that's where I'm stuck. I'm not sure how to show symmetry or transitivity here.
 

fresh_42

Mentor
Insights Author
2018 Award
11,157
7,662
1. Homework Statement

View attachment 108566

2. Homework Equations

I don't think there are any in this case

3. The Attempt at a Solution

I know that in order to prove R is an equivalence relation, I'd have to show that it is Reflexive, Symmetric, and Transitive. I'm not sure why, but I'm finding this a bit difficult in this case, possibly because the "elements" in question are now sets instead of just regular elements.
As how far does this matter in this case? Your elements are sets, nothing "instead".
Here's what I've thought up so far:

For Reflexivity, I have to demonstrate that ##\forall S\in A((S,S) \in R)##. Since ##A## is the class of all possible sets, of course ##S \in A##, which gets the first requirement out of the way.
It seems you're a little bit confused. The point is not to get ##S## into ##A##. It is already there by assumption. The point is to show ##(S,S) \in R##. What do you need for that?
As for ##[\exists f : S \rightarrow S \space\ bijective function]##... I can think of one possible example for such a function, namely the identity function ##f(x) = x##; since N maps into itself, the identity function should be both injective (each element in the domain outputs itself in the codomain) and surjective (each element in the codomain is output by itself).
Here we go. You needed a bijection, that's right. And the identity is one, correct. Just replace ##N## by ##S##.
I'm not sure if this is right, though.
It is. Now you have shown reflexivity.
I'm not sure how to demonstrate symmetry here. By definition I'd have to show ##\forall S \forall Q ((S,Q) \in R \rightarrow (Q,S) \in R)##, which really just boils down to showing that ##[\exists f : (S \rightarrow Q \space\ bijective function) \rightarrow (Q \rightarrow S \space\ bijective function) ]##, if I'm not mistaken?
And which function does the job, if you already have ##(S,Q) \in R## and thus a bijection ##f: S \rightarrow Q\;##? What does it mean for ##f## to be bijective? Which function could be the required bijection ##g: Q \rightarrow S \;##? The answer will give you symmetry.
(By the way: If you write "\Rightarrow" with a capital letter, then you get ##\Rightarrow## instead of ##\rightarrow##. This helps to distinguish between mappings (functions) and implications.)
However, in this case, S and Q are two different functions, so I can't just use the identity function like with reflexivity... and that's where I'm stuck. I'm not sure how to show symmetry or transitivity here.
##S## and ##Q## are not functions, they are elements from the point of view from the relation ##R##.
Proceed as in the case of symmetry. This time you have given two bijections ##f: S \rightarrow Q## and ##g : Q \rightarrow P## and will have to find a bijection ##h: S \rightarrow P##. What can be chosen as ##h \,##?
 
As how far does this matter in this case? Your elements are sets, nothing "instead".

It seems you're a little bit confused. The point is not to get ##S## into ##A##. It is already there by assumption. The point is to show ##(S,S) \in R##. What do you need for that?

Here we go. You needed a bijection, that's right. And the identity is one, correct. Just replace ##N## by ##S##.

It is. Now you have shown reflexivity.

And which function does the job, if you already have ##(S,Q) \in R## and thus a bijection ##f: S \rightarrow Q\;##? What does it mean for ##f## to be bijective? Which function could be the required bijection ##g: Q \rightarrow S \;##? The answer will give you symmetry.
(By the way: If you write "\Rightarrow" with a capital letter, then you get ##\Rightarrow## instead of ##\rightarrow##. This helps to distinguish between mappings (functions) and implications.)

##S## and ##Q## are not functions, they are elements from the point of view from the relation ##R##.
Proceed as in the case of symmetry. This time you have given two bijections ##f: S \rightarrow Q## and ##g : Q \rightarrow P## and will have to find a bijection ##h: S \rightarrow P##. What can be chosen as ##h \,##?

I just thought of this, but if ##f: S \rightarrow Q## and ##f## is bijective, then the inverse function ##f^{-1}## be ##g: Q \rightarrow S##? Since the inverse function only swaps the domain and codomain of a function and ##f## is bijective, its inverse ##f^{-1}##should be bijective too, I think?
 

fresh_42

Mentor
Insights Author
2018 Award
11,157
7,662
I just thought of this, but if ##f: S \rightarrow Q## and ##f## is bijective, then the inverse function ##f^{-1}## be ##g: Q \rightarrow S##? Since the inverse function only swaps the domain and codomain of a function and ##f## is bijective, its inverse ##f^{-1}##should be bijective too, I think?
This is correct. Bijection means a one-to-one relation between domain and codomain. They therefore can be swapped.
 

Want to reply to this thread?

"Difficulty proving a relation is an equivalence relation" You must log in or register to reply here.

Related Threads for: Difficulty proving a relation is an equivalence relation

  • Posted
Replies
3
Views
9K
Replies
4
Views
4K
Replies
3
Views
1K
Replies
2
Views
793

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top