2.5 Quantified statements
All of the statements discussed in the previous sections were of the “completely unambiguous” sort; that is, they didn’t have any unknowns in them. As a reader of this text, it’s a sure bet that you’ve mastered algebra and are firmly convinced of the utility of \(x\) and \(y\). Admittedly, we’ve used variables to refer to sentences (or sentence fragments) themselves, but we’ve said that sentences that had variables in them were ambiguous and didn’t even deserve to be called logical statements. The notion of quantification allows us to use the power of variables within a sentence without introducing ambiguity.
Consider the sentence “There are exactly seven odd primes less than 20.”
This sentence has some kind of ambiguity in it (because it doesn’t mention the primes explicitly) and yet it certainly seems to have a definite truth value! The reason its truth value is known (by the way, it is 1) is that the sentence is quantified. “X is an odd prime less than 20.” is an ambiguous sentence, but “There are exactly seven distinct X’s that are odd primes less than 20.” is not. This example represents a fairly unusual form of quantification. Usually, we take away the ambiguity of a sentence having a variable in it by asserting one of two levels of quantification: “this is true at least once” or “this is always true”. We’ve actually seen the symbols (\(\exists\) and \(\forall\)) for these concepts already (in Section 1.3).
An open sentence is one that has variables in it. We represent open sentences using a sort of functional notation to show what variables are in them.
Examples:
\(P(x)\) = “\(2^{2^x}+1\) is a prime.”
\(Q(x,y)\) = “\(x\) is prime or \(y\) is a divisor of \(x\).”
\(L(f,c,l)\) = “The function \(f\) has limit \(l\) at \(c\), if and only if, for every positive number \(\epsilon\), there is a positive number \(\delta\) such that whenever \(|x-c| < \delta,\) it follows that \(|f(x)-l| < \epsilon\).”
That last example certainly is a doozey! At first glance, it would appear to have more than three variables in it, and indeed it does! In order of appearance, we have \(f\), \(l\), \(c\), \(\epsilon\), \(\delta\) and \(x\) — the last three variables that appear (\(\epsilon\), \(\delta\) and \(x\)) are said to be bound. A variable in an open sentence is bound if it is in the scope of a quantifier. Bound variables don’t need to be mentioned in the argument list of the sentence. Unfortunately, when sentences are given in natural languages the quantification status of a variable may not be clear. For example in the third sentence above, the variable \(\delta\) is easily seen to be in the scope of the quantifier \(\exists\) because of the words “there is a positive number” that precede it. Similarly, \(\epsilon\) is universally quantified (\(\forall\)) because the phrase “for every positive number” appears before it. What is the status of \(x\)? Is it really bound? The answers to such questions may not be clear at first, but after some thought you should be able to decide that \(x\) is universally quantified.
Exercise 2.6 What word in the second example above indicates that \(x\) is in the scope of a \(\forall\) quantifier?
It is not uncommon, in advanced mathematics, to encounter compound sentences involving dozens of variables and four or five levels of quantification. Such sentences seem hopelessly complicated at first sight — the key to understanding them is to determine each variable’s quantification status explicitly and to break things down into simpler sub-parts. For instance, in understanding the third example above, it might be useful to define some new open sentences:
\(D(x,c,\delta)\) = “\(|x-c| < \delta\)”
\(E(f,x,l,\epsilon)\) = “\(|f(x)-l| < \epsilon\)”
Furthermore, it’s often handy to replace an awkward phrase (such as “the limit of \(f\) at \(c\) is \(l\)”) with symbols when possible.
The third example now looks like
\[ \lim_{x\rightarrow c}f(x) = l \iff \forall \epsilon>0 \, \exists \delta>0 \, \forall x \, D(x,c,\delta) \implies E(f,x,l,\epsilon). \]
The sentence \(D(x,c,\delta)\) is usually interpreted as saying that “\(x\) is close to \(c\)” (where \(\delta\) tells you how close.) The sentence \(E(f,x,l,\epsilon)\) could be expressed informally as “\(f(x)\) is close to \(l\)” (again, \(\epsilon\) serves to make the word “close” more exact).
It’s instructive to write this sentence one last time, completely in symbols and without the abbreviations we created for saying that \(x\) is near \(c\) and \(f(x)\) is near \(l\):
\(\displaystyle \lim_{x\rightarrow c}f(x) = l \iff \forall \epsilon>0 \, \exists \delta>0 \, \forall x \, (|x-c| < \delta) \implies (|f(x)-l| < \epsilon)\).
It would not be unfair to say that developing the facility to read, and understand, this hieroglyph (and others like it) constitutes the first several weeks of a course in real analysis.
Let us turn back to another of the examples (of an open sentence) from the beginning of this section. \(P(x)\) = “\(2^{2^x}+1\) is a prime.”
In the 17th century, Pierre de Fermat made the conjecture23 that \(\forall x \in {\mathbb N}, P(x)\). No doubt, this seemed reasonable to Fermat because the numbers given by this formula (they are called Fermat numbers in his honour) are all primes — at first! Fermat numbers are conventionally denoted with a subscripted \(F\), \(F_n = 2^{2^n}+1.\) The first five Fermat numbers are prime.
\[\begin{align*} F_0 & = 2^{2^0}+1 = 3\\ F_1 & = 2^{2^1}+1 = 5\\ F_2 & = 2^{2^2}+1 = 17\\ F_3 & = 2^{2^3}+1 = 257\\ F_4 & = 2^{2^4}+1 = 65537 \end{align*}\]Fermat probably computed that \(F_5=4294967297\), and we can well imagine that he checked that this number was not divisible by any small primes. Of course, this was well before the development of effective computing machinery, so we shouldn’t blame Fermat for not noticing that \[4294967297 = 641 \cdot 6700417.\] This remarkable feat of factoring can be replicated in seconds on a modern computer, however it was done first by Leonhard Euler in 1732!
There is quite a lot of literature concerning the primeness and/or compositeness of Fermat numbers. So far, all the Fermat numbers between \(F_5\) and \(F_{32}\) (inclusive) have been shown to be composite. One might be tempted to conjecture that only the first five Fermat numbers are prime, however this temptation should be resisted…
Let us set aside, for the moment, further questions about Fermat numbers. Suppose that we define the set \(U\) (for `Universe’) by \(U=\{0,1,2,3,4\}\). Then the assertion “\(\forall x \in U, P(x)\)” is certainly true. You should note that the only variable in this sentence is \(x\), and that the variable is bound — it is universally quantified. Open sentences that have all variables bound are statements. It is possible (in principle, and in finite universes, in practice) to check the truth value of such sentences. Indeed, the sentence “\(\forall x \in U, P(x)\)” has the same logical content as “\(P(0) \land P(1) \land P(2) \land P(3) \land P(4)\)”. Both happen to be true, but the real point here is to note that a universally quantified sentence can be thought of instead as a conjunction.
Exercise 2.7 Define a new set \(U\) by \(U=\{0,1,2,3,4,5\}\). Write a sentence using disjunctions that is equivalent to “\(\exists x \in U, {\lnot}P(x)\).”
Even when we are dealing with infinite universes, it is possible to think of universally quantified sentences in terms of conjunctions, and existentially quantified sentences in terms of disjunctions. For example, a quick look at the graphs should be sufficient to convince you that “\(x > \ln x\)” is a sentence that is true for all \(x\) values in \({\mathbb R}_{>0}\). There is a notation, reminiscent of so-called sigma notation for sums, that can be used to express this universally quantified sentence as a conjunction.
\[ \forall x \in {\mathbb R}_{>0}, x > \ln x \; \cong \; \bigwedge_{x \in {\mathbb R}_{>0}} x > \ln x \]
A similar notation exists for disjunctions. Purely as an example, consider the following problem from recreational math: Find a four digit number that is an integer multiple of its reversal. (By reversal, we mean the four digit number with the digits in the opposite order — for example, the reversal of 1234 is 4321.) The sentence24 that states that this question has a solution is \[ \exists abcd \in {\mathbb Z}, \exists k \in {\mathbb Z}, abcd = k\cdot dcba \]
This could be expressed instead as the disjunction of 9000 statements, or more compactly as \[ \bigvee_{1000\leq abcd \leq 9999} \exists k \in {\mathbb Z}, abcd = k\cdot dcba. \]
Exercise 2.8 The existential statement above is true because \(8712 = 4\cdot 2178\). There is one other solution — find it!
An important, or at least useful, talent for a mathematics student to develop is the ability to negate quantified sentences. There are two major reasons for this: the techniques known as proof by contradiction and proof by contraposition. The contrapositive of a conditional sentence is logically equivalent to it. Many veteran proof writers give newcomers the advice:
“If you get stuck, try writing down the contrapositive.”
Writing down the contrapositive of a logical statement will often involve finding the negation of a quantified sentence. Proof by contradiction also requires you to be able to negate a logical statement in order to even get started. Let’s try one.
Our universe of discourse25 will be \(P = \{ \mbox{Manny}, \mbox{Moe}, \mbox{Jack} \}\).
Consider the sentence “\(\forall x \in P, x\; \mbox{starts with M}\).” The equivalent sentence expressed conjunctively is \[\begin{gather*} (\mbox{Manny starts with M}) \land \\ (\mbox{Moe starts with M}) \land \\ (\mbox{Jack starts with M}). \end{gather*}\]
The negation of this sentence (by De Morgan’s law) is a disjunction: \[\begin{gather*} (\mbox{Manny doesn't start with M}) \lor \\ (\mbox{Moe doesn't start with M}) \lor \\ (\mbox{Jack doesn't start with M}) \end{gather*}\]
Finally, this disjunction of three sentences can be converted into a single sentence, existentially quantified over \(P\):
“\(\exists x \in P, {\lnot}(x \, \mbox{starts with M})\).”
The discussion in the previous paragraphs justifies some laws of logic which should be thought of as generalizations of De Morgan’s laws:
\[ {\lnot}( \forall x \in U, P(x)) \; \cong \; \exists x \in U, {\lnot}P(x) \] and \[ {\lnot}( \exists x \in U, P(x)) \; \cong \; \forall x \in U, {\lnot}P(x). \]
It’s equally valid to think of these rules in a way that’s divorced from De Morgan’s laws. To show that a universal sentence is false, it suffices to show that an existential sentence involving a negation of the original is true.
If someone announces that “All the Pep boys name’s start with M!” you might counter that with “Uhhmmm…What about Jack?”
In other words, to show that it is not the case that every Pep boy’s name starts with ‘M’, one only needs to demonstrate that there is a Pep boy (Jack) whose name doesn’t start with ‘M’.
2.5.1 Exercises
There is a common variant of the existential quantifier, \(\exists !\), if you write \(\exists ! \, x, \, P(x)\) you are asserting that there is a unique element in the universe that makes \(P(x)\) true. Determine how to negate the sentence \(\exists ! \, x, \, P(x)\).
The order in which quantifiers appear is important. Let \(L(x,y)\) be the open sentence “\(x\) is in love with \(y\).” Discuss the meanings of the following quantified statements and find their negations.
\(\forall x \, \exists y \; L(x,y)\).
\(\exists x \, \forall y \; L(x, y)\).
\(\forall x \, \forall y \; L(x, y)\).
\(\exists x \, \exists y \; L(x, y)\).
Determine a useful denial of:
\[\forall \epsilon>0 \, \exists \delta>0 \, \forall x \, (|x-c| < \delta) \implies (|f(x)-l| < \epsilon).\]
The denial above gives a criterion for saying \(\lim_{x\rightarrow c}f(x) \neq l.\)
A Sophie Germain prime is a prime number \(p\) such that the corresponding odd number \(2p+1\) is also a prime. For example 11 is a Sophie Germain prime since \(23 = 2\cdot 11 + 1\) is also prime. Almost all Sophie Germain primes are congruent to \(5 \pmod{6}\), nevertheless, there are exceptions — so the statement “There are Sophie Germain primes that are not 5 mod 6.” is true. Verify this.
Alvin, Betty, and Charlie enter a cafeteria which offers three different entrees, turkey sandwich, veggie burger, and pizza; four different beverages, soda, water, coffee, and milk; and two types of desserts, pie and pudding. Alvin takes a turkey sandwich, a soda, and a pie. Betty takes a veggie burger, a soda, and a pie. Charlie takes a pizza and a soda. Based on this information, determine whether the following statements are true or false.
\(\forall\) people \(p\), \(\exists\) dessert \(d\) such that \(p\) took \(d\)
\(\exists\) person \(p\) such that \(\forall\) desserts \(d\), \(p\) did not take \(d\).
\(\forall\) entrees \(e\), \(\exists\) person \(p\) such that \(p\) took \(e\).
\(\exists\) entree \(e\) such that \(\forall\) people \(p,\ p\) took \(e\)
\(\forall\) people \(p\), \(p\) took a dessert \(\iff p\) did not take a pizza.
Change one word of statement (d) so that it becomes true.
Write down the negation of (a) and compare it to statement (b). Hopefully you will see that they are the same! Does this make you want to modify one or both of your answers to (a) and (b)?
Fermat’s more famous conjecture, that \(x^n+y^n=z^n\) has no non-trivial integer solutions if \(n\) is an integer with \(n>2\) was discovered after his death.↩
This sentence uses what is commonly referred to as an “abuse of notation” in order avoid an unnecessarily complex problem statement. One should not necessarily avoid such abuses if one’s readers can be expected to easily understand what is meant, any more than one should completely eschew the splitting of infinitives.↩
The Pep Boys — Manny, Moe and Jack — are hopefully known to some readers as the mascots of a chain of automotive supply stores.↩