# Difficulty proving a relation is an equivalence relation

Tags:
1. Nov 6, 2016

### Enharmonics

1. The problem statement, all variables and given/known data

2. Relevant 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.

2. Nov 6, 2016

### Staff: Mentor

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 \,$?

3. Nov 7, 2016

### Enharmonics

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. Nov 8, 2016

### Staff: Mentor

This is correct. Bijection means a one-to-one relation between domain and codomain. They therefore can be swapped.