我们将要介绍一个涉及到集的大小的基本概念：可枚举（可数）集。

我们想当然的会认为一个只有几个元素的集合很小，有着一百个元素的集则挺大，规模为十亿的集就更加是伟哉大矣，而我们能想象大到极限的集合，可能就是一个拥有着无量元素的集。

然而从我们将要定义的理论来判断的话，一个像{1, 2, 3, ….} 这样的正整数无限集，实际上是相对而言算小的，数学上存在着无数多比它还大的集合！更确切地说，所有的有限集，以及有些无限集，是可数的(Countable)。不可数集比可数集要大，我们还是首先定义一下什么是可数集：

一个集合S是可枚举的（即可数的），当且仅当存在一个从正整数到S的满射函数F

这样的一个满射方程F，我们称之为对S的枚举（Enumeration）

【注：即此函数式说明了存在一种S与正整数集的对应关系】

直觉性地去理解这个定义还可以这么来思考：想象正整数集是一本厚度无限的书（所以它有第一页但没有最后一页）。如果一个集能被“塞进”这本书的话，这是一个可数集。也就是说该集的所有元素都能出现在书的某一页上，且保证每一页只对应一个元素。那么显然的，有些无限集因此是可数的：比如Z⁺正整数集它本身。枚举函数可以是F(x)= x，第一页上写1，第二页上写2 ……

值得注意的是，枚举函数F是满射的，但不一定要是单射或全函数(totalfunction)：允许书本上出现空白页，也允许两页纸上写着同样的东西，这两种情况都不妨碍S是可枚举的，只要S不是“大”到容不进书里就足够了。

【注：即当我们一页页地翻开这本书的时候，我们最终可以遍历完该集，但不限制该集是用哪种规律、顺序呈现在书上的。首要保证的是“遍历”，所以以下的枚举是错误的：

从偶数部分开始，数字2出现在∞+1页，4出现在∞+2页……，而不是对于某个可准确赋值的数n，元素出现在n^th页上】

2.2 有木有另一种定义方式？

你可能会想，为什么不定义说当存在一个全函数F: S→Z⁺的时候，称S为可数的呢？原因是这样一来，就无法满足“枚举”这个概念的直观意义了。举个栗子：

左边的对应关系显然不是一个恰当的列举，因为Boolos和Burgess

而且这么做的话，会导致所有集都是可数集了，方法就是我们可以让任意集的所有元素，都和“1”对应……

【注：后面还有一小段篇幅都是在论证为什么从S到Z⁺的函数应该是满射的，而不需再说它是单射全函数之类的……其实从前面的书本比喻，就足够说明问题了，因此偷懒一下不再详述-w-

先过一遍课本上7~14页的内容，以下是对于其中一些例子的补充说明

……当然还有很多的其他方法，比如f(1)不取零，或一次性列三个数再摆回负数部分等等。

有序正整数对集：从这开始我们就可以初尝下神奇的康托尔对角线方法了！列举方式如左图

【注：对角线方法能够保证我们总是能够遍历完这个矩阵上的每一个数字。因为这个方法不是等遍历完某一行/列后再开启下二行/列，巧妙的保证了算法的覆盖范围是全矩阵的，而且不会“卡死”在某一步而走不下去】

需建立在有序正整数对集(ex1.2)的枚举基础上，我们把每一个正整数对(m,n)替换为一个有理数m/n，虽然这会导致有一大堆的冗余（比如2/2,3/3都是1），但不违背枚举函数的初衷J

【注：该例子也顺带证明了如果集合T是可数的，S是T的子集，那么S也是可数的。因为存在这么一种办法，可以把T的所有元素排到列表上，再把列表上所有和S等价的替换为S的元素】

我们从有序正整数二元组的基础上出发，回顾一下对角线法给出的结果

如果把第二位上的数N，替换为L中的第N个元素，这将给出一个新的三元组<x,<y, z>>，如果对L中的每一个数做这样的替换，实际上就得出了所有正整数三元组的枚举。

但是我们还要再想一下为什么这个方法不会遗漏任何可能性。首先原来的对角线方法保证给出了所有的<1,x>、<2,x>、<3, x> ……那么以首位数为1的数列为例(<1,x>)，作了替换后，可以保证x会替换成所有的二元数组，也就是说保证列出了所有首位数为1的三元数组<1,y, z>。以此类推，可以列出所有首位为2的三元数组，首位为3的三元数组…

【注：用相似的证明方式，可以说明所有的有序N元数组都是可数的】

“长度为N的有限序列”等价于“有序N元组”。正整数有限序列集S是一个无限集，但它的每一个元素都是有限长度的，即一个有序N元组。证明S是可数的有两种方法：

设想一个长宽无限的表格，所有一元组列在第一行，二元组列第二行……然后就在这张巨大的表格上从最左上角开始玩那扭曲的Z字爬行。

=（m_1,….., m_n），为其定义一个编码x↓

那么我们就可以定义一个函数是 F: X→S. 比如说，和序列(2, 4) 匹配的编码就是

【注：由此可见，质数编码法给出的匹配x大多数是极大的数，但目前的理论阶段我们不考虑其效用问题，只要这个方法可行、结果是有限的就可以了】

x_i≠x_j)。前者是明显的，x的定义方式本身已经说明了这一点，每个序列都有一个匹配数x。所以我们主要看下后者，因为的确有如下的例子：

ofArithmetic)，我们永远不能从同一个x中，反编码出两个不同的序列J。基本定理说：每个大于1的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。比如10只能表达为2×5而不是5×2，因为违背了质因子从小到大排列的规则。32只能表达为2×2×2×2×2=2⁵。那么我们回到刚才给出的例子，324的唯一质因子表达式是2²×3⁴，即反编码为序列(2,4)。

p_i≠0，就不可以跳去尝试p_i+1，2³×3²×5¹违反了这一规定】

将F的定义域扩大到正整数集Z⁺的话，F就成为了我们的枚举函数，但注意因为XZ⁺，F不是全函数。虽然所有正整数都可以表达为唯一的质因子积，但不是所有的正整数都是某个数列的编码，比如10=2¹×3⁰×5¹，匹配序列(1,0, 1)并不是本例的正整数有限序列集的元素。所以“书本”的第十页是空白的，上面没有写着任何序列L。

既然我们已经在1.9中得到了正整数有限序列集的枚举方法，那么简单粗暴的把<x₁,x_{2 ….,} x_n> 1>是不同的序列，但都对应同一个集合{1,2}……

目前为止我们还只是在讨论一个集合是否是可枚举的（可数的），这是一个关乎集的大小的问题，即这个集合是否比自然数集有更多的元素。要满足一个集是可数的，我们只需要找到一个（当然，只存在于抽象概念上的）列出了所有元素的列表，但不需要给出生成这个列表的公式(recipeor formula for constructing the list)。当然了，给出一个有效的公式固然可以证明存在这么一个列表【注：如1.2中的算法】，但这不是证明的必要条件。

set)，这些集合的元素列表可以通过遵循某个算法(algorithm)来生成。那么是什么来区别可枚举和有效可枚举呢？这就是关乎集的复杂性(complexity)问题了，而不是集的大小(size)。

我们之前用到了这样一个逻辑：正有理数可以与正整数有序二元组，形成一一对应关系( m/n:= <m, n> ) 【注：即两者间存在一个双射函数bijection function】。我们又知道如何枚举所有正整数二元组，所以自然地正有理数也是可枚举的。再详细一些的话【注：感觉这里的描述累赘了。。。不知道为什么加入这一段】，为了说明有序二元组集S是可数的，我们需要展示存在一个从Z⁺到S的满射函数，再展示了正有理数V可与有序二元组配对后。这就证明了存在一个枚举复合函g·f: Z⁺→V，定义g: S→V 是双射函数

集合A与B是等势的当且仅当存在从A到B的双射函数

（这个也是“两个集同样大小”的精确定义）

2、可交换：如果A与B等势，则B与A等势；

3、可传递：如果A与B等势，B与C等势

【注：原NOTES中是为每一个例子开一个新section，方便起见将其整合到一起了，这些集的中文名字想不出如何翻译更好，看英文名直观很多】

我们已经见证了很多可数集，虽然它们当中的相当一部分当你首次接触到时，直觉上会认为它们肯定不可数。那么我们接下来便要看看真正的不可数集长什么样子。

正整数所有集合的集是不可数的 （康托尔定理）

首先要回忆的一个结论是：正整数有限集合的集是可数的 （也就是这个集中的每个元素，都是一个正整数有限集，结论在1.10中推出）。但当它的规模扩充到可以包含无限集的时候，就成为了不可数集，这也是我们马上要来证明的：

我们的证明方法是归谬法(Reductio ad absurdum)， 也就是首先假设正整数所有集合的集S存在一种枚举方式，然后由此得出一个矛盾结论 --- 于是证明了假设前提（存在S的枚举）是错误、不可能的。

【注：为了避免自己翻的中文名时不时恶心到自己，一律用S代表它吧 (╯﹏╰)】

假设列表L是S的枚举：

每一个S_i代表某个正整数集，L能够枚举所有的正整数集（包括有限和无限的），一切都还很美好。但这时定义一个新的正整数集△(L)：

【注：也就是说，△(L)参考L里的每一个集，然后根据该集的内容来尝试为自己添加一个元素。当集S_n正好没有元素n时，△(L)就为自己添加这个对方没有的数"n"

△(L)已经定义完毕，我们再回忆一下L是什么，L是一个包罗了正整数所有组合可能性的集，过去现在未来的所有元素是正整数的集，都是L的子集。那么自然的，△(L)也必然在L中有一席之地，所以我们假设存在一个m，使得S_m

于是瞬间L 就不好了(⊙o⊙) ：根据定义，仅当m不是S_m的元素时，m才能收录到△(L)，而现在S_m正好就是△(L)，结论就是“仅当m不是△(L)的元素时，m才是△(L)的元素”。简直天大的笑话……既然不可能的结论出现了，那么最初的假设肯定是错误的，也就是S不存在一个枚举L，S是不可数的！

正整数所有序列的集合是不可数的

现在我们考虑一个新的例子。首先还是确认一遍，正整数有限序列是可数的（结论在1.9中推出），但一旦它涉足到“无限”的大坑，或许下场就和上面的那位一样了。虽然这个结论其实很好得出，如果正整数所有序列的集合是可数的，那么我们马上就可以得出正整数所有集合的集也是可数的了（参考1.10的方法，<…>转换成{…}），但这已经证实是不可能的。但是为了介绍神奇的康托尔对角线方法(Techniqueof Diagonalization），我们可以先不管前面的经验，而去尝试直接证明；

同样是归谬法，假设L是正整数所有序列的集合S的枚举，则L_n是L中的n^th序列。这时定义一个新的序列△(L)：

【注：如果我们考虑大大地拓展上面三个序列，并且通过为让有限序列添加特殊占位符B而让每一行都是无限长度，我们就得到了一个规模庞大的矩阵。比如沿用上面的例子的话前三列就是：

←那么△(L)就是矩阵对角线上的每个数加

△(L)可以说是从L自己身上衍生而来的一 个“怪胎”】

于是矛盾冉冉而生。既然L包罗了所有的正整数序列可能性，那么△(L)自然也不过是L的一个元素，假设L_m= △(L)。根据定义，△(L)的m^th与L_m的m^th不同，但L_m此时不是别的，正是△(L)自己！于是造成了△(L) ≠△(L)。同样的，正确的前提不可能导出错误的结论，我们的假设是错误的，S是不可数的L

其实不必考虑浩瀚的实数范围，只考虑(0, 1)这个区间其实就足够了。比如0.10,  0.….,  0.….如果我们拿去前头的“0.”，那么小数部分可以看作是一个正整数序列。我们知道大于0小于1的数字可以是无穷精确的，因此数量无穷，最终我们得出的其实是一个包含一切可能性的正整数序列（是上面那位的亲兄弟），而正整数所有序列的集合已经证实为不可数。既然0到1之间的实数都“数不过来”，整个实数集也不可能是可数的L

并且每个指令都满足以下三个特征：

举个栗子，回忆一下我们小学时是如何做加法运算的。

③；如果该数位上加法结果小于10，那么直接写下结果在横线上。如果结果大于10，则把十位数上的数字进位。回到步骤②，但这次从下一位数开始计算，直到上下再也没有任何数字可以相加

以上就是这里所讲的“有效过程”，我们也为此写了一段运行此过程的指令（或曰步骤，当然这段指令还可以更严谨、精确），而且每一步指令都满足以上的三点要求：mechanical、deterministic、finitely

这里需要注意两点。第一：因为每一步都是确定性的，以及每一步的步骤也被阐明在了过程中，不同的人只要正确遵循步骤都肯定能得出同样结果。第二：在一个有效过程中可能包含循环（比如加法中的②③），所以虽然单个的指令是有限时间内可达成的，但作为整体的过程，可能是一个永远无法停机的死循环……比如以下的这个有效过程：

一个函数F:A→B是可计算的（或曰有效可计算 effectively computable），当且仅当存在这么一个有效过程：输入a∈A，输出f(a)∈B。

（我们允许一个偏函数partial function是可计算的。即当输入a∈A的时候，F无法提供任何与a的匹配，也就是说，F对于a这样的输入是未定义的。在这种情况下，要么F进入死循环，要么立刻停机而且不作任何输出）

然而目前为止，所谓的“有效过程”是一个直觉观念，我们给出的都还只是非正式定义，在数学意义上非常不精确。【注：而且看起来也不可能严格地被数学证明，正因如此，我们后面要接触到的丘奇-图灵论题还不能被称为定理，只能是假说】我们之后还会接触一些在数学意义上更严谨的、能够等价定义“可计算函数”的概念（图灵可计算函数、递归函数）。