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.]