1. A set S and a relation ∼ on S is given. For each example, check if ∼
is (i) reflexive, (ii) symmetric, and/or (iii) transitive. If ∼ satisfies the
property that you are checking, then prove it. If ∼ does not satisfy the
property that you are checking, then give an example to show it.
(a) S = R where a ∼ b if and only if a ≤ b.
Solution:
(i) Yes, ∼ is reflexive. Proof: Let a ∈ R. Then a ≤ a. So a ∼ a.
(ii) No, ∼ is not symmetric. Counterexample: 3 ≤ 4, but 4 6≤ 3.
That is, 3 ∼ 4 but 4 6∼ 3.
(iii) Yes, ∼ is transitive. Proof: Let a, b, c ∈ R and suppose that
a ∼ b and b ∼ c. Then a ≤ b and b ≤ c. So a ≤ c. Thus a ∼ c.
(b) S = R where a ∼ b if and only if |a| = |b|.
Solution:
(i) Yes, ∼ is reflexive. Proof: Let a ∈ R. Then |a| = |a|. So a ∼ a.
(ii) Yes, ∼ is symmetric. Proof: Let a, b ∈ R and suppose that
a ∼ b. Then |a| = |b|. So |b| = |a|. Thus b ∼ a.
(iii) Yes, ∼ is transitive. Proof: Let a, b, c ∈ R and suppose that
a ∼ b and b ∼ c. Then |a| = |b| and |b| = |c|. So |a| = |c|. Thus
a ∼ c.
(c) S = Z where a ∼ b if and only if a|b.
Solution:
(i) Yes, ∼ is reflexive. Proof: Let a ∈ Z. Then a(1) = a. Hence
a|a. So a ∼ a.
(ii) No, ∼ is not symmetric. Counterexample: 3|6, but 6 - 3.
(iii) Yes, ∼ is transitive. Proof: Let a, b, c ∈ Z. Suppose that
a ∼ b and b ∼ c. Then a|b and b|c. Thus there exists k, m ∈ Z
such that ak = b and bm = c. Then c = bm = (ak)m = a(km).
So a|c. Thus a ∼ c.
(d) S is the set of subsets of N where A ∼ B if and only if A ⊆ B.
Some examples of elements of S are {1, 10, 199}, {2, 7, 10}, and
{2, 10, 3, 7}. Note that {2, 7, 10} ∼ {2, 10, 3, 7}