- Read Chapter 1 of the text.
- Compute 3
^{50}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.)

3^{50}= (3^{3})^{16}3^{2}== (-1)^{16}3^{2}== 9 mod 14

- (It's hard to write the congruence symbol on the web, so I'll
use == for it, and I'll use = for ordinary equality.)
- Compute 3
^{50}mod 12. Show how to obtain your answer.- 3
^{50}= (3^{3})^{16}3^{2}== (3)^{16}3^{2}= 3^{18}= (3^{3})^{6}== 3^{6}= (3^{3})^{2}== (3)^{2}= 9 mod 12

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