Nuts and Bolts of Proofs (eBook)

An Introduction to Mathematical Proofs

Antonella Cupillari (Autor)

eBook Download: EPUB

2005 | 3. Auflage
192 Seiten
Elsevier Science (Verlag)
978-0-08-053790-0 (ISBN)

Infos

The Nuts and Bolts of Proof instructs students on the basic logic of mathematical proofs, showing how and why proofs of mathematical statements work. It provides them with techniques they can use to gain an inside view of the subject, reach other results, remember results more easily, or rederive them if the results are forgotten.A flow chart graphically demonstrates the basic steps in the construction of any proof and numerous examples illustrate the method and detail necessary to prove various kinds of theorems.

* The List of Symbols has been extended.
* Set Theory section has been strengthened with more examples and exercises.
* Addition of A Collection of Proofs

---

The Nuts and Bolts of Proof instructs students on the basic logic of mathematical proofs, showing how and why proofs of mathematical statements work. It provides them with techniques they can use to gain an inside view of the subject, reach other results, remember results more easily, or rederive them if the results are forgotten.A flow chart graphically demonstrates the basic steps in the construction of any proof and numerous examples illustrate the method and detail necessary to prove various kinds of theorems.* The "e;List of Symbols"e; has been extended.* Set Theory section has been strengthened with more examples and exercises.* Addition of "e;A Collection of Proofs"e;

Inhalt

Front Cover 1
The Nuts and Bolts of Proofs 4
Copyright Page 5
Contents 10
List of Symbols 6
Preface 12
Chapter 1. Introduction and Basic Terminology 14
Chapter 2. General Suggestions 18
Chapter 3. Basic Techniques to Prove If/Then Statements 22
Direct Proof 25
Related Statements 32
Proof by Contrapositive (AKA Proof by Contradiction or Indirect Proof) 35
How to Construct the Negation of a Statement 38
Chapter 4. Special Kinds of Theorems 48
"If and Only If" or "Equivalence Theorems" 48
Use of Counterexamples 58
Mathematical Induction 61
Existence Theorems 71
Uniqueness Theorems 74
Equality of Sets 81
Equality of Numbers 91
Composite Statements 94
Limits 104
Chapter 5. Review Exercises 116
Chapter 6. Exercises Without Solutions 120
Chapter 7. Collection of Proofs 128
Chapter 8. Solutions for the Exercises at the End of the Sections and the Review Exercises 136
Solutions for the Exercises at the End of the Sections 137
Solutions for the Review Exercises 164
Chapter 9. Other Books on the Subject of Proofs and Mathematical Writing 186
Index 190
A Guide to Selecting a Method of Proof 193

Textauszug

Basic Techniques To Prove If/Then Statements

Let’s start by looking at the details of a process that goes on almost automatically in our minds hundreds of times every day–deciding whether something is true or false. Suppose you make the following statement:

If I go home this weekend, I will take my parents out to dinner.

When is your statement true? When is it false; that is, when could you be accused of lying?

The statement we are considering is a composite statement, and its two parts are the following simple statements:

A: I go home this weekend.

B: I will take my parents out to dinner.

As far as your trip is concerned, there are two possibilities:

i. You are going home this weekend (A is true).

ii. You are not going home this weekend (A is false).

Regarding the dinner, there are two possibilities as well:

i. You will take your parents out to dinner (B is true).

ii. You will not take your parents out to dinner (B is false).

Thus, we can consider four possibilities:

1. A is true and B is true.

2. A is true and B is false.

3. A is false and B is true.

4. A is false and B is false.

Case 1. You do go home and you do take your parents out to dinner. Your statement is true.

Case 2. You go home for the weekend, but you do not take your parents out to dinner. You have been caught lying! Your statement is false.

Cases 3 and 4. You cannot be accused of lying if you did not go home, but you did take your parents out to dinner, because they came to visit. If you did not go home, nobody can accuse you of lying if you did not take your parents out to dinner. It is very important to notice that you had not specified what you would do in case you were not going home (A is false). So, whether you did take your parents out to dinner or not, you did not lie.

In conclusion, there is only one case in which your statement is false–namely, when A is true and B is false. This is a general feature of statements of the form “If A, then B” or “A implies B.”

A statement of the form “If A, then B” is true if we can prove that it is impossible for A to be true and B to be false at the same time; that is, whenever A is true, B must be true as well.

The statement “If A, then B” can be reworded as “A is a sufficient condition for B” and as “B is a necessary condition for A.” The mathematical use of the words “sufficient” and “necessary” is very similar to their everyday use. If a given statement is true and it provides enough (sufficient) information to reach the conclusion, then the statement is called a sufficient condition. If a statement is an inevitable (certain) consequence of a given statement, it is called a necessary condition. A condition can be sufficient but not necessary or necessary but not sufficient.

As an example, consider the statement “If an animal is a cow, then it has four legs.” Having four legs is a necessary condition for an animal to be a cow, but it is not a sufficient condition for identifying a cow, as it is possible for an animal to have four legs and not be a cow. On the other hand, being a cow is a sufficient condition for knowing that the animal has four legs. Consult the James & James Mathematics Dictionary if you want to find out more about “sufficient” and “necessary” conditions.

All arguments having this form (called modus ponens) are valid. The expression “modus ponens” comes from the Latin ponere, meaning “to affirm.”

Very often one of the so-called truth tables* is used to remember the information just seen (T = true, F = false):

A	B	If A, then B

T

T

T

T

F

F

F

T

T

F

F

T

Because in a statement of the form “If A, then B” the hypothesis and the conclusion are clearly separated (part A, the hypothesis, contains all the information we are allowed to use; part B is the conclusion we want to reach, given the previous information), it is useful to try to write in this form any statement to be proved. The following steps can make the statement of a theorem simpler and therefore more manageable, without changing its meaning:

1. Identify the hypothesis (A) and conclusion (B) so the statement can be written in the form “If A, then B” or “A implies B.”

2. Watch out for irrelevant details.

3. Rewrite the statement to be proved in a form you are comfortable with, even if it is not the most elegant.

4. Check all relevant properties (from what you are supposed to know) of the objects involved.

If you get stuck while constructing the proof, double-check whether you have overlooked some explicit or implicit information you are supposed to know and be able to use in the given context. As mentioned in the General Suggestions section, the proof of a statement depends on the context in which the statement is presented. The examples included in the next sections will illustrate how to use these suggestions, which at this point are somewhat vague, to construct some proofs.

DIRECT PROOF

A direct proof is based on the assumption that the hypothesis contains enough information to allow the construction of a series of logically connected steps leading to the conclusion.

EXAMPLE 1.

The sum of two odd numbers is an even number.

Discussion

The statement is not in the standard form “If A, then B”; therefore, we have to identify the hypothesis and the conclusion. What explicit information do we have? We are dealing with any two odd numbers. What do we want to conclude? We want to prove that their sum is not an odd number. So, we can set:

A. Consider any two odd numbers and add them. (Implicit hypothesis: As odd numbers are integer number, we can use the properties and operations of integer numbers.)

B. Their sum is an even number.

Thus, we can rewrite the original statement as: If we consider two odd numbers and add them, then we obtain a number that is even. This statement is less elegant than the original one, but it is more explicit because it separates clearly the hypothesis and the conclusion.

From experience we know that the sum of two odd numbers is an even number, but this is not sufficient (good enough) evidence (we could be over-generalizing). We must prove this fact. We will start by introducing some symbols so it will be easier to refer to the numbers used.

Let a and b be two odd numbers. Thus (see the section on facts and properties of numbers at the front of the book), we can write:

where t and s are integer numbers. Therefore,

The number t + s + 1 is an integer number, because t and s are integers. This proves that the number a + b is indeed even.

We reached the conclusion that was part of the original statement! We seem to be on the right track. Can we rewrite the proof in a precise and easy to follow way? Let us try!

Proof

Let a and b be two odd numbers. As the numbers are odd, it is possible write:

where t and s are two integers. Therefore,

The number p = t + s + 1 is an integer because t and s are integers. Thus,

where p is an integer.

This implies that a + b is an even number. Because this is the conclusion in the original statement, the proof is...

Produkt-Details

• Erscheint lt. Verlag: 8.9.2005
• Sprache: englisch
• Themenwelt: Sachbuch/Ratgeber
• Themenwelt: Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre
• Themenwelt: Technik
• ISBN-10: 0-08-053790-1 / 0080537901
• ISBN-13: 978-0-08-053790-0 / 9780080537900