Proofs and Fundamentals: A First Course in Abstract Mathematics

Title ......Page 1
Copyright ......Page 2
Contents ......Page 3
Introduction ......Page 7
To the Student ......Page 11
To the Instructor ......Page 17
Part I. PROOFS ......Page 21
1.1 Introduction ......Page 23
1.2 Statements ......Page 24
1.3 Relations Between Statements ......Page 38
1.4 Valid Arguments ......Page 51
1.5 Quantifiers ......Page 61
2.1 Mathematical Proofs — What They Are and Why We Need Them ......Page 75
2.2 Direct Proofs ......Page 83
2.3 Proofs by Contrapositive and Contradiction ......Page 87
2.4 Cases, and If and Only If ......Page 94
2.5 Quantifiers in Theorems ......Page 101
2.6 Writing Mathematics ......Page 113
Part II. FUNDAMENTALS ......Page 125
3.1 Introduction ......Page 127
3.2 Sets — Basic Definitions ......Page 129
3.3 Set Operations ......Page 139
3.4 Indexed Families of Sets ......Page 149
4.1 Functions ......Page 155
4.2 Image and Inverse Image ......Page 165
4.3 Composition and Inverse Functions ......Page 172
4.4 Injectivity, Surjectivity and Bijectivity ......Page 181
4.5 Sets of Functions ......Page 190
5.1 Relations ......Page 197
5.2 Congruence ......Page 204
5.3 Equivalence Relations ......Page 211
6.1 Cardinality of Sets ......Page 223
6.2 Cardinality of the Number Systems ......Page 238
6.3 Mathematical Induction ......Page 246
6.4 Recursion ......Page 256
Part III. EXTRAS ......Page 269
7.1 Binary Operations ......Page 271
7.2 Groups ......Page 278
7.3 Homomorphisms and Isomorphisms ......Page 287
7.4 Partially Ordered Sets ......Page 293
7.5 Lattices ......Page 304
7.6 Counting: Products and Sums ......Page 314
7.7 Counting: Permutations and Combinations ......Page 324
8.1 Back to the Beginning ......Page 343
8.2 The Natural Numbers ......Page 344
8.3 Further Properties of the Natural Numbers ......Page 353
8.4 The Integers ......Page 358
8.5 The Rational Numbers ......Page 368
8.6 The Real Numbers and the Complex Numbers ......Page 372
8.7 Appendix: Proof of Theorem 8.2.1 ......Page 381
9.1 Introduction ......Page 383
9.2 Greatest Common Divisors ......Page 384
9.3 Divisibility Tests ......Page 386
9.4 Real-Valued Functions ......Page 387
9.5 Iterations of Functions ......Page 388
9.6 Fibonacci Numbers and Lucas Numbers ......Page 389
9.7 Fuzzy Sets ......Page 391
Appendix: Properties of Numbers ......Page 395
Hints for Selected Exercises ......Page 399
References ......Page 425
Index ......Page 433