-1
$\begingroup$

The following instruction defineds an Equivalence relation on the set of natural numbers.

$x \sim y \Leftrightarrow x,y$ are even

My idea:

Reflexivity: $x \sim x \Leftrightarrow x,x$ is even

Symmetry: $x \sim y \Leftrightarrow x,y$ are even

Transitivity: $x \sim y \Leftrightarrow x,y$ are even, $y \sim z \Leftrightarrow y,z$ are even $\Rightarrow x \sim z \Leftrightarrow x,z$ are even

So my result is, that it is an Equivalence relation, but the solution says it is not, but doesn't say why. Where is my mistake?

$\endgroup$
1
  • 6
    $\begingroup$ An element should always be equivalent to itself. As you remarked $x\sim x \Leftrightarrow x$ is even, so this is not an equivalence relation as it is not reflexive for uneven numbers. $\endgroup$
    – Marc
    Mar 15 '14 at 15:16
1
$\begingroup$

Reflexivity means that no equivalence class is empty, since the equivalence class of an element $x$ always contains at least one element: $x$ itself. As Marc pointed out in his comment, reflexivity fails, indeed if $x$ is odd then the set of $y$ such that $x \sim y$ is empty, thus $\sim$ is not an equivalence relation.

$\endgroup$
2
  • 1
    $\begingroup$ A consequence of fact that reflexivity fails is that we cannot speak of an equivalence relation. Then there are no equivalence classes so expressions like 'the equivalence class of $x$ is empty' make no sense. $\endgroup$
    – drhab
    Mar 15 '14 at 15:24
  • $\begingroup$ @drhab thanks, edited $\endgroup$ Mar 15 '14 at 15:29
1
$\begingroup$

According to the question the relation is defined on $\Bbb N$ in which case reflexivity does not work.

If $\mathscr R$ is an equivalence relation on the set $A$ then $\mathscr R$ is a reflexive relation iff $a \mathscr aR \;\; \forall a \in A$. I'm sure according to the definition of the relation above in your exercise the relation is not reflexive since it would not work for every element in the given set. If my assumption is correct your counter example is $1 \not \sim 1$ and hence this is not an equivalence relation.

$\endgroup$
1
$\begingroup$

For the reflexivity: is $(1,1)$ an element of the relation?

$\endgroup$
0
$\begingroup$

If $\sim=\left\{ \left(x,y\right)\in\mathbb{N}^{2}\mid x\; and\; y\; even\right\} $ then $\left(1,1\right)\notin\sim$ showing that $\sim$ is not reflexive.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.