Assignment 5

DEPARTMENT OF MATHEMATICS, THE UNIVERSITY OF HONG KONG
MATH2012 Fundamental Concepts of Mathematics
Assignment 5, due 5pm on Monday, November 14, 2016
You need only to give your answers to those questions indicated with *. Other
problems are optional and will not be marked. However, we do expect you to
eventually finish all problems.
Relations
1. In each of the following cases, a relation R on a set A is given. Determine whether the
relation is reflexive, symmetric or transitive. For those that are equivalence relations, write
down all the distinct equivalence classes:
(a) A = Z and aRb if 2a + 2b ⌘ 0 (mod 4).

(b) A = Z and aRb if 4a + b ⌘ 0 (mod 5).
(c) A = R and aRb if |a b|  1.
(d) A = R and aRb if ab = 0.
*2. Let S be a nonempty set and P(S) the power set of S. For any A, B 2 P(S), define the
following relation on P(S):
ARB if A [ B = S.
Prove or disprove that R is (a) reflexive; (b) symmetric; (c) transitive.
*3. (Intersection of Relations)

Let R and S be equivalence relations on a set A. Prove that R \ S is also an equivalence
relation on A.
(Remark: Both R and S are subsets of A ⇥ A. Their intersection R \ S is also a subset
of A ⇥ A. )
1
*4. Let R be a relation defined on a set A. Prove that R is symmetric if and only if R = R .
(Remark: R 1 is the inverse relation of R defined in Definition 4.7)
1
*5. For any sets A, B and C, let R1 be a relation from A to B and R2 be a relation from B
to C. Define the composition of R1 and R2 to be the relation from A to C given by
R2 R1 := {(a, c) 2 A ⇥ C : (a, b) 2 R1 and (b, c) 2 R2 for some b 2 B} ✓ A ⇥ C.
(a) Let A = {1, 2, 3, 4}, B = {5, 6, 7} and C = {8, 9, 10}. Consider the relations
R1 = {(1, 5), (1, 7), (2, 6), (2, 7), (3, 5), (4, 5), (4, 6), (4, 7)} from A to B
and
R2 = {(5, 10), (6, 8), (6, 9), (6, 10), (7, 9), (7, 10)} from B to C.
Write down the composition R2 R1 from A to C.
(b) Prove that for any sets A, B, C, D and for any relations R1 from A to B, R2 from
B to C and R3 from C to D, we have
R3 (R2 R1 ) = (R3 R2 ) R1 .
*6. Let R be a relation defined on N ⇥ N by
(a, b) R (c, d) if a + d = b + c.
Prove that R is an equivalence relation on N ⇥ N.
7. Let S be the set of all straight lines in the Cartesian plane R2 . Two lines `1 and `2 are
said to be parallel if they coincide or they have no point in common. Define a relation R
on S in the following way: `1 R `2 if `1 and `2 are parallel.
(a) Prove that R is an equivalence relation on S.

(Hint: You may use an axiom in affine geometry that given a line ` and a point P
which is not on `, there is exactly one line m, having no point in common with ` and
passing through P .)
(b) Describe the equivalence class [`] of `, where ` is the x-axis.
(c) Let R0 be another relation defined on S such that `1 R0 `2 if `1 intersects `2 .
Prove or disprove that R0 is an equivalence relation on S.
8. Let R be the relation on R2 defined by (x, y)R(a, b) if y x2 = b a2 .
(a) Prove that R is an equivalence relation.

(b) Sketch the equivalence classes [(0, 0)], and [(1, 3/2)].
(c) Sketch a few more equivalence classes to illustrate the partition on R2 associated
with the relation R.
2
9. Let R be the relation on R2 defined by (x, y)R(a, b) if x2 + y 2 = a2 + b2 .
(a) Prove that R is an equivalence relation.

(b) Sketch the equivalence classes [(3, 4)], and [(0, 0)].
(c) Sketch a few more equivalence classes to illustrate the partition on R2 associated
with the relation R.
10. (See also Chapter 4, p.6, Exercise (a) )
(a) Let n 2 Z. Prove that
n2 ⌘ 1 (mod 3) () n ⌘ 1 (mod 3) or n ⌘ 2 (mod 3).
(b) A relation R is defined on Z by xRy if x2 ⌘ y 2 (mod 3). Prove that R is an

equivalence relation on Z.
(c) Use (a) to find the distinct equivalence classes and give a partition on Z with respect
to the relation R defined in (b).
*11. Let R be the equivalence relation defined on Z by xRy if x2 ⌘ y 2 (mod 5). Give a partition
on Z with respect to R.
(Hint: You may use the following results: For any x 2 Z,
x2 ⌘ 0 (mod 5) if and only if x ⌘ 0 (mod 5),

x2 ⌘ 1 (mod 5) if and only if x ⌘ 1 (mod 5) or x ⌘ 4 (mod 5),
x2 ⌘ 4 (mod 5) if and only if x ⌘ 2 (mod 5) or x ⌘ 3 (mod 5). )
(Remark: Make sure you know the proof of these results!)
12. (See also Chapter 4, p.6, Exercise (b) )

A relation R is defined on Z ⇥ Z by (x1 , y1 ) R (x2 , y2 ) if x1 = x2 .
(a) Prove that R is an equivalence relation on Z ⇥ Z.

(b) Describe the equivalence class [(0, 0)] of the element (0, 0). Is the class [(1, 0)] equal
to the class [(0, 0)]?
(c) Write down the distinct equivalence classes with respect to the relation R.
*13. Let R be the equivalence relation defined on R by xRy if x y 2 Z.
(a) Prove that R is an equivalence relation on R.

(b) Find [0].
(c) Show that [⇡] = {⇡ + n : n 2 Z}.
*14. Let R be the relation on R2 defined by (x, y)R(a, b) if
max {|x|, |y|} = max {|a|, |b|}.
3
(a) Prove that R is an equivalence relation on R2 .
(b) Sketch the equivalence classes [(0, 0)] and [(1, 3)].
*15. Prove or disprove: Let R be an equivalence relation defined on a set A. For any x, y 2 A,
either [x] \ [y] = ; or [x] = [y].
*16. Let A be a nonempty set and let P be a partition of A. Define a relation R (corresponding
to P ) on A by
xRy if there exists S 2 P such that x, y 2 S. (⇤)
(a) Let A = {1, 2, 3}. Write down ALL possible partitions of A. For each of the partition
P , use (⇤) to write down the relation R (as a subset of A ⇥ A) corresponding to P .
(b) Observe that all the relations in (a) are equivalence relations. Prove that this is true
in general, that is, prove that if A is a nonempty set, and P is a partition of A, then
the relation R corresponding to P defined in (⇤) must be an equivalence relation.
Extra Problems – (for those students who are studying/have studied linear algebra)
17. Let A, B be two n ⇥ n matrices. We say that A is similar to B if there exists a nonsingular
n ⇥ n matrix S such that A = S 1 BS.
(a) Prove that similarity is an equivalence relation on the set of n ⇥ n matrices.

(b) Denote by 0n and In the zero matrix and the identity matrix respectively. Find [0n ]
and [In ].
(c) Let A be a nonsingular n ⇥ n matrix. Consider the equivalence class [A] of A with
respect to the similarity relation. If X 2 [A], show that X is also nonsingular. In
other words, show that any matrix that is similar to a nonsingular matrix must also
be nonsingular.
(Remark: One also observes that any matrix that is similar to a singular matrix must
be singular.)
18. Let V be a vector space over R and H ✓ V be a vector subspace of V . Define a relation
R on V by
uRv if there exists h 2 H such that v = u + h.
(a) Prove that R is an equivalence relation on V .

(b) Describe the equivalence class [v] of any v 2 V .
(c) Denote by 0 the zero vector in V . Find [0].
(d) Let h 2 H. Find [h].

Assignment 5

Uploaded by

Copyright:

Available Formats

Assignment 5

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Assignment 5

Uploaded by

Copyright:

Available Formats

DEPARTMENT OF MATHEMATICS, THE UNIVERSITY OF HONG KONG

MATH2012 Fundamental Concepts of Mathematics

Assignment 5, due 5pm on Monday, November 14, 2016

(a) A = Z and aRb if 2a + 2b ⌘ 0 (mod 4).

Prove or disprove that R is (a) reflexive; (b) symmetric; (c) transitive.

*3. (Intersection of Relations)

R2 R1 := {(a, c) 2 A ⇥ C : (a, b) 2 R1 and (b, c) 2 R2 for some b 2 B} ✓ A ⇥ C.

Write down the composition R2 R1 from A to C.

*6. Let R be a relation defined on N ⇥ N by

Prove that R is an equivalence relation on N ⇥ N.

(a) Prove that R is an equivalence relation on S.

8. Let R be the relation on R2 defined by (x, y)R(a, b) if y x2 = b a2 .

(a) Prove that R is an equivalence relation.

(a) Prove that R is an equivalence relation.

10. (See also Chapter 4, p.6, Exercise (a) )

(a) Let n 2 Z. Prove that

n2 ⌘ 1 (mod 3) () n ⌘ 1 (mod 3) or n ⌘ 2 (mod 3).

(b) A relation R is defined on Z by xRy if x2 ⌘ y 2 (mod 3). Prove that R is an

x2 ⌘ 0 (mod 5) if and only if x ⌘ 0 (mod 5),

(Remark: Make sure you know the proof of these results!)

12. (See also Chapter 4, p.6, Exercise (b) )

(a) Prove that R is an equivalence relation on Z ⇥ Z.

*13. Let R be the equivalence relation defined on R by xRy if x y 2 Z.

(a) Prove that R is an equivalence relation on R.

*14. Let R be the relation on R2 defined by (x, y)R(a, b) if

max {|x|, |y|} = max {|a|, |b|}.

(a) Prove that similarity is an equivalence relation on the set of n ⇥ n matrices.

(a) Prove that R is an equivalence relation on V .

You might also like