equivalence classes

**NidhiS** · December 11th 2008, 06:37 AM

Let D be the relation on Z defined as follows:

for all m,n in Z m D n <==> 3|(m^2 - n^2)

1.prove that D is an equivalence relation and
2.describe the distinct equivalence classes of D.

I don't know how to go abt it

**TheEmptySet** · December 11th 2008, 07:51 AM

To be an equivelence relation it must be

Reflexive $a \mathcal{R} a$

Symmetric $a \mathcal{R} b \implies b \mathcal{R} a$
and
Transative if $a \mathcal{R} b \mbox{ and } b \mathcal{R}c \implies a \mathcal{R}c$

Reflexive $n \mathcal{R} n$ yes becuause

$3|(n^2-n^2) \implies 3|0$

symmetric yes because if $m \mathcal{R} n$

$3|(m^2-n^2) \implies 3q=(m^2-n^2)$ for some integer q, factoring we get

$3q=-1(n^2-m^2) \implies 3(-q)=n^2-m^2 \implies 3|(n^2-m^2)$
so $n \mathcal{R}m$

Transative

$a \mathcal{R} b \mbox{ and } b \mathcal{R}c$

$3q_1=(a^2-b^2),q_1 \in \mathbb{Z}$ and

$3q_2=(b^2-c^2),q_2 \in \mathbb{Z}$

solving the 2nd for $b^2$ we get

$b^2=3q_2+c^2$ sub this into the first one to get

$3q_1=[a^2-(3q_2+c^2)] \iff 3q_1=a^2-3q_2-c^2 \iff 3(q_1+q_2)=a^2-c^2$

This tells us that $3|(a^2-c^2) \implies a\mathcal{R}c$

for part two think graphically. Good luck.

**Soroban** · December 11th 2008, 09:57 AM

Hello, NidhiS!

I'll do part 1 . . .

Let $\mathbb{D}$ be the relation on $Z$ defined as follows:

. . for all $m,n \in Z\!:\;\; m\,\mathbb{D}\,n\;\Longleftrightarrow\;3|(m^2 - n^2)$

1. Prove that $\mathbb{D}$ is an equivalence relation.

Definition: . $m \,\mathbb{D}\,n\:\text{ if and only if }\: m^2-n^2 \:=\:3k\:\text{ for some integer }k.$
. . . . . . . . (The difference of their squares is a multiple of 3.)

Reflexive: .Is $a\,\mathbb{D}\,a$ ?

. . $a\,\mathbb{D}\,a \;=\;a^2-a^2 \;=\;0 \;=\;3(0)$ . . . Yes!

Symmetric: . $\text{If }a\,\mathbb{D}\,b,\:\text{ does }\:b\,\mathbb{D}\,a$ ?

. . We have: . $a\,\mathbb{D}\,b \quad\Longrightarrow\quad a^2-b^2 \:=\:3k$

. . Then: . $b^2-a^2 \:=\:3(\text{-}k) \quad\Longrightarrow\quad b\,\mathbb{D}\,a$ . . . Yes!

Transitive: . $\text{If }\,a\,\mathbb{D}\,b\,\text{ and }\,b\,\mathbb{D}\,c,\:\text{ does }a\,\mathbb{D}\,c$ ?

. . $\text{We have: }\:\begin{array}{ccc}a^2-b^2 &=&3h \\ b^2-c^2 &=& 3k \end{array}$

. . Add: . $a^2-c^2 \:=\:3(h+k) \quad\Longrightarrow\quad a\,\mathbb{D}\,c$ . . . Yes!

$\mathbb{D}$ is reflexive, symmetric and transitive.

Therefore, $\mathbb{D}$ is an equivalence relation.

Thread: equivalence classes

LinkBack

Thread Tools

Display

equivalence classes

Similar Math Help Forum Discussions

equivalence classes of P(N)

Question on equivalence relations and equivalence classes

equivalence relation and equivalence classes

Equivalence relation and Equivalence classes?

Equivalence classes

Search Tags