Subsection 8.6.4 Double Implication
Suppose that we want to prove a claim of the form:
P ≡ Q
In other words, P and Q share the same truth value.
Double implication statements of this sort often occur inside a universal quantifier. So we might have:
∀x (P(x) ≡ Q(x))
In other words, for any given x, either both P and Q are true of it or neither is.
The most straightforward way to prove equivalence claims of this sort is to rewrite P ≡ Q as:
(P → Q) ∧ (Q → P)
Now it’s clear that we can do two (we hope) simpler proofs:
Prove (P → Q).
Prove (Q → P).
When we do those two proofs, we are free to use whatever techniques are appropriate (not necessarily the same ones for both directions).
Consider the claim:
[1] For any integer x, (x + 2 is even) (x2 is even)
By the way, the intuition here is that both x + 2 and x2 will be even if and only if x itself is even.
Prove that (x + 2 is even) (x2 is even): Since x + 2 is even, we have that there exists an integer k such that:
\begin{gather*} x + 2 = 2k\\ x = 2k - 2 \\ = 2 (k – 1) \\ x2 = 2 2(k – 1)2 \end{gather*}Since k is an integer, so is k – 1. So (k – 1)2 is an integer and so is 2(k – 1)2. Thus x2 is even.
Prove that (x2 is even) (x + 2 is even): Let’s try to do this in the same way we just did the first direction. We have that x2 is even, so:
x2 = 2kWe want to say something about x, so it’s tempting to take the square root of both sides. We can do that, and we get:
x = √2kBut now we seem stuck. Our problem is that, in the first proof, we could square both sides and get integers. When we go the other direction and take the square root, we get something that we can’t say much of anything about. We know that x is an integer (we’re only talking about integers here). So, since √2 is not an integer, we know that k would have to have √2 as a factor. But this isn’t getting us anywhere.
We’re in a bind where we can’t simply reverse what we did in proving the other direction. We appear stuck. When this happens, it’s often a good idea to try a proof by contradiction (an indirect proof). It lets us, in a very restricted way, “reverse” our proof. Let’s try it:
The proof is by contradiction. We are assuming that x2 is even. Suppose that x + 2 were odd. Then there exists an integer j such that:
\begin{gather*} x + 2 = 2j + 1 \\ x = 2j - 1\\ x^2 = (2j - 1)2 Now we can square both sides.\\ = 4j^2 – 4j + 1 \\ = 2(2j^2 – 2j) + 1 \end{gather*}Since j is an integer, so is j2. So is 2j2. So is 2j. And thus, so is (2j2 – 2j). By letting k = (2j2 – 2j), we have that x2 is 2k + 1. But this means that x2 is odd, which contradicts the assumption that x2 is even. So our supposition that x + 2 is odd, must be false. x + 2 must be even.