Direct Proof and the Element Method

Videos (~40 mins)

Reading (~20 mins)

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

Warmup (~50 mins)

Problem 1

Note: in the last part of this problem, you will find it useful to use the formal definition of divisibility: an integer \(a\) divides an integer \(b\) if there exists a third integer \(k\) such that \(ak = b\).

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

DMOI 3.5

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.

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

Problem 3

Define the two sets

\[ \begin{aligned} A &= \{x \in \mathbb{Z} \;|\; x > 0\;,\; x^2 \leq 32\} \\ B &= \{x \in \mathbb{Z} \;|\; x > 0 \;,\; \log_2 x < 7\} \end{aligned} \]

Use the element method to write a proof that that \(A \subseteq B\).