Equivalence RelationsDate: 02/10/2003 at 01:55:05 From: Minnow Subject: Equivalence Relations For integers m and n, define m~n if n|m^k and m|n^k for some positive integers j and k. a) Prove that ~ is an equivalence relation on Z b) Determine the equivalence classes of [1] [2] [6] and [12] c) Give a characterization of the equivalence class [m] Date: 02/10/2003 at 02:48:19 From: Doctor Jacques Subject: Re: Equivalence Relations Hi Minnow, First, I want to make sure I understood the question correctly: m ~ n iff we can find integers j and k such that m | n^j and n | m^k. (Note that you used k twice). I also assume that the integers j and k may depend on m and n. We could also say that m divides some power of n and n divides some power of m. If this is not what you intend, please write back. Part (a) ======== We must prove that ~ is an equivalence. As you say, we have three things to prove : reflexivity, symmetry, and transitivity. The best thing to do is simply to write down explicitly what we want to prove. Reflexivity ----------- We must show that we can find j and k such that: m | m^j and m | m^k This one is easy, any j and k > 0 will do. Symmetry -------- Assume that m | n^j and n | m^k. We must find p, q such that n | m^p and m | n^q This one is also easy, just take p = k and q = j Transitivity ------------ Assume that: m | n^j and n | m^k n | p^r and p | n^s We must find u and v such that: m | p^u and p | m^v I'll let you try this one, write back if you don't see it. It is somewhat easier to tackle part (c) before part (b) Part (c) ======== Assume that m ~ n, i.e. m | n^j and n | m^k Consider a prime factor p of m. As m | n^j, this means that p | n^j, and therefore that p | n. In a similar way, every prime factor of n divides m. This means that m and n have the same prime factors. Conversely, assume that m and n have the same prime factors, and let p be one of such factors. Assume that p^a | m and p^b | n, and that a and b are the highest exponents for which this is true, i.e.: m = p^a * m' n = p^b * n' and p divides neither m' nor n'. Assume first that m' = n' = 1, or that m = p^a and n = p^b. We will have m | n^j iff p^a | (p^b)^j = p^(bj), i.e. if bj >= a. As a and b are at least 1, we can certainly find such a j. In a similar way, we will have n | m^k iff ak >= b, and we can also find such a k. To summarize, we must have: bj >= a ak >= b Note that j and k are minimum values - any greater value will also do the job. We have such a condition for each prime factor of m and n (those factors are the same, by hypothesis). It is therefore sufficient to take for j and k the least value that satisfies all these conditions, and this will ensure that m | n^j and n | m^k. We have thus proven that m ~ n. In summary, m ~ n if and only if m and n have the same prime factors (possibly with different exponents). Part (b) ======== Now that we know the meaning of "~", this should be easy... Please do not hesitate to write back if you are still stuck. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ Date: 02/11/2003 at 22:54:06 From: Minnow Subject: Equivalence Relations I am still unable to see how (c) would work... Could you please explain it to me? Date: 02/12/2003 at 02:41:47 From: Doctor Jacques Subject: Re: Equivalence Relations Hi Minnow, and thank you for writing again. We want to show that equivalence classes are sets of numbers with the same prime factors (and different exponents for these factors). Let the prime factorisations of m and n be: m = p_1^r_1 * p_2^r_2 * ... n = q_1^s_1 * q_2^s^2 * ... We must show that m ~ n if and only if the p_i and q_j are the same set of numbers. Assume first that m ~ n, and consider a prime factor p_i of m; we have p_i | m. As there is a k such that m | n^k, p_i | n^k. Now, this implies that p_i | n, because, if p_i did not divide n, it could not divide n^k either. This shows that every prime factor of m is a prime factor of n (every p_i is among the q_j), and we can show in exactly the same way that every q_j is among the p_i. This means that the sets {p_i} and {q_j} are the same. Conversely, assume that m and n have the same prime factors. We can rewrite the factorisations as: m = p_1^r_1 * p_2^r_2 * ... n = p_1^s_1 * p_2^s_2 * ... We must show that m ~ n, i.e. that we can find j and k such that: m | n^j n | m^k Consider a prime p_i. The condition m | n^j requires that: p_i^r_i | p_i^(j*s_i) or j * s_i >= r_i. As r_i >= 1, this will be true if and only if j >= j_i = ceil(s_i / r_i) (this means the least integer such that j_i >= s_i/r_i). We have such a condition for each prime factor p_i. If we take j >= max (j_i), all these conditions will be satisfied, and we will have m | n^j. In exactly the same way, we can find a k such that n | m^k, and we have thus shown that m ~ n. As an example, let us prove that 24 ~ 18. The prime factorisations are 24 = 2^3 * 3 and 18 = 2 * 3^2. We must find j and k such that 24 | 18^j and 18 | 24 ^k. 18^j = 2^j * 3^(2j) In order to have 24 | 18^j, we must have: 2^3 | 2^j, or j >= 3 3 | 3^(2j), or j >= 1 Putting these conditions together, we find that it is enough to have j >= 3. Indeed, 18^3 = 5832 = 24 * 243. In a similar way, in order to have 18 | 24^k, we must have: 2 | 2^(3k), or k >= 1 3^2 | 3^k, or k >= 2 and we see that we can take k >= 2. Indeed, 24^2 = 576 = 18 * 32. As 24 | 18^3 and 18 | 24^2, we conclude that 24 ~ 18. Note that, for example, 24 is not equivalent to 42, because no power of 24 can be divisible by 7, as 24 itself is not. In summary, if the prime factoristation of m is: m = p_1^r_1 * p_2^r_2 *... * p_M^r_M the equivalence class of m is the set of numbers: n = p_1^s_1 * p_2^s_2 * ... * p_M^s^M where all the s_i are >= 1. If we look now at part (b), we find: [1] just contains the element 1. [2] is the set of powers of 2 : {2, 4, 8, ...} [6] = [12] is the set of numbers of the form 2^i*3^j, with i and j >=1 Extra credit ------------ We see that the gcd of all the numbers of an equivalence class is the number where all the exponents are 1. In the above example, all the numbers of the class [6] = [12] are multiples of 6; the converse is NOT true : 30 does not belong to the class. Please feel free to write back if you require further assistance. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ Date: 02/12/2003 at 14:09:56 From: Minnow Subject: Equivalence Relations Thank you so much for your prompt response... You have no idea how grateful I am that you are able to help me out... Could you please help me with these equivalence classes? I am now understanding equivalence relations a lot better, thanks to you. 1. Let S be the set of all finite subsets of Z. Define a relation on S by letting A~B if there is a bijection f: A-->B I proved that this is an equivalence relation, but I cannot b) give a description of the equivalence class of {1,2,3} 2. Let S = R and say a~b if a-b is in Z I once again proved that this is an equivalence relation, but I cannot describe the equivalence class. Would it be the set of all real numbers? Thank you SO much. Date: 02/13/2003 at 01:59:06 From: Doctor Jacques Subject: Re: Equivalence Relations Hi Minnow, In general, you have to imagine an equivalence class as the set of elements equivalent to a given element. 1. There is a bijection between two finite sets if and only if they have the same number of elements - there are your equivalence classes. 2. A given real number a will be equivalent to x iff the difference x-a is an integer. This means that a and x have the same integer part. For example, we have 2 ~ 5 3.78 ~ 6.78 (-3.2) ~ 5.8 Do you see the pattern ? - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/