Math 310: Problem set 1

Instructions: This problem set is due Thursday, August 31, 2006. Your goal is not only to give correct answers but to communicate your ideas well. Make sure you use good English.
1. Read Chapter 1 of the text.
• (It's hard to write the congruence symbol on the web, so I'll use == for it, and I'll use = for ordinary equality.)
350 = (33)1632 == (-1)1632 == 9 mod 14
• 350 = (33)1632 == (3)1632 = 318 = (33)6 == 36 = (33)2 == (3)2 = 9 mod 12
4. Give an example of a relation R on a set S (you pick the R and S) that is reflexive and symmetric but not transitive. Justify your answers (i.e., define your S and R explicitly, explain why R is reflexive and symmetric, and give a specific example of elements for which transitivity fails).
• Let S = {1,2,3} and let R = {(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2)}. Then R is reflexive since (s,s) is in R for every element s of S, and R is symmetric since (b,a) is in R whenever (a,b) is in R. However, R is not transitive, since (1,2) and (2,3) are in R but (1,3) is not.
5. Give an example of a relation R on a set S that is reflexive and transitive but not symmetric. Justify your answers.
• Let S = {1,2,3} and let R = {(1,1), (2,2), (3,3), (1,2)}. Then R is reflexive since (s,s) is in R for every element s of S, but R is not symmetric since (1,2) is in R but (2,1) is not in R. However, R is transitive, since if (a,b) and (b,c) are in R then by checking every possible case we see either a=b (and hence (a,c)=(b,c) is in R) or b=c (and hence (a,c)=(a,b) is in R).
• Here's another solution. Let S be the same but let R be the relation defined by ≥ (i.e., by "greater than or equal to"). Thus R = { (a,b) : a ≥ b for a and b in S }. Then a ≥ a for every a in S, so R (i.e., ≥) is reflexive, and whenever a ≥ b and b ≥ c are true, we know a ≥ c is true, so R is transitive. However, R is not symmetric, since 2 ≥ 1 is true but 1 ≥ 2 is not; i.e., (2,1) is in R but (1,2) is not in R.
6. Give an example of a relation R on a set S (you pick the R and S) that is transitive and symmetric but not reflexive. Justify your answers.
• Let S = {1,2,3} and let R = { } be the empty relation. Then as discussed in class R is not reflexive but it is symmetric and transitive.
7. Consider the relation R = {(a, b) : a and b are reals and 0 < |a - b| < 1} on the set S = R of real numbers. For each of the three properties of an equivalence relation, either show the property holds, or given an example for which it does not hold.
• Reflexivity fails since (a,a) is never in R, because 0 < |a - a| is false. Symmetry holds since |a - b| = |b - a| always holds, so if (a,b) is in R, then 0 < |a - b| < 1, hence 0 < |b - a| < 1, so (b,a) is in R. Transitivity fails since (0.1,1.0) and (1.0,1.9) are in R but (0.1,1.9) is not in R.
8. Consider the relation R = {(a, b) : a and b are reals and |a - b| < 1} on the set S = R of real numbers. Is R an equivalence relation? Justify your answer.
• Although R is reflexive and symmetric, R is not an equivalence relation, since R is not transitive: (0.1,1.0) and (1.0,1.9) are in R but (0.1,1.9) is not in R.
9. Consider the relation R = {(a, b) : a and b are integers and |a - b| < 1} on the set S = Z of integers. Is R an equivalence relation? Justify your answer.
• In this case R is an equivalence relation, since in order for integers a and b to satisfy |a - b| < 1 we must have a = b, and ordinary "=" is reflexive, symmetric and transitive.