集合的归纳定义法

2024/09/20

常见的集合表示方法有枚举法和抽象法（也即描述法，描述出集合元素具有的特征）。但抽象法有一定的局限性，比如无法表示C语言程序集合。这引出了集合的归纳定义法。

归纳定义法

1 基本项

规定 \(A\) 的一些生成元: \(S_0 \subseteq A\)

2 归纳项

一组规则，从 \(A\) 中元素出发，依据这些规则所获得的元素仍然是 \(A\) 中的元素

3 极小化

(a) \(A\) 中的每个元素都是通过有限次使用 (1) 或 (2) 获得的

(b) 如果集合 \(S \subseteq A\) 也满足 (1) 和 (2)，则 \(S = A\)

Note

基本项和归纳项指明了哪些元素在集合内，但并没有排除不在集合内的元素。极小化保证 \(A\) 是同时满足 (1) 和 (2) 的最小集合

一个例子

用归纳定义法给出下列集合: 不允许有前 \(0\) 的十进制无符号整数的集合

(1) 令 \(S_0 = \{0,1,2,3,4,5,6,7,8,9\} \subseteq A\)

(2) 若 \(a \in S_0 - \{ 0\}\) 且 \(\alpha \in A\) ，则 \(a\alpha \in A\) ( \(a\alpha\) 表示拼接字符串)

(3) 极小化

解法合理与否？发现这样归纳会漏掉像 \(100005\) 这样中间段有 \(0\)​ 的数字

我们应该将归纳项改为:

(2) 若 \(\alpha, \beta \in A\) 且 \(\alpha \neq 0\) ，则 \(\alpha\beta \in A\)

即不断往前段添加已在 \(A\) 内的数，而不是仅仅添加一位

联立归纳定义法

再看一个神奇的例子

定义集合: 不允许有前 \(0\) 的被 \(3\) 整除的二进制无符号整数的集合

我们先考虑几个集合: 除 \(3\) 余 \(0\) 的集合 \(B_0\) ，除 \(3\) 余 \(1\) 的集合 \(B_1\) ，除 \(3\) 余 \(2\) 的集合 \(B_2\)

设二进制数 \(X\) 对应的十进制数为 \(x\) ，除 \(3\) 后商为 \(k\) ，余数为 \(b\) ，则 \(x=3k + b\) ，往 \(X\) 的末尾添加 \(y\) (\(y \in \{0,1\}\)) ，得到新数 \(x' = 2x+y = 2(3k+b) + y = 6k + 2b + y\) ，此时 \(x'\equiv 2b + y \pmod 3\)

据此我们可以归纳定义:

(1) 基本项: \(\{ 0 \} \subseteq B_0, \{1\} \subseteq B_1\)

(2) 归纳项:

若 \(\alpha \in B_0\) 且 \(\alpha \neq 0\) ，则 \(\alpha0 \in B_0, \alpha1 \in B_1\)

若 \(\alpha \in B_1\) ，则 \(\alpha0 \in B_2, \alpha1 \in B_0\)

若 \(\alpha \in B_2\) ，则 \(\alpha0 \in B_1, \alpha1 \in B_2\)

(3) 极小化: \(B_0\) 就是我们想要的集合