Quiz 1

(1p) What is the contrapositive of “if n is non-zero, then pigs can fly”?

1. If pigs can fly, then n is non-zero.

2. If pigs cannot fly, then n is non-zero.

3. If pigs can fly, then n is not non-zero.

4. If pigs cannot fly, then n is not non-zero.

(1p) Which of the following proof methods are correct? (Here ℕ stands for the set of natural numbers, {0, 1, 2, …}, and ℤ stands for the set of integers, {…,  − 2,  − 1, 0, 1, 2, …}. The variable P stands for an arbitrary integer predicate.)

1. Proof by cases: P(0) × (∀n ∈ ℕ.P(n + 1)) ⇒ ∀n ∈ ℕ.P(n).

2. Proof by cases: (∀n ∈ ℕ.P( − (n + 1))) × (∀n ∈ ℕ.P(n + 1)) ⇒ ∀i ∈ ℤ.P(i).

3. Induction: P(0) × (∀n ∈ ℕ.P(n) ⇒ P(n + 1)) ⇒ ∀n ∈ ℕ.P(n).

4. Induction: P(0) × (∀i ∈ ℤ.P(i) ⇒ P(i + 1)) ⇒ ∀i ∈ ℤ.P(i).

(2p) Where is the error in the following “proof” of “All horses have the same colour”?

1. Let us prove the following generalisation: For every positive n ∈ ℕ and every set of horses of size n, every horse has the same colour.
2. We proceed by induction on n.
3. Base case, n = 1:
4. In a set with one horse all horses have the same colour.
5. Step case, n > 1:
6. We are given a set of n horses, H = {h₁, …, h_n}.
7. Let us form two subsets of this set, A = {h₁, …, h_n − 1} and B = {h₂, …, h_n}.
8. Note that H = A ∪ B.
9. The set A has size n − 1, so the inductive hypothesis implies that all horses in A have the same colour.
10. Similarly all horses in B have the same colour.
11. The sets A and B overlap, so all horses in H = A ∪ B have the same colour.

(This question is based on an example that seems to be due to George Pólya.)

(1p) Define the set T inductively by the following rules:

• If n ∈ ℕ, then leaf(n) ∈ T.

• If l, r ∈ T, then node(l, r) ∈ T.

Define the function f ∈ T → ℕ by recursion on the structure of its argument in the following way:

  f(leaf(n)) = n
  f(node(l, r)) = f(r) − f(l)

What is the value of f(node(node(leaf(1), leaf(2)), leaf(3)))?