-1

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?

fear.xD
  • 1,530
  • 3
  • 15
  • 20
  • 6
    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. – Marc Mar 15 '14 at 15:16

4 Answers4

1

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.

Ishfaaq
  • 10,034
  • 2
  • 30
  • 57
1

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.

Danae Kissinger
  • 2,143
  • 1
    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. – drhab Mar 15 '14 at 15:24
  • @drhab thanks, edited – Danae Kissinger Mar 15 '14 at 15:29
1

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

Michael Hoppe
  • 18,103
  • 3
  • 32
  • 49
0

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.

drhab
  • 151,093