Book of Proof

Home > Other > Book of Proof > Page 9
Book of Proof Page 9

by Richard Hammack

logical structure and meanings of the sentences. Sometimes it is necessary

  or helpful to parse them into expressions involving logic symbols. This may

  be done mentally or on scratch paper, or occasionally even explicitly within

  the body of a proof. The purpose of this section is to give you sufficient

  practice in translating English sentences into symbolic form so that you

  can better understand their logical structure. Here are some examples:

  Example 2.8

  Consider the Mean Value Theorem from Calculus:

  If f is continuous on the interval [a, b] and differentiable on (a, b), then

  f (b)−f (a)

  there is a number c ∈ (a, b) for which f 0(c) =

  b−a

  .

  Here is a translation to symbolic form:

  ³

  ´

  ³

  ´

  ¡ f

  f (b)−f (a)

  cont. on [a, b]¢ ∧ ¡ f is diff. on (a, b)¢ ⇒ ∃ c ∈ (a, b), f 0(c) =

  b−a

  .

  56

  Logic

  Example 2.9

  Consider Goldbach’s conjecture, from Section 2.1:

  Every even integer greater than 2 is the sum of two primes.

  This can be translated in the following ways, where P is the set of prime

  numbers and S = {4, 6, 8, 10, . . .} is the set of even integers greater than 2.

  ¡n ∈ S¢ ⇒ ¡∃ p, q ∈ P, n = p + q¢

  ∀ n ∈ S, ∃ p, q ∈ P, n = p + q

  These translations of Goldbach’s conjecture illustrate an important

  point. The first has the basic structure (n ∈ S) ⇒ Q(n) and the second has

  structure ∀ n ∈ S, Q(n), yet they have exactly the same meaning. This is

  significant. Every universally quantified statement can be expressed as a

  conditional statement.

  Fact 2.2

  Suppose S is a set and Q(x) is a statement about x for each

  x ∈ S. The following statements mean the same thing:

  ∀ x ∈ S, Q(x)

  (x ∈ S) ⇒ Q(x).

  This fact is significant because so many theorems have the form of

  a conditional statement. (The Mean Value Theorem is an example!) In

  proving a theorem we have to think carefully about what it says. Sometimes

  a theorem will be expressed as a universally quantified statement but it will

  be more convenient to think of it as a conditional statement. Understanding

  the above fact allows us to switch between the two forms.

  We close this section with some final points. In translating a state-

  ment, be attentive to its intended meaning. Don’t jump into, for example,

  automatically replacing every “and” with ∧ and “or” with ∨. An example:

  At least one of the integers x and y is even.

  Don’t be led astray by the presence of the word “and.” The meaning of

  the statement is that one or both of the numbers is even, so it should be

  translated with “or,” not “and”:

  (x is even) ∨ ( y is even).

  Finally, the logical meaning of “but” can be captured by “and.” The

  sentence “The integer x is even, but the integer y is odd,” is translated as

  (x is even) ∧ ( y is odd).

  Negating Statements

  57

  Exercises for Section 2.9

  Translate each of the following sentences into symbolic logic.

  1. If f is a polynomial and its degree is greater than 2, then f 0 is not constant.

  2. The number x is positive but the number y is not positive.

  p

  3. If x is prime then

  x is not a rational number.

  4. For every prime number p there is another prime number q with q > p.

  5. For every positive number ε, there is a positive number δ for which |x − a| < δ

  implies | f (x) − f (a)| < ε.

  6. For every positive number ε there is a positive number M for which |f (x)−b| < ε,

  whenever x > M.

  7. There exists a real number a for which a + x = x for every real number x.

  8. I don’t eat anything that has a face.

  9. If x is a rational number and x 6= 0, then tan(x) is not a rational number.

  10. If sin(x) < 0, then it is not the case that 0 ≤ x ≤ π.

  11. There is a Providence that protects idiots, drunkards, children and the United

  States of America. (Otto von Bismarck)

  12. You can fool some of the people all of the time, and you can fool all of the people

  some of the time, but you can’t fool all of the people all of the time. (Abraham

  Lincoln)

  13. Everything is funny as long as it is happening to somebody else. (Will Rogers)

  2.10 Negating Statements

  Given a statement R, the statement ∼ R is called the negation of R. If R

  is a complex statement, then it is often the case that its negation ∼ R can

  be written in a simpler or more useful form. The process of finding this

  form is called negating R. In proving theorems it is often necessary to

  negate certain statements. We now investigate how to do this.

  We have already examined part of this topic. DeMorgan’s laws

  ∼ (P ∧ Q) = (∼ P) ∨ (∼ Q)

  (2.6)

  ∼ (P ∨ Q) = (∼ P) ∧ (∼ Q)

  (2.7)

  (from Section 2.6) can be viewed as rules that tell us how to negate the

  statements P ∧ Q and P ∨ Q. Here are some examples that illustrate how

  DeMorgan’s laws are used to negate statements involving “and” or “or.”

  58

  Logic

  Example 2.10

  Consider negating the following statement.

  R : You can solve it by factoring or with the quadratic formula.

  Now, R means (You can solve it by factoring) ∨ (You can solve it with Q.F.),

  which we will denote as P ∨ Q. The negation of this is

  ∼ (P ∨ Q) = (∼ P) ∧ (∼ Q).

  Therefore, in words, the negation of R is

  ∼ R : You can’t solve it by factoring and you can’t solve it with

  the quadratic formula.

  Maybe you can find ∼ R without invoking DeMorgan’s laws. That is good;

  you have internalized DeMorgan’s laws and are using them unconsciously.

  Example 2.11

  We will negate the following sentence.

  R : The numbers x and y are both odd.

  This statement means (x is odd) ∧ ( y is odd), so its negation is

  ∼ ¡(x is odd) ∧ (y is odd)¢ = ∼ (x is odd) ∨ ∼ (y is odd)

  = (x is even) ∨ (y is even).

  Therefore the negation of R can be expressed in the following ways:

  ∼ R : The number x is even or the number y is even.

  ∼ R : At least one of x and y is even.

  Now let’s move on to a slightly different kind of problem. It’s often

  necessary to find the negations of quantified statements. For example,

  consider ∼ (∀ x ∈ N, P(x)). Reading this in words, we have the following:

  It is not the case that P(x) is true for all natural numbers x.

  This means P(x) is false for at least one x. In symbols, this is ∃ x ∈ N, ∼ P(x).

  Thus ∼ (∀ x ∈ N, P(x)) = ∃ x ∈ N, ∼ P(x). Similarly, you can reason out that

  ∼ (∃ x ∈ N, P(x)) = ∀ x ∈ N, ∼ P(x). In general:

  ∼ (∀ x ∈ S, P(x)) = ∃ x ∈ S, ∼ P(x),

  (2.8)

  ∼ (∃ x ∈ S, P(x)) = ∀ x ∈ S, ∼ P(x).

  (2.9)

  Negating Statements

  59

  Example 2.12

&nb
sp; Consider negating the following statement.

  R : The square of every real number is non-negative.

  Symbolically, R can be expressed as ∀ x ∈ R, x2 ≥ 0, and thus its negation is

  ∼ (∀ x ∈ R, x2 ≥ 0) = ∃ x ∈ R, ∼ (x2 ≥ 0) = ∃ x ∈ R, x2 < 0. In words, this is

  ∼ R : There exists a real number whose square is negative.

  Observe that R is true and ∼ R is false. You may be able to get ∼ R

  immediately, without using Equation (2.8) as we did above. If so, that is

  good; if not, you will probably be there soon.

  If a statement has multiple quantifiers, negating it will involve several

  iterations of Equations (2.8) and (2.9). Consider the following:

  S : For every real number x there is a real number y for which y3 = x.

  This statement asserts any real number x has a cube root y, so it’s true.

  Symbolically S can be expressed as

  ∀ x ∈ R, ∃ y ∈ R, y3 = x.

  Let’s work out the negation of this statement.

  ∼ (∀ x ∈ R, ∃ y ∈ R, y3 = x) = ∃ x ∈ R, ∼ (∃ y ∈ R, y3 = x)

  = ∃ x ∈ R, ∀ y ∈ R, ∼ (y3 = x)

  = ∃ x ∈ R, ∀ y ∈ R, y3 6= x.

  Therefore the negation is the following (false) statement.

  ∼ S : There is a real number x for which y3 6= x for all real numbers y.

  In writing proofs you will sometimes have to negate a conditional

  statement P ⇒ Q. The remainder of this section describes how to do this.

  To begin, look at the expression ∼ (P ⇒ Q), which literally says “ P ⇒ Q is

  false.” You know from the truth table for ⇒ that the only way that P ⇒ Q

  can be false is if P is true and Q is false. Therefore ∼ (P ⇒ Q) = P∧ ∼ Q.

  ∼ (P ⇒ Q) = P∧ ∼ Q

  (2.10)

  (In fact, in Exercise 12 of Section 2.6, you used a truth table to verify that

  these two statements are indeed logically equivalent.)

  60

  Logic

  Example 2.13

  Negate the following statement about a particular (i.e.,

  constant) number a.

  R : If a is odd then a2 is odd.

  Using Equation (2.10), we get the following negation.

  ∼ R : a is odd and a2 is not odd.

  Example 2.14

  This example is like the previous one, but the constant a

  is replaced by a variable x. We will negate the following statement.

  R : If x is odd then x2 is odd.

  As discussed in Section 2.8, we interpret this as the universally quantified

  statement

  R : ∀x ∈ Z, (x odd) ⇒ (x2 odd).

  By Equations (2.8) and (2.10), we get the following negation for R.

  ∼ ¡∀x ∈ Z, (x odd) ⇒ (x2 odd)¢ = ∃x ∈ Z,∼ ¡(x odd) ⇒ (x2 odd)¢

  = ∃x ∈ Z, (x odd)∧ ∼ (x2 odd).

  Translating back into words, we have

  ∼ R : There is an odd integer x whose square is not odd.

  Notice that R is true and ∼ R is false.

  The above Example 2.14 showed how to negate a conditional statement

  P(x) ⇒ Q(x). This type of problem can sometimes be embedded in more

  complex negation. See Exercise 5 below (and its solution).

  Exercises for Section 2.10

  Negate the following sentences.

  1. The number x is positive, but the number y is not positive.

  p

  2. If x is prime, then

  x is not a rational number.

  3. For every prime number p, there is another prime number q with q > p.

  4. For every positive number ε, there is a positive number δ such that |x − a| < δ

  implies | f (x) − f (a)| < ε.

  5. For every positive number ε, there is a positive number M for which |f (x)−b| < ε

  whenever x > M.

  6. There exists a real number a for which a + x = x for every real number x.

  Logical Inference

  61

  7. I don’t eat anything that has a face.

  8. If x is a rational number and x 6= 0, then tan(x) is not a rational number.

  9. If sin(x) < 0, then it is not the case that 0 ≤ x ≤ π.

  10. If f is a polynomial and its degree is greater than 2, then f 0 is not constant.

  11. You can fool all of the people all of the time.

  12. Whenever I have to choose between two evils, I choose the one I haven’t tried

  yet. (Mae West)

  2.11 Logical Inference

  Suppose we know that a statement of form P ⇒ Q is true. This tells us

  that whenever P is true, Q will also be true. By itself, P ⇒ Q being true

  does not tell us that either P or Q is true (they could both be false, or P

  could be false and Q true). However if in addition we happen to know

  that P is true then it must be that Q is true. This is called a logical

  inference: Given two true statements we can infer that a third statement

  is true. In this instance true statements P ⇒ Q and P are “added together”

  to get Q. This is described below with P ⇒ Q and P stacked one atop the

  other with a line separating them from Q. The intended meaning is that

  P ⇒ Q combined with P produces Q.

  P ⇒ Q

  P ⇒ Q

  P ∨ Q

  P

  ∼ Q

  ∼ P

  Q

  ∼ P

  Q

  Two other logical inferences are listed above. In each case you should

  convince yourself (based on your knowledge of the relevant truth tables)

  that the truth of the statements above the line forces the statement below

  the line to be true.

  Following are some additional useful logical inferences.

  The first

  expresses the obvious fact that if P and Q are both true then the statement

  P ∧ Q will be true. On the other hand, P ∧ Q being true forces P (also Q)

  to be true. Finally, if P is true, then P ∨ Q must be true, no matter what

  statement Q is.

  P

  Q

  P ∧ Q

  P

  P

  P

  ∧ Q

  P

  ∨ Q

  These inferences are so intuitively obvious that they scarcely need to

  be mentioned. However, they represent certain patterns of reasoning that

  we will frequently apply to sentences in proofs, so we should be cognizant

  of the fact that we are using them.

  62

  Logic

  2.12 An Important Note

  It is important to be aware of the reasons that we study logic. There

  are three very significant reasons. First, the truth tables we studied tell

  us the exact meanings of the words such as “and,” “or,” “not” and so on.

  For instance, whenever we use or read the “If..., then” construction in

  a mathematical context, logic tells us exactly what is meant. Second,

  the rules of inference provide a system in which we can produce new

  information (statements) from known information. Finally, logical rules

  such as DeMorgan’s laws help us correctly change certain statements into

  (potentially more useful) statements with the same meaning. Thus logic

  helps us understand the meanings of statements and it also produces new

  meaningful statements.

  Logic is the glue that holds strings of statements together and pins down

  the exact meaning of certain key phrases such as the “If..., then” or “For

  all” constructions. Logic is the common language that all mathematicians

&nbs
p; use, so we must have a firm grip on it in order to write and understand

  mathematics.

  But despite its fundamental role, logic’s place is in the background of

  what we do, not the forefront. From here on, the beautiful symbols ∧, ∨,

  ⇒, ⇔, ∼, ∀ and ∃ are rarely written. But we are aware of their meanings

  constantly. When reading or writing a sentence involving mathematics we

  parse it with these symbols, either mentally or on scratch paper, so as to

  understand the true and unambiguous meaning.

  CHAPTER

  3

  Counting

  t may seem peculiar that a college-level text has a chapter on counting.

  I At its most basic level, counting is a process of pointing to each object

  in a collection and calling off “one, two, three,... ” until the quantity of

  objects is determined. How complex could that be? Actually, counting

  can become quite subtle, and in this chapter we explore some of its more

  sophisticated aspects. Our goal is still to answer the question “How many? ”

  but we introduce mathematical techniques that bypass the actual process

  of counting individual objects.

  Almost every branch of mathematics uses some form of this “sophisti-

  cated counting.” Many such counting problems can be modeled with the

  idea of a list, so we start there.

  3.1 Counting Lists

  A list is an ordered sequence of objects. A list is denoted by an opening

  parenthesis, followed by the objects, separated by commas, followed by a

  closing parenthesis. For example (a, b, c, d, e) is a list consisting of the first

  five letters of the English alphabet, in order. The objects a, b, c, d, e are

  called the entries of the list; the first entry is a, the second is b, and so

  on. If the entries are rearranged we get a different list, so, for instance,

  (a, b, c, d, e) 6= (b, a, c, d, e).

  A list is somewhat like a set, but instead of being a mere collection of

  objects, the entries of a list have a definite order. Note that for sets we

  have

  ©a, b, c, d, eª = ©b, a, c, d, eª,

  but—as noted above—the analogous equality for lists does not hold.

  Unlike sets, lists are allowed to have repeated entries. For example

  (5, 3, 5, 4, 3, 3) is a perfectly acceptable list, as is (S,O, S). The number of

  entries in a list is called its length. Thus (5, 3, 5, 4, 3, 3) has length six, and

  (S, O, S) has length three.

  64

  Counting

  Occasionally we may get sloppy and write lists without parentheses

  and commas; for instance, we may express (S, O, S) as SOS if there is no

 

‹ Prev