\begin{matrix}c \\ ◯ \end{matrix} Stephen A. Fulling, Texas A&M Univ., 1997

Logic

To the Student: The purpose of this supplement is to help you understand the definitions of “limit” and “continuity” that lie at the foundation of calculus. The “ϵ–δ” definition of a limit has the reputation of being extremely difficult for students. One reason is that it logically comes at the very beginning of a calculus sequence, when most students are not prepared to receive it; one can’t appreciate an abstraction without some experience with the concrete problems to which it provides a solution. Another reason is that the topic seems to involve such tangled, complex sentences. For example, if we substitute the definition of a limit into the definition of continuity (to get a definition of continuity from first principles), we arrive at

The function f is continuous if, for every x in the domain of f, for every number ϵ > 0 there is a number δ > 0 such that for any number y in the domain, if |y − x| < δ, then |f(y) − f(x)| < ϵ. (1)

The problem here is largely linguistic: We need a better notation than ordinary English for expressing relationships among various assertions or hypothetical states of affairs. That is what is provided by modern symbolic logic.

In the Foundation Coalition we have, by default, solved the first problem. In the necessary rush to build up the calculational tools needed immediately in the rest of the curriculum, a thorough study of the meaning of “limit” was omitted from the beginning of our course sequence. We now have a breathing space in which we can return to this subject at a time when it can be better understood, and when studying it can accomplish more good. It fits with a cluster of related topics — convergence of series, sequences, improper integrals, asymptotes — which can mutually illuminate and reinforce each other.

To address the second problem, we shall take a small amount of time to discuss the logical structure of complex sentences such as (1) and introduce a mathematical notation for such structure. The irony here is that we are trying to overcome a difficult abstraction with an even deeper dose of abstraction. Fortunately, this abstraction does not require any quantitative intuition to understand, and it can be illustrated (somewhat artificially) by simple sentences from everyday life as well as the mathematical statements that are the real focus of our interest.

Quantifiers

We present symbolic logic in the notation common among mathematicians as “blackboard shorthand”. The notation used by professional logicians (who are usually located in philosophy departments) is sometimes slightly different.^{1}

∀x means “For all x”:

∀x [x < x + x^{2} + 1]  (real numbers understood)  (2)

is a true statement. ∃x means “There exists an x such that,” as in^{2}

∃x [x is rotten in Denmark].  (3)

∀x and ∃x are called universal and existential quantifiers, respectively.

Expressions such as

x < x + x^{2} + 1  and  x is rotten in Denmark

(which contain a variable and would be sentences if the variable were replaced by a meaningful name or noun) are called open sentences. They are just like functions or formulas in algebra and calculus, except that the value of such a function, when something particular is plugged in for x, is not a number, but rather a truth value — either True or False (or either “Yes” or “No”).

A quantifier, ∀x or ∃x, closes off an open sentence and turns it into a genuine sentence, which is either true or false (although we may not know which). They are very much like the definite integral and limit notations in calculus, which turn formulas into numbers:

∫_{0}^{1} x^{2} dx  and  lim_{x→2} x^{2}

are particular numbers, even though the expressions representing them involve a variable, x. In calculus such a variable is often called a “dummy variable”; in logic it’s traditionally called a “bound variable” (because it’s tied to its quantifier).

1 The logicians would probably also say that we are being rather sloppy in implying that “ ⇒ ”

and “ ⟺ ” are the same things as “implication” and “equivalence”, but being more careful would take us off into a philosophical digression that we can’t afford.

2 Of course, the usual expression is, “Something is rotten in Denmark,” not “There is an x such that x is rotten in Denmark.” This brings out the point that there are many ways of saying the same thing in English, often with slightly different connotations. No one way is the only right way. In addition to “for all,” universal quantifiers can be translated “for each,” “for every,” or “for any.” Similarly, for an existential quantifier we may say “There is an x for which …,” or just “Some x … [does so-and-so].” Furthermore, to make a natural English sentence, we sometimes use common sense to rephrase a logical construction rather drastically. (For example, compare sentences (6′) and (6) below.)

The quantified variable stands for objects in some “universe of discourse”, which may be either stated explicitly —

∀x [if x is a real number, then x < x + x^{2} + 1]  (2′)

— or understood from context. The universe of discourse is just like the “domain” of a numerical function. (Don’t think of “universe” in the astronomical sense.)

Leading universal quantifiers are often omitted when we state “identities” in mathematics, such as

x + y = y + x  and  (n + 1)! = (n + 1)n!.  (4)

[What universe of discourse is understood from context in each of these cases?] If two or more quantifiers of the same type are adjacent, their order doesn’t matter:

∀x∀y [x + y < y + x + 1]  and  ∀y∀x [x + y < y + x + 1]  (5)

say exactly the same thing.

However, the order of quantifiers of different type is extremely important. (This is the place where this discussion first gets beyond the obvious into something both important and subtle.) Consider, for example, the old saying

Behind every successful man there is a woman.  (6)

The structure of this proposition (whether or not you believe it to be true or false) is

∀x∃y [if x is a man and x is successful, then y is a woman and y is behind x].  (6′)

But

∃y∀x [if x is a man and x is successful, then y is a woman and y is behind x]  (7)

says something completely different: There is one particular woman who stands behind every successful man in the world! (There may be more than one, but each one of them must deal with all the men.)

It is notorious that this point is important for the ϵ and δ in the definition of a limit. For example, this slight variation of (1):

For every x in the domain of f, there is a number δ > 0 such that for every number ϵ > 0 and every number y in the domain, if |y − x| < δ, then |f(y) − f(x)| < ϵ. (8) is false unless f is a constant function. For a nontrivial f, one has to know ϵ before one can choose the right δ. There is not (usually) one δ that works for every ϵ.

Similarly, if we move the universal quantifier ∀x in (1) after the existential quantifier ∃δ, we get a different condition:

For every number ϵ > 0 there is a number δ > 0 such that for every

x and y in the domain of f, if |y − x| < δ, then |f(y) − f(x)| < ϵ. (9)

Although this condition is simpler to state in English than the one in the definition (1), it is harder for the function f to satisfy, because it requires that the same δ work for all x. For example, the function f(x) = 1/x is continuous on the domain (0, ∞), but it does not satisfy (9) because its graph becomes increasingly steep as x approaches 0.^{3}

If two quantifiers of one type are separated by one (or more) of the other type, then they cannot be reversed:

∃x∀y∃z is not equivalent to ∃z∀y∃x;  (10)

“There is a country where behind every man there is a woman” is not equivalent to “There is a woman such that for every man there a country where she stands behind him.”

Propositional calculus (the logical connectives)

Letters p, q, … are used as variables standing for sentences or open sentences. (For example, let p stand for “n is a perfect square” — i.e.,

∃m [n = m^{2}]

— and q for “n is an even number.”) The second major part of logical notation expresses how simple sentences are combined into compound ones. The easiest of these to understand simply translate the English words “and”, “or”, and “not”.

AND: p ∧ q (n is a square and also is even.)

OR: p ∨ q (Either n is a square, or it is even (possibly both).)

NOT: ¬p (n is not a perfect square.)

Note that ¬¬p simplifies to p. Also, it is easy to see that ∧ and ∨ are commutative and associative operations, so we can write things like p ∧ q ∧ r.

3 A function that does satisfy (9) is called uniformly continuous. Uniform continuity is an important condition in more advanced mathematics, but we are interested in it today only as an example of the need to keep track of the order of quantifiers. (Do you find this example hard to understand? Well, Augustin-Louis Cauchy, who did as much as anyone to invent the concept of a limit, seems to have been confused on this point for at least 26 years, so you shouldn’t expect to find it easy on the first day.)

Truth tables It is convenient and standard to let 1 represent “True” or “Yes” and 0 represent

“False” or “No”.

Each connective can be precisely defined by telling what its truth value is for each possible truth value of its parts.

\begin{matrix}p & q & p ∧ q \\ 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{matrix}  \begin{matrix}p & q & p ∨ q \\ 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{matrix}

From these the truth tables of more complicated sentences can be deduced. For example, let’s establish that ∧ and ∨ satisfy a distributive law:

p ∧ (q ∨ r) is equivalent to (p ∧ q) ∨ (p ∧ r),  (11)

We list all 8 possible cases:

\begin{matrix}p & q & r & q ∨ r & p ∧ (q ∨ r) & p ∧ q & p ∧ r & (p ∧ q) ∨ (p ∧ r) \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix}

From the fifth and eighth columns of this table, we see that the two sides of the distributive law (11) are true in exactly the same cases (the last 3); therefore, replacing one side by the other is a universally valid principle of logical reasoning.

Connectives expressing logical equivalence and implication We consider two more extremely important logical connectives:

\begin{matrix}p & q & p ⟺ q \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{matrix}  \begin{matrix}p & q & p ⇒ q \\ 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{matrix}

Observe:

1. p ⟺ q says that p and q have the same truth value (either both true or both false). Therefore, if we know one, we can conclude the other. The distributive law (11) that we just proved can be expressed totally in symbolic notation as

p ∧ (q ∨ r) ⟺ (p ∧ q) ∨ (p ∧ r).  (11′)

2. p ⟺ q is equivalent to (p ⇒ q) ∧ (q ⇒ p).

3. p ⇒ q is intended to symbolize that if we know that p is true, then we can conclude that q is true. Note that the bottom half of its truth table guarantees this. The most common English rendering of p ⇒ q is, “If p, then q.” One also says “p implies q.” The connective ⇒ is slightly subtle conceptually. Right now you may be wanting to

ask:

1. What is the justification for the top half of the table? Does it make sense to say, “If 2 + 2 = 5, then sin x is a continuous function,” or “If 2 + 2 = 5, then sin x is a discontinuous function.”?

2. Does it make sense to say, “If China is in Asia, then sin x is a continuous function,” when the two statements obviously have no connection with each other? The answer to question 1 is that we want p ⇒ q to be meaningful and useful when p

and q are open sentences — in particular, when they are inside quantified sentences, such as

∀x [If |x| < \frac{π}{4} , then | sin x| < \frac{1}{\sqrt{2}} .]  (12)

This is a true and useful theorem. It does what we want of a theorem: Whenever a number is less than \frac{π}{4} in magnitude, it enables us to conclude (correctly) that its sine is less than \frac{1}{\sqrt{2}} . However, there are other numbers, such as x = \frac{π}{2} , for which both the hypothesis and the conclusion are false, and there are still other numbers, such as x = π, for which the hypothesis is false but the conclusion is true. We must demand that these cases be consistent with the theorem, and the connective ⇒ is defined to make this so. If we changed the top two lines of the truth table, or left them undefined, then the theorem would become false, or indeterminate, for some of these cases. This would make the formulation of mathematical statements very cumbersome.

The resolution of point 2 is similar. Propositional calculus is concerned only with the truth values of sentences, not with what they mean. There are only 2 truth values, Yes and No. In this sense all true sentences are the same, and all false ones are the same, just as all numbers 9 are the same, regardless of what things you counted to get the number 9. Therefore, to say

If China is in Asia, then sin x is a continuous function.  (13)

is no more strange than to say

The number of planets in the solar system is less than or equal

to the number of states in the Union. (14)

There is no scientific law that makes the latter statement true; it is simply a fact.

Some terminology and language quirks

1. It is sometimes said that the English counterpart of ⇒ is IF, but this is not true in the same sense that the English counterpart of ∧ is AND. Notice that p ⇒ q can be expressed as

If p, then q,  (15)

but that

p IF q

corresponds instead to q ⇒ p. However, if we say

p ONLY IF q,  (15′)

then we do get something that means p ⇒ q; it says that if q is false, then p is false, which is the contrapositive (see 3 below) of p ⇒ q. A consequence of this is that

p IF AND ONLY IF q  (16)

is an English way of saying p ⟺ q. In fact, it is the standard way of expressing equivalent conditions (usually ∀x [p(x) ⟺ q(x)] statements) in mathematical English. Often it is “blackboard abbreviated” to “IFF”.

2. If p ⇒ q, or ∀x [p(x) ⇒ q(x)], then one says

p is a sufficient condition for q  (15′′)

and

q is a necessary condition for p  (15′′′)

(that is, if q is false, then p can’t be true). Therefore, if p is both necessary and sufficient for q, then p ⟺ q or ∀x [p(x) ⟺ q(x)].

3. Associated with p ⇒ q are 3 closely related propositions:

contrapositive:  ¬q ⇒ ¬p
converse:  q ⇒ p
inverse:  ¬p ⇒ ¬q

The original statement and its contrapositive are logically equivalent. The converse and the inverse are equivalent, because the inverse is the contrapositive of the converse. But the original and the converse are not logically equivalent (although they may both be true under certain circumstances). Example of 2 and 3: (You may wish to postpone studying this until after you have

read Chapter 10 of Stewart.) Very soon we shall be studying infinite series, ∑_{n=0}^{∞} a_{n}. Let p stand for

a_{n} → 0 as n → ∞,  (17)

and q stand for

The series ∑_{n=0}^{∞} a_{n} converges.  (18)

Then we shall see that q implies p (because ¬p ⇒ ¬q, Theorem 7, Sec. 10.2), but p does not imply q (the example of the harmonic series, Sec. 10.2). Thus (A) Tending of the terms to 0 is a necessary condition for convergence, but not a suffi-

cient condition. (In contrast, most of the series convergence theorems state sufficient conditions (e.g., the alternating series test (Sec. 10.5) and the ratio test (Sec. 10.6).)

(B) p ⇒ q is false for the harmonic series, but its converse, q ⇒ p, is true. (Of course, p ⇒ q is true of all series that happen to be convergent.) If we attach a universal quantifier over all series, a ≡ {a_{n}}, then the result

∀a [p(a) ⇒ q(a)]  (19)

is false, but

∀a [q(a) ⇒ p(a)]  (20)

is true.

Exercises

1. In each part of (4), what universe of discourse is understood from context? (For the first part, at least, more than one correct answer is possible.)

2. Express in logical notation (quantifiers and connectives):

(a) Everybody loves a lover.

(b) If something quacks like a duck and waddles like a duck, then it is a duck.

(c) All that glitters is not gold. (This one is worth a paragraph of discussion!)

3. Express in logical notation (quantifiers and connectives):

(a) n is an even number.

(b) For every number that is a perfect cube, there is a larger number that is even.

4. Express in logical notation (quantifiers and connectives):

(a) Every U.S. citizen, and any person who earns income in the United States, must file a tax return.

(b) Taxpayer Smith may claim his daughter as a dependent, provided that she is not married and filing a joint return, if he provides more than half of his support, or if he and another person together provide more than half of her support and he paid over 10% of her support. (Let s = Smith, d = daughter.)

5. Translate into standard mathematical English:

∀n ∀a ∀b [(n < a ∧ n < b) ⇒ n < ab].

(A really good answer uses no letters for variables and is brief.)

6. Translate into standard mathematical English:

∃f∀x ∃y ∀z [z < x ⇒ f(z) ≤ f(x) + y].

(This time variables are allowed.)

7. Use truth tables to establish the validity of the other distributive law,

p ∨ (q ∧ r) is equivalent to (p ∨ q) ∧ (p ∨ r).

(Thus AND and OR are each distributive over the other, unlike addition and multiplication!)

8. Use truth tables to show that ¬(¬p ∧ ¬q) is equivalent to p ∨ q.

9. Explain why

¬∀x [¬p(x)] is equivalent to ∃x p(x).

Study Sec. 1.4 of Stewart before tackling the remaining exercises:

10. We stated that (8) is true only for constant functions. Verify and strengthen this claim as follows: Show that (for a given x)

∃δ∀ϵ∀y [|y − x| < δ ⇒ |f(y) − f(x)| < ϵ]

if and only if

∃z∃ϵ∀y [|y − x| < ϵ ⇒ f(y) = z].

(The latter condition is expressed in mathematical English as “f is constant on some neighborhood of x.”) The universe of discourse for ϵ and δ is the positive real numbers; the universe of discourse for x, y, and z is the domain of f.

11. Demonstrate by numerical examples that f(x) = 1/x satisfies (1) but not (9). (Given an ϵ and a δ, show that x and y can be put so close to 0 that |y − x| < δ but |f(y) − f(x)| > ϵ.)