集合的归纳定义法¶

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}$ 且 $α \in A$ ，则 $a α \in A$ ( $a α$ 表示拼接字符串)

(3) 极小化

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

我们应该将归纳项改为:

(2) 若 $α, β \in A$ 且 $α \neq 0$ ，则 $α β \in A$

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

联立归纳定义法¶

再看一个神奇的例子

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

我们先考虑几个集合: 除 $3$ 余 $0$ 的集合 $B_{0}$ ，除 $3$ 余 $1$ 的集合 $B_{1}$ ，除 $3$ 余 $2$ 的集合 $B_{2}$

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

据此我们可以归纳定义:

(1) 基本项: ${0} \subseteq B_{0}, {1} \subseteq B_{1}$

(2) 归纳项:

若 $α \in B_{0}$ 且 $α \neq 0$ ，则 $α 0 \in B_{0}, α 1 \in B_{1}$

若 $α \in B_{1}$ ，则 $α 0 \in B_{2}, α 1 \in B_{0}$

若 $α \in B_{2}$ ，则 $α 0 \in B_{1}, α 1 \in B_{2}$

(3) 极小化: $B_{0}$ 就是我们想要的集合