集合划分、封闭性与有限结构

若要把对象分成若干类，应区分只要求覆盖与要求恰好属于一类。

幂集、子集族、覆盖与划分

集合 $X$ 的全部子集组成幂集

\mathcal P(X)=\{A:A\subseteq X\}.

它的元素是集合； $\mathcal F\subseteq\mathcal P(X)$ 称为 $X$ 的一个子集族。若 $|X|=n$ ，则 $|\mathcal P(X)|=2^n$ ，子集族的个数为 $2^{2^n}$ ，不能混淆这两层选择。

设 $X\ne\varnothing$ ， $S_1,\ldots,S_k$ 为非空子集。

若 $S_1\cup\cdots\cup S_k=X$ ，则它们构成一个覆盖；允许不同子集重叠。
若再满足任意 $i\ne j$ 都有 $S_i\cap S_j=\varnothing$ ，则构成一个划分；每个元素恰属于一个部分。

例如 $\{\{1,2\},\{2,3\}\}$ 覆盖 $\{1,2,3\}$ ，但不是划分； $\{\{1,2\},\{3\}\}$ 是划分。本页约定覆盖与划分的部分均非空；涉及编号部分或允许空部分的计数时须另行声明。

幂集的交满足

\mathcal P(A)\cap\mathcal P(B)=\mathcal P(A\cap B).

因为一个集合 $T$ 同时属于左侧两幂集，当且仅当 $T\subseteq A$ 且 $T\subseteq B$ ，也就是 $T\subseteq A\cap B$ 。特别地， $A\cap B=\varnothing$ 时交幂集为 $\{\varnothing\}$ ，不是 $\varnothing$ 。

运算封闭性的定义

设某运算对集合 $A$ 内的一切允许输入都有定义。若运算结果总属于 $A$ ，就称 $A$ 对该运算封闭。例如整数对加法、减法和乘法封闭；对除法则不封闭，因为 $1,2$ 都是整数，而 $1/2$ 不是整数。分母为零的情形本来就不在除法的允许输入中。

“对加法封闭”要求任意 $x,y\in A$ （允许 $x=y$ ）都满足 $x+y\in A$ 。若条件只针对不同元素，必须另行注明；下文两类有限数集会说明这个差别如何改变结论。

例：封闭性约束有限集合

设非空有限实数集 $A$ 对加法封闭。若含正数 $a$ ，则 $a,2a,3a,\ldots$ 全在 $A$ ，产生无穷多个不同元素，矛盾。含负数同理。因此 $A$ 只能为 $\{0\}$ ，而该集合确实加法封闭。

有限数集闭合条件：先检查极端元素

不同元素相加闭合。 设 $A$ 为有限实数集，并且不同的 $x,y\in A$ 总满足 $x+y\in A$ 。 $A$ 至多有一个正数：否则取其中最大的正数 $M$ 与另一个正数 $t$ ，则 $M+t>M$ 仍在 $A$ ，矛盾。同理至多有一个负数，再加可能的零，得 $|A|\le3$ 。 $\{-c,0,c\}$ （ $c>0$ ）满足条件，故上界可达。

必须保留“不同”：若对相同元素也要求闭合，非零最大绝对值元素与自身相加就矛盾，非空有限实数集只能是 $\{0\}$ 。

乘积或比值至少一个仍在集合。 设 $1\le a_1<\cdots<a_n=M$ 、 $n\ge2$ ，且对 $i\le j$ ， $a_ia_j$ 与 $a_j/a_i$ 至少一个在 $A$ 。因 $M>1$ ，取 $i=j=n$ 时 $M^2>M$ 不可能在 $A$ ，所以 $1\in A$ ，即 $a_1=1$ 。

对任意 $a_i>1$ ，取 $a_j=M$ ，乘积 $Ma_i>M$ 不在 $A$ ，故 $M/a_i\in A$ ； $a_i=1$ 时对应值为 $M$ 也在 $A$ 。变换 $a\mapsto M/a$ 两次还原，是 $A$ 到自身的双射，因此

\sum_{a\in A}a=M\sum_{a\in A}\frac1a, \qquad \frac{\sum a}{\sum1/a}=M.

这里结论来自已证明的配对，不能仅因“看起来对称”就断言两串数相同。

例：覆盖中的重计

区间 $[0,2]$ 与 $[1,3]$ 覆盖 $[0,3]$ ，但不是它的划分，因为交集 $[1,2]$ 非空。若把它们的长度直接相加会把交集重复计算。

易错点

“对加法封闭”不包含“对减法封闭”。题目说存在某些元素能运算，与要求任意元素都能运算，也有不同强度。

区间对平方封闭：把全称条件化为像集包含

设非空闭区间 $S=[m,n]$ 满足对每个 $x\in S$ 都有 $x^2\in S$ 。条件等价于平方函数在该区间的最小值不小于 $m$ 、最大值不大于 $n$ 。

若 $n<0$ ，平方非负，不可能留在负区间。若 $m>0$ ，最小平方为 $m^2$ ，最大平方为 $n^2$ ，所以 $m^2\ge m,n^2\le n$ ，结合 $0<m\le n$ ，只能 $m=n=1$ 。

若 $m\le0\le n$ ，像集为 $[0,\max(m^2,n^2)]$ 。包含条件等价于

0\le n\le1,\qquad -\sqrt n\le m\le0.

因此全部这样的区间恰为 $\{1\}$ ，以及满足上述两条条件的 $[m,n]$ 。这也包括 $\{0\}$ 。例如 $m=-1/2$ 时，必须且只须 $1/4\le n\le1$ ； $n=1/2$ 时必须且只须 $-1/\sqrt2\le m\le0$ 。

处理“每个元素经某变换后仍在集合内”时，先求整个像集，而不是只代入一个随意选取的数；变换非单调时尤其不能只检查两个端点而漏掉内部极值。

关联阅读

先修：集合运算与韦恩图 · 分类、分步与计数对象。

同主题：量词、否定与参数中的存在性 · 真假条件与有限逻辑推理。