How to Prove It: A Structured Approach

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Dedication......Page 7
Contents......Page 9
Preface......Page 11
Introduction......Page 15
1.1. Deductive Reasoning and Logical Connectives......Page 22
1.2. Truth Tables......Page 28
1.3. Variables and Sets......Page 40
1.4. Operations on Sets......Page 48
1.5. The Conditional and Biconditional Connectives......Page 57
2.1. Quantifiers......Page 69
2.2. Equivalences Involving Quantifiers......Page 78
2.3. More Operations on Sets......Page 87
3.1. Proof Strategies......Page 98
3.2. Proofs Involving Negations and Conditionals......Page 109
3.3. Proofs Involving Quantifiers......Page 122
3.4. Proofs Involving Conjunctions and Biconditionals......Page 138
3.5. Proofs Involving Disjunctions......Page 150
3.6. Existence and Uniqueness Proofs......Page 160
3.7. More Examples of Proofs......Page 169
4.1. Ordered Pairs and Cartesian Products......Page 177
4.2. Relations......Page 185
4.3. More About Relations......Page 194
4.4. Ordering Relations......Page 203
4.5. Closures......Page 216
4.6. Equivalence Relations......Page 227
5.1. Functions......Page 240
5.2. One-to-one and Onto......Page 250
5.3. Inverses of Functions......Page 259
5.4. Images and Inverse Images: A Research Project......Page 269
6.1. Proof by Mathematical Induction......Page 274
6.2. More Examples......Page 281
6.3. Recursion......Page 293
6.4. Strong Induction......Page 302
6.5. Closures Again......Page 314
7.1. Equinumerous Sets......Page 320
7.2. Countable and Uncountable Sets......Page 329
7.3. The Cantor–Schröder–Bernstein Theorem......Page 336
Section 1.2......Page 343
Section 1.3......Page 344
Section 1.4......Page 345
Section 1.5......Page 346
Section 2.2......Page 347
Section 3.1......Page 348
Section 3.2......Page 349
Section 3.3......Page 350
Section 3.4......Page 351
Section 3.5......Page 353
Section 3.6......Page 354
Section 3.7......Page 355
Section 4.2......Page 356
Section 4.3......Page 357
Section 4.4......Page 358
Section 4.5......Page 359
Section 4.6......Page 361
Section 5.1......Page 363
Section 5.2......Page 365
Section 5.3......Page 366
Section 6.1......Page 367
Section 6.2......Page 369
Section 6.3......Page 372
Section 6.4......Page 375
Section 6.5......Page 377
Section 7.1......Page 379
Section 7.3......Page 384
Appendix 2 Proof Designer......Page 387
Suggestions for Further Reading......Page 389
To prove a goal of the form......Page 390
To use a given of the form......Page 392
Techniques that can be used in any proof......Page 393
Index......Page 395