MATH327 – HOMEWORK SOLUTIONS HOMEWORK #3

Section 1.3: Problems 1, 3, 4, 5 Section 1.4: Problems 2, 3, 5, 6, 15, 16

Krzysztof Galicki Problem 1.3.1.

The Cartesian product S ×B is a set of all ordered pairs (s, b), where s is any student of the college and b is any book in the library. As an example we can consider the following binary relation R ⊂ S × B

R = {(s, b) ∈ S × B | s read b}.

Problem 1.3.3.

a) not reflexive, not symmetric, not transitive.

b) reflexive, symmetric, but not transitive (here there is a slight problems as the word friend is not well defined; other answers can be argued for).

c) not reflexive, not symmetric, but transitive.

d) reflexive, symmetric, and transitive.

e) not reflexive, not symmetric, not transitive.

Problem 1.3.4. A = {a, b, c, d}. We give 4 examples of binary relations R ⊂ A × A such that each example has at least elements and is:

a) not reflexive and symmetric

| a b c d
− + − − − −
a |  x x x
b | x  x x
c | x x  x
d | x x x

b) not symmetric and not antisymmetric

| a b c d
− + − − − −
a |  x x x
b |  x x
c | x x  x
d | x x x

c) not symmetric but antisymmetric

| a b c d
− + − − − −
a |  x x x
b |  x x
c |  x
d |

d) transitive

| a b c d
− + − − − −
a |  x x x
b |  x x
c |  x
d |  x

Problem 1.3.5. Let A = {1, 2, 3}. Below are some examples of binary relations with the required properties. They are not unique.

a) {(1, 2), (2, 3), (1, 1)}.

b) {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3)}.

c) {1, 2), (2, 1)}.

d) {1, 2), (2, 3), (1, 3)}.

e) {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (3, 2)}.

f) {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3), (1, 3)}.

g) {(1, 1), (1, 2), (2, 1)}.

h) {(1, 1), (2, 2), (3, 3)}.

Problem 1.4.2.

a) R is clearly not reflexive as (2, 2) ∉ R. It is not transitive either.

b) R is not symmetric as (2, 3) ∈ R but (3, 2) ∉ R.

c) R is not symmetric as (1, 3) ∈ R but (3, 1) ∉ R.

Problem 1.4.3. This relations is the equality of elements

“ = ” = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)}.

Problem 1.4.5. Let A = \{\sqrt{3}, −2, 1/2, π, 6, \sqrt{12}\}.

a) define a relation “ ∼ ” by a ∼ b if a/b ∈ ℚ. We show that this is an equivalence relations:

1. It is reflexive: For any a ∈ A we have a/a = 1 and 1 ∈ Q.

2. It is symmetric: If a/b is rational then so is b/a. (Note that A does not contain 0).

3. It is transitive: If a/b ∈ ℚ and b/c ∈ ℚ than the product \frac{a}{b} · \frac{b}{c} = \frac{a}{c} ∈ ℚ.

b) The equivalence classes here are the subsets

\{−2, 1/2, 6\}, \{\sqrt{3}, \sqrt{12}\}, \{π\}.

Actually, the fact that \sqrt{3} and π are not equivalent, or that \frac{\sqrt{3}}{π} is not rational is not trivial. It follows from the fact that π is not an algebraic number (it is not a root of any polynomial with integer coefficients).

Problem 1.4.6. Let A = ℕ. Define

a ∼ b if a^{2} + b is even.

1. It is reflexive: For each a ∈ ℕ we have a^{2} + a even.

2. It is symmetric: Suppose a ∼ b. Then a^{2} + b is even. But that means that either both a and b are odd, or both a and b are even. In each case b^{2} + a must be even and, hence, b ∼ a.

3. It is transitive: If a ∼ b and b ∼ c then a^{2} + b is even and b^{2} + c is even. But then a^{2} + c = (a^{2} + b) + (b^{2} + c) − (b^{2} + b) is a sum of three even numbers and hence even. The parity of the first two follows from the hypothesis and the third is even by reflexivity of the relation “∼”.

Thus we have an equivalence relation. The equivalence classes are

[1] = {1, 3, 5, 7, …}, [2] = {2, 4, 6, 8, …}

the odd numbers (all equivalent to 1) and the even numbers (all equivalent to 2).

Problem 1.4.15.

a) It is an equivalence relation.

1. It is reflexive: For any (a, b) ∈ ℝ^{2} we have a+2b = a+2b and, hence (a, b) ∼ (a, b).

2. It is symmetric: if (a, b) ∼ (c, d) then a + 2b = c + 2d. But then c + 2d = a + 2b which says that (c, d) ∼ (a, b).

3. It is transitive: if (a, b) ∼ (c, d) and (c, d) ∼ (e, f) then a + 2b = c + 2d and c + 2d = e + 2f which implies that a + 2b = e + 2f, hence, (a, b) ∼ (e, f).

Here, the equivalence classes can be labeled by a real number λ and an equivalence class corresponding to λ consists of all point on the line x + 2y = λ in the XY -plane. We can also denote it by [(−λ, −2λ).

b) It is an equivalence relation and the proof all all three properties is identical to the one in (a). Here, the equivalence classes can be labeled by a real number λ and an equivalence class corresponding to λ consists of all point on the hyperbola xy = λ in the XY -plane. We can also denote it by [(λ, 1)]. The equivalence class [0, 1) consists of the two axes.

c) This is not not equivalence relation as it is not reflexive. For example, it is not It is not true that for any (a, b) we have (a, b) ∼ (a, b), that is a^{2} + b = a + b^{2}. Take (1, 2), for instance.

d) It is an equivalence relation.

1. It is reflexive: for any (a, b) ∈ ℝ^{2} we have a = a and, hence (a, b) ∼ (a, b).

2. It is symmetric: if (a, b) ∼ (c, d) then a = c. But then c = a which says that (c, d) ∼ (a, b).

3. It is transitive: if (a, b) ∼ (c, d) and (c, d) ∼ (e, f) then a = c and c = e which implies that a = e, hence, (a, b) ∼ (e, f).

Here, the equivalence classes can be labeled by a real number λ and an equivalence class corresponding to λ consists of all point on the line x = λ in the XY -plane (lines parallel to the y-axis). We can also denote it by [(λ, 0)]

e) This is not and equivalence relation as it is not reflexive. For example, it is not true that for any (a, b) ∈ ℝ^{2} we have ab = a^{2}. Take (1, 2), for instance.

Problem 1.4.16. For any a, b ∈ ℝ, define a ≃ b if a − b ∈ ℤ.

a) This is an equivalence relation because: 1. It is reflexive. For any real number a the difference a − a = 0 ∈ ℤ.

2. It is symmetric. If for some a, b the difference a − b is an integer then so is b − a = −(a − b).

3. It is transitive. Suppose a − b is an integer and b − c is an integer. Then a − c = a − b + b − c must also be an integer.

b) The equivalence class of 5 are all integers [5] = ℤ. The equivalence class of 5\frac{1}{2} are all “half-integers”, that is all real numbers obtained from integers by adding 1/2.

c) The quotient set is the half-closed interval [0, 1). For any λ ∈ [0, 1) define

[λ] = [0 + λ] = {x ∈ ℝ | x = n + λ, n ∈ ℤ}.