MA 240, Theory of Proof, Section 1
Worcester State University, Fall 2019
Do all of the indicated exercises. Hand in only the bold exercises.

### Homework 9, due Wednesday, 12/4:

Chapter 11: 3, 10 (construct an enumeration of $$A \times B$$), 23, 24 (exhibit a bijection from one set to the other), 26 (for each part, clearly state whether the statement is true or false, and give a one sentence justification for your answer), 29.

(hand in): Prove that the set of integers $$\mathbb{Z}$$ is countable by constructing a bijection $$f:\mathbb{N} \to \mathbb{Z}$$.
[Use a piecewise function.]

(hand in): In exercise 3 you proved that if $$A$$ and $$B$$ are disjoint countable sets, then $$A \cup B$$ is countable. Prove that if $$A$$ and $$B$$ are any countable sets, then $$A \cup B$$ is countable.
[Start with your proof for exercise 3, and adust it to account for the possibility that $$A \cap B \neq \varnothing$$.]

(hand in): Let $$A_1, A_2, \ldots, A_n$$ be countable sets. Prove that $$A_1 \cup A_2 \cup \cdots \cup A_n$$ is countable.
[You may use the results of the previous exercise.]

(hand in): Let $$B$$ be a countable set and $$f:A \to B$$ a one-to-one function. Prove that $$A$$ is countable.
[Construct a bijection from $$A$$ to a subset of $$B$$.]

(Six exercises to hand in.)

### Homework 8, due Wednesday, 11/13:

Chapter 6: 5, 6(b), 10 ($$a$$ is a constant), 13, 21, 24, 48.

(hand in): Explain where you needed the hypothesis $$x > -1$$ in exercise 24. Would $$x \ge -1$$ have been sufficient?

(hand in): Recall that if $$f$$ and $$g$$ are differentiable functions, then $\frac{d}{dx} \left(f(x) + g(x)\right) = f'(x) + g'(x).$
Prove: If $$f_1, f_2, \ldots, f_n$$ are differentiable functions, then $\frac{d}{dx}\left(f_1(x) + f_2(x) + \cdots + f_n(x)\right) = f_1'(x) + f_2'(x) + \cdots + f_n'(x)$ for any natural number $$n$$.

(Five exercises to hand in.)

### Homework 7, due Wednesday, 11/6:

Chapter 5: 4, 12, 13, 15, 16, 18, 20, 25, 31, 60.

(hand in): Prove that there exists a function $$f: \mathbb{N} \to \mathbb{R}$$ such that $$f(n)$$ is irrational for all $$n \in \mathbb{N}$$.

A single sentence is all that is required for exercise 4.

For numbers 12 and 13, largest and smallest refer to the usual ordering of real numbers, so, for example, -1 is larger than -5.

For exercise 31 you might prefer not to follow the hint in the back of the text. In particular, it might be easier to start by proving that $$x+y$$ is even if and only if $$x-y$$ is even.

For exercise 60 part b, consider the possibilities for the congruence of $$pq + 2$$ modulo 3.

(Six exercises to hand in.)

### Homework 6, due Wednesday, 10/30:

Chapter 10: 3, 7, 8, 12a,b,c, 18, 23, 25, 26, 28, 33, 37, 42, 43 (for part (a), only prove it once - not "using as many of the following proof techniques as possible"), 58.

(hand in): Let $$a,b \in \mathbb{R}$$ with $$a \neq 0$$. Prove that the function $$f : \mathbb{R} \to \mathbb{R}$$ defined by $$f(x) = ax+b$$ is a bijection.

Exercises 23, 25, and 33 are good questions that require some thought - it's unfortunate that the answers are in the back of the book. We will discuss these in class.

(Five exercises to hand in.)

### Homework 5, due Wednesday, 10/16:

Chapter 9: 11, 12, 13, 14, 17, 18, 23, 25, 26, 28, 29, 30, 31, 39, 63.

(hand in): Let $$A = \{1,2,3\}$$. Define a relation $$R : A \to \mathcal{P}(A)$$ by $$x \, R \, Y$$ if $$x \in Y$$. What is $$R$$?
(Your answer should be an explicit definition of the set $$R$$, listing all its elements.)

(Six exercises to hand in.)

### Homework 4, due Wednesday, 10/2:

Chapter 1: 1, 3, 15, 16, 22, 29.

Check your answers to the odd-numbered questions in the back of the text.
For 16, the cardinality is 4.
(a) {1, 3, 5, 9, 13, 15}
(b) {9}
(c) {1, 5, 13}
(d) {3, 15}
(e) {3, 7, 11, 15}
(f) {1, 5, 13}

Chapter 4: 14, 18, 19, 20, 42, 45, 60, 61, 65, 67.

(For the congruence questions, give proofs based on the definition of congruence - do not quote the results proven in Section 4.2.)

(Five exercises to hand in.)

### Homework 3, due Wednesday, 9/25:

(hand in): Prove the following Lemma: Let $$a,b \in \mathbb{Z}$$. If $$a$$ is odd and $$ab$$ is even, then $$b$$ is even.

Chapter 4: 1, 2, 5, 6 (use the lemma above), 10, 73.

(hand in): Result 4.4 in your textbook is that if $$2 | (n^2 - 1)$$, then $$4 | (n^2 - 1)$$. A stronger statement is true: Prove that if $$2 | (n^2 - 1)$$, then $$8 | (n^2 - 1)$$.

(Five exercises to hand in.)

### Homework 2, due Wednesday, 9/18:

Chapter 3: 8, 9, 10, 16, 18, 19 (see the proof on page 93 that 5x-7 odd implies 9x+2 even), 49, 50.

(Five exercises to hand in.)

### Homework 1, due Wednesday, 9/11:

Chapter 2: 13, 15, 19, 21, 25, 26, 30 (simplify all arithemtic expressions), 34, 35, 46, 54, 60, 61, 67, 70, 71, 72, and:
(hand in): Show that $$P \Rightarrow Q$$ is logically equivalent to $$(\sim\! Q) \Rightarrow (\sim\! P)$$.

(Seven exercises to hand in.)

[Answers to Chapter 2, 72: (a) True, (b) True, (c) False, (d) True, (e) True, (f) False, (g) True, (h) False.]