Proving and Disproving Universal Statements
Proving Universal Statements Directly
Recall the following:
For example, to prove a universally quantified statement such as “\(\forall n\in \mathbb{N}, n\geq 5\ or\ n\leq 4\)” we need to show that \(n\geq 5\ or\ n\leq 4\) for every single natural number \(n\).
It is NOT ENOUGH to show that \(n\geq 5\ or\ n\leq 4\) for only a few different \(n\)’s (such as \(n=1,2\) or \(3\)), because the original statement asserted that \(n\geq 5\ or\ n\leq 4\) is true FOR EVERY NATURAL NUMBER. It would also be impractical (read: impossible) to check \(n\geq 5\ or\ n\leq 4\) for every single number \(n\in \mathbb{N}\). What do we do?
This is best explained with an example.
Proof: Let \(a\) be an arbitrary real number. Then note that the product \((a+1)(a-1)\) expands as follows.
$$\begin{align} (a+1)(a-1)&=a^2+a-a-1\\&=a^2-1.\end{align}$$
Therefore, since we have shown that \((a+1)(a-1)=a^2-1\) for an arbitrary real number \(a\), it follows that for all (or “for any”) real numbers \(x\), \((x+1)(x-1)=x^2-1\). QED
Proof: Let \(n\) and \(m\) be (arbitrary) natural numbers. Note that the expression \(\frac{1}{n}\cdot\frac{1}{m}=\frac{1}{nm}.\) And, since an integer times another integer is indeed an integer, it follows that \(nm\) is an integer. Thus, since \(\frac{1}{n}\cdot\frac{1}{m}=\frac{1}{nm}\) and since \(\frac{1}{nm}\) is a fraction of integers, it follows that \(\frac{1}{n}\cdot\frac{1}{m}\) is also a fraction of integers, and therefore is a rational number, by definition of rational numbers. (Unnecessary bit: Since \(n,m\) were arbitrary, it follows that \(\forall n,m\in\mathbb{N}, \frac{1}{n}\cdot \frac{1}{m}\) is a rational number.) QED
The above proof is a little more wordy than it needs to be to get the point across. A simpler, optimized one is as follows.
Proof: Let \(n\) and \(m\) be natural numbers. We know that products of integers is an integer, so \(n\cdot m\) is an integer. Therefore, since \(\frac{1}{n}\cdot \frac{1}{m}=\frac{1}{nm}\) and since \(1\) is an integer, it follows by this equality that \(\frac{1}{n}\cdot \frac{1}{m}\) is a rational number (since it’s a fraction of integers). Therefore, the original statement is true. QED
Proving Implicitly Quantified Universal Statements
More often than not, one does not prove conditional statements expressed in their full universally quantified glory, such in the statement “\(\forall n\in \mathbb{N},\) if \(4\vert n\), then \(2\vert n\).” Instead, we tend to prove statements in their simpler form, “if n is a natural number that is divisible by \(4\), then \(n\) is even,” where the variable \(n\) in the “if” and “then” part of the implication is implicitly quantified by its “arbitrariness.” The method for proving these sorts of implications is as follows.
Proof: Let \(n\) be an (arbitrary) natural number that is divisible by \(4\) (We want to show that \(n\) is even; i.e. \(n=2m\) for some integer \(m\)). This implies that \(n=4\cdot m\) for some integer \(m\), which further implies \(n=2\cdot 2\cdot m=2\cdot (2m)\). Since \(2m\) is an integer, it follows that \(n\) is equal to \(2\) times some integer (by the last equality). Therefore, by the definition of “even” \(n\) is even. (Unnecessary part: Therefore we have shown that if \(n\) is a natural number such that \(4\vert n\), then \(n\) is even.) QED
The above proof is a good example of “definition unpacking,” which entails repeatedly answering the question “what does that mean?” or “what does that imply?”
Note also that nearly every good proof has, what I like to call, a “gimmick” or a “trick,” which is a key step that makes the whole proof work. In the proof above, the gimmick was factoring the \(4\) so that \(n\) could be written as \(2\) times another integer. Without that step, the proof would not get much further. Typically, that step is the hardest to find and takes the most patience to arrive at.
Translating the statement to an “If, then”: “If \(n\) is odd, then \(n^2\) is odd”
Proof: Let \(n\) be an odd integer (we want to show that \(n^2=2x+1\) for some \(x\in \mathbb{Z}\)). This implies/means that there is an integer \(m\) such that \(n=2m+1\). Now, note that
$$\begin{align}n^2&=(2m+1)^2\\&=(2m+1)(2m+1)\\&=4m^2+4m+1\\&=2(2m^2+2m)+1.\end{align}$$
Now, note that since \((2m^2+2m)\) is an integer (because products and squares of integers (i.e. whole numbers; either negative, positive or zero) are obviously integers as well). Therefore, by the equality above we have that \(n^2=2(2m^2+2m)+1\) which implies that \(n^2\) is an odd number (i.e. \(n^2\) has the form \(2x+1\) for some integer \(x\)). Thus, the original statement in the problem is true. QED.
In the above argument, we first set out by labeling what our \(n\) will be and assume the hypothesis of the statement in the problem; that is, we assume that \(n\) is an odd number. We then state (in parentheses) what we are aiming to prove. This step is not required, but it helps keep your focus on where you want your argument to go. In these first steps, it is useful to “unpack” the definitions you are using; in this case, state what it means for \(n\) and \(n^2\) to be odd. This will further help you clarify what info you are starting with and where you want to go.
Disproving Universal Statements
Let \(P(x)\) be a predicate and let \(D\) be the domain of \(x\). Recall that the negation of the universal statement “\(\forall x\in D, P(x)\)” is “\(\exists x\in D\) such that \(\neg P(x)\).” That is, in a universal statement, we are claiming that a statement \(P(x)\) is true for every single \(x\in D\). So the negation of such a statement means that there is at least one \(x\in D\) where \(P(x)\) is FALSE. So, the following idea holds.
Counterexample: The statement is false. As a counterexample, note that \(2\) is an even natural number that is prime. QED.
Counterexample: “False, Mom. I cleaned my room once last year around the holidays.”
Proving the Negation of Implicitly Quantified Implications
Counterexample: Let \(x=15\). Then clearly \(x=15\) is an odd number, BUT \(x=15\) is not prime, since \(15\) factors as \(3\cdot 5\). Therefore, the statement is false.
Note that the hypothesis of the original statement “\(x\) is an odd number” is satisfied/true, but the conclusion was shown to be false. This is EXACTLY in line with how negations of implications work: \(\neg(p\rightarrow q)\equiv p\wedge \neg q\).
Counterexample: Let \(n=70\). Then certainly \(7\vert 70\), BUT \(n\) is even! Therefore, the above statement is false.
Here again, our choice of \(n=70\) satisfies the condition given in the hypothesis, but the conclusion is violated. That is exactly what needs to happen every. single. time.
Disproving Existential Statements
It was briefly mentioned in the last topic how to disprove an existential statement. The reason the following idea finds a home here in a topic on “universal statements” is because the negation of an existential statement is a universal statement!
This makes sense because if you want to disprove a statement like “\(P(x)\) is true for some \(x\in D\)” you’d have to show that there is NEVER an \(x\in D\) such that \(P(x)\); equivalently, prove that it is ALWAYS the case that the opposite of \(P(x)\) is true; i.e. that \(\neg P(x)\) is true for every \(x\in D\).
Negation of the statement: “Every even number greater than 3 is not prime.”
Proof (of the negation of the above statement): Suppose \(n\) is an even number greater than \(3\). (We want to show that \(n\) is NOT prime; i.e. is composite). Then it follows (by definition of even) that \(n=2\cdot m\) for some integer \(m\). Since \(n\) is greater than \(3\), \(m\neq 1\) because otherwise, if \(m=1\) then \(n=2\) which is false because \(n\) was assumed to be greater than \(3\). This therefore implies that \(m>1\). Therefore, \(n\) is the product of two integers greater than \(1\), making \(n\) a composite number (i.e. not prime). Therefore, we have shown that every even number greater than \(3\) is not prime, which implies that the original statement given in the problem is false (because we proved its opposite).
After letting \(x\in \mathbb{R}\), start with the left side of the equation, and FOIL.
Proof: Let \(x\in\mathbb{R}\). Then, note that the following expression distributes as follows:
$$\begin{align} (x+1)(x^2-x+1)&=x^3-x^2+x+x^2-x+1\\&=x^3+1.\end{align}$$
Therefore, by the above equation, and since \(x\) was an arbitrarily chosen real number, it follows that \((x+1)(x^2-x+1)=x^3+1\) for every real number \(x\), as was to be demonstrated.
After letting \(n,m\in\mathbb{N}\), try finding a common denominator for \(\frac{1}{n}+\frac{1}{m}\).
Proof: Let \(n,m\) be natural numbers. Notice that
$$\begin{align}\frac{1}{n}+\frac{1}{m}&=\frac{m}{nm}+\frac{n}{nm}\\&=\frac{n+m}{nm}\end{align}$$
Note that \(n+m\) is an integer (because sums of integers are obviously integers) and that \(nm\) is also an integer (because products of integers are integers). Therefore \(\frac{n+m}{nm}\) is a rational number (since it is a fraction of integers), which implies by the above equation that \(\frac{1}{n}+\frac{1}{m}\) is also a rational number (because it’s equal to \(\frac{n+m}{nm}\)). Therefore, since \(m,n\) were arbitrarily chosen natural numbers and \(\frac{1}{n}+\frac{1}{m}\) is rational, the original statement in the problem is true.
After letting \(n\in \mathbb{N}\), note that \(n\) being even means \(n=2m\) for some integer \(m\). Cube both sides of that expression and see if you can write the result as 2 times some other number.
Proof: Let \(n\) be an even integer. Then by definition of even, it follows that \(n=2m\) for some integer \(m\). Note that \(n^3=(2m)^3=8m^3=2\cdot (4m^3)\). Since \(4m^3\) is an integer, \(n^3\) is therefore a multiple of \(2\) by the last equation. Therefore, we can conclude that \(n^3\) is even. (Perhaps unnecessary bit: Since \(n\) was arbitrarily chosen and we had shown that \(n^3\) is even, the original statement in the problem is true.)
Since \(n\) and \(m\) are even, then there are integers \(a\) and \(b\) such that \(n=2a\) and \(m=2b\). Add these expressions, then factor.
Note that we wanted two different variables \(a\) and \(b\) above because using the same variable makes it look like \(n=2a\) and \(m=2a\) which indicates that \(n=m\), which might not be the case.
Proof: Let \(n\) and \(m\) be even numbers. Then, by definition of even there are integers \(a\) and \(b\) such that \(n=2a\) and \(m=2b\). Then, notice that \(n+m=2a+2b=2(a+b)\) and \((a+b)\) is an integer (because the sum of two integers is an integer). Therefore, \(n+m\) is a multiple of \(2\) and therefore even. (Perhaps unnecessary bit: Since the \(n\) and \(m\) chosen at the outset were arbitrary and since we proved that \(n+m\) is even, the original statement in the problem is true.)
Note that an integer \(n\) is equivalent to \(1\) modulo \(3\) if and only if \(n=3m+1\) for some integer \(m\), by the quotient remainder theorem. Use this fact.
Put another way, to help with comprehension, \(n\equiv 1 \pmod 3\) means that the “remainder” one gets when they divide this number \(n\) by \(3\) is 1. The above expression \(n=3m+1\) represents the fact that such a number can be written as a multiple of \(3\) plus that remainder of \(1\).
Proof: Suppose \(n\) is an integer such that \(n\equiv 1 \pmod 3\). Then by the quotient remainder theorem, there is an integer \(m\) such that \(n=3m+1\). Then, notice. by FOILing,
$$\begin{align} n^2&=(3m+1)^2\\&=(3m+1)(3m+1)\\&= 9m^2+6m+1\\&= 3(3m^2+2m)+1\end{align}$$
So, by the above equation, we see that \(n^2=3(3m^2+2m)+1\). Since \(3m^2+2m\) is an integer (because products and squares and sums of integers are also integers), it follows that \(n^2\) (by the last equation) is of the form \(3x+1\) for some integer \(x\). Therefore, by definition of \(\pmod 3\), we can conclude that \(n^2 \equiv 1 \pmod 3\), which verifies the statement given in the problem.
Since we are trying to disprove a universal statement, it is sufficient to find one counterexample of the statement given. So try to find a prime that does NOT meet the specifications given.
Counterexample: Let \(p=41\). Note that \(41\) is prime, because \(\sqrt{41}<7\) and every prime less than \(7\) does NOT divide \(41\). Clearly, the \(1\)’s digit is NOT greater than 5. Therefore, the original statement is false.
Since we are trying to disprove a universal statement, it suffices to find a counterexample to the above statement; i.e. find a pair of odd integers \(n\) and \(m\) so that their difference \(n-m\) is NOT odd.
Counterexample: Let \(n=3\) and \(m=1\). Then \(n-m=3-1=2\) which is obviously even. Therefore, we have found a pair of integers whose difference is even, which proves the original statement in the problem false.
Here we are trying to disprove an existential statement. To do this, we need to prove the statement’s negation, namely “For all pairs of even numbers \(n\) and \(m\), their sum \(n+m\) is even.”
Proof: Suppose \(n\) and \(m\) are even integers. Then by definition of evenness, there exist integers \(a\) and \(b\) such that \(n=2a\) and \(m=2b\). Note that \(n+m=2a+2b=2(a+b)\) and \((a+b)\) is an integer. So, \(n+m\) is a multiple of \(2\), which implies that \(n+m\) is even. Therefore, since we have shown that an abritrary pair of even numbers has an even sum, we have shown “for all pairs of even numbers \(n\) and \(m\), their sum \(n+m\) is even” which disproves the statement given in the problem.