2
$\begingroup$

I am asked to show the follow set if an equivalence relation on a given set.

So I have:

Set: A=Map$(\mathbb{R},\mathbb{R})$
Relation: $f \sim g$ if $f(0)=g(0)$ or $f(1)=g(1)$.

I know that this is not an equivalence relation but I was wondering if someone could check my reasoning.

Reflexivity: $f \sim f$ implies $f(0)=f(0)$ or $f(1)=f(1)$

This will always be true for any function in the real numbers so the reflexivity property is always satisfied.

Symmetry: $f \sim g$ and $g \sim f$ implies $g(0)=f(0)$ or $g(1)=f(1)$

The equality still preserves the original definition so this is essentially the same as the original statement so the symmetry property is still satisfied.

Transitivity: $f \sim g$, $g \sim h$ implies $f \sim h$ implies that we should have:

$f \sim g:$ $f(0)=g(0)$ or $f(1)=g(1)$

$g \sim h:$ $g(0)=h(0)$ or $g(1)=h(1)$

implies we should have:

$f \sim h:$ $f(0)=h(0)$ or $f(1)=h(1)$.

Let $f(x)=1$ and $g(x)=x$ and $h(x)=2$

The $f \sim h:$ $f(0)=h(0)$ or $f(1)=h(1)$ fails so this is not an equivalence relation. Is that the right idea?

EDIT: I changed $h(x)=2$ instead of $x^2$.

$\endgroup$
3
  • 2
    $\begingroup$ One comment: I don't like the way you stated the reflexivity. IMO a correct way of writing it would be " $\forall f: f$ ~ $f$ holds because $f(0)=f(0)$ (and $f(1)=f(1)$) trivially" $\endgroup$
    – Amelian
    Commented Jun 3, 2021 at 23:44
  • $\begingroup$ Fair enough! Thanks a lot. $\endgroup$ Commented Jun 4, 2021 at 5:36
  • $\begingroup$ I'm amazed because nobody has helped you yet ! You have the right ideas (though your counterexample is not completely right), if you want I can share with you the way I would show it's not an equivalence relation in an answer below. $\endgroup$
    – Amelian
    Commented Jun 4, 2021 at 14:39

1 Answer 1

1
$\begingroup$

You are right, the relation on your exercise is not an equivalence relation because it's not transitive. You have the right ideas, but I see that you are having troubles to explain them. The implication

$$f \sim f \Rightarrow f(0)=f(0) \vee f(1)=f(1) $$

is not what you need to prove to state that the relation is reflexive (we already know that if $f$ happens to be related with itself, it's because $f(0)=f(0) \vee f(1)=f(1)$ because of the definition of being related). Instead, what you are interested in proving is that the statement

$$ \forall f: f \sim f $$ is true.

Below I show you how I would solve your exercise:

  1. Since for every mapping $f$ the equation $f(0)=f(0)$ is trivially true, the relation is reflexive.
  2. Let $f$ and $g$ be two maps for which the statement $f$ ~ $g$ is true. WLOG let's suppose that $f(0)=g(0)$. Then we have $g(0)=f(0)$ too, and $g$ ~ $f$ holds.

(note that points 1 and 2 are true because equality is an equivalence relation in $\mathbb{R}$).

  1. Let's show that the relation is not transitive. Consider the mappings $f(x)=1$, $g(x)=x$, $h(x)=0$. Since $f(1)=g(1)$ and $g(0)=h(0)$, we have that $f$ ~ $g$ and $g$ ~ $h$. However, $f$ is not related with $h$, since $f(0) \neq h(0)$ nor $f(1) \neq h(1)$. We have found mappings $f$, $g$ and $h$ for which $f \sim g $ and $g \sim h $, but $f \nsim h$, so the statement $$f \sim g \wedge g \sim h \Rightarrow f \sim h$$ is false, and the relation is not transitive, thus it's not an equivalence relation.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .