包含所有整数序列子序列的集合S是否不可数？请求证

别担心卡在定义函数这一步，其实可数集的核心就是能把所有元素按顺序一一列出来，咱们顺着这个思路往下走：

首先，假设S是可数的，根据可数集的定义，必然存在一个从自然数集ℕ到S的双射函数f——说白了就是，我们可以把S里的所有整数序列排成一个无限列表：

• f(0) = (a₀₀, a₀₁, a₀₂, ...) （第0个序列）
• f(1) = (a₁₀, a₁₁, a₁₂, ...) （第1个序列）
• f(2) = (a₂₀, a₂₁, a₂₂, ...) （第2个序列）
• ...
  这里的a_{nk}表示第n个序列的第k个元素，每个f(n)都是S里的成员。

接下来咱们用对角线法构造一个“特殊”的整数序列b = (b₀, b₁, b₂, ...)，构造规则很简单：对每个自然数k，让b_k ≠ a_{kk}就行——比如如果a_{kk}是0，b_k就取1；如果a_{kk}不是0，b_k就取0，保证每个位置的元素都和列表里对应对角线位置的元素不一样。

现在看题目的关键前提：任意整数序列都存在一个子序列属于S，那这个新造的序列b肯定也得有个子序列在S里。假设这个子序列对应列表里的f(m)，也就是f(m)是b的某个下标子序列（比如取b的第k₀, k₁, k₂...个元素组成的序列，k₀<k₁<k₂...）。

这时候矛盾就出现了：

• 先看f(m)的第m个元素，它是a_{mm}，但根据我们构造b的规则，b_m ≠ a_{mm}。
• 如果m是子序列下标k₀, k₁...中的某一个（比如m=k_t），那f(m)的第t个元素应该是b_{k_t}=b_m，但f(m)的第m个元素却是a_{mm}≠b_m，这就和“f(m)是b的子序列”矛盾了。
• 如果m不在这个子序列下标里，那f(m)的所有元素都来自b的其他位置，但f(m)本身是一个无限序列，它的第m个位置是a_{mm}，而b里只有b_m这个位置的元素不等于a_{mm}，这也和“f(m)是b的子序列”冲突——因为子序列的元素必须完全匹配b对应位置的元素啊。

这个矛盾说明咱们最开始的假设“S可数”是错的，所以S一定是不可数的。

内容的提问来源于stack exchange，提问作者user534199