Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

[Identity relations] Need help at some odd identity relation problem

  1. Jan 17, 2007 #1
    1. The problem statement, all variables and given/known data

    On the set of Natural Numbers from 1 to 10000 are given the following identity relations.

    R1 ; n R1 m where m and n have the same remainder by division by 24, that is mod n 24 == mod m 24.
    R2 ; n R2 m where n and m have in decimal notation the same number of 2s
    R3; n R3 m where n and m have in decimal notation the same number of 4s.

    The questions.

    1. Show that R = R1 intersection R2 intersection R3 is an indentity relation
    2. Show that no identity class has more than 653 elements
    3. Find identity class with the least number of elements
    4. Can there be an equivalence class with exactly 2 elements? Why.

    2. Relevant equations
    3. The attempt at a solution

    1. Is easy. Since ab definitio R1, R2, R3 are reflexive, symmetric and transitive by the theorem of relation properties, R is aswell reflexive, symmetric and transitive since this properies are preserved by the intersection operation.

    2. I have no idea. Please give me some pointers
    3. Same as above.

    4. Easy. e.g. let R be relation on the set of integers where nRm ; n^2 == m^2, then n-th identity class would be

    [n] = {n,-n} with the exception of [0] = {0}, therefore I have shown that there can be a identity class with exactly 2 elements.
  2. jcsd
  3. Jan 19, 2007 #2
    The number of element in identity class R1 is roughly 10000 / 24 < 653
    R2 and R3 is basically the same, let's take a close look on R2 first,
    For the set of number having zero 2s, it must be the number 10000 or
    share the form 0xxxx, where as x could be 0-9 except 2. that's mean
    there are 9x9x9x9+1 = 6562 elements in that class > 653 elements...
    The proof is failed....

    3. For R2, for the number having 5 2s, the identity class is an empty set...
    It has least number of element (zero). If the answer must be non-empty set,
    pick out the number which have four 2s. You have only one possible choice...
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook