《同构 - 编程中的数学》

【实例截图】

【核心代码】

目录
第一章 数字 1
1.1 数的诞生 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 皮亚诺自然数公理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 自然数和计算机程序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 自然数的结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 自然数的同构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.6 形式与结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
第二章 递归 17
2.1 万物皆数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 欧几里得算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1 欧几里得和《几何原本》 . . . . . . . . . . . . . . . . . . . . . 20
2.2.2 欧几里得算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.3 扩展欧几里得算法 . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.4 欧几里得算法的意义 . . . . . . . . . . . . . . . . . . . . . . . . 29
2.3 λ 演算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.3.1 表达式化简 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.3.2 λ 抽象 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3.3 λ 变换规则 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.4 递归的定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.4.1 Y 组合子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.5 λ 演算的意义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.6 更多的递归结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.7 递归的形式与结构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.8 扩展阅读 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.9 附录：倒水趣题完整程序 . . . . . . . . . . . . . . . . . . . . . . . . . 46
第三章 对称 47
3.1 群 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
v
vi 目录
3.1.1 群的定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.1.2 幺半群与半群 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.1.3 群的性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.1.4 置换群 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.1.5 群与对称 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.1.6 循环群 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.1.7 子群 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.1.8 拉格朗日定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.2 环与域 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.2.1 环的定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.2.2 除环和域 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.3 伽罗瓦理论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.3.1 扩域 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.3.2 自同构和伽罗瓦群 . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.3.3 伽罗瓦基本定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.3.4 可解性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
3.4 扩展阅读 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
第四章 范畴 105
4.1 范畴 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.1.1 范畴的例子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.1.2 箭头 ?= 函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
4.2 函子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.2.1 函子的定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.2.2 函子的例子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.3 积和余积 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
4.3.1 积和余积的定义 . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
4.3.2 积和余积的性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
4.3.3 积和余积作为函子 . . . . . . . . . . . . . . . . . . . . . . . . . 129
4.4 自然变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.4.1 自然变换的例子 . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.4.2 自然同构 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
4.5 数据类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
4.5.1 起始对象和终止对象 . . . . . . . . . . . . . . . . . . . . . . . . 137
4.5.2 幂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
4.5.3 笛卡尔闭和对象算术 . . . . . . . . . . . . . . . . . . . . . . . . 146
0 次幂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
1 的幂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
目录 vii
1 次幂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
幂的和 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
幂的幂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
积的幂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.5.4 多项式函子 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.5.5 F-代数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
递归和不动点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
初始代数和向下态射 . . . . . . . . . . . . . . . . . . . . . . . . 156
代数数据类型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.6 小节 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
4.7 扩展阅读 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
4.8 附录：例子代码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
第五章 融合 169
5.1 叠加——构建的融合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
5.1.1 列表的叠加操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
5.1.2 叠加——构建融合律 . . . . . . . . . . . . . . . . . . . . . . . . 172
5.1.3 列表的构建形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
5.1.4 使用融合律化简 . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
5.1.5 类型限制 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
5.1.6 用范畴论推导融合律 . . . . . . . . . . . . . . . . . . . . . . . . 178
5.2 巧算 100 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
5.2.1 穷举法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
5.2.2 改进 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
5.3 小结和扩展阅读 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
5.4 附录代码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
第六章 无穷 187
6.1 无穷概念的提出 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
6.1.1 无穷的哲学 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
6.1.2 穷竭法与微积分 . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
6.2 潜无穷与编程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
6.2.1 余代数和无穷流 ⋆ . . . . . . . . . . . . . . . . . . . . . . . . . 199
6.3 实无穷的思考 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
6.3.1 无穷王国的花园 . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
6.3.2 一一对应与无穷集合 . . . . . . . . . . . . . . . . . . . . . . . . 206
康托尔与戴德金 . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
利用（可数）无穷定义斐波那契数列和哈明数列 . . . . . . . . . 211
6.3.3 可数无穷与不可数无穷 . . . . . . . . . . . . . . . . . . . . . . . 213
viii 目录
6.3.4 戴德金分割 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
6.3.5 超限数和连续统假设 . . . . . . . . . . . . . . . . . . . . . . . . 217
超限数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
连续统假设 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
6.4 无穷与艺术 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
6.5 附录：例子代码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
6.6 附录：康托尔定理的证明 . . . . . . . . . . . . . . . . . . . . . . . . . 227
6.7 附录：巴赫《音乐的奉献》无限上升的卡农 . . . . . . . . . . . . . . . 228
第七章 悖论 231
7.1 计算的边界 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
7.2 罗素悖论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
7.2.1 罗素悖论的影响 . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
7.3 数学基础的分歧 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
7.3.1 逻辑主义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
7.3.2 直觉主义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
7.3.3 形式主义 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
7.3.4 公理集合论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
7.4 哥德尔不完全性定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
7.5 不完全性定理的证明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
7.5.1 构建形式系统 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
公理和推理规则 . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
印符系统的不完全性 . . . . . . . . . . . . . . . . . . . . . . . . 250
7.5.2 哥德尔配数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
7.5.3 构造自我指涉 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
7.6 万能的程序与对角线证明 . . . . . . . . . . . . . . . . . . . . . . . . . 253
7.7 尾声 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
Appendices
参考答案 259
.1 前言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
.2 数字 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
.3 递归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
.4 对称 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
.5 范畴 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
.6 融合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
.7 无穷 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
.8 悖论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
目录 ix
加法交换律的证明 311
积和余积的唯一性 313
集合的笛卡尔积和不相交并集构成积和余积的证明 315
参考文献 317
GNU Free Documentation License 327
1. APPLICABILITY AND DEFINITIONS . . . . . . . . . . . . . . . . . . 327
2. VERBATIM COPYING . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
3. COPYING IN QUANTITY . . . . . . . . . . . . . . . . . . . . . . . . . 329
4. MODIFICATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
5. COMBINING DOCUMENTS . . . . . . . . . . . . . . . . . . . . . . . . 332
6. COLLECTIONS OF DOCUMENTS . . . . . . . . . . . . . . . . . . . . 333
7. AGGREGATION WITH INDEPENDENT WORKS . . . . . . . . . . . 333
8. TRANSLATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
9. TERMINATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
10. FUTURE REVISIONS OF THIS LICENSE . . . . . . . . . . . . . . . 334
11. RELICENSING . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
ADDENDUM: How to use this License for your documents . . . . . . . . . 335