A Gentle Introduction to the Art of Mathematics Version 3.1 by Joseph Fields

Contents
1 Introduction and notation 1
1.1 Basic sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Definitions: Prime numbers . . . . . . . . . . . . . . . . . . . 12
1.3 More scary notation . . . . . . . . . . . . . . . . . . . . . . . 20
1.4 Definitions of elementary number theory . . . . . . . . . . . . 23
1.4.1 Even and odd . . . . . . . . . . . . . . . . . . . . . . . 23
1.4.2 Decimal and base-n notation . . . . . . . . . . . . . . . 23
1.4.3 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.4.4 Floor and ceiling . . . . . . . . . . . . . . . . . . . . . 26
1.4.5 Div and mod . . . . . . . . . . . . . . . . . . . . . . . 27
1.4.6 Binomial coefficients . . . . . . . . . . . . . . . . . . . 29
1.5 Some algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.6 Rational and irrational numbers . . . . . . . . . . . . . . . . . 45
1.7 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2 Logic and quantifiers 55
2.1 Predicates and Logical Connectives . . . . . . . . . . . . . . . 55
2.2 Implication . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
2.3 Logical equivalences . . . . . . . . . . . . . . . . . . . . . . . . 74
2.4 Two-column proofs . . . . . . . . . . . . . . . . . . . . . . . . 88
2.5 Quantified statements . . . . . . . . . . . . . . . . . . . . . . 92
2.6 Deductive reasoning and Argument forms . . . . . . . . . . . . 101
2.7 Validity of arguments and common errors . . . . . . . . . . . . 110

3 Proof techniques I . . . . . . . . 119
3.1 Direct proofs of universal statements . . . . . . . . . . . . . . 119
3.2 More direct proofs . . . . . . . . . . . . . . . . . . . . . . . . 132
3.3 Contradiction and contraposition . . . . . . . . . . . . . . . . 137
3.4 Disproofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
3.5 By cases and By exhaustion . . . . . . . . . . . . . . . . . . . 148
3.6 Existential statements . . . . . . . . . . . . . . . . . . . . . . 157
4 Sets 165
4.1 Basic notions of set theory . . . . . . . . . . . . . . . . . . . . 165
4.2 Containment . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
4.3 Set operations . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
4.4 Venn diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . 188
4.5 Russell’s Paradox . . . . . . . . . . . . . . . . . . . . . . . . . 197
5 Proof techniques II | Induction 201
5.1 The principle of mathematical induction . . . . . . . . . . . . 201
5.2 Formulas for sums and products . . . . . . . . . . . . . . . . . 211
5.3 Other proofs using PMI . . . . . . . . . . . . . . . . . . . . . 222
5.4 The strong form of mathematical induction . . . . . . . . . . . 230
6 Relations and functions 233
6.1 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
6.2 Properties of relations . . . . . . . . . . . . . . . . . . . . . . 243
6.3 Equivalence relations . . . . . . . . . . . . . . . . . . . . . . . 251
6.4 Ordering relations . . . . . . . . . . . . . . . . . . . . . . . . . 260
6.5 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
6.6 Special functions . . . . . . . . . . . . . . . . . . . . . . . . . 283
7 Proof techniques III | Combinatorics 293 
7.1 Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
7.2 Parity and Counting arguments . . . . . . . . . . . . . . . . . 309
7.3 The pigeonhole principle . . . . . . . . . . . . . . . . . . . . . 323
7.4 The algebra of combinations . . . . . . . . . . . . . . . . . . . 328
8 Cardinality 339
8.1 Equivalent sets . . . . . . . . . . . . . . . . . . . . . . . . . . 339
8.2 Examples of set equivalence . . . . . . . . . . . . . . . . . . . 345
8.3 Cantor’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . 357
8.4 Dominance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
8.5 CH and GCH . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
9 Proof techniques IV | Magic 381
9.1 Morley’s miracle . . . . . . . . . . . . . . . . . . . . . . . . . . 383
9.2 Five steps into the void . . . . . . . . . . . . . . . . . . . . . . 390
9.3 Monge’s circle theorem . . . . . . . . . . . . . . . . . . . . . . 402

References  . . . . . . . . . . . . . . . . .410 

Index  . . . . . . . . . . . . . . .410