An Infinite Descent into Pure Mathematics - CMU

An Infinite Descent into Pure Mathematics

...

BY CLIVE NEWSTEAD

Version 0.3 Last updated on Wednesday 3rd July 2019



c 2019 Clive Newstead All Rights Reserved.

Preview of First Edition, 2019 (forthcoming)

ISBN 978-1-950215-00-3 (paperback) ISBN 978-1-950215-01-0 (hardback)

A free PDF copy of An Infinite Descent into Pure Mathematics can be obtained from the book's website:

This book, its figures and its TEX source are released under a Creative Commons Attribution?ShareAlike 4.0 International Licence. The full text of the licence is replicated at the end of the book, and can be found on the Creative Commons website:

0 2 4 6 8 10 9 7 5 3 1

Contents

Preface

vii

Acknowledgements

xi

0 Getting started

1

0.E Chapter 0 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

I Core concepts

17

1 Logical structure

19

1.1 Propositional logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.2 Variables and quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

1.3 Logical equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

1.E Chapter 1 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

2 Sets and functions

67

2.1 Sets and set operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

2.2 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

2.3 Injections and surjections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

2.E Chapter 2 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

3 Mathematical induction

113

iii

iv

Contents

3.1 Peano's axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 3.2 Weak induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 3.3 Strong induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 3.E Chapter 3 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140

4 Relations

141

4.1 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

4.2 Equivalence relations and partitions . . . . . . . . . . . . . . . . . . . . . . . . . . 150

4.E Chapter 4 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

II Topics in pure mathematics

163

5 Number theory

165

5.1 Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

5.2 Prime numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

5.3 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

5.E Chapter 5 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

6 Enumerative combinatorics

211

6.1 Finite sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

6.2 Counting principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

6.3 Alternating sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

6.E Chapter 6 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250

7 Real numbers

253

7.1 Inequalities and means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254

7.2 Completeness and convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270

7.3 Series and sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

7.E Chapter 7 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311

iv

Contents

v

8 Infinity

313

8.1 Countable and uncountable sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

8.2 Cardinality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326

8.3 Cardinal arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334

8.E Chapter 8 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344

9 Discrete probability theory

347

9.1 Discrete probability spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348

9.2 Discrete random variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

9.E Chapter 9 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377

10 Additional topics

379

10.1 Orders and lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380

10.2 Inductively defined sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390

10.E Chapter 10 exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406

v

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download