Results 1 to 4 of 4

Math Help - Equivalence classes

  1. #1
    Newbie
    Joined
    Dec 2008
    Posts
    18

    Equivalence classes

    Given the following words {rot, tot, root, toot, roto, toto, too, to, otto}

    Let f be the function that maps a word to its bag of letters. For the kernel relation of f, describe the equivalence classes.


    I understand the first part of the question but not the second.

    Next question

    Let R be a relation on a set S such that R is symmetric and transitive and for each x c- S there is an element y c- S ( those are supposed to be the E rounded) such that x R y. Prove that R is an equivalence relation in other words prove that it is reflexive.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by cj's mom View Post
    Given the following words {rot, tot, root, toot, roto, toto, too, to, otto}

    Let f be the function that maps a word to its bag of letters. For the kernel relation of f, describe the equivalence classes.


    I understand the first part of the question but not the second.
    I have seen a similar problem (on equivalence classes) posted by you, before. Unfortunately I fail to understand the language. Can you tell me the definition of "the kernel relation of a mapping"??

    I will be able to help you, if you do so...

    Let R be a relation on a set S such that R is symmetric and transitive and for each x c- S there is an element y c- S ( those are supposed to be the E rounded) such that x R y. Prove that R is an equivalence relation in other words prove that it is reflexive.
    Pick any element x \in S, then by hypothesis \exists y \in S such that x \text{ R } y. But since the relation is symmetric we get y \text{ R } x.

    So x \text{ R } y and y \text{ R } x.... what do you think transitivity will do?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,751
    Thanks
    651
    Hello, cj's mom!

    Let R be a relation on a set S such that R is symmetric and transitive
    and for each x \in S, there is an element y \in S such that x\:R\:y.

    Prove that R is an equivalence relation.
    Iin other words, prove that R is reflexive.

    We are told that: "every x has a y": . x \:R\:y

    We are told that R is symmetric: .If x\:R\:y, then y\:R\:x

    We are told that R is transitive: .If (x\:R\:y) \wedge (y\:R\:z), then x\:R\:z.


    Hence, we have: . x\:R\:y and y \:R\:x

    By the transitive property: . (x\:R\:y) \wedge (y\:R\:x) \;\Rightarrow\;x\:R\:x


    Therefore, R is reflexive.

    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,792
    Thanks
    1532
    Quote Originally Posted by cj's mom View Post
    Given the following words {rot, tot, root, toot, roto, toto, too, to, otto}

    Let f be the function that maps a word to its bag of letters. For the kernel relation of f, describe the equivalence classes.
    Do you mean that two words are equivalent if they are mapped to the same thing? That's not the way I would understand the word "kernel".
    You also say "bag" rather than "set". That's more a computer term than math term- it's like a set but multiples of the same thing are allowed. In that case, "toot", "toto", and "otto" are mapped to the same thing and "roto" and "root" are mapped to the same thing but none of the others are mapped to the same thing. If that is what you mean then the equivalence classes are {rot}, {tot}, {root, roto}, {toot, toto, otto},{too}, {to}.


    I understand the first part of the question but not the second.

    Next question

    Let R be a relation on a set S such that R is symmetric and transitive and for each x c- S there is an element y c- S ( those are supposed to be the E rounded) such that x R y. Prove that R is an equivalence relation in other words prove that it is reflexive.
    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