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.
For 22 the answers are:
(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.]