Can any of you maths geniuses help me?
I am stuck in a group theory question, want to give it a try?
Let R be a relation on Z (integers) such that m is a positive integer, x R y if and only if m divides x - y, where x, y are integers.
Prove that this equivalence relation partitions Z into m distinct classes.
[ 11-10-2002: Message edited by: soulcrusher ]</p>
Let R be a relation on Z (integers) such that m is a positive integer, x R y if and only if m divides x - y, where x, y are integers.
Prove that this equivalence relation partitions Z into m distinct classes.
[ 11-10-2002: Message edited by: soulcrusher ]</p>
Comments
<strong>sorry man, we don't do homework.
</strong><hr></blockquote>
Well played Alcimedes, i have a different reply, but luckily you replied before me (our reputation of Genius is saved ).
<strong>42 is the answer. </strong><hr></blockquote>
Yes it is. Now where's that damn towel?
I would suggest that you forget about the precise statement of the relation R (congruence of integers) and focus instead on equivalence classes in general. Specifically, any equivalence relation on a set A will partition A into mutually disjoint, nonempty subsets. Prove that first, then use the congruence of integers afterwards to prove that there are actually m of these congruence classes.
You can show that an equivalence relation partitions its set by working with the definition of a partition:
(Goes to fetch old math textbook)
Partition:
Let {A_k}, k in K, be a collection of subsets of the nonempty set A. Then {A_k} is a partition of A iff these conditions apply:
1. each A_k is nonempty.
2. A = Union of all A_k over all k in K.
3. if A_1 intersect A_2 is nonempty, then A_1 = A_2
For example, the first part is easy to prove: since your equivalence relation is reflexive, you know that xRx for all x in A, so each equivalence class associated with any given element will at least contain itself as a member.
Use the reflexivity, symmetry and transitivity of R to prove the rest.
Good luck. (It's been years since I've seen this stuff, btw, so you take my advice at your own risk!)
<strong>
Yes it is. Now where's that damn towel?</strong><hr></blockquote>
Don't Panic