Book of Proof

Home > Other > Book of Proof > Page 6
Book of Proof Page 6

by Richard Hammack


  matics. For example, suppose you are working with a certain circle, call it

  “Circle X,” and you have available the following two pieces of information.

  1. Circle X has radius equal to 3.

  2. If any circle has radius r, then its area is π r2 square units.

  You have no trouble putting these two facts together to get:

  3. Circle X has area 9 π square units.

  In doing this you are using logic to combine existing information to

  produce new information. Because deducing new information is central to

  mathematics, logic plays a fundamental role. This chapter is intended to

  give you a sufficient mastery of it.

  It is important to realize that logic is a process of deducing information

  correctly, not just deducing correct information. For example, suppose we

  were mistaken and Circle X actually had a radius of 4, not 3. Let’s look at

  our exact same argument again.

  1. Circle X has radius equal to 3.

  2. If any circle has radius r, then its area is π r2 square units.

  3. Circle X has area 9 π square units.

  The sentence “Circle X has radius equal to 3 .” is now untrue, and so is our

  conclusion “Circle X has area 9 π square units.” But the logic is perfectly

  correct; the information was combined correctly, even if some of it was

  false. This distinction between correct logic and correct information is

  significant because it is often important to follow the consequences of an

  incorrect assumption. Ideally, we want both our logic and our information

  to be correct, but the point is that they are different things.

  34

  Logic

  In proving theorems, we apply logic to information that is considered

  obviously true (such as “Any two points determine exactly one line.” ) or is

  already known to be true (e.g., the Pythagorean theorem). If our logic is

  correct, then anything we deduce from such information will also be true

  (or at least as true as the “obviously true” information we began with).

  2.1 Statements

  The study of logic begins with statements. A statement is a sentence

  or a mathematical expression that is either definitely true or definitely

  false. You can think of statements as pieces of information that are either

  correct or incorrect. Thus statements are pieces of information that we

  might apply logic to in order to produce other pieces of information (which

  are also statements).

  Example 2.1

  Here are some examples of statements. They are all true.

  If a circle has radius r, then its area is π r2 square units.

  Every even number is divisible by 2.

  2 ∈ Z

  p2 ∉Z

  N ⊆ Z

  The set {0, 1, 2} has three elements.

  Some right triangles are isosceles.

  Example 2.2

  Here are some additional statements. They are all false.

  All right triangles are isosceles.

  5 = 2

  p2 ∉R

  Z ⊆ N

  {0, 1, 2} ∩ N = ;

  Example 2.3

  Here we pair sentences or expressions that are not state-

  ments with similar expressions that are statements.

  NOT Statements:

  Statements:

  Add 5 to both sides.

  Adding 5 to both sides of x − 5 = 37 gives x = 42.

  Z

  42 ∈ Z

  42

  42 is not a number.

  What is the solution of 2x = 84?

  The solution of 2x = 84 is 42.

  Statements

  35

  Example 2.4

  We will often use the letters P, Q, R and S to stand for

  specific statements. When more letters are needed we can use subscripts.

  Here are more statements, designated with letters. You decide which of

  them are true and which are false.

  P : For every integer n > 1, the number 2n − 1 is prime.

  Q : Every polynomial of degree n has at most n roots.

  R : The function f (x) = x2 is continuous.

  S1 : Z ⊆ ;

  S2 : {0, −1,−2} ∩ N = ;

  Designating statements with letters (as was done above) is a very useful

  shorthand. In discussing a particular statement, such as “The function

  f (x) = x2 is continuous,” it is convenient to just refer to it as R to avoid

  having to write or say it many times.

  Statements can contain variables. Here is an example.

  P : If an integer x is a multiple of 6, then x is even.

  This is a sentence that is true. (All multiples of 6 are even, so no matter

  which multiple of 6 the integer x happens to be, it is even.) Since the

  sentence P is definitely true, it is a statement.

  When a sentence or

  statement P contains a variable such as x, we sometimes denote it as P(x)

  to indicate that it is saying something about x. Thus the above statement

  can be denoted as

  P(x) : If an integer x is a multiple of 6, then x is even.

  A statement or sentence involving two variables might be denoted

  P(x, y), and so on.

  It is quite possible for a sentence containing variables to not be a

  statement. Consider the following example.

  Q(x) : The integer x is even.

  Is this a statement? Whether it is true or false depends on just which

  integer x is. It is true if x = 4 and false if x = 7, etc. But without any

  stipulations on the value of x it is impossible to say whether Q(x) is true or

  false. Since it is neither definitely true nor definitely false, Q(x) cannot be

  a statement. A sentence such as this, whose truth depends on the value

  of one or more variables, is called an open sentence. The variables in

  an open sentence (or statement) can represent any type of entity, not just

  numbers. Here is an open sentence where the variables are functions:

  36

  Logic

  R( f , g) : The function f is the derivative of the function g.

  This open sentence is true if f (x) = 2x and g(x) = x2. It is false if f (x) = x3

  and g(x) = x2, etc. We point out that a sentence such as R( f , g) (that

  involves variables) can be denoted either as R( f , g) or just R. We use the

  expression R( f , g) when we want to emphasize that the sentence involves

  variables.

  We will have more to say about open sentences later, but for now let’s

  return to statements.

  Statements are everywhere in mathematics. Any result or theorem

  that has been proved true is a statement. The quadratic formula and the

  Pythagorean theorem are both statements:

  p

  −b ± b2 − 4ac

  P : The solutions of the equation ax2 + bx + c = 0 are x =

  .

  2a

  Q :

  If a right triangle has legs of lengths a and b and hypotenuse of

  length c, then a2 + b2 = c2.

  Here is a very famous statement, so famous, in fact, that it has a name.

  It is called Fermat’s last theorem after Pierre Fermat, a seventeenth-

  century French mathematician who scribbled it in the margin of a notebook.

  R : For all numbers a, b, c, n ∈ N with n > 2, it is the case that an+bn 6= cn.

  Fermat believed this statement was true. He noted that he could prove

  it was true, except his notebook’s margin was too narrow to contain his

  proof. It
is doubtful that he really had a correct proof in mind, for after his

  death generations of brilliant mathematicians tried unsuccessfully to prove

  that his statement was true (or false). Finally, in 1993, Andrew Wiles of

  Princeton University announced that he had devised a proof. Wiles had

  worked on the problem for over seven years, and his proof runs through

  hundreds of pages. The moral of this story is that some true statements

  are not obviously true.

  Here is another statement famous enough to be named. It was first

  posed in the eighteenth century by the German mathematician Christian

  Goldbach, and thus is called the Goldbach conjecture:

  S : Every even integer greater than 2 is a sum of two prime numbers.

  You must agree that S is either true or false. It appears to be true, because

  when you examine even numbers that are bigger than 2, they seem to

  be sums of two primes: 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7,

  Statements

  37

  100 = 17 + 83 and so on. But that’s not to say there isn’t some large even

  number that’s not the sum of two primes. If such a number exists, then S

  is false. The thing is, in the over 260 years since Goldbach first posed this

  problem, no one has been able to determine whether it’s true or false. But

  since it is clearly either true or false, S is a statement.

  This book is about the methods that can be used to prove that S (or

  any other statement) is true or false. To prove that a statement is true,

  we start with obvious statements (or other statements that have been

  proven true) and use logic to deduce more and more complex statements

  until finally we obtain a statement such as S. Of course some statements

  are more difficult to prove than others, and S appears to be notoriously

  difficult; we will concentrate on statements that are easier to prove.

  But the point is this: In proving that statements are true, we use logic

  to help us understand statements and to combine pieces of information

  to produce new pieces of information. In the next several sections we

  explore some standard ways that statements can be combined to form new

  statements, or broken down into simpler statements.

  Exercises for Section 2.1

  Decide whether or not the following are statements. In the case of a statement,

  say if it is true or false, if possible.

  1. Every real number is an even integer.

  2. Every even integer is a real number.

  3. If x and y are real numbers and 5x = 5y, then x = y.

  4. Sets Z and N.

  5. Sets Z and N are infinite.

  6. Some sets are finite.

  7. The derivative of any polynomial of degree 5 is a polynomial of degree 6.

  8. N ∉ P(N).

  9. cos(x) = −1

  10. (R × N) ∩ (N × R) = N × N

  11. The integer x is a multiple of 7.

  12. If the integer x is a multiple of 7, then it is divisible by 7.

  13. Either x is a multiple of 7, or it is not.

  14. Call me Ishmael.

  15. In the beginning, God created the heaven and the earth.

  38

  Logic

  2.2 And, Or, Not

  The word “and” can be used to combine two statements to form a new

  statement. Consider for example the following sentence.

  R1 : The number 2 is even and the number 3 is odd.

  We recognize this as a true statement, based on our common-sense under-

  standing of the meaning of the word “and.” Notice that R1 is made up of

  two simpler statements:

  P : The number 2 is even.

  Q : The number 3 is odd.

  These are joined together by the word “and” to form the more complex

  statement R1. The statement R1 asserts that P and Q are both true. Since

  both P and Q are in fact true, the statement R1 is also true.

  Had one or both of P and Q been false, then R1 would be false. For

  instance, each of the following statements is false.

  R2 : The number 1 is even and the number 3 is odd.

  R3 : The number 2 is even and the number 4 is odd.

  R4 : The number 3 is even and the number 2 is odd.

  From these examples we see that any two statements P and Q can

  be combined to form a new statement “P and Q.” In the spirit of using

  letters to denote statements, we now introduce the special symbol ∧ to

  stand for the word “and.” Thus if P and Q are statements, P ∧ Q stands

  for the statement “P and Q.” The statement P ∧ Q is true if both P and Q

  are true; otherwise it is false. This is summarized in the following table,

  called a truth table.

  P

  Q

  P ∧ Q

  T

  T

  T

  T

  F

  F

  F

  T

  F

  F

  F

  F

  In this table, T stands for “True,” and F stands for “False.” (T and F are

  called truth values.) Each line lists one of the four possible combinations

  or truth values for P and Q, and the column headed by P ∧Q tells whether

  the statement P ∧ Q is true or false in each case.

  And, Or, Not

  39

  Statements can also be combined using the word “or.” Consider the

  following four statements.

  S1 : The number 2 is even or the number 3 is odd.

  S2 : The number 1 is even or the number 3 is odd.

  S3 : The number 2 is even or the number 4 is odd.

  S4 : The number 3 is even or the number 2 is odd.

  In mathematics, the assertion “P or Q” is always understood to mean that

  one or both of P and Q is true. Thus statements S1, S2, S3 are all true,

  while S4 is false. The symbol ∨ is used to stand for the word “or.” So if P

  and Q are statements, P ∨ Q represents the statement “P or Q.” Here is

  the truth table.

  P

  Q

  P ∨ Q

  T

  T

  T

  T

  F

  T

  F

  T

  T

  F

  F

  F

  It is important to be aware that the meaning of “or” expressed in the

  above table differs from the way it is often used in everyday conversation.

  For example, suppose a university official makes the following threat:

  You pay your tuition or you will be withdrawn from school.

  You understand that this means that either you pay your tuition or you

  will be withdrawn from school, but not both. In mathematics we never use

  the word “or” in such a sense. For us “or” means exactly what is stated

  in the table for ∨. Thus P ∨ Q being true means one or both of P and Q

  is true. If we ever need to express the fact that exactly one of P and Q is

  true, we use one of the following constructions:

  P or Q, but not both.

  Either P or Q.

  Exactly one of P or Q.

  If the university official were a mathematician, he might have qualified

  his statement in one of the following ways.

  Pay your tuition or you will be withdrawn from school, but not both.

  Either you pay your tuition or you will be withdrawn from school.

  40

  Logic

&nb
sp; To conclude this section, we mention another way of obtaining new

  statements from old ones. Given any statement P, we can form the new

  statement “It is not true that P.” For example, consider the following

  statement.

  The number 2 is even.

  This statement is true. Now change it by inserting the words “It is not

  true that” at the beginning:

  It is not true that the number 2 is even.

  This new statement is false.

  For another example, starting with the false statement “2 ∈ ;,” we get

  the true statement “It is not true that 2 ∈ ;.”

  We use the symbol ∼ to stand for the words “It’s not true that,” so

  ∼ P means “It’s not true that P.” We often read ∼ P simply as “not P.”

  Unlike ∧ and ∨, which combine two statements, the symbol ∼ just alters

  a single statement. Thus its truth table has just two lines, one for each

  possible truth value of P.

  P

  ∼ P

  T

  F

  F

  T

  The statement ∼ P is called the negation of P. The negation of a

  specific statement can be expressed in numerous ways. Consider

  P : The number 2 is even.

  Here are several ways of expressing its negation.

  ∼ P : It’s not true that the number 2 is even.

  ∼ P : It is false that the number 2 is even.

  ∼ P : The number 2 is not even.

  In this section we’ve learned how to combine or modify statements with

  the operations ∧, ∨ and ∼. Of course we can also apply these operations

  to open sentences or a mixture of open sentences and statements. For

  example, (x is an even integer) ∧ (3 is an odd integer) is an open sentence

  that is a combination of an open sentence and a statement.

  Conditional Statements

  41

  Exercises for Section 2.2

  Express each statement or open sentence in one of the forms P ∧ Q, P ∨ Q, or ∼ P.

  Be sure to also state exactly what statements P and Q stand for.

  1. The number 8 is both even and a power of 2.

  2. The matrix A is not invertible.

  3. x 6= y

  4. x < y

  5. y ≥ x

  6. There is a quiz scheduled for Wednesday or Friday.

  7. The number x equals zero, but the number y does not.

  8. At least one of the numbers x and y equals 0.

  9. x ∈ A − B

  10. x ∈ A ∪ B

  11. A ∈ ©X ∈ P(N) : |X | < ∞ª

  12. Happy families are all alike, but each unhappy family is unhappy in its own

  way. (Leo Tolstoy, Anna Karenina)

  13. Human beings want to be good, but not too good, and not all the time.

 

‹ Prev