-
Notifications
You must be signed in to change notification settings - Fork 0
/
file.txt
173 lines (173 loc) · 3.04 KB
/
file.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
Prefacevii
Introductionviiiwhatstheproblemmate
Fundamentals
1. Sets
1.1. Introduction to Sets
1.2. The Cartesian Product
1.3. Subsets
1.4. Power Sets
1.5. Union, Intersection, Difference
1.6. Complement
1.7. Venn Diagrams
1.8. Indexed Sets
1.9. Sets That Are Number Systems
1.10. Russell’s Paradox
2. Logic
2.1. Statements
2.2. And, Or, Not
2.3. Conditional Statements
2.4. Biconditional Statements
2.5. Truth Tables for Statements
2.6. Logical Equivalence
2.7. Quantifiers
2.8. More on Conditional Statements
2.9. Translating English to Symbolic Logic
2.10. Negating Statements
2.11. Logical Inference
2.12. An Important Note
3. Counting
3.1. Lists
3.2. The Multiplication Principle
3.3. The Addition and Subtraction Principles
3.4. Factorials and Permutations
3.5. Counting Subsets
3.6. Pascal’s Triangle and the Binomial Theorem
3.7. The Inclusion-Exclusion Principle
3.8. Counting Multisets
3.9. The Division and Pigeonhole Principles
3.10. Combinatorial Proof
108v
II
How to Prove Conditional Statements
4. Direct Proof
4.1. Theorems
4.2. Definitions
4.3. Direct Proof
4.4. Using Cases
4.5. Treating Similar Cases
5. Contrapositive Proof
5.1. Contrapositive Proof
5.2. Congruence of Integers
5.3. Mathematical Writing
6. Proof by Contradiction
6.1. Proving Statements with Contradiction
6.2. Proving Conditional Statements by Contradiction
6.3. Combining Techniques
6.4. Some Words of Advice
III
113
113
115
118
124
125
128
128
131
133
137
138
141
142
143
More on Proof
7. Proving Non-Conditional Statements
7.1. If-and-Only-If Proof
7.2. Equivalent Statements
7.3. Existence Proofs; Existence and Uniqueness Proofs
7.4. Constructive Versus Non-Constructive Proofs
8. Proofs Involving Sets
8.1. How to Prove a ∈ A
8.2. How to Prove A ⊆ B
8.3. How to Prove A = B
8.4. Examples: Perfect Numbers
9. Disproof
9.1. Counterexamples
9.2. Disproving Existence Statements
9.3. Disproof by Contradiction
10. Mathematical Induction
10.1. Proof by Induction
10.2. Proof by Strong Induction
10.3. Proof by Smallest Counterexample
10.4. The Fundamental Theorem of Arithmetic
10.5. Fibonacci Numbers
147
147
149
150
154
157
157
159
162
165
172
174
176
178
180
182
187
191
192
193vi
IV
Relations, Functions and Cardinality
11. Relations
11.1. Relations
11.2. Properties of Relations
11.3. Equivalence Relations
11.4. Equivalence Classes and Partitions
11.5. The Integers Modulo n
11.6. Relations Between Sets
12. Functions
12.1. Functions
12.2. Injective and Surjective Functions
12.3. The Pigeonhole Principle Revisited
12.4. Composition
12.5. Inverse Functions
12.6. Image and Preimage
13. Proofs in Calculus
13.1. The Triangle Inequality
13.2. Definition of a Limit
13.3. Limits That Do Not Exist
13.4. Limit Laws
13.5. Continuity and Derivatives
13.6. Limits at Infinity
13.7. Sequences
13.8. Series
14. Cardinality of Sets
14.1. Sets with Equal Cardinalities
14.2. Countable and Uncountable Sets
14.3. Comparing Cardinalities
14.4. The Cantor-Bernstein-Schröder Theorem
201
201
205
210
215
218
221
223
223
228
233
235
238
242
244
245
246
249
251
256
258
261
265
269
269
275
280
284
Conclusion291
Solutions292