Xavier D.

Domingo
Math 29 Problem Set 3

1.) Let Ω = {𝐴𝑛 : n ∈ Z}, where 𝐴𝑛 = (n − 1, 1 + n). Find ∩Ω and R − ∪Ω and prove your
claim.

∩Ω = ∅

𝐴−2 = (−3, −1)

𝐴−1 = (−2, 0)
𝐴0 = (−1, 1)
𝐴1 = (0, 2)
𝐴2 = (1, 3)

∪ Ω = {… , (−3, −1), (−2, 0), (−1, 1), (0, 2), (1, 3), … }
NTS: ∪Ω ⊆ {… , (−3, −1), (−2, 0), (−1, 1), (0, 2), (1, 3), … } and
{… , (−3, −1), (−2, 0), (−1, 1), (0, 2), (1, 3), … } ⊆ ∪Ω

(⟹) ∪ Ω ⊆ {… , (−3, −1), (−2, 0), (−1, 1), (0, 2), (1, 3), … }, Let x ∈ ∪ Ω
x ∈ 𝐴𝑛 for some n ∈ Z
n< x <n for some n ∈ Z
x ∈ {… , (−3, −1), (−2, 0), (−1, 1), (0, 2), (1, 3), … }
∴ ∪Ω ⊆ {… , (−3, −1), (−2, 0), (−1, 1), (0, 2), (1, 3), … }

(⟸) {… , (−3, −1), (−2, 0), (−1, 1), (0, 2), (1, 3), … } ⊆∪ Ω, let x
∈ {… , (−3, −1), (−2, 0), (−1, 1), (0, 2), (1, 3), … }
case 1: x≤ 𝑛 ⟹ x ∈ 𝐴𝑛 ⟹ 𝑥 ∈ ∪ Ω
case 2: x≥ 𝑛 ⟹ x ∈ 𝐴𝑥 ⟹ 𝑥 ∈ ∪ Ω

In any case, 𝑥 ∈ ∪ Ω, {… , (−3, −1), (−2, 0), (−1, 1), (0, 2), (1, 3), … } ⊆∪ Ω
Hence, ∪ Ω = {… , (−3, −1), (−2, 0), (−1, 1), (0, 2), (1, 3), … }
 Xavier D. Domingo
Math 29 Problem Set 3

2.) Let A = {1, 2, 5, 10}. Define R on A by xRy if and only if y divides x.

a) List all the members of R.
R = {(1,1), (2, 2), (4, 4), (5, 5), (10, 10), (1, 2), (1, 4), (1, 5), (1, 10), (2, 4), (2, 10), (5, 10)}
b) Determine whether R is reflexive, symmetric, antisymmetric, or transitive.
a.) As (1, 1), (2, 2), (4, 4), (5, 5), and (10, 10) belong to R.
therefore R is reflexive.

b.) Here, R is not symmetric

We may observe that (2, 10) ∈ R but (10, 2) is not in R. Infact, x divides y does not imply y
divides x when x=y.

c.) here R is antisymmetric.

we may observe that (1, 1) ∈ R, whenever we have (a, b) in R, we will never have (b, a) in R
until or unless (a=b).

d.) As x divides y and y divides z

(1, 5) ∧ (5, 10) → (1, 10)
therefore, the relation R is transitive.
3.) Assume R is a relation on A. Prove that R is reflexive on A if and only if 1𝐴 ⊆ R.

Solution:
(⟹) Let R be a reflexive relation on A and let (x, y) be an element in 1𝐴 . By the definition of the
Identity relation, we must have y = x, so (x, y) = (x, x). Moreover, since R is reflexive and x ∈ A
we must also have (x, x) ∈ R. Therefore, 1𝐴 ⊆ R.

(⟸) Now let R be a relation on A and assume1𝐴 ⊆ R. By definition of the identity relation, we
must have (x, x) ∈ 1𝐴 for all x ∈ A. Since1𝐴 ⊆ R, this implies (x, x) ∈ R for all x ∈ A. This is
precisely the definition of reflexivity, so, therefore, 1𝐴 ⊆ R implies R is reflexive. Since we have
shown both implications, it follows that R is reflexive if and only if1𝐴 ⊆ R.

4.) Let f: D → C be a bijective function. Prove that f has an inverse. (Hint: Think of f as a
relation. Then 𝑓 −1 is a relation. Prove that 𝑓 −1 is a function from C to D and that f ◦ 𝑓 −1 = 1𝐶 .
and 𝑓 −1 ◦ f = 1𝐷 .)

Proof. Let f : D → C be bijective. We will define a function: C → D as follows. Let c ∈ C. Since

f is surjective, there exists a ∈ A such that f(d) = c. Let 𝑓 −1 (c) = d. Since f is injective, this a is
unique, so 𝑓 −1 is well-defined. Now we much check that 𝑓 −1 is the inverse of f. First we will
show that 𝑓 −1 ◦ f =1𝐷 . Let d ∈ D. Let c = f(d). Then, by definition, 𝑓 −1 (c) = d. Then 𝑓 −1 ◦ f(d) =
𝑓 −1 (f(d)) = 𝑓 −1 (c) = d. Now we will show that f ◦ 𝑓 −1 =1𝐶 . Let c ∈ C. Let d = 𝑓 −1 (c). Then, by
definition, f(d) = c. Then f ◦ 𝑓 −1 (c) = f(𝑓 −1 (c)) = f(d) = c.
 Xavier D. Domingo
Math 29 Problem Set 3

5.) Let f : D → C and A, B ⊆ D. Prove: If f is 1-1, then f[A ∩ B] = f[A] ∩ f[B].

Proof. We show the implications separately. =⇒: Let 𝑥1 , 𝑥2 ∈ X be arbitrary with f(𝑥1 ) = f(𝑥2 ).
Let A = {𝑥1 } and B = {𝑥2 }. By assumption, f(A ∩ B) = f(A) ∩ f(B) = {f(𝑥1 )} ∩ {f(𝑥2 )} =
{f(𝑥1 )}. This implies that there exists an element x ∈ A ∩ B with f(x) = f(𝑥1 ). Since x ∈ A and x
∈ B we have that x = 𝑥1 and x = 𝑥2 , and hence 𝑥1 = 𝑥2 . This shows that f is injective.

6.) Let R be a relation on A. Prove that A/(A/R) = R.

Any partition P has a corresponding equivalence relation. Specifically, we define x ∼ y if and
only if x and y are in the same element of P. This relation is obviously reflexive, symmetric, and
transitive.
Let’s prove that if R is an equivalence relation on a set A, the equivalence classes of R form a
partition of A. First, recall the precise definition of an equivalence class.

[x] R = {y ∈ A | xRy}

First, since R is reflexive, xRx for any x ∈ A. So x ∈ [x] for any x ∈ A. Therefore, no
equivalence class is empty and the union of all equivalence classes is the whole set A. So the
only thing that remains to be shown is that two distinct equivalence classes don’t overlap.

Let x and y be two elements of A and suppose that [x]∩[y] ≠∅. We need to show that [x] = [y].

Since [x]∩[y] 6= ∅, we can pick an element c that is in [x]∩[y]. I.e. c ∈ [x] and c ∈ [y]. By the
definition of equivalence class, this means that xRc and yRc. Since R is symmetric, we also have
that cRy. So, by transitivity, xRy. And, thus by symmetry, yRx.

Let f be a function defined on a set A, and consider the relation R={(a,b) | f(a) = f(b)}. Show R is
an equivalence relation and describe the partition of A induced by R.

REF: f(a) = f(a) for all a Î A;

SYM: If f(a) = f(b), then f(b) = f(a);
TRAN: If f(a) = f(b) and f(b) = f(c), f(a) = f(c).

• Each partition set contains those elements whose output from f is the same
 Xavier D. Domingo
Math 29 Problem Set 3

7.) Define a relation S on R by xSy if and only if sin x = sin y.

a) Prove that S is an equivalence relation.

sin 𝑥 = sin 𝑥
(i)
(x, x) ∈ S∈R
xSx (Ɐx ∈R)
so, S is Reflexive

(ii)
xSy
sin 𝑥 = sin 𝑦 (Ɐx, y ∈R)
sin 𝑦 = sin 𝑥 (Ɐx, y ∈R)
ySx
so, sRs is Symmetric
(iii)
xSy ⟺ sin 𝑥 = sin 𝑦 (Ɐx, y, z ∈R)
𝑦𝑆𝑧 ⟺ sin 𝑦 = sin 𝑧 (Ɐx, y, z ∈R)
sin 𝑥 = sin 𝑧 ⟹ 𝑥𝑆𝑧
so, S is Transitive

∴ S is an equivalence relation

b) List the elements in the equivalence classes [0], [π/2], [π], and [π/3].

[𝑎] = {(−1)𝑛 𝑎 + 𝑛𝜋: 𝑛 ∈ Z}

[𝑎] = {−𝜋 − 𝑎, 𝑎, 𝜋 − 𝑎, 2𝜋 + 𝑎, 3𝜋 − 𝑎, … }
[0] = {𝑛𝜋: ∈ Z}
= {… , −2𝜋, −𝜋, 0, 𝜋, 2𝜋, … }
𝜋 𝜋
[ ] = {(−1)𝑛 + 𝑛𝜋 ∶ ∈ Z}
2 2
𝜋
= {2𝑛 − 1) : ∈ Z}
2
3𝜋 𝜋 𝜋 3𝜋
= {… , − ,− , , , …}
2 2 2 2
[ 𝜋] = {(−1)𝑛 𝜋 + 𝑛𝜋: 𝑛 ∈ Z}
= {… , −2𝜋, −𝜋, 0, 𝜋, 2𝜋, … }
𝜋 𝜋
[ ] = {(−1)𝑛 + 𝑛𝜋 ∶ ∈ Z}
3 3
5𝜋 4𝜋 𝜋 2𝜋 7𝜋
= {… , − ,− , , , , …}
3 3 3 3 3
 Xavier D. Domingo
Math 29 Problem Set 3

8.) Let A = {1, 2, 4, 5, 10}, and define a partial order by x ≤ y if x divides y.

a) Draw the Hasse diagram for the poset (A, ≤).
{(1,1), (2, 2), (4, 4), (5, 5), (10, 10), (1, 2), (1, 4), (1, 5), (1, 10), (2, 4), (2, 10), (5, 10)}

b) Find any maximal and minimal elements.

minimal elements: 4 & 10
maximal element: 1
c) Find any greatest or least elements.
greatest element: ∅
least element: 1
d) Find all lower bounds and upper bounds of {2, 4, 5}.
lower bound of {2, 4, 5: 1
upper bounds of {2, 4, 5}: ∅
e) Find the glb({2, 4}), if it exists.
glb of ({2, 4}): 1
f) Find the lub({2, 4, 5}), if it exits.
lub({2, 4, 5}): ∅