Practice with Proofs

Videos (0 minutes)

No videos for today.

Reading (~45 minutes)

Book of Proof, Chapter 5.

Focus on:

Reviewing the idea of contrapositive proof.
Congruence of integers (\(a \equiv b \mod{n}\)).
Proof style.

Warmup (~40 minutes)

Problem 1

Here are three facts about modular congruence which will become important for us later in the course.

Symmetry: For any \(a, b, n \in \mathbb{Z}\), if \(a \equiv b \pmod{n}\), then \(b \equiv a \pmod{n}\).
Reflexivity: For any \(a, n \in \mathbb{Z}\), it is the case that \(a \equiv a \pmod{n}\).
Transitivity: For any \(a, b, c, n \in \mathbb{Z}\), if \(a \equiv b \pmod{n}\) and \(b\equiv c \pmod{n}\), then \(a \equiv c \pmod{n}\).

Part A

Here are “proofs” of Symmetry and Reflexivity. These proofs contain the right general idea, but they are written very poorly.

Symmetry: \(a, b, n \in \mathbb{Z}\). \(a - b = cn\), \(b - a = -cn\). \(b = a \pmod{n}\).

Reflexivity: \(a-a=0\), since this is true for any integer. It is \(=\) to \(0n\).

Fix these proofs. For each of the two, go down the checklist in Chapter 5.3 of Book of Proof. Using this checklist, write correct, beautiful proofs that does not violate any of the rules in the list.

Part B

Write a correct, beautiful proof of Transitivity which does not violate any of the rules in the list.