Results 1 to 3 of 3

Math Help - equivalence classes

  1. #1
    Member
    Joined
    Sep 2008
    Posts
    76

    equivalence classes

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,707
    Thanks
    626
    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.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. equivalence classes of P(N)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 13th 2010, 08:26 AM
  2. Replies: 10
    Last Post: January 14th 2010, 12:28 PM
  3. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 06:36 PM
  4. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 03:39 AM
  5. Equivalence classes
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 30th 2008, 11:04 PM

Search Tags


/mathhelpforum @mathhelpforum