Copyright 3
Preface 5
Contents 9
Notes for the Student 12
Notes for Instructors 14
Part I: The Discrete 19
Chapter 1 Integers 20
1.1 Axioms 21
1.2 First Consequences 22
1.3 Subtraction 27
1.4 Philosophical Questions 28
Chapter 2 Natural Numbers and Induction 30
2.1 Natural Numbers 31
2.2 Ordering the Integers 32
2.3 Induction 34
2.4 The Well-Ordering Principle 38
Chapter 3 Some Points of Logic 41
3.1 Quantifiers 42
3.2 Implications 44
3.3 Negations 45
3.4 Philosophical Questions 46
Chapter 4 Recursion 48
4.1 Examples 49
4.2 Finite Series 52
4.3 Fishing in a Finite Pool 53
4.4 The Binomial Theorem 54
4.5 A Second Form of Induction 58
4.6 More Recursions 58
Chapter 5 Underlying Notions in Set Theory 61
5.1 Subsets and Set Equality 62
5.2 Intersections and Unions 64
5.3 Cartesian Products 66
5.4 Functions 67
Chapter 6 Equivalence Relations and Modular Arithmetic 69
6.1 Equivalence Relations 70
6.2 The Division Algorithm 73
6.3 The Integers Modulo n 74
6.4 Prime Numbers 76
Chapter 7 Arithmetic in Base Ten 79
7.1 Base-Ten Representation of Integers 80
7.2 The Addition Algorithm for Two Nonnegative Numbers (Base 10) 83
Part II: The Continuous 87
Chapter 8 Real Numbers 88
8.1 Axioms 89
8.2 Positive Real Numbers and Ordering 92
8.3 Similarities and Differences 93
8.4 Upper Bounds 94
Chapter 9 Embedding Z in R 97
9.1 Injections and Surjections 98
9.2 The Relationship between Z and R 102
9.3 Apples and Oranges Are All Just Fruit 104
Chapter 10 Limits and Other Consequences of Completeness 106
10.1 The Integers Are Unbounded 107
10.2 Absolute Value 107
10.3 Distance 108
10.4 Limits 109
10.5 Square Roots 114
Chapter 11 Rational and Irrational Numbers 117
11.1 Rational Numbers 118
11.2 Irrational Numbers 119
11.3 Quadratic Equations 121
Chapter 12 Decimal Expansions 123
12.1 Infinite Series 124
12.2 Decimals 126
Chapter 13 Cardinality 130
13.1 Injections, Surjections, and Bijections Revisited 131
13.2 Some Countable Sets 133
13.3 Some Uncountable Sets 134
13.4 An Infinite Hierarchy of Infinities 135
13.5 Nondescribable Numbers 136
Chapter 14 Final Remarks 139
Further Topics 140
Appendix A Continuity and Uniform Continuity 141
A.1 Continuity at a Point 141
A.2 Continuity on a Subset of R 142
A.3 Uniform Continuity 143
Appendix B Public-Key Cryptography 146
B.1 Repeated Squaring 146
B.2 Diffie\u2013Hellman Key Exchange 147
Appendix C Complex Numbers 150
C.1 Definition and Algebraic Properties 150
C.2 Geometric Properties 152
Appendix D Groups and Graphs 156
D.1 Groups 156
D.2 Subgroups 157
D.3 Symmetries 158
D.4 Finitely Generated Groups 160
D.5 Graphs 160
D.6 Cayley Graphs 161
D.7 G as a Group of Symmetries of 螕 163
D.8 Lie Groups 164
Appendix E Generating Functions 166
E.1 Addition 166
E.2 Multiplication and Reciprocals 168
E.3 Differentiation 170
Appendix F Cardinal Number and Ordinal Number 171
F.1 The Cantor\u2013Schr枚der\u2013Bernstein Theorem 171
F.2 Ordinal Numbers 173
Appendix G Remarks on Euclidean Geometry 176
List of Symbols 178
Index 181