Direct Proofs and Proof by Contrapositive

Videos (~40 minutes)

Reading (~30 minutes)

DMOI Chapter 3.2 through Example 3.2.6.
Direct Proofs by Katy Dobson and Alan Slomson at the University of Leeds

Warmup (~40 minutes)

Problem 1

These are the problems at the end of Dobson + Slomson in the reading

Hint: The video Proving that Divisibility is Transitive (11:08) is not required for today but you might find it very helpful with one of the warmup problems.

For each of the following four statements:

First, represent the statement using logical symbols, including quantifiers. Define any predicates you need.
- For example, a symbolic representation of the first statement would be \(\forall m \in \mathbb{Z}: E(m) \rightarrow E(7m+4)\), where \(E(x)\) is the predicate “\(x\) is even.”
Then, write a careful proof of the statement, justifying each of your steps. You do not need to use logical symbols in your proofs.

If \(m\) is an even integer then \(7m+4\) is an even integer.
If \(m\) is an even integer and \(n\) is an odd integer then \(m+n\) is an odd integer.
If \(m\) is an even integer and \(n\) is an odd integer then \(mn\) is an even integer.
If \(a\), \(b\), and \(c\) are integers such that \(a\) divides \(b\) and \(b\) divides \(c\), then \(a\) divides \(c\).

Notation note: For some of these statements, you may find yourself needing to write things like \(\forall x \in \mathbb{Z}, \forall y \in \mathbb{Z}\). A common notational shortcut is to write \(\forall x, y \in \mathbb{Z}\) to mean the same thing while saving some space.

Problem 2

Prove that for all integers \(n\), it is the case that \(n\) is even if and only if \(3n\) is even. This proof has two parts: you must show that \(n\) being even implies that \(3n\) is even; then you must show that \(3n\) being even implies that \(n\) is even.

In your proof, please one of the two directions using direct proof. Then, prove the other direction using proof by contrapositive.