Difficulty proving a relation is an equivalence relation

In summary, the conversation discussed the steps required to prove that a relation R is an equivalence relation. The first step is to show reflexivity, which can be done by demonstrating that for all elements S in the set A, (S,S) is in R. The second step is to show symmetry, which can be done by finding a bijection between two elements, S and Q, in R. The third and final step is to show transitivity, which can be done by finding a bijection between two bijections, S and Q, and using it to find a bijection between S and P.
  • #1
Enharmonics
29
2

Homework Statement



Screenshot 2016-11-06 15.36.00.png


Homework Equations



I don't think there are any in this case

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.
 
Physics news on Phys.org
  • #2
Enharmonics said:

Homework Statement



View attachment 108566

Homework Equations



I don't think there are any in this case

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 \,##?
 
  • #3
fresh_42 said:
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?
 
  • #4
Enharmonics said:
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.
 

1. What is an equivalence relation?

An equivalence relation is a mathematical concept that describes a relationship between elements of a set in which they are considered equivalent or equal to each other in some way. It is denoted by the symbol "~" and has three main properties: reflexivity, symmetry, and transitivity.

2. How do you prove that a relation is an equivalence relation?

To prove that a relation is an equivalence relation, you must show that it satisfies all three properties: reflexivity, symmetry, and transitivity. This can be done through logical reasoning and examples, or by using mathematical proofs.

3. What are the main challenges in proving a relation is an equivalence relation?

Some of the main challenges in proving a relation is an equivalence relation include identifying and understanding the specific properties that need to be satisfied, finding counterexamples to disprove the relation, and using precise and rigorous mathematical language and logic.

4. Can a relation be partially an equivalence relation?

No, a relation cannot be partially an equivalence relation. It either satisfies all three properties and is considered a full equivalence relation, or it fails to satisfy at least one property and is not an equivalence relation at all. There is no middle ground.

5. How do you use equivalence relations in real-world applications?

Equivalence relations are widely used in various fields of mathematics, including abstract algebra, topology, and graph theory. They also have practical applications in computer science, economics, and social sciences, where they are used to define and analyze relationships between different entities or elements.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
457
  • Calculus and Beyond Homework Help
Replies
3
Views
762
  • Calculus and Beyond Homework Help
Replies
1
Views
532
  • Calculus and Beyond Homework Help
Replies
4
Views
898
  • Calculus and Beyond Homework Help
Replies
3
Views
466
  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
21
Views
3K
  • Calculus and Beyond Homework Help
Replies
3
Views
853
  • Calculus and Beyond Homework Help
Replies
24
Views
2K
Back
Top