Results 1 to 2 of 2

Thread: Show that R is an equivalence relation

  1. #1
    Member
    Joined
    Jan 2010
    Posts
    232

    Show that R is an equivalence relation

    Let $\displaystyle A$ be the set of all bit strings of length 10. Let $\displaystyle R$ be the relation defined on $\displaystyle A$ where two bit strings are related if the third, fourth and last bits are the same. Show that $\displaystyle R$ is an equivalence relation and enumerate one bit string from each of the different equivalence classes of $\displaystyle R$.

    I've already proven that $\displaystyle R$ is an equivalence relation, so don't worry about that half of the question.

    The second half is what's giving me trouble. I am not entirely sure of how to do this, though I could guess. Since three bits are the same, are there $\displaystyle 2^3=8$ different equivalence classes of $\displaystyle R$?

    EDIT: Here's my current answer to the second half. Can someone confirm if it works?
    1100111110
    1100111111
    1101111110
    1101111111
    1110111110
    1110111111
    1111111110
    1111111111
    Last edited by Runty; Mar 21st 2010 at 10:27 AM. Reason: Addition to answer
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    Hello, Runty!

    Let $\displaystyle A$ be the set of all bit strings of length 10.
    Let $\displaystyle R$ be the relation defined on $\displaystyle A$ where two bit strings
    are related if the third, fourth and last bits are the same.

    a) Show that $\displaystyle R$ is an equivalence relation.

    (b) Enumerate one bit string from each of the different equivalence classes of $\displaystyle R$.
    You are right . . . There are 8 equivalence classes.

    And they look like this:

    . . $\displaystyle \begin{array}{c}
    \_\;\_\;0\;0\;\_\;\_\;\_\;\_\;\_\;0 \\
    \_\;\_\;0\;0\;\_\;\_\;\_\;\_\;\_\;1 \\
    \_\;\_\;0\;1\;\_\;\_\;\_\;\_\;\_\;0 \\
    \_\;\_\;0\;1\;\_\;\_\;\_\;\_\;\_\;1 \\
    \_\;\_\;1\;0\;\_\;\_\;\_\;\_\;\_\;0 \\
    \_\;\_\;1\;0\;\_\;\_\;\_\;\_\;\_\;1 \\
    \_\;\_\;1\;1\;\_\;\_\;\_\;\_\;\_\;0 \\
    \_\;\_\;1\;1\;\_\;\_\;\_\;\_\;\_\;1
    \end{array} $


    And the blanks can be filled with any combination of 0's and 1's.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Apr 6th 2011, 11:46 PM
  2. Show Equivalence Relation
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Oct 19th 2010, 08:51 AM
  3. Equivalence relation and order of each equivalence class
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Sep 30th 2009, 09:03 AM
  4. Show that this is an equivalence relation
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: Apr 27th 2009, 12:49 PM
  5. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Jan 7th 2009, 03:39 AM

Search Tags


/mathhelpforum @mathhelpforum