Scribd
Upload
30 views3 pages

Proofs TOC

The document outlines a comprehensive table of contents for a mathematical text, covering various topics such as proofs, number theory, sets, logic, and functions. Each section includes subsections on specific concepts, examples, and exercises. Additionally, it introduces advanced topics like Ramsey theory, game theory, and group theory, along with appendices on other proof methods.

Uploaded by

Engoulou Ngomo Juan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
30 views3 pages

Proofs TOC

The document outlines a comprehensive table of contents for a mathematical text, covering various topics such as proofs, number theory, sets, logic, and functions. Each section includes subsections on specific concepts, examples, and exercises. Additionally, it introduces advanced topics like Ramsey theory, game theory, and group theory, along with appendices on other proof methods.

Uploaded by

Engoulou Ngomo Juan
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Contents

1 Intuitive Proofs 1
1.1 Chessboard Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Naming Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 The Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Bonus Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

Introduction to Ramsey Theory . . . . . . . . . . . . . . . . . . . . . 41

2 Direct Proofs 47
2.1 Working From Definitions . . . . . . . . . . . . . . . . . . . . . . . . 48
2.2 Proofs by Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.3 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.4 Greatest Common Divisors . . . . . . . . . . . . . . . . . . . . . . . 59
2.5 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.6 Bonus Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

Introduction to Number Theory . . . . . . . . . . . . . . . . . . . . . 89

3 Sets 97
3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.2 Proving A ✓ B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.3 Proving A = B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.4 Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
3.5 Bonus Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

Introduction to Topology . . . . . . . . . . . . . . . . . . . . . . . . . 137

4 Induction 147
4.1 Dominoes, Ladders and Chips . . . . . . . . . . . . . . . . . . . . . . 147
4.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.3 Strong Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
4.4 Non-Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

iii
iv CONTENTS

4.5 Bonus Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175


Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

Introduction to Sequences . . . . . . . . . . . . . . . . . . . . . . . . 199

5 Logic 207
5.1 Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
5.2 Truth Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
5.3 Quantifiers and Negations . . . . . . . . . . . . . . . . . . . . . . . . 219
5.4 Proving Quantified Statements . . . . . . . . . . . . . . . . . . . . . 227
5.5 Paradoxes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
5.6 Bonus Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

Introduction to Real Analysis . . . . . . . . . . . . . . . . . . . . . . 253

6 The Contrapositive 261


6.1 Finding the Contrapositive of a Statement . . . . . . . . . . . . . . . 263
6.2 Proofs Using the Contrapositive . . . . . . . . . . . . . . . . . . . . . 264
6.3 Counterexamples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
6.4 Bonus Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278

Introduction to Big Data . . . . . . . . . . . . . . . . . . . . . . . . . 285

7 Contradiction 293
7.1 Two Warm-Up Examples . . . . . . . . . . . . . . . . . . . . . . . . . 295
7.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
7.3 The Most Famous Proof in History . . . . . . . . . . . . . . . . . . . 300
7.4 The Pythagoreans . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
7.5 Bonus Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320

Introduction to Game Theory . . . . . . . . . . . . . . . . . . . . . . 325

8 Functions 331
8.1 Approaching Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 331
8.2 Injections, Surjections and Bijections . . . . . . . . . . . . . . . . . . 335
8.3 The Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
8.4 Invertibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
8.5 Bonus Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362

Introduction to Cardinality . . . . . . . . . . . . . . . . . . . . . . . . 371


9 Relations 379
9.1 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . 379
9.2 Abstraction and Generalization . . . . . . . . . . . . . . . . . . . . . 391
9.3 Bonus Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402

Introduction to Group Theory . . . . . . . . . . . . . . . . . . . . . . 413

Appendices 421

A Other Proof Methods 423


A.1 Probabilistic Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
A.2 Linear Algebra Method . . . . . . . . . . . . . . . . . . . . . . . . . 429
A.3 Combinatorial Method . . . . . . . . . . . . . . . . . . . . . . . . . . 434
A.4 Computer-Assisted Proofs . . . . . . . . . . . . . . . . . . . . . . . . 440
A.5 Proofs by Picture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448

B Proofs From The Book 453


B.1 Merry Madness from March . . . . . . . . . . . . . . . . . . . . . . . 454
B.2 Significant Sets of Shifting Shapes . . . . . . . . . . . . . . . . . . . 455
B.3 A Flow of Factors From Fermat . . . . . . . . . . . . . . . . . . . . . 460
B.4 A Pinpointed Proof Pausing Prussian Parades . . . . . . . . . . . . . 462
B.5 Cleverly Cutting the Cruising Coins . . . . . . . . . . . . . . . . . . 464
B.6 An Antisocial Ant Avalanche . . . . . . . . . . . . . . . . . . . . . . 468
B.7 A Pack of Pretty (Book) Proofs by Picture . . . . . . . . . . . . . . 472
B.8 An Image’s Insightful Illusion . . . . . . . . . . . . . . . . . . . . . . 476
B.9 Monotone Marches through Muddled Marks . . . . . . . . . . . . . . 479
B.10 Zigging Zeniths and Zagging Zones . . . . . . . . . . . . . . . . . . . 484

C Writing Advice 487


C.1 Writing Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487
C.2 Writing in LATEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493

Index 497

You might also like