Good Math: A Geek's Guide to the Beauty of Numbers, Logic, and Computation

Cover......Page 1
Table of Contents......Page 7
Where\'d This Book Come From?......Page 11
Acknowledgments......Page 13
Part I—Numbers......Page 15
1. Natural Numbers......Page 17
The Naturals, Axiomatically Speaking......Page 18
Using Peano Induction......Page 21
What\'s an Integer?......Page 23
Constructing the Integers—Naturally......Page 25
The Reals, Informally......Page 29
The Reals, Axiomatically......Page 32
The Reals, Constructively......Page 34
What Are Irrational Numbers?......Page 37
The Argh! Moments of Irrational Numbers......Page 38
What Does It Mean, and Why Does It Matter?......Page 40
Part II—Funny Numbers......Page 43
The History of Zero......Page 45
An Annoyingly Difficult Number......Page 48
The Number That\'s Everywhere......Page 51
History......Page 53
Does e Have a Meaning?......Page 54
7. φ: The Golden Ratio......Page 55
What Is the Golden Ratio?......Page 56
Legendary Nonsense......Page 58
Where It Really Lives......Page 59
The Origin of i......Page 61
What i Does......Page 63
What i Means......Page 64
Part III—Writing Numbers......Page 67
A Positional System......Page 69
Where Did This Mess Come From?......Page 71
Arithmetic Is Easy (But an Abacus Is Easier)......Page 72
Blame Tradition......Page 75
A 4000-Year-Old Math Exam......Page 78
Fibonacci\'s Greedy Algorithm......Page 79
Sometimes Aesthetics Trumps Practicality......Page 81
11. Continued Fractions......Page 82
Continued Fractions......Page 83
Cleaner, Clearer, and Just Plain Fun......Page 85
Doing Arithmetic......Page 87
Part IV—Logic......Page 90
12. Mr. Spock Is Not Logical......Page 92
What Is Logic, Really?......Page 94
FOPL, Logically......Page 95
Show Me Something New!......Page 99
13. Proofs, Truth, and Trees: Oh My!......Page 104
Building a Simple Proof with a Tree......Page 105
A Proof from Nothing......Page 107
All in the Family......Page 109
Branching Proofs......Page 111
14. Programming with Logic......Page 115
Computing Family Relationships......Page 116
Computation with Logic......Page 120
15. Temporal Reasoning......Page 128
Statements That Change with Time......Page 129
What\'s CTL Good For?......Page 134
Part V—Sets......Page 136
16. Cantor\'s Diagonalization: Infinity Isn\'t Just Infinity......Page 138
Sets, Naively......Page 139
Cantor\'s Diagonalization......Page 142
Don\'t Keep It Simple, Stupid......Page 146
17. Axiomatic Set Theory: Keep the Good, Dump the Bad......Page 149
The Axioms of ZFC Set Theory......Page 150
The Insanity of Choice......Page 157
Why?......Page 160
18. Models: Using Sets as the LEGOs of the Math World......Page 162
Building Natural Numbers......Page 163
Models from Models: From Naturals to Integers and Beyond!......Page 165
Introducing the Transfinite Cardinals......Page 170
The Continuum Hypothesis......Page 172
Where in Infinity?......Page 173
Puzzling Symmetry......Page 176
Different Kinds of Symmetry......Page 180
Stepping into History......Page 182
The Roots of Symmetry......Page 185
Part VI—Mechanical Math......Page 189
The Simplest Machine......Page 191
Finite State Machines Get Real......Page 195
Bridging the Gap: From Regular Expressions to Machines......Page 197
22. The Turing Machine......Page 204
Adding a Tape Makes All the Difference......Page 205
Going Meta: The Machine That Imitates Machines......Page 210
23. Pathology and the Heart of Computing......Page 216
Introducing BF: The Great, the Glorious, and the Completely Silly......Page 218
Turing Complete, or Completely Pointless?......Page 221
From the Sublime to the Ridiculous......Page 222
24. Calculus: No, Not That Calculus—λ Calculus......Page 225
Writing λ Calculus: It\'s Almost Programming!......Page 226
Evaluation: Run It!......Page 230
Programming Languages and Lambda Strategies......Page 232
But Is It Turing Complete?......Page 236
Numbers That Compute Themselves......Page 237
Decisions? Back to Church......Page 240
Recursion: Y Oh Y Oh Y?......Page 242
26. Types, Types, Types: Modeling λ Calculus......Page 248
Playing to Type......Page 249
Prove It!......Page 254
What\'s It Good For?......Page 255
27. The Halting Problem......Page 257
A Brilliant Failure......Page 258
To Halt or Not To Halt?......Page 260
Bibliography......Page 265