function - 如何为 N 的所有有限子集定义编码函数？

Question

为了使用可数集，我必须定义 N（自然数）的所有有限子集的编码函数。我怎样才能做到这一点？我从寻找所有自然数的函数开始：f(n)=1+2+...+(n-1)+n。但是我怎样才能为所有可能的 f 子集表达一个编码函数呢？我怎么能说 f 包含所有有限的自然数呢？我不能说 n=infinity-1 因为 infinity-1 仍然是无穷大。有没有一种正式的方式构成所有有限的自然数？

Answer 1

如果我理解正确，您希望定义一个函数来计算 N 的所有有限子集。实现此目的的一种方法是使用1数字的二进制表示中的 sn来编码 的元素f(n)，即 f(n) = {k \in N | the k-th binary digit of n is 1}。

在编程术语中，例如在 Python 中（这里我使用列表来表示 N 的子集）这看起来像

def f(n):
    result = []
    k = 1
    while n != 0:
        if n % 2 == 1:
            result.append(k)
        k += 1
        n //= 2
    return result