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.
- Read Chapter 1 of the text.
- Compute 350 mod 14. Show how to obtain your answer.
- (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
- Compute 350 mod 12. Show how to obtain your answer.
- 350 = (33)1632 == (3)1632 = 318
= (33)6 == 36 = (33)2 == (3)2 = 9 mod 12
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.