For all
A rule has worked in every case anyone has tried. What would it mean for it to hold in every case, and how could anyone check infinitely many?
Where you are 4 in Quantifiers
Why this exists
In letters of 1742, Christian Goldbach and Leonhard Euler discussed a guess that now carries Goldbach’s name: every even number greater than 2 is the sum of two primes. 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, and it keeps working. Computers have checked every even number up to 4 \times 10^{18} and found no exception. The guess is still not a theorem. It is a claim about every even number, and past any point that has been checked there are infinitely many more.
In 1769 Euler made a guess of the same shape: among other things, that four fifth powers of positive whole numbers can never add up to a fifth power. It stood for almost two hundred years, until in 1966 L. J. Lander and T. R. Parkin, searching by computer, found
One equation, and the claim was dead.
Those are the two faces of a claim about everything: no pile of successes proves it, and one failure destroys it. Most theorems have this shape (“the angles of every triangle add to 180^\circ”), and English says it with “all”, “every”, “each”, “any” and “always”, not always in the same way. A proof needs one exact meaning and a symbol for it.
Definition
As for “there exists”, start with a collection of objects D, the domain, and a predicate P(x): a sentence about x that becomes true or false once x is replaced by a member of D.
The statement “for all x in D, P(x)” is true when every member of D makes P(x) true, and false when at least one member makes it false. In symbols:
The symbol \forall is an upside-down A, for “all”, and it is called the universal quantifier. “For all”, “for every”, “for each”, “all”, “any” (as in “any square is a rectangle”) and “always” all become \forall. The letter is only a placeholder: {\forall x \in \mathbb{R},\ x^2 \ge 0} and {\forall t \in \mathbb{R},\ t^2 \ge 0} are the same statement. Here \mathbb{Z} and \mathbb{R} are the integers and the real numbers, and \mathbb{Z}^+ is the positive integers 1, 2, 3, \ldots
A condition on the members. “Every odd integer has an odd square” is about only part of \mathbb{Z}. Either shrink the domain to the odd integers, or keep \mathbb{Z} and put the condition in an “if”:
The two say the same thing. An even n makes the “if” part false, and a conditional with a false “if” part counts as true, so no even integer can make this statement fail.
Hidden quantifiers. A formula with a free letter, such as 2(x + 5) = 2x + 10, depends on x, so strictly it is not yet a statement. By agreement it is read with a “for all” in front: {\forall x \in \mathbb{R},\ 2(x + 5) = 2x + 10}. Every identity written with letters is a universal statement in disguise.
Intuition
Think of the domain as a warehouse and the predicate as an inspection each item passes or fails. {\forall x \in D,\ P(x)} promises that every item passes.
To break the promise, one failing item is enough, and that item is a counterexample. To keep it, you need an argument that covers every item, including the ones nobody will ever look at.
A small warehouse can be inspected in full. If D = \{1, 2, 3\}, then “every member passes” means “1 passes and 2 passes and 3 passes”, one long and statement.
An infinite one cannot, and this is the central idea of a proof: inspect one item chosen with no special features. “Let n be any integer” means: I will use nothing about n except that it is an integer. Such an argument works just as well for 7, for -3 and for 10^{100}, because nothing in it can tell those numbers apart.
And if the warehouse is empty, nothing in it fails, so the promise is kept.
Results
Specialization. If {\forall x \in D,\ P(x)} is true and a is a member of D, then P(a) is true.
One failure refutes it. If a is a member of D and P(a) is false, then {\forall x \in D,\ P(x)} is false.
Proof by an arbitrary member. If P(a) can be proved using nothing about a except that a is a member of D, then {\forall x \in D,\ P(x)} is true.
On a finite domain it is an “and”. If D = \{a_1, a_2, \ldots, a_n\}, then {\forall x \in D,\ P(x)} says the same as
Over an empty domain it is true. {\forall x \in \varnothing,\ P(x)} is true, whatever P is.
A smaller domain can only help. If every member of D is also a member of E, and {\forall x \in E,\ P(x)} is true, then {\forall x \in D,\ P(x)} is true. The reverse can fail.
It passes through “and” but not through “or”.
{\forall x,\ \big(P(x) \land Q(x)\big)} says the same as
{\big(\forall x,\ P(x)\big) \lor \big(\forall x,\ Q(x)\big)} guarantees
but the second does not guarantee the first.
Why it is true
Each of these comes straight from “every member of D makes P true”.
Specialization. a is one of the members, and every member makes P true.
One failure. If a is a member and P(a) is false, then not every member makes P true.
Arbitrary member. Take any member b of D. The proof for a used only that a is in D, which is true of b too, so the same steps with b in place of a prove P(b).
Finite domain. “Every one of a_1, \ldots, a_n makes P true” and “P(a_1) and P(a_2) and ... and P(a_n)” are the same sentence, because an “and” of several statements is true exactly when all of them are.
Empty domain. The statement is false only if some member fails, and the empty set has no members to fail.
Smaller domain. A member of D is a member of E, and every member of E makes P true. The reverse fails because the extra members of E may be exactly where P breaks: Example 2 has a predicate that holds for every integer but fails at the real number \displaystyle \frac{1}{2}.
“And”. A member makes P(x) \land Q(x) true exactly when it makes P true and makes Q true, so “every member does both” and “every member does the first, and every member does the second” are the same claim.
“Or”. If every member makes P true, then every member makes P \lor Q true, and the same if every member makes Q true. The reverse fails because different members may use different halves. Every integer is even or odd, but “every integer is even” is false (take 1), and so is “every integer is odd” (take 2).
Worked examples
Reading and deciding
Write each statement in words and decide whether it is true.
(a) {\forall x \in \mathbb{R},\ x^2 + 1 > 0}
(b) {\forall x \in \mathbb{R},\ x^2 > 0}
(c) {\forall n \in \mathbb{Z}^+,\ 3n \ge n + 2}
Solution(a) “For every real number x, x^2 + 1 is positive.” A square of a real number is never negative, so x^2 \ge 0, and adding 1 gives x^2 + 1 \ge 1 > 0. That argument used nothing about x except that it is real, so it covers every real number at once. True.
(b) “Every real number has a positive square.” Take x = 0: 0^2 = 0, and 0 > 0 is false. One member fails, so the statement is false, however many other real numbers pass.
(c) “For every positive integer n, 3n is at least n + 2.” Subtract to compare: 3n - (n + 2) = 2n - 2 = 2(n - 1). A positive integer has n \ge 1, so n - 1 \ge 0 and 2(n - 1) \ge 0. True. Over all of \mathbb{Z} it would be false: n = 0 gives 0 \ge 2.
The same sentence over different domains
Decide whether {\forall x \in D,\ x^2 \ge x} is true when D is \mathbb{R}, when it is \mathbb{Z}, and when it is the set of real numbers x with x \ge 1.
SolutionMove everything to one side and factor: x^2 - x = x(x - 1). The claim is that this product is never negative.
Over \mathbb{R} it is false. Take \displaystyle x = \frac{1}{2}: then \displaystyle x^2 = \frac{1}{4}, which is less than \displaystyle \frac{1}{2}. In the factored form, for x between 0 and 1 the factor x is positive and x - 1 is negative, so the product is negative.
Over \mathbb{Z} it is true. Let n be any integer. Either n \ge 1, and then n and n - 1 are both at least 0; or n \le 0, and then n and n - 1 are both at most 0. In both cases the two factors do not have opposite signs, so n(n - 1) \ge 0.
Over the reals with x \ge 1 it is also true: both x and x - 1 are at least 0.
The predicate never changed. The failing members all lie strictly between 0 and 1, a gap the other two domains do not reach.
Checking every member of a finite domain
Let D = \{1, 2, 3, 4, 5, 6\}. Decide whether each statement is true.
(a) {\forall n \in D,\ n^3 - n \text{ is a multiple of } 6}
(b) {\forall n \in D,\ n^2 < 5n}
SolutionThe domain has six members, so each statement is an “and” of six statements, and it can be settled by checking all six.
| n | {n^3 - n} | n^2 | 5n |
|---|---|---|---|
| 1 | 0 | 1 | 5 |
| 2 | 6 | 4 | 10 |
| 3 | 24 | 9 | 15 |
| 4 | 60 | 16 | 20 |
| 5 | 120 | 25 | 25 |
| 6 | 210 | 36 | 30 |
(a) Every entry in the {n^3 - n} column is a multiple of 6: 0 = 6 \times 0, 6 = 6 \times 1, and so on up to 210 = 6 \times 35. All six members pass, so the statement is true. On a finite domain, checking every member is a complete proof.
(b) The first four members pass. At n = 5 both sides are 25, and 25 < 25 is false, so the statement is false. (So is n = 6, since 36 < 30 is false.) Anyone who stopped checking after n = 4 would have got the wrong answer: a “for all” is settled only when every member has been checked, or a failure has been found.
Statement (a) is in fact true for every integer, but a table can never show that, because the integers do not end. Exercise 21 asks for the argument that does.
A proof about an arbitrary member
Prove that the sum of any two odd integers is even.
SolutionWrite O for the set of odd integers. The claim is
Let a and b be any two odd integers. An integer is odd when it is one more than a multiple of 2, so {a = 2j + 1} for some integer j, and {b = 2k + 1} for some integer k. The letters are different because a and b may be different numbers. Then
and j + k + 1 is an integer, so a + b is a multiple of 2: it is even. Nothing about a and b was used except that each is odd, so the argument covers every pair of odd integers.
Writing {a = 2k + 1} and {b = 2k + 1} with the same k would quietly assume a = b, and prove only that an odd number added to itself is even. A proof about “any” member must not give that member properties it was not promised.
Check. a = 7 and b = 13 have j = 3 and k = 6, and 7 + 13 = 20 = 2(3 + 6 + 1).
A condition inside “for all”
(a) Write “every real number greater than 3 has a square greater than 9” in symbols, and prove it.
(b) Is {\forall x \in \mathbb{R},\ (x^2 > 9 \to x > 3)} true?
(c) Is {\forall x \in \mathbb{R},\ (x > 3 \land x^2 > 9)} true?
Solution(a) The claim is {\forall x \in \mathbb{R},\ (x > 3 \to x^2 > 9)}. Let x be any real number with x > 3. Then x is positive, and multiplying both sides of x > 3 by a positive number keeps the direction. Multiplying by x gives x^2 > 3x; multiplying by 3 gives 3x > 9. Together, x^2 > 3x > 9. A real number with x \le 3 makes the “if” part false, so it cannot make the conditional fail. The statement is true.
(b) This is the converse, and it is false. Take x = -4: then x^2 = 16 > 9, but -4 > 3 is false. The “if” part is true and the “then” part is false, so -4 makes the conditional fail.
(c) This says that every real number is greater than 3 and has a square greater than 9. Take x = 0: 0 > 3 is false. The statement is false. Writing “and” in place of “if ... then” turned a claim about the numbers above 3 into a claim about all numbers.
“For all” as a condition on a number
For which real numbers k is {\forall x \in \mathbb{R},\ x^2 + kx + 4 > 0} true?
SolutionFor each fixed k this is a statement, true or false, and the question asks for every k that makes it true. Completing the square shows the smallest value the expression can take:
The square is never negative, and it is 0 exactly when \displaystyle x = -\frac{k}{2}. So the least value of the expression is \displaystyle 4 - \frac{k^2}{4}, reached at \displaystyle x = -\frac{k}{2}.
If \displaystyle 4 - \frac{k^2}{4} > 0, every value is at least that positive number, so every x passes. If \displaystyle 4 - \frac{k^2}{4} \le 0, the member \displaystyle x = -\frac{k}{2} fails. The statement is therefore true exactly when
Check. For k = 4 the expression is (x + 2)^2, which is 0 at x = -2, so that member fails. For k = 5, the member \displaystyle x = -\frac{5}{2} gives \displaystyle \frac{25}{4} - \frac{25}{2} + 4 = -\frac{9}{4}, which fails too.
Boundaries
Change the domain and the answer can change. {\forall x,\ x^2 \ge x} is true over \mathbb{Z} and false over \mathbb{R} (Example 2). A “for all” with no domain named has one anyway, taken for granted, and a proof has to know which.
Cases prove nothing on an infinite domain. Four quintillion successes have not proved Goldbach’s guess, and they never will; only an argument about an arbitrary even number could (a pattern is not a proof). Checking every case is a proof only when there are finitely many cases and all of them are checked.
Over an empty domain, anything goes. “Every even prime greater than 2 is divisible by 7” is true, because there is no even prime greater than 2 to break it. So is “every even prime greater than 2 is not divisible by 7”. A statement true for this reason is called vacuously true. So “for all” does not promise that anything exists: over the empty set, every “for all” is true and every “there exists” is false.
“Any” and “all” do not always mean “every”. “Any square is a rectangle” means every square, but “if any student failed, the class retakes the test” means “if at least one student failed”. And “all that glitters is not gold” means “not everything that glitters is gold”, a negated “for all” (negating a quantified statement).
A condition goes in an “if”, not an “and”. “Every number above 3 has a square above 9” is {\forall x,\ (x > 3 \to x^2 > 9)}. Written with “and”, it becomes {\forall x,\ (x > 3 \land x^2 > 9)}, which claims that every number is above 3 (Example 5).
Where this goes next
Most theorems are “for all” statements, so most proofs are proofs of one. The plainest kind is the one in Example 4: let the object be arbitrary, and reason from its definition alone, which is a direct proof. When the domain is the positive integers there is a second tool, proof by induction, which proves the claim for 1 and then shows that each case hands the claim on to the next.
In the other direction, a single counterexample refutes a “for all”, as Lander and Parkin’s equation did; turning “not everything passes” into “something fails” is the skill of negating a quantified statement. When a “for all” is paired with a “there exists”, as in “for every x there is a larger y”, the order of the two decides what is said; that is nested quantifiers, and it is how the limit is made precise.
Exercises
Reading and writing
- Write in words, and decide whether it is true: {\forall x \in \mathbb{R},\ x^2 + 4 > 0}.
- Write in symbols, and decide whether it is true: “Every integer is less than its square.”
- Write in symbols, with an “if ... then”, and decide whether it is true: “The square of every even integer is a multiple of 4.”
- Which of these are universal statements? (a) Every prime greater than 2 is odd. (b) Some primes are even. (c) A square has four equal sides. (d) No perfect square ends in the digit 7. Explain.
- The formula x^2 - 1 = (x - 1)(x + 1) has no quantifier written in it. Write the statement it makes, and decide whether it is true.
True or false
For each statement, give a proof if it is true and a member that fails if it is false.
- {\forall x \in \mathbb{R},\ x^2 \ge 2x - 1}
- {\forall x \in \mathbb{R},\ x^2 > 2x - 1}
- {\forall n \in \mathbb{Z},\ n^2 + n \text{ is even}}
- {\forall n \in \mathbb{Z}^+,\ n^2 + 1 \text{ is prime}}
- D = \{1, 2, 3, 4, 5\} and the statement is {\forall n \in D,\ 3^n > n^3}.
- D = \{5, 7, 11, 13, 17\} and the statement is “for every p in D, p^2 - 1 is a multiple of 24”.
- \displaystyle {\forall x \in \mathbb{R},\ \sqrt{x^2} = x}
Domains, “and” and “or”
- The statement {\forall x,\ 2x \ge x} is true in exactly one of the domains \mathbb{Z}^+, \mathbb{Z} and \mathbb{R}. Which one, and why?
- For which real numbers c is {\forall x \in \mathbb{R},\ x^2 + 2x + c \ge 0} true?
- For which real numbers a is {\forall x \in \mathbb{R},\ ax + 1 > 0} true?
- Decide each. (a) {\forall n \in \mathbb{Z},\ (n \ge 0 \lor n < 0)}; (b) {\big(\forall n \in \mathbb{Z},\ n \ge 0\big) \lor \big(\forall n \in \mathbb{Z},\ n < 0\big)}.
- Decide each. (a) {\forall x \in \mathbb{R},\ (x > 2 \to x^2 > 4)}; (b) {\forall x \in \mathbb{R},\ (x^2 > 4 \to x > 2)}; (c) {\forall x \in \mathbb{R},\ (x > 2 \land x^2 > 4)}.
- Let D be the set of even primes greater than 2. Is {\forall p \in D,\ p = 100} true? Explain.
Reasoning
- A student checks that n^2 - n + 11 is prime for n = 1, 2, \ldots, 10 and concludes that {\forall n \in \mathbb{Z}^+,\ n^2 - n + 11 \text{ is prime}}. Is the conclusion right, and was the reason good enough? Explain.
- Here is a “proof” that the sum of any two even integers is a multiple of 4: “Let a = 2k and b = 2k. Then a + b = 4k.” Explain what is wrong with it, and decide whether the claim is true.
- Prove that {\forall n \in \mathbb{Z},\ n^3 - n \text{ is a multiple of } 6}.
- Explain why, when D has exactly one member, {\forall x \in D,\ P(x)} and {\exists x \in D,\ P(x)} say the same thing.
Answers
- True. “For every real number x, x^2 + 4 is positive.” For every real x, x^2 \ge 0, so x^2 + 4 \ge 4 > 0.
- {\forall n \in \mathbb{Z},\ n < n^2}. False: n = 0 fails, since 0 < 0 is false. (n = 1 fails too.)
- {\forall n \in \mathbb{Z},\ (n \text{ even} \to n^2 \text{ is a multiple of } 4)}. True. If n = 2k for an integer k, then n^2 = 4k^2, and k^2 is an integer.
- (a), (c) and (d). (a) is about every prime above 2. (c) begins with “a”, but it means every square. (d) says that for every integer n, n^2 does not end in 7. Only (b) is not: it is a “there exists” statement.
- {\forall x \in \mathbb{R},\ x^2 - 1 = (x - 1)(x + 1)}. True for every x, since (x - 1)(x + 1) = x^2 + x - x - 1 = x^2 - 1.
- True. x^2 - (2x - 1) = x^2 - 2x + 1 = (x - 1)^2 \ge 0 for every real x.
- False. x = 1 fails: 1 > 1 is false. By Exercise 6, it is the only member that fails.
- True. n^2 + n = n(n + 1) is a product of two consecutive integers, and one of any two consecutive integers is even.
- False. n = 3 gives 10 = 2 \times 5. (n = 1 and n = 2 give the primes 2 and 5.)
- False. n = 3 fails: there both sides are 3^3 = 27, and 27 > 27 is false. The others pass: 3 > 1, 9 > 8, 81 > 64, 243 > 125.
- True. The values are 24, 48, 120, 168 and 288, which are 24 times 1, 2, 5, 7 and 12. The domain has five members and all five pass.
- False. x = -1 fails: \displaystyle \sqrt{(-1)^2} = \sqrt{1} = 1, not -1. In general \displaystyle \sqrt{x^2} = \lvert x \rvert, which equals x only for x \ge 0.
- \mathbb{Z}^+. Subtracting x, 2x \ge x holds exactly when x \ge 0. Every positive integer passes; in \mathbb{Z} and in \mathbb{R} the member x = -1 fails, since -2 \ge -1 is false.
- c \ge 1. Completing the square, x^2 + 2x + c = (x + 1)^2 + c - 1, whose least value is c - 1, at x = -1. Every x passes exactly when c - 1 \ge 0.
- Only a = 0. If a \ne 0, the member \displaystyle x = -\frac{1}{a} gives -1 + 1 = 0, which is not positive. If a = 0, the expression is 1 > 0 for every x.
- (a) True: every integer is at least 0 or below 0. (b) False: “every integer is at least 0” fails at -1, and “every integer is below 0” fails at 0.
- (a) True: if x > 2 then x is positive, so x^2 > 2x > 4. (b) False: x = -3 has 9 > 4 but -3 > 2 is false. (c) False: x = 0 fails, since 0 > 2 is false.
- True, vacuously. 2 is the only even prime, so D is empty and has no member that could fail. For the same reason {\forall p \in D,\ p \ne 100} is true as well.
- The conclusion is wrong: n = 11 gives 121 - 11 + 11 = 121 = 11 \times 11, which is not prime. The reason was not good enough either. The ten checks do all pass (the values are 11, 13, 17, 23, 31, 41, 53, 67, 83, 101, all prime), but ten cases say nothing about the infinitely many others.
- Writing both numbers with the same k assumes a = b, so it proves the claim only for an even number added to itself. With a = 2j and b = 2k, the sum is 2(j + k), a multiple of 4 only when j + k is even. The claim is false: 2 + 4 = 6, which is not a multiple of 4.
- Let n be any integer. Then n^3 - n = (n - 1)n(n + 1), a product of three consecutive integers. One of any two consecutive integers is even, and one of any three consecutive integers is a multiple of 3, so the product is a multiple of 2 and of 3. Since 2 and 3 have no common factor, it is a multiple of 6.
- If D = \{a\}, then “every member makes P true” and “at least one member makes P true” both say exactly “P(a) is true”, since a is the only member there is.