已知素数集可数，如何构造其与自然数集的双射映射？

嘿，这个问题问得特别好！你说得完全没错——素数集确实是可数集，而且构造对应的双射其实比你想象的要直接，咱们一步步来捋清楚：

最直观的构造：按素数的自然顺序映射 #

我们都知道素数可以按从小到大的顺序无限排列：2, 3, 5, 7, 11, 13, 17,... 基于这个排序，我们可以直接定义映射 f: ℕ → 素数集：

• f(1) = 2（第一个素数）
• f(2) = 3（第二个素数）
• f(3) = 5（第三个素数）
• ...
• 一般地，f(n) 等于第n个素数

接下来我们验证这是一个双射：

1. 单射性：如果 f(m) = f(n)，说明第m个素数和第n个素数是同一个数。由于素数的排序是严格递增且唯一的，显然只有m=n时才会成立，满足单射的要求。
2. 满射性：随便取一个素数p，根据素数的无穷性（欧几里得早已证明），p必然在这个排序序列里占据某个位置k，那么 f(k) = p，也就是说每个素数都被映射到了，满足满射的要求。

既是单射又是满射，那这个映射就是标准的双射啦。

更具构造性的递归定义 #

如果你觉得“第n个素数”的描述不够“具象”，我们还可以用递归的方式来定义这个映射：

1. 令 p₁ = 2（第一个素数）
2. 对于任意n > 1，定义 pₙ 为大于 pₙ₋₁ 的最小素数
3. 最终映射仍为 f(n) = pₙ

这个定义的核心是利用了“素数有无穷多个”的性质——每一步都能找到比前一个素数更大的下一个素数，递归不会中断，同样能实现自然数和素数的一一对应。

可能你之前卡壳的点是觉得需要一个“封闭形式的公式”？但其实双射的定义完全不需要公式是简洁的，只要我们能明确地把每个自然数对应到唯一的素数，反过来每个素数也对应唯一的自然数，就完全符合要求啦。可数集的本质就是能被这样“逐个枚举出来”，而素数恰好满足这个条件。

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