贡献者: 零穹
通过 “集合” 的预备知识,我们应该知道,集合是由元素构成的。这是说,在一开始讨论集合的时候,必须先行给出一个集合,才能继续进行有关的讨论。这是说当你说集合 $A$ 时,我们已经知道了它的元素。具体而言,当谈论集合 $A$ 时,你应该马上将其理解成 $A=\{a_1,\cdots,a_n,\cdots\}$,其中花括号里的是 $A$ 的元素。既然提到集合相当于指出它的元素,那同时就能判断哪些使它的元素,哪些不是它的元素,$a$ 是 $A$ 的元素记作 $a\in A$,$a$ 不是 $A$ 的元素记作 $a\notin A$,这些都是在提到集合的时候就同时表明了的。有了集合后,一个重要的任务是其上运算的定义及运算规则,这便是本节要介绍的,本文较通常的教科书创新之处在于给出了通常集合中 “且” 和 “或” 的精确定义。
1. 与 $\land$ 和 或 $\lor$
同样在 “集合” 里,已经知道集合间可以进行运算 $\cap$(交)、$\cup$(并)。现在来给出它们的具体定义。严格的定义需要用到两个逻辑学概念 $\land$(读作 “与”)和 $\lor$(读作 “或”)。它们仅仅代表两个函数,下面将记 $Z_2=\{0,1\}$。
定义 1 与
称函数 $f:Z_2\times Z_2\rightarrow Z_2$ 为与,若
\begin{equation}
f(0,0)=0,\quad f(0,1)=0,\quad f(1,0)=0,\quad f(1,1)=1~.
\end{equation}
并将与函数 $f$ 记作 $\land$。
定义 2 或
称函数 $f:Z_2\times Z_2\rightarrow Z_2$ 为或,若
\begin{equation}
f(0,0)=0,\quad f(0,1)=1,\quad f(1,0)=1,\quad f(1,1)=1~.
\end{equation}
并将或函数 $f$ 记作 $\lor$。
下面的定理起着重要作用。
定理 1 与或分配律
对任意 $a,b,c\in Z_2$,成立恒等式:
\begin{equation}
\begin{aligned}
\lor(\land(a,b),c)&=\land(\lor(a,c),\lor(b,c)),\\
\land(\lor(a,b),c)&=\lor(\land(a,c),\land(b,c))~.
\end{aligned}
\end{equation}
证明:
我们以第一式的证明为例,读者完全可以类似的证明出第二式。证明的关键只需要代入所有可能的 $a,b,c$ 即可,由于取值只有 $0,1$,这是方便的。
若 $c=1$,由定义 2 ,$\lor(\land(a,b),1)=1$。于是只需证明右边无论 $a,b$ 取 $0,1$ 哪个指都为 1 即可。同样由 $\lor$ 的定义,右边 $\land$ 函数的两个变量都是 1:
\begin{equation}
\lor(a,1)=\lor(b,1)=1~.
\end{equation}
于是由
定义 1 ,右边为 $\land(1,1)=1$,即
\begin{equation}
\lor(\land(a,b),1)=\land(\lor(a,1),\lor(b,1))~.
\end{equation}
若 $c=0$,那么仅当 $\land(a,b)=1$ 时左边为 1,而右边也是仅当 $a=b=1$ 时为 1。于是
\begin{equation}
\lor(\land(a,b),0)=\land(\lor(a,0),\lor(b,0))~.
\end{equation}
证毕!
式 3 之所以称为分配律,是因为若记 $a\land b:=\land(a,b),a\lor b:=\lor(a,b)$,则式 3 成为
\begin{equation}
\begin{aligned}
(a\land b)\lor c&=(a\lor c)\land(b\lor c),\\
(a\lor b)\land c&=(a\land c)\lor(b\land c)~.
\end{aligned}
\end{equation}
以后将采用此记号。总结成定义和定理的形式就是:
定义 3
定义 $a\land b:=\land(a,b),a\lor b:=\lor(a,b)$。
定理 2 分配律
\begin{equation}
\begin{aligned}
(a\land b)\lor c&=(a\lor c)\land(b\lor c),\\
(a\lor b)\land c&=(a\land c)\lor(b\land c)~.
\end{aligned}
\end{equation}
2. 属于 $\in$ 的数值化
在精确定义集合的交和并前,还需要引入一种特定的函数,它将元素和集合的关系数值化了,不妨称为集合上的坐标函数。
定义 4
设 $X$ 是集合,则称函数 $f_X$ 是集合 $X$ 上的坐标,若
\begin{equation}
f_X(x)=\left\{\begin{aligned}
&1,\quad x\in X,\\
&0,\quad x\notin X~.
\end{aligned}\right.
\end{equation}
并称 $f_X(x)$ 是元素 $x$ 关于 $X$ 的
坐标。
元素的坐标其实就表达了元素是否属于对应的集合。由于坐标函数的取值是 $0,1$,所以可以将其和逻辑与或的关系联系起来。
定义 5 简记约定
当集合的坐标函数和逻辑与或函数连用时,直接记 $x\in X:=f_X(x)$。
这一约定并不会引起混乱,它仅仅在符号 $\in$ 和 $\land,\lor$ 同时出现在一个表达时中时被采用。例如 $x\in X\land y\in Y=f_X(x)\land f_Y(y)$。
利用这一约定,则可将定理 2 翻译成下面定理
定理 3
设 $X,Y,Z$ 是三个集合,则成立
\begin{equation}
\begin{aligned}
&(x\in X\land y\in Y)\lor z\in Z=(x\in X\lor z\in Z)\land(y\in Y\lor z\in Z),\\
& \left(x\in X\lor y\in Y \right) \land z\in Z=(x\in X\land z\in Z)\lor(y\in Y\land z\in Z)~.
\end{aligned}
\end{equation}
定义交和并的原材料已经制备完成了,接下来就可以造出交并的严格形式了。
3. 交 $\cap$,并 $\cup$
定义 6 交集
设 $X,Y$ 是两集合,称集合
\begin{equation}
\{z|z\in X\land z\in Y=1 \}~
\end{equation}
为 $X,Y$ 的
交集,记作 $X\cap Y$。
这事实上表达了交集的元素同时属于两集合这样的概念。
定义 7 并集
设 $X,Y$ 是两集合,称集合
\begin{equation}
\{z|z\in X\lor z\in Y=1 \}~
\end{equation}
为 $X,Y$ 的
并集,记作 $X\cup Y$。
这事实上表达了并集的元素至少属于两集合之一这样的概念。
定理 4
\begin{equation}
\begin{aligned}
f_{X\cap Y}(z)&=f_X(z)\land f_Y(z),\\
f_{X\cup Y}(z)&=f_X(z)\lor f_Y(z)~.
\end{aligned}
\end{equation}
证明:以第一式证明为例:
\begin{equation}
\begin{aligned}
&f_{X\cap Y}(z)=1\overset{定义 4 }{\Leftrightarrow} z\in (X\cap Y)\overset{定义 6 ,定义 5 }{\Leftrightarrow}f_X(z)\land f_Y(z)=1~.\\
&f_{X\cap Y}(z)=0\overset{定义 4 }{\Leftrightarrow} z\notin (X\cap Y)\overset{定义 6 ,定义 5 }{\Leftrightarrow}f_X(z)\land f_Y(z)=0~.\\
\end{aligned}
\end{equation}
证毕!
推论 1
\begin{equation}
\begin{aligned}
f_{\bigcap_\alpha X_\alpha}(z)&=\underset{\alpha}{\land} f_{X_\alpha}(z),\\
f_{\bigcup_\alpha X}(z)&=\underset{\alpha}{\lor} f_{X_\alpha}(z)~.
\end{aligned}
\end{equation}
使用数学归纳法证明即可。
4. 运算性质
现在,我们就可以严格的证明集合的交运算和并运算的分配律了。
定理 5 交并的分配律
设 $X,Y,Z$ 是三个集合,则成立
\begin{equation}
\begin{aligned}
&(X\cap Y)\cup Z=(X\cup Z)\cap (Y\cup Z),\\
&(X\cup Y)\cap Z=(X\cap Z)\cup (Y\cap Z)~.
\end{aligned}
\end{equation}
证明:由定义 6 ,定义 7 ,只需证明
\begin{equation}
\begin{aligned}
z\in (X\cap Y)&\lor z\in Z=1\\
&\Updownarrow\\
(z\in X\cup Z)&\land (z\in Y\cup Z)=1~.
\end{aligned}
\end{equation}
和
\begin{equation}
\begin{aligned}
z\in (X\cup Y)&\land z\in Z=1\\
&\Updownarrow\\
(z\in X\cap Z)&\lor (z\in Y\cap Z)=1~.
\end{aligned}
\end{equation}
由
定理 4 和
定义 5 ,
式 17 和
式 18 等式左边可写为
\begin{equation}
\begin{aligned}
z\in (X\cap Y)\lor z\in Z&=(z\in X\land z\in Y)\lor z\in Z,\\
(z\in X\cup Z)\land (z\in Y\cup Z)&=(z\in X\lor z\in Y)\land (z\in Y\lor z\in Z),\\
z\in (X\cup Y)\lor z\in Z&=(z\in X\lor z\in Y)\land z\in Z,\\
(z\in X\cap Z)\lor (z\in Y\cap Z)&=(z\in X\land z\in Y)\lor (z\in Y\land z\in Z)~.
\end{aligned}
\end{equation}
于是只需证明
\begin{equation}
\begin{aligned}
(z\in X\land z\in Y)&\lor z\in Z=1\\
&\Updownarrow\\
(z\in X\lor z\in Y)&\land (z\in Y\lor z\in Z)=1,\\
\\
(z\in X\lor z\in Y)&\land z\in Z=1\\
&\Updownarrow\\
(z\in X\land z\in Y)&\lor (z\in Y\land z\in Z)=1~.
\end{aligned}
\end{equation}
由定理 3 ,式 20 成立。
证毕!
定理 6 对偶原理(de Morgan 定理)
\begin{equation}
\begin{aligned}
S\backslash \bigcup_\alpha A_\alpha&=\bigcap_\alpha(S\backslash A_\alpha),\\
S\backslash \bigcap_\alpha A_\alpha&=\bigcup_\alpha(S \backslash A_\alpha)~,\\
\end{aligned}
\end{equation}
在证明之前,首先明确,$x \in A\backslash B$ 等价于 $f_A(x)=1,f_B(x)=0$.
证明:这里的对偶是指:定理中的两式已知其中之一,便可推得另一式。以第一式成立为例,那么
\begin{equation}
\begin{aligned}
S\backslash \bigcap_\alpha (S\backslash A_\alpha)&=S\backslash \left(S\backslash\bigcup_\alpha A_\alpha \right) =\bigcup_\alpha A_\alpha,\\
\Downarrow\\
S\backslash \bigcap_\alpha A_\alpha&=S\backslash \bigcap_\alpha (S\backslash (S\backslash A_\alpha))=\bigcup_\alpha (S\backslash A_\alpha)~.
\end{aligned}
\end{equation}
于是我们只需证明第一式即可。这只需证明
\begin{equation}
\begin{aligned}
f_S(x)=1,&\quad f_{\bigcup_\alpha A_\alpha}(x)=0\\
&\Updownarrow\\
f_{\bigcap_\alpha (S\backslash A_\alpha)}(x)&=1~.
\end{aligned}
\end{equation}
由
推论 1 ,只需证明
\begin{equation}
\begin{aligned}
f_S(x)=1,&\quad \underset{\alpha}{\lor}f_{A_\alpha}(x)=0\\
&\Updownarrow\\
\underset{\alpha}{\land}f_{(S\backslash A_\alpha)}(x)&=1~.
\end{aligned}
\end{equation}
这可证明如下
\begin{equation}
\begin{aligned}
f_S(x)=1,&\quad \underset{\alpha}{\lor}f_{A_\alpha}(x)=0\\
\Updownarrow\\
f_S(x)=1,&\quad f_{A_\alpha}(x)=0,\quad\forall \alpha\\
\Updownarrow\\
f_{S\backslash A_\alpha}(x)=1,&\quad\forall \alpha\\
\Updownarrow\\
\underset{\alpha}{\land}f_{(S\backslash A_\alpha)}(x)&=1~.
\end{aligned}
\end{equation}
证毕!
总结一下本文的内容,引入逻辑与或的概念并定义集合的坐标函数,我们可以将集合中的概念严格定义一遍而避免使用 “或” 和 “且” 这样模糊的概念,并且在证明集合运算的两个性质做到清楚了当。