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 7 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 T) is that the sentence is quantified. “X is an odd prime less than 20.” is an ambiguous sentence, but “There are exactly 7 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:

1. \(P(x)\) = “\(2^{2^x}+1\) is a prime.”

2. \(Q(x,y)\) = “\(x\) is prime or \(y\) is a divisor of \(x\).”

3. \(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| \lt \delta\) it follows that \(|f(x)-l| \lt \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.

It is not uncommon, in advanced Mathematics, to encounter compound sentences involving dozens of variables and 4 or 5 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 example iii) above, it might be useful to define some new open sentences:

\(D(x,c,\delta)\) = “\(|x-c| \lt \delta\)”

\(E(f,x,l,\epsilon)\) = “\(|f(x)-l| \lt \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.

Example iii) now looks like \begin{equation*} \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). \end{equation*}

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| \lt \delta) \implies (|f(x)-l| \lt \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 conjecture¹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. 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 honor) are all primes — at first! Fermat numbers are conventionally denoted with a subscripted letter F, \(F_n = 2^{2^n}+1\), the first five Fermat numbers are prime.

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 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.

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}^+\). 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. \begin{equation*} \forall x \in {\mathbb R}^+, x > \ln x \; \cong \; \bigwedge_{x \in {\mathbb R}^+} x > \ln x \end{equation*}

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 sentence²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. that states that this question has a solution is \begin{equation*} \exists abcd \in {\mathbb Z}, \exists k \in {\mathbb Z}, abcd = k\cdot dcba \end{equation*}

This could be expressed instead as the disjunction of 9000 statements, or more compactly as \begin{equation*} \bigvee_{1000\leq abcd \leq 9999} \exists k \in {\mathbb Z}, abcd = k\cdot dcba. \end{equation*}

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 proofwriters 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 a one.

Our universe of discourse³The Pep Boys — Manny, Moe and Jack — are hopefully known to some readers as the mascots of a chain of automotive supply stores. 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 DeMorgan'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 DeMorgan's laws: \begin{equation*} {\lnot}( \forall x \in U, P(x)) \; \cong \; \exists x \in U, {\lnot}P(x) \end{equation*} and \begin{equation*} {\lnot}( \exists x \in U, P(x)) \; \cong \; \forall x \in U, {\lnot}P(x). \end{equation*}

It's equally valid to think of these rules in a way that's divorced from DeMorgan'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'.