同构 编程中的数学

本书从七个方面介绍了计算机程序的数学基础和原理，并以“同构”概念为线索揭示出编程本质上是和数学同构的。这七个方面分别是：数字、递归、对称、范畴、融合、无穷、悖论。第1章“数字”介绍皮亚诺算术公理系统。通过5条公理，构筑了计算机程序大厦的基石。通过单向链表，斐波那契数列等例子，展示了和自然数同构的计算结构。第2章介绍递归。通过欧几里得算法作为开端，把递归的数学原理构建在Lambda演算和Y组合子之上。第3章通过对称介绍群、环、域等抽象代数结构，并解释伽罗瓦理论这一抽象思维的明珠。第4章介绍范畴论。把列表、异常、多态、类型系统、复合数据结构等众多编程概念构筑在范畴论的基础上。第5章介绍融合律。它是进行算法推导和优化的有力工具。第6章介绍无穷。给出了康托尔的无穷集合论和超限数概念，介绍了编程中流的概念和无穷的关系。第7章以罗素悖论、可计算性和哥德尔不接近性定理结束本书。介绍了计算能力的边界和对编程基础哲学的影响。

刘新宇 亚马逊中国研发中心研发经理，负责分布式仓储物流系统的开发。1999年和2002年在清华大学自动化系分别获得学士和硕士学位。长期专注于函数式基础算法，著有《算法新解》一书（2017年出版）。

推荐序
前言
第1章数字1
1.1数的诞生1
1.2皮亚诺自然数公理2
1.3自然数和计算机程序4
1.4自然数的结构6
1.5自然数的同构10
1.6形式与结构14
第2章递归16
2.1万物皆数16
2.2欧几里得算法18
2.2.1欧几里得和《几何原本》19
2.2.2欧几里得算法概述19
2.2.3扩展欧几里得算法22
2.2.4欧几里得算法的意义26
2.3λ演算28
2.3.1表达式化简30
2.3.2λ抽象31
2.3.3λ变换规则31
2.4递归的定义35
2.5λ演算的意义36
2.6更多的递归结构38
2.7递归的形式与结构39
2.8附录：倒水趣题完整程序42
第3章对称43
3.1什么是对称43
3.2群46
3.2.1群的定义50
3.2.2幺半群与半群52
3.2.3群的性质55
3.2.4置换群58
3.2.5群与对称61
3.2.6旋转对称与循环群62
3.2.7分圆方程65
3.2.8子群66
3.2.9拉格朗日定理72
3.3环与域82
3.3.1环的定义84
3.3.2除环和域86
3.4伽罗瓦理论87
3.4.1扩域87
3.4.2从牛顿、拉格朗日到伽罗瓦89
3.4.3自同构和伽罗瓦群95
3.4.4伽罗瓦基本定理96
3.4.5可解性98
3.5附录：伽罗瓦群100
第4章范畴102
4.1范畴概述104
4.1.1范畴的例子106
4.1.2箭头≠函数110
4.2函子111
4.2.1函子的定义111
4.2.2函子的例子112
4.3积与和118
4.3.1积与和的定义120
4.3.2积与和的性质122
4.3.3积与和作为函子123
4.4自然变换126
4.4.1自然变换的例子127
4.4.2自然同构130
4.5数据类型131
4.5.1起始对象和终止对象131
4.5.2幂136
4.5.3笛卡儿闭和对象算术140
4.5.4多项式函子142
4.5.5F-代数143
4.6小结156
4.7扩展阅读158
4.8附录：例子代码158
第5章融合160
5.1叠加-构建的融合161
5.1.1列表的叠加操作162
5.1.2叠加-构建融合律163
5.1.3列表的构建形式164
5.1.4使用融合律化简165
5.1.5类型167
5.1.6用范畴论推导融合律168
5.2巧算100171
5.2.1穷举法171
5.2.2改进173
5.3小结和扩展阅读175
5.4附录：巧算100问题的代码175
第6章无穷177
6.1无穷概念的提出179
6.1.1无穷的哲学181
6.1.2穷竭法与微积分183
6.2潜无穷与编程186
6.3实无穷的思考191
6.3.1无穷王国的花园192
6.3.2一一对应与无穷集合194
6.3.3可数无穷与不可数无穷200
6.3.4戴德金分割203
6.3.5超限数和连续统假设205
6.4无穷与艺术209
6.5附录：例子代码214
6.6附录：康托尔定理的证明215
6.7附录：巴赫《音乐的奉献》无限上升的卡农216
第7章悖论218
7.1计算的边界221
7.2罗素悖论222
7.3数学基础的分歧225
7.3.1逻辑主义225
7.3.2直觉主义227
7.3.3形式主义229
7.3.4公理集合论230
7.4哥德尔不接近性定理232
7.5不接近性定理的证明234
7.5.1构建形式系统234
7.5.2哥德尔配数237
7.5.3构造自我指涉238
7.6万能的程序与对角线证明239
7.7尾声240
附录241
加法交换律的证明241
积与和的专享性242
集合的笛卡儿积和不相交并集构成积与和的证明243
参考答案246
参考文献296