Chapter 0 wrap-up

Readiness: the discrete math this course leans on

Closing thought

Each tool here answers a question the rest of this course keeps asking. Sets and Cartesian products say what you are combining. Bijections say when two collections match up exactly, with nothing doubled and nothing missed. Equivalence relations sort a set into classes that never overlap. Direct proof, contradiction, contrapositive, and induction turn a pattern you noticed into a fact you can trust. The division algorithm turns any integer into a quotient and a remainder in a fixed range.

So you can already handle a small case of what's coming. Sort the integers by their remainder when divided by $3$ , and you get three classes. Add any number with remainder $1$ to any number with remainder $2$ , and the sum always has remainder $0$ , since $(3a+1) + (3b+2) = 3(a+b+1)$ . Chapter 1 takes that idea, combining two things to get a third of the same kind, and asks which rules make it trustworthy.

Recipes in this chapter

Step-by-step procedures for the problem types this chapter teaches.

Check a relation and find its classes Equivalence relations and partitions, revisited Find q and r from the division algorithm Divisibility and the division algorithm, revisited

Chapter review

One practice set per topic this chapter taught — same fixed, ungraded ladders as the practice panels inside each section.

Practice: Readiness check: sets, functions, and equivalence relations (5 problems · doesn’t affect your progress)

Let $A = \{2, 4, 6, 8\}$ and $B = \{4, 8, 12\}$ . Which set is $A \setminus B$ ?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

Why

$A \setminus B$ keeps what is in $A$ and removes anything also in $B$ . Removing $4$ and $8$ from $A$ leaves $\{2, 6\}$ . $\{12\}$ is $B \setminus A$ , and $\{4, 8\}$ is $A \cap B$ .

$\{2, 6\}$

A set $A$ has 4 elements. How many ordered pairs does $A \times A$ contain?

Correct! 🎉 Not quite.

Why

$|A \times A| = 4 \cdot 4 = 16$ . Order matters, so $(a, b)$ and $(b, a)$ count separately, and pairs like $(a, a)$ count too.

Correct answer

Also accepted:

Why

Each of the 4 choices for the first entry pairs with each of the 4 choices for the second.

Define $f$ on $\{1, 2, 3, 4\}$ by $f(1) = 2$ , $f(2) = 4$ , $f(3) = 2$ , $f(4) = 1$ . Which describes $f$ ?

Correct! 🎉 Not quite.

Why

$f(1) = f(3) = 2$ , so $f$ is not one-to-one. No input reaches $3$ , so $f$ is not onto. On a finite set mapped to itself, failing one of these always comes with failing the other.

Neither one-to-one nor onto

On $\{1, 2, 3\}$ , let $f(1) = 3$ , $f(2) = 1$ , $f(3) = 2$ and $g(1) = 2$ , $g(2) = 3$ , $g(3) = 1$ . What is $(g \circ f)(1)$ ?

Correct! 🎉 Not quite.

Why

$f(1) = 3$ , then $g(3) = 1$ . In fact $g \circ f$ sends every element back to itself, so $g$ undoes $f$ .

Correct answer

Also accepted:

Why

$(g \circ f)(1) = g(f(1))$ : apply $f$ first.

On the integers, say $x \sim y$ when $|x - y| \le 1$ . Which property of an equivalence relation fails?

Correct! 🎉 Not quite.

Why

$0 \sim 1$ and $1 \sim 2$ , but $|0 - 2| = 2$ , so $0 \not\sim 2$ . The reflexive property holds since $|x - x| = 0$ , and the symmetric property holds since $|x - y| = |y - x|$ .

Try a chain of three integers, each one step from the next.

The transitive property

Practice: Readiness check: proof, induction, and division (5 problems · doesn’t affect your progress)

You want to prove that there is no largest even integer. Which first move fits best?

Correct! 🎉 Not quite.

Why

A claim that something doesn't exist gives nothing to reason forward from, so assume it does exist. If $M$ were the largest even integer, $M + 2$ would be a larger one. Checking examples or one integer proves nothing about all of them.

Assume some largest even integer exists, then derive something impossible

What is the contrapositive of "If $n^2$ is odd, then $n$ is odd"?

Correct! 🎉 Not quite.

Why

The contrapositive of "if P then Q" is "if not Q then not P". Here not Q is " $n$ is even" and not P is " $n^2$ is even". "If $n$ is odd, then $n^2$ is odd" swaps P and Q without negating them. "If $n^2$ is even, then $n$ is even" negates without swapping. Neither is equivalent to the original.

If $n$ is even, then $n^2$ is even

You prove $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ by induction. In the step, you assume it for $n = k$ . Which term do you add to both sides to reach $n = k + 1$ ?

Correct! 🎉 Not quite.

Why

Going from the sum up to $k$ to the sum up to $k + 1$ adds one more term, $k + 1$ . Then $\frac{k(k+1)}{2} + (k + 1) = \frac{(k+1)(k+2)}{2}$ , the formula at $n = k + 1$ .

$k + 1$

The division algorithm writes $-23 = 6q + r$ with $0 \le r < 6$ . What is the remainder $r$ ?

Correct! 🎉 Not quite.

Why

$6 \cdot (-4) = -24$ is the largest multiple of $6$ not above $-23$ , so $r = -23 - (-24) = 1$ . Taking $q = -3$ would leave $r = -5$ , which is out of range.

Correct answer

Also accepted:

Why

Find the largest multiple of $6$ that is at most $-23$ .

Each claim below is proved by building case $k+1$ as shown. Which proof needs strong induction rather than weak?

Correct! 🎉 Not quite.

Why

Paying $k + 1$ cents by adding one $4$ -cent stamp to $k - 3$ cents needs the claim at $k - 3$ , not at $k$ . Strong induction allows that. The divisibility, sums, and powers steps each use only case $k$ , so weak induction is enough for them.

Look for a step that leans on a case other than $k$ itself.

Stamps: pay $k+1$ cents ( $k+1 \ge 16$ ) by adding a $4$ -cent stamp to $k-3$ cents

Take the chapter quiz On to Chapter 1 →

← Divisibility and the division algorithm, revisited Foundations and the idea of a group →