Description

Exercise 2.1 (2pts)
Show by induction that every nonempty finite set of real numbers has a smallest element.
Exercise 2.2 (2pts)
What is wrong with the following proof of the “theorem”?
Theorem. Given any positive number a, then for all positive integer n, we have an−1 = 1.
Proof. If n = 1, an−1 = a1−1 = a0 = 1. By induction, assume that the theorem is true for n = 1,2,…,k, then for n = k + 1,
1 therefore the theorem is true for all positive integers n.
Exercise 2.3 (2pts)
Define a nonempty sorted list as either
• ⟨x,⟨⟩⟩; or
• ⟨x,⟨y,L⟩⟩ where x ≤ y and ⟨y,L⟩ is a nonempty sorted list.
Prove by structural induction that in a nonempty sorted list ⟨x,L⟩, every element z in L satisfies z ≥ x.
Exercise 2.4 (4pts)
Show that for any logical proposition φ using the connectives {¬,∧,∨,→}, i.e., wffs, there exists a proposition that is logically equivalent to φ using only
(i) (2pts) {↓}, where ↓ is the Peirce arrow (NOR), with p ↓ q ⇔ ¬(p ∨ q).
(ii) (2pts) {|}, where | is the Sheffer stroke (NAND), with p | q ⇔ ¬(p ∧ q).
Exercise 2.5 (4pts)
Show by induction that the following two algorithms mergeSort and merge are correct.

Input: A[1…n], unsorted array
3
4 5
6
7
8
3
4
5
6
7
8
9
10
Page 1 of 2
Exercise 2.6 (10pts)
Let
m ∼ n :⇔ 2 | (n − m), m,n ∈ Z.
(i) (1pt) Show that ∼ is an equivalence relation.
(ii) (1pt) What partition Z2 := Z/ ∼ is induced by ∼?
(iii) (2pts) Define addition and multiplication on Z2 by the addition and multiplication of class representatives, i.e.,
[m] + [n] := [m + n], [m] · [n] := [m · n].
Show that these operations are well-defined, i.e., independent of the representatives m and n of each class.
(iv) (6pts) Verify that (Z2,+,·) is a field, i.e.,
(a) Closure under addition, i.e., ∀m,n ∈ Z2, ∃m + n ∈ Z2;
(b) Closure under multiplication, i.e., ∀m,n ∈ Z2, ∃m · n ∈ Z2;
(c) Commutativity of the addition “+”, i.e., m + n = n + m for all m,n ∈ Z2;
(d) Commutativity of the multiplication “·”, i.e., m · n = n · m for all m,n ∈ Z2;
(e) Associativity of the addition “+”, i.e., (m + n) + k = n + (m + k) for all m,n,k ∈ Z2;
(f) Associativity of the multiplication “·”, i.e., (m · n) · k = n · (m · k) for all m,n,k ∈ Z2;
(g) Distributivity: k · (m + n) = k · m + k · n for all k,m,n ∈ Z2;
(h) Existence of an additive identity, i.e., ∃0 ∈ Z2, ∀m ∈ Z2: 0 + m = m + 0 = m;
(i) Existence of a multiplicative identity, i.e., ∃1 ∈ Z2, ∀m ∈ Z2: 1 · m = m · 1 = m;
(j) Existence of an additive inverse, i.e., ∀m ∈ Z2, ∃n ∈ Z2 such that m + n = n + m = 0; (k) Existence of a multiplicative inverse, i.e., ∀m ∈ Z2, m ̸= 0, ∃n ∈ Z2 such that m · n = n · m = 1; (l) The additive and multiplicative identity elements are different, i.e., 0 ̸= 1.
Exercise 2.7 (8pts)
Determine whether the relation R on the set of all integers is reflexive, symmetric and/or transitive, where (x,y) ∈ R

iff
(i) x + y = 0 (ii) 2 | (x − y) (iii) xy = 0

(iv) x = 1 or y = 1
(v) x = ±y (vi) x = 2y (vii) xy ≥ 0 (viii) x = 1
Exercise 2.8 (12pts)
Let f : X → Y be any function. Show that for all A,B ⊂ X, we have
(i) (2pts) f(A ∪ B) = f(A) ∪ f(B).
(ii) (2pts) f(A ∩ B) ⊂ f(A) ∩ f(B), where equality holds if f is injective.
(iii) (2pts) f(A) − f(B) ⊂ f(A − B), where equality holds if f is injective.
Show that for all C,D ⊂ Y , we have
(iv) (2pts) f−1(C ∪ D) = f−1(C) ∪ f−1(D). (v) (2pts) f−1(C ∩ D) = f−1(C) ∩ f−1(D).
(vi) (2pts) f−1(C − D) = f−1(C) − f−1(D).
Note that the function f−1 : 2Y → 2X has better behavior than f : 2X → 2Y with respect to union, intersection, and complementation. (Note that f : 2X → 2Y is induced by f : X → Y , which is a not uncommmon overloading/abusing
of notation.)
Page 2 of 2