可数集合是指与自然数集合具有相同基数（大小）的集合，通常记为 N（在集合论中常表示为 0, 1, 2, 3,…）。
> 如果一个集合的元素能与自然数建立一一对应的映射，那么它就是可数的。
在计算理论和数学中，当且仅当给定集合 S 满足以下两个条件之一时，我们称其为可数集：
> S 是有限的。
> 或者
> 集合 S 的元素与所有自然数集合 N 之间存在双射（即一一对应关系）。换句话说，集合 S 的基数与 N 的基数相同。
判定集合可数性的方法
为了证明给定集合是否可数，我们有两种方法，例如：
- 使用形式化定义
- 使用替代定义
使用形式化定义
这是证明给定集合是否可数的最正规的方法。请遵循以下步骤：
> – 如果给定集合是有限的，这意味着根据定义它已经是可数的。
> – 如果给定集合是无限的，则尝试在给定集合与所有自然数集合 N 之间建立一个一一对应的函数。
示例
> 例如，让我们取有限长度的二进制字符串集合。有限长度的二进制字符串集合简单地表示为字母表 Σ = {0, 1} 上的所有有限长度字符串，换句话说就是 Σ。在本文中，我们将证明 Σ 是可数的。
>
> 给定的集合是无限的。因此根据定义，我们必须在 Σ 和 N 之间建立一个一一对应的函数。让我们在 Σ 和 N 之间定义一个函数。
>
> w 是一个有限长度的二进制字符串，满足 w ∈ Σ*
> w 的长度 = n
>
> f(w) = 1 n=0
> f(w) = 2ⁿ + decimal_representation(w)
>
> f(w) 是一个从 Σ* → N 的一对一函数，因为：
>
> – 对于每一对不同的 w1, w2 ∈ Σ*，我们都有不同的 f(w) 值。这意味着 f(w) 是单射。
> – 对于每一个自然数 x ∈ N，我们都有某个 w ∈ Σ* 使得 f(w) = x。这意味着 f(w) 是满射。
>
> 让我们参考下面的图示表示：
> f(w) : Σ* → N
使用替代定义
现在，正如你从第一个证明中看到的那样，想出一个从给定集合 S 到 N 的一一对应函数并不总是容易的。所以现在我们要使用一种非正式且更简单的替代定义来证明给定集合是否可数。
替代定义： 当且仅当对于所有 n ∈ N，我们可以分配 S 的一个空或非空的有限子集，使得在整个映射过程中 S 的每个元素至少被覆盖一次时，给定集合 S 是可数的。
示例：
> 让我们拿前面用过的有限长度二进制字符串集合的例子来看看，这次我们的工作变得多么简单。
>
> 我们所要做的就是为每个 n ∈ N 分配一个 Σ 的有限子集，使得 Σ 的所有元素都至少被覆盖一次。
>
> 对于每个 n ∈ N，我们将分配由长度为 n 的字符串组成的 Σ* 的子集。长度为 n 的字符串正好有 2ⁿ 个。这是有限的。
>
> – 1 → {λ, 0, 1} 空字符串和所有长度为 1 的字符串。我们把空字符串放在 1 中，因为它之前被遗漏了。
> – 2 → {00, 01, 10, 11} 所有长度为 2 的字符串
> – 3 → {000, 001, 010, 011, 100, 101, 110, 111} 所有长度为 3 的字符串
> – n → 所有长度为 n 的字符串
>
> 通过这种方式，我们将能够至少覆盖一次 Σ 的所有元素。因此 Σ 是可数的。
推荐问题
> – GATE CS 1997 | Question 19