VE203-Assignment 2 Solved

Exercise 2.1 

Show by induction that every nonempty finite set of real numbers has a smallest element.

Exercise 2.2 

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 

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 

Show that for any logical proposition φ using the connectives {¬,∧,∨,→}, i.e., wffs, there exists a proposition that is logically equivalent to φ using only

(i)       {↓}, where ↓ is the Peirce arrow (NOR), with p ↓ q ⇔ ¬(p ∨ q).

(ii)      {|}, where | is the Sheffer stroke (NAND), with p | q ⇔ ¬(p ∧ q).

Exercise 2.5 

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 

Let

                                                  m ∼ n           :⇔           2 | (n − m),                                                    m,n ∈ Z.

(i)         Show that ∼ is an equivalence relation.

(ii)       What partition Z2 := Z/ ∼ is induced by ∼?

(iii)      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)      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 

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 

Let f : X → Y be any function. Show that for all A,B ⊂ X, we have

(i)         f(A ∪ B) = f(A) ∪ f(B).

(ii)       f(A ∩ B) ⊂ f(A) ∩ f(B), where equality holds if f is injective.

(iii)      f(A) − f(B) ⊂ f(A − B), where equality holds if f is injective.

Show that for all C,D ⊂ Y , we have

(iv)      f−1(C ∪ D) = f−1(C) ∪ f−1(D). (v) (2pts) f−1(C ∩ D) = f−1(C) ∩ f−1(D).

(vi) 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