• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • Thread starter haki
  • Start date
  • #1
161
0
1. Homework Statement

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. Homework 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.
 

Answers and Replies

  • #2
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...
 

Related Threads for: [Identity relations] Need help at some odd identity relation problem

  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
2
Views
1K
Replies
1
Views
536
  • Last Post
Replies
1
Views
1K
Replies
3
Views
1K
Replies
0
Views
977
Top