Results 1 to 2 of 2

Math Help - Show that R is an equivalence relation

  1. #1
    Member
    Joined
    Jan 2010
    Posts
    232

    Show that R is an equivalence relation

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

    I've already proven that 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 2^3=8 different equivalence classes of 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; March 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
    11,738
    Thanks
    644
    Hello, Runty!

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

    a) Show that R is an equivalence relation.

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

    And they look like this:

    . . \begin{array}{c}<br />
\_\;\_\;0\;0\;\_\;\_\;\_\;\_\;\_\;0 \\ <br />
\_\;\_\;0\;0\;\_\;\_\;\_\;\_\;\_\;1 \\ <br />
\_\;\_\;0\;1\;\_\;\_\;\_\;\_\;\_\;0 \\ <br />
\_\;\_\;0\;1\;\_\;\_\;\_\;\_\;\_\;1 \\ <br />
\_\;\_\;1\;0\;\_\;\_\;\_\;\_\;\_\;0 \\ <br />
\_\;\_\;1\;0\;\_\;\_\;\_\;\_\;\_\;1 \\ <br />
\_\;\_\;1\;1\;\_\;\_\;\_\;\_\;\_\;0 \\ <br />
\_\;\_\;1\;1\;\_\;\_\;\_\;\_\;\_\;1<br />
\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: April 6th 2011, 11:46 PM
  2. Show Equivalence Relation
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: October 19th 2010, 08:51 AM
  3. Equivalence relation and order of each equivalence class
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 30th 2009, 09:03 AM
  4. Show that this is an equivalence relation
    Posted in the Discrete Math Forum
    Replies: 17
    Last Post: April 27th 2009, 12:49 PM
  5. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 03:39 AM

Search Tags


/mathhelpforum @mathhelpforum