[ Pobierz całość w formacie PDF ]
Book of Proof
Richard Hammack
Virginia Commonwealth University
Mathematics Textbook Series. Editor: Lon Mitchell
1.
Book of Proof
by Richard Hammack
2.
Linear Algebra
by Jim Heeron
3.
Abstract Algebra: Theory and Applications
by Thomas Judson
4.
Ordinary and Partial Dierential Equations
by John W. Cain and Angela Reynolds
5.
Introduction to Modern Set Theory
by Judith Roitman
Department of Mathematics & Applied Mathematics
Virginia Commonwealth University
Richmond, Virginia, 23284
Book of Proof
Edition 1.1
©2009 by Richard Hammack
This work is licensed under the Creative Commons Attribution-No Derivative Works 3.0
License
Cover art by Eleni Kanakis,©2009, all rights reserved, used by permission
Typeset in 11pt T
E
X Gyre Schola using PDFL
A
T
E
X
To my students
Contents
vii
Preface
viii
Introduction
I Fundamentals
3
1. Sets
1.1. Introduction to Sets
3
1.2. The Cartesian Product
8
1.3. Subsets
11
1.4. Power Sets
14
1.5. Union, Intersection, Dierence
17
1.6. Complement
19
1.7. Venn Diagrams
21
1.8. Indexed Sets
24
28
2. Logic
2.1. Statements
29
2.2. And, Or, Not
33
2.3. Conditional Statements
36
2.4. Biconditional Statements
39
2.5. Truth Tables for Statements
41
2.6. Logical Equivalence
44
2.7. Quantifiers
46
2.8. More on Conditional Statements
48
2.9. Translating English to Symbolic Logic
50
2.10. Negating Statements
52
2.11. Logical Inference
55
2.12. An Important Note
56
57
3. Counting
3.1. Counting Lists
57
3.2. Factorials
64
3.3. Counting Subsets
67
3.4. Pascal’s Triangle and the Binomial Theorem
72
3.5. Inclusion-Exclusion
75
 v
II How to Prove Conditional Statements
81
4. Direct Proof
4.1. Theorems
81
4.2. Definitions
83
4.3. Direct Proof
85
4.4. Using Cases
90
4.5. Treating Similar Cases
92
94
5. Contrapositive Proof
5.1. Contrapositive Proof
94
5.2. Congruence of Integers
97
5.3. Mathematical Writing
99
103
6. Proof by Contradiction
6.1. Proving Statements with Contradiction
104
6.2. Proving Conditional Statements by Contradiction
107
6.3. Combining Techniques
108
6.4. Some Words of Advice
109
III More on Proof
7. Proving Non-conditional Statements
113
7.1. If-And-Only-If Proof
113
7.2. Equivalent Statements
115
7.3. Existence Proofs
116
119
8. Proofs Involving Sets
8.1. How to Prove
a
2
A
119
8.2. How to Prove
A
µ
B
121
8.3. How to Prove
A
Æ
B
124
8.4. Examples: Perfect Numbers
127
134
9. Disproof
9.1. Counterexamples
136
9.2. Disproving Existence Statements
138
9.3. Disproof by Contradiction
139
142
10. Mathematical Induction
10.1. Proof by Strong Induction
148
10.2. Proof by Smallest Counterexample
152
10.3. Fibonacci Numbers
153
[ Pobierz całość w formacie PDF ]