Necessity and sufficiency

Given two propositions \(P\) and \(Q\), we say that \(Q\) is necessary for \(P\) if \(P \Rightarrow Q\) holds and that \(Q\) is sufficient for \(P\) if \(Q \Rightarrow P\) holds.

We call \(Q \Rightarrow P\) the converse of \(P \Rightarrow Q\).

It is quite common to see statements in mathematics using these terms. It is therefore important to be comfortable with what they mean.

Examples

1. Let \(n\) be an integer. “\(n\) is even” is sufficient for “\(n^2\) is even”.

   In other words, if \(n\) is even, then \(n^2\) is even.

   The converse reads, “If \(n^2\) is even, then \(n\) is even.”

   Note that both the original statement and its converse are true.

2. Let \(x \in \mathbb{R}\). If \(x\) is an integer, then \(\lvert \sin x \rvert < 1\).

   The converse reads, “if \(\lvert \sin x \rvert < 1\), then \(x\) is an integer.” However, this statement is false because \(|\sin \frac{\pi}{4}| < 1\) but \(\frac{\pi}{4}\) is not an integer.

Proving if-and-only-if (iff) statements

Proving a statement of the form \(P \Leftrightarrow Q\) or \(\forall x, P(x) \Leftrightarrow Q(x)\) typically requires two proofs: one for necessity and one for sufficiency. Below are two possible outlines for proving \(\forall x, P(x) \Leftrightarrow Q(x)\) that one can adopt.

1. Theorem. \(\forall x \in U, P(x) \Leftrightarrow Q(x)\)

   Proof.

   Let \(a\) be an arbitrary element of \(U\).

   We first prove necessity; that is, \(P(a) \Rightarrow Q(a)\).

   …

   Next, we prove sufficiency; that is, \(Q(a) \Rightarrow P(a)\).

   …

2. Theorem. \(\forall x \in U, P(x) \Leftrightarrow Q(x)\)

   Proof.

   Let \(a\) be an arbitrary element of \(U\).

   Suppose that \(P(a)\) holds.

   …

   Thus, \(Q(a)\) holds. This proves necessity.

   Conversely, suppose that \(Q(a)\) holds.

   …

   Thus, \(P(a)\) holds. This proves sufficiency.

Note that it is not necessary to prove necessity first. As long as both necessity and sufficiency are established, the proof is complete.

Examples

1. \(\forall n \in \mathbb{Z}, 2 \mid n \Leftrightarrow (-1)^n = 1.\)

   Proof. Let \(n \in \mathbb{Z}.\)

   We first prove necessity; that is, if \(2 \mid n\), then \((-1)^n = 1\).

   Note that by definition, \(2 \mid n\) means \(n = 2k\) for some integer \(k\). Thus, \((-1)^n = (-1)^{2k} = ((-1)^2)^k = 1^k = 1\).

   Next, we prove sufficiency; that is if \((-1)^n = 1\), then \(2 \mid n\).

   We prove the contrapositive instead; namely, if \(2 \not \mid n\), then \((-1)^n \neq 1\).

   Note that \(2 \not \mid n\) implies that \(n\) is odd. Thus, \(n = 2k+1\) for some integer \(k\). Then, \((-1)^n = (-1)^{2k+1} = (-1)(-1)^{2k} = (-1)((-1)^2)^k = -1^k = -1\neq 1\).

2. Let \(x\) and \(y\) be real numbers. Prove that \(x + y = x\) if and only if \(y = 0\).

   Proof. Suppose that \(y = 0\). Then \(x + y = x + 0 = x\).

   Conversely, suppose that \(x + y = x\). Adding \(-x\) to both sides of the equation gives \((-x) + x + y = (-x) + x\), giving \(y = 0\).

3. Let \(b\) be a real number. Then \(x^2 + 2x + b \geq 0\) for every real number \(x\) iff \(b \leq 1\).

   Proof. Note that \[\begin{align*} x^2 + 2x + b & = (x^2 + 2x + 1) - 1 + b \\ & = (x - 1)^2 - (1 - b) \\ \end{align*}\] Hence, we can prove instead the equivalent statement, “\((x - 1)^2 \geq b - 1\) for every \(x \in \mathbb{R}\) iff \(b \leq 1\).”

   Suppose that \((x - 1)^2 \geq b - 1\) for every \(x \in \mathbb{R}\).. Setting \(x = 1\) gives \(0 \geq b -1\), implying that \(b \leq 1\). This proves necessity.

   Conversely, suppose that \(b \leq 1\). Then \(b - 1 0 \leq 0\). Since \((x-1)^2\) is never negative for every \(x \in \mathbb{R}\), we have \((x - 1)^2 \geq b - 1\) for every \(x \in \mathbb{R}\). This proves sufficiency.

Exercises

1. For each of the following statements, write down its converse. If the converse is true, give a proof. Otherwise, give a counterexample.

   1. Let \(x\) be a real number. If \(x \geq 2\), then \(x^2 \geq 4\).

   2. If \(x = 1\), then \(x^3 - 3x + 3x - 1 = 0\).

   3. Let \(n \in \mathbb{N}\). If \(10 \mid n\), then \(5 \mid n\).

2. Let \(x\) and \(y\) be real numbers. Prove that \(xy = 0\) iff \(x = 0 \vee y = 0\).

3. Prove that \(\forall x \in \mathbb{R}, \exists y \in \mathbb{R}, x - 2y = xy \Leftrightarrow x \neq -2\).