Group  ^{List No.}^{Last Name}^{Name}  ^{Student No.}^{Department}  ^{Section}^{Signature} ^{:}^{:}  ^{:}^{:}^{:}^{:}^{:}^{:}^{:}^{:}^{:}^{:}^{:}^{Code}^{Acad. Year}^{Semester}^{Instructor}^{Date}^{Time}^{Duration}  M E T U Department of Mathematics^{Fundamentals of Mathematics}^{Midterm 2}^{Math 111}^{2013}^{Fall}^{G.Ercan, S.Finashin,}^{M.Kuzucuoğlu, ^{}Ö.Küçüksakallı.}^{December 19, 2013}^{17:40}^{100 minutes}  ^{6 QUESTIONS ON 4 PAGES}^{60 TOTAL POINTS}^{1}  ^{2}  ^{3}  ^{4}  ^{5}  ^{6}

1. (12pts) Let f : ℤ → ℤ be the function defined by f(x) = 2x + 3. Define a relation R on ℤ by xRy if and only if f(x) ≡ f(y)(mod 5) for any x, y in ℤ.

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

(b) Describe the R-equivalence class [0] explicitly.

2. (10pts) (a) Define the function f : ℤ → ℤ by f(x) = 7x − 2. Determine whether f is injective, surjective and bijective.

(b) Define the function g : ℚ → ℚ by g(x) = 7x − 2. Determine whether g is injective, surjective and bijective.

3. (10pts) Prove that a function f : A → B has a left inverse if and only if f is injective.

4. (6pts) Give an example of subsets A, B and C of ℤ such that A − (B − C) ≠ (A − B) − C.

5. (10pts) Prove that if A, B and C are sets, then A × (B − C) = (A × B) − (A × C).

Solution: Let us show first that \underline{A × (B − C) ⊆ (A × B) − (A × C))}. If we take any (x, y) ∈ A × (B − C), then x ∈ A and y ∈ B − C, the latter means that y ∈ B and y ∉ C. Then (x, y) ∈ A × B (since x ∈ A and y ∈ B), and (x, y) ∉ A × C (since y ∉ C). Thus, (x, y) ∈ (A × B) − (A × C), and we proved that A × (B − C) ⊆ (A × B) − (A × C).

Now, let us show that \underline{A × (B − C) ⊇ (A × B) − (A × C)}. If we take any (x, y) ∈ (A × B) − (A × C), then (x, y) ∈ (A × B), but (x, y) ∉ (A × C). So, x ∈ A and y ∈ B (since (x, y) ∈ (A × B)). Since x ∈ A, but (x, y) ∉ A × C, we can conclude that y ∉ C. Thus, y ∈ B − C (since y ∈ B and y ∉ C) and (x, y) ∈ A × (B − C). We proved the other inclusion A × (B − C) ⊇ (A × B) − (A × C), and therefore,

\underline{A × (B − C) = (A × B) − (A × C)}.

6. (12pts) Consider the poset (P(ℤ), ⊆) and let A = {{4}, {1, 2}, {2, 3}, {3, 4}, {1, 3, 4}}.

(a) Draw a Hasse diagram for the poset (A, ⊆).

Solution:

{1, 3, 4}
|
{1, 2} {3, 4} {2, 3}
|
{4}

(b) List all maximal elements of (A, ⊆). Solution: {1, 2}, {2, 3}, {1, 3, 4}.

(c) List all minimal elements of (A, ⊆). Solution: {4}, {1, 2}, {2, 3}.

(d) Are there the greatest and the least elements in (A, ⊆). Solution: There is no greatest element (which contains all the others) and no least element (which is contained in all the others).

(e) Find the least upper bound and the greatest lower bound for A in the poset (P(ℤ), ⊆), if any. Solution: The least upper bound is {1, 2, 3, 4} (the union of the sets that are elements of A), and the greatest lower bound is ∅ (the intersection of the sets that are elements of A).