数学极客：探索数字、逻辑、计算之美

数学是美丽的，它既有趣又令人兴奋，同时也很实用。本书探讨了两千多年的数学发展历程中一些伟大的突破和有趣的话题：从埃及分数到图灵机，从数字 的真正意义到证明树、群对称和机械化计算。如果你想知道高中几何课中难以完成的证明背后到底隐藏着什么，或者什么限制了计算机的能力，本书将会带你找到答案。 作者从数字的基础开始带你开启美丽的数学之旅，首先通过探讨一些有趣的和奇怪的数字，如整数、自然数、有理数、超越数、零、黄金比例、虚数、罗马数字、埃及分数和连分数，带你领略数字的趣味性、数字之美和数字之用，然后深入研究现代逻辑，包括线性逻辑、Prolog语言等，以及现代集合论和现代机械化计算的进展与悖论，带你感受数学的逻辑性和计算性。 

目录

序

译者简介

前言

第一部分　数　　字

第1章　自然数　/2

1.1　自然数的公理化定义　/3

1.2　使用皮亚诺归纳法　/6

第2章　整数　/8

2.1　什么是整数　/8

2.2　自然地构造整数　/10

第3章　实数　/14

3.1　实数的非正式定义　/14

3.2　实数的公理化定义　/17

3.3　实数的构造性定义　/20

第4章　无理数与超越数　/23

4.1　什么是无理数　/23

4.2　聚焦无理数　/24

4.3　无理数和超越数有什么意义，为什么它们很重要　/26

第二部分　有趣的数字第5章　零　/30

5.1　零的历史　/30

5.2　一个令人生厌的困难数字　/33

第6章　e：不自然的自然数　/36

6.1　无处不在的数字　/36

6.2　e的历史　/38

6.3　e有什么含义　/39

第7章　φ：黄金比例　/41

7.1　什么是黄金比例　/42

7.2　荒唐的传奇　/44

7.3　黄金比例真正存在的地方　/46

第8章　i：虚数　/48

8.1　i的起源　/48

8.2　i是做什么的　/50

8.3　i有什么意义　/51

第三部分　书
写 数 字

第9章　罗马数字　/56

9.1　进位系统　/56

9.2　这场混乱来自哪里　/58

9.3　计算很简单（但是算盘更简单）　/59

9.4　传统的过失　/63第10章　埃及分数　/66

10.1　一场4000年前的数学考试　/66

10.2　斐波那契的贪婪算法　/67

10.3　有时美胜过实用　/69第11章　连分数　/70

11.1　连分数简介　/71

11.2　更干净，更清晰，纯粹是为了好玩　/73

11.3　作计算　/75

第四部分　逻　　辑

第12章　斯波克先生与不符合逻辑　/80

12.1　什么是真正的逻辑　/82

12.2　一阶谓词逻辑　/83

12.3　展示一些新东西　/88

第13章　证明、真理和树　/93

13.1　用树来建立简单的证明　/94

13.2　零基础的证明　/96

13.3　家族关系的例子　/98

13.4　分支证明　/100

第14章　使用逻辑编程　/103

14.1　计算家族关系　/104

14.2　使用逻辑计算　/109

第15章　时序推理　/118

15.1　随时间变化的命题　/119

15.2　CTL擅长什么　/124

第五部分　集　　合

第16章　康托尔对角化：无穷不仅是无穷　/128

16.1　朴素的集合　/128

16.2　康托尔对角化　/132

16.3　不要保持简单和直接　/136

第17章　公理化集合论：取其精华，去其糟粕　/139

17.1　ZFC集合论公理　/140

17.2　疯狂的选择　/147

17.3　为什么　/150

第18章　模型：用集合作为搭建数学世界的积木　/151

18.1　构建自然数　/152

18.2　从模型到模型：从自然数到整数，以及超越　/154

第19章　超限数：无限集的计数和排序　/158

19.1　超限基　/158

19.2　连续统假设　/160

19.3　无限何在　/161

第20章　群论：用集合寻找对称性　/164

20.1　费解的对称性　/164

20.2　不同的对称性　/168

20.3　走入历史　/170

20.4　对称性之源　/172

第六部分　机械化数学

第21章　有限状态机：从简单机器开始　/178

21.1　最简单的机器　/178

21.2　实际使用的有限状态机　/182

21.3　跨越鸿沟：从正则表达式到机器　/185

第22章　图灵机　/192

22.1　添加磁带让一切都变得不同　/193

22.2　变元：模仿机器的机器　/198

第23章　计算的核心与病态　/204

23.1　BF：伟大的、光荣的、完全愚蠢的　/206

23.2　图灵完备还是毫无意义　/209

23.3　从庄严到荒谬　/210

第24章　微积分：不是那个微积分，是λ演算　/213

24.1　写λ演算：几乎就是编程　/214

24.2　求值：运行　/218

24.3　编程语言与λ策略　/221

第25章　数字、布尔运算和递归　/224

25.1　λ演算是图灵完备的吗　/224

25.2　计算自身的数字　/225

25.3　决定？回到Church　/228

25.4　递归　/231

第26章　类型，类型，类型：对λ演算建模　/238

26.1　类型简介　/239

26.2　证明　/244

26.3　类型擅长什么　/246

第27章　停机问题　/248

27.1　一个杰出的失败　/249

27.2　是否停机　/251

参考文献　/256

前言这本书来自哪里在成长过程中，我对父亲最早的记忆是数学。我爸爸是一位物理学家，他在RCA公司做半导体制造，所以他的工作涉及很多数学知识。周末他有时会带着一些未完成的工作回家。他会坐在我们家的客厅里，身边散落着一堆纸张和他那把可靠的计算尺。

    作为一个极客小孩，我认为他做的东西看起来很酷，我问他相关的一些事情。当我这样做的时候，他总是停下手上的工作，向我解释。他是个了不起的老师，我从他那里学到了很多数学知识。在我上三年级的时候，他就教给我贝尔（钟形）曲线、标准差和线性回归的基本知识！直到我上大学之前，我在学校的数学课上从来没有学过任何东西，因为在我上课之前，我爸爸已经教给我更多的数学知识。

    他做的不仅仅是向我解释内容。他教我如何教书。他总是告诉我，在你向别人解释某事之前，你自己不会真正明白它。所以他会让我把内容解释给他听，好像他不知道那些似的。

    那些和爸爸在一起的时光奠定了我对数学的热爱之情，并且一直持续了几十年。

    大约在2006年，我开始读科学博客。我觉得这些博客的内容真的很吸引人，真的令人激动。但我不认为我有什么话可以引起别人的兴趣，所以我只是读别人写的，有时候做点评论。

    然后有一天，我读了一个叫“Respectful
Insolence”的博客，作者的笔名是Orac，是一名专业的肿瘤外科医生。他谈到几个怪人完成了一篇论文，他们从数据中得出了荒谬的结论，并将它发表在了公共数据库中。Orac精心地驳斥了他们的论点，解释为什么作者声称的基础医学和生物学是荒谬的。但在阅读原文后，令我印象深刻的是，反驳作者对生物的误解是不必要的，他们解释图形数据的整个论断完全是虚假的。那时候我意识到，存在大量的生物学家、医生、神经病学家、生理学家、物理学家的博客，并且各有特点，但是没有一个博客是关于数学的！

    于是我去Bolgger网站创建了一个博客。我写了我对草率数学的批判，然后把链接发送给Orac。我想可能会有几十人来读它，我可能会在几个星期后放弃它。

    但是，我在我的新博客上发表了第一篇文章之后，我就想起了我的爸爸。他是那种不喜欢花时间取笑别人的人。偶尔做这件事很好，但要把整个爱好都放弃呢？他是不会引以为傲的。

    记得他教我的方法，我开始写我喜欢的那种数学，努力帮助其他人看到为什么它是如此美丽、如此有趣、如此迷人。最终的结果是我的博客——Good Math/Bad Math。我写博客已经快七年了，现在我的文章数以千计！

    当我开始写博客的时候，我想没人会对我说的话感兴趣。我想我可能会被几十人读到，我会在几个星期后放弃。相反，几年后，我获得了成千上万的粉丝，他们阅读了我写的每一篇文章。

    这本书是我接触更多读者的方式。数学是有趣的、美丽的、迷人的。我想与你分享乐趣、美丽和魅力。在这本书中，你会发现我和我爸爸一起度过的时光，他教我热爱数学，教我如何教别人。

    我一直保留着他的计算尺。这是我最珍贵的财产之一。

    读者对象如果你对数学感兴趣，这本书是给你的！我试着把它写出来，以便任何一个有高中数学基础的人都能阅读。具有更多的背景知识，你会发现更具深度的内容，但是即使你只学习了高中代数，也应该能读懂。

    如何读这本书这不是一本需要你逐页阅读的书。每一章几乎都是独立的。你可以选择感兴趣的话题，按任意顺序阅读。在这本书的六部分中，各章将经常引用同一部分的前几章来介绍细节。如果你阅读参考章节，会从这些章节中得到更多知识，但如果你不喜欢，仍然可以读懂。

    你需要做什么对于大部分书中内容，你只需要好奇心。在几章中，有几个程序。如果你想运行它们，程序中有链接和说明。

    致谢感谢每个对这本书有贡献的人，总是很难。我确信我会忘记某人：如果你应该得到感谢，但我把你忘记了，我提前道歉，谢谢你的帮助！

    非常感谢以下人士：

    ■我的“blogfather”和朋友Orac（又名David
Gorski），开始的时候他给了我写博客的动机，并且帮助我引起读者的注意。

    ■我博客的许多读者，他们指出了我的错误，帮助我成为一个更好的作家。

    ■我在Scientopia的朋友们。

    ■献出时间和精力对这本书的草稿进行技术审校的人：Paul Keyser、Jason Liszka、Jorge Ortiz和Jon Shea。

    ■我在Foursquare的同事，他们给我支持和反馈，让工作成为一个有趣的地方。

    ■The
Pragmatic Bookshelf的员工，尤其是David Thomas和David Kelly，他们超越职责地排版这本数学书。

    ■当然，还有我的家人，他们忍受着疯狂的极客作者。

Mark C. Chu-Carroll是世界上较早的数学博主之一，他能够引导读者愉快地、不经意地理解复杂的概念。在本书中，他使用相同的技巧为读者带来一场别开生面的数学之旅，从数字的基本概念一直到计算机程序设计的*发展。如果你曾经对黄金比例、图灵机或者为什么圆周率永远算不完感到好奇，这本书就是为你准备的。

 ——Carl Zimmer，《The New
York Times》的专栏“Matter”（http://bit.ly/NYTZimmer）和《National Geographic
Magazine》的博客“The Loom”（http://phenomena.nationalgeographic.com/blog/the-loom）的作者

Mark C. Chu-Carroll的生动、丰富的博客“Good
Math/Bad Math”的粉丝，细细品味这本数学指南所带来的饕餮盛宴吧！Chu-Carroll涵盖了一切，包括自然数、无理数、虚数、黄金比例、康托尔集、群论、逻辑、证明、编程和图灵机。全书充满了他热爱的主题，相信你也会喜欢。

——Jennifer Ouellette，《The Calculus Diaries》的作者

本书的作者Mark C. Chu-Carroll从解读数字的角度为我们打开了重新认识和了解数学的大门。作者在自己的博客上长期向社会大众开展有关数学基本概念的解读，以幽默的方式和独特的理解表达了自己对数学和数字的热爱之情，并在世界范围内极大地推广了学习数学之道。……本书具有非常好的可读性和趣味性，同时也能够为很多没有坚实数学基础的人提供学习和参考的帮助。

——吕述望，中科院信息安全国家重点实验室教授