一个关于康托对角线的构造

---

首先描述一个集合

• 注：以下串都是比特串
• 首先，有个origin串，为全0的无穷串
• 规定，该集合内的元素除了origin串外，其他元素都是对origin串修改某一个bit得到的。
• 比如，$100000...000$ ，其为origin 串修改第一个bit得到的，又比如$01000000...0000$ ，其为origin串修改第二个bit得到的

使用康托对角线证明其不可数

• 将除了origin 串外的其他串从上往下排列——修改第一bit的串排在第一行，修改第二bit的串排在第二行，以此类推。最后，origin 串排在最后一行
• 然后，使用康托对角线法——显然，上面的构造方法使得串中那些相对于origin串被修改的位 就是对角线法将修改的位，从而使得，对角线法每一步总是复位一个串中相对于origin串修改的那 一位，从而该对角线法最后得到的串就是origin 串，所以，康托对角线证明了这是一个不可数集合

为什么对角线法不会修改到处于矩阵最末尾的origin串

• 因为，对角线法修改的任意一个坐标$(i,j)$，都有$i=j$，而假设该集合有N个非origin串和一个origin串，则最后一行的坐标都是$(N+1,i), i\leq N$，所以，最后一行没有任意一个元素会被修改到

使用一一对应证明其可数

• 使用N编码该集合内的元素——修改第一bit的串编码为2，修改第二bit的串编码为3，以此类推，origin 串编码为1

问题

• 两种方法得到不同结果，这其中哪里出问题了

我必须承认，我没怎么看懂问题。。。

@bintou emm，重新修改了问题

这里, 对角线法的证明貌似没有推理出矛盾吧?!

对角线法来证明不可数, 先假设了存在那么一个一一对应的函数, 使到自然数集可以映射到这个language. 但是呢, 用对角线法构造出来了一个串$\in$这个language, 它没有对应的定义域, 从而推理出了矛盾.

emmm, 这里是不是缺少点什么呀??感觉证明不可数的过程有问题.

一一对应证明可数, 可以将这个语言覆盖.应该是可数的.