大学数学导论2.4.md

牛津大学数学院在其官网同步存放着各种数学课程的课件，详情参考其官网链接. 本文以及可能会有的今后的一个系列，就是对上述内容阅读学习所做的笔记。

牛津数学导论 （2019-2020）学习笔记【1.2】归纳法

讲课人： Richard Earl 博士

笔记者：CycleUser

2019年12月16日09:10:54

2.4 德摩根定律(De Morgan’s Laws)

奥古斯都 德 摩根（Augustus De Morgan）是伦敦数学协会（London Mathematical Society）的第一任主席。除此以外，他主要被记住的成就还是下面这些双集合理论（two set-theoretic laws）以及各种逻辑等价命题（logical equivalents）。

定理（Theorem 48）德摩根定律-有限版本（finite version）

设$A_1,A_2,...,a_N$是一个集合$S$的子集和族(a family of subsets). 然后有：

$$ \begin{aligned} (\bigcap_{k=1}^nA_k)^c &=\bigcup^n_{k=1}A_k^c\\ (\bigcup_{k=1}^nA_k)^c &=\bigcap^n_{k=1}A_k^c\\ \end{aligned} $$

证明 当$n=2$时,上面第一个式子可以用下面的真值表来证明.

$A_1$	$A_2$	$A_1\cap A_2$	LHS	$A_1^C$	$A_2^C$	RHS
N	N	N	Y	Y	Y	Y
N	Y	N	Y	Y	Y	N
Y	N	N	Y	N	Y	Y
Y	Y	Y	N	N	N	N

然后利用归纳法(induction)就可以将上面的结果泛化,推广到一般情形.假如第一个德摩根定律对n个子集成立.则有:

$$ (\bigcap_{k=1}^{n+1}A_k )^c =(\bigcap_{k=1}^n A_k \cap A_{n+1})^c=(\bigcap_{k=1}^n A_k )^c \cup A^c_{n+1}\cup A^c_{n+1}=\bigcup_{k=1}^{n+1}A^c_k $$

所以接下来就可以归纳证明了.

第二个不等式(inequality,原文这么写的)就可以用第一条来证明了.

$$ \bigcap^n_{k+1}A^c_k=(\bigcap^n_{k=1}A^c_k)^{cc}=(\bigcup^n_{k=1}A^{cc}k)^c=(\bigcup^n{k=1}A_k)^c $$

证明完毕. 如上所述,德摩根定律就有逻辑等价(have logical equivalents)了.也就是:

$$ \begin{aligned} \neg (P \wedge Q) & \iff (\neg P) \vee (\neg Q)\\ \neg (P \vee Q) & \iff (\neg P) \wedge (\neg Q) \end{aligned} $$

上面这样的形式是德摩根定律更直观的等价形式.第一条实说如果P或者Q当中有一个是假的则P且Q为假,或者反过来说就是只要表明两个当中任意一个为假就足以证明P且Q不都是真了.第二个命题里面实收只要P和Q当中有任意一个成立,$P\vee Q$ 就为真了,如果这个不满足那么这两个肯定都是假的.

样例 49

设$A,B\subseteq S$,而$C,D\subseteq T$.则有:

$$ (A\times B)^c=(A^c\times T)\cup(S^c\times B) $$

解: $$ \begin{aligned} (s,t)\in(A \times B)^c &\iff \neg((s,t)\in A\times B) \ &\iff \neg(s\in A\vee t\in B) \ &\iff \neg(s\in A)\vee \neg(t\in B) \ &\iff s\in A^c\vee t\in B^c \ &\iff (s,t)\in A^c\times B^c \ \end{aligned} $$

证明完毕.

更进一步泛化,对任意的并集(union)和交集(intersection),从逻辑上来说,定量器$\forall$和$\exist$能够明确一个元素属于这样的交集和并集的确切含义.上文中将到达都还是有限个集合的并集和交集.很自然地就能想到应该考虑无穷个集合$A_0,A_1,A_2,...$然后考虑他们的交集和并集: $$ \bigcap_{n=0}^{\infty}A_n, \space \bigcup_{n=0}^{\infty}A_n $$

一个元素属于交集,就需要这个元素要存在于$A_n$中的每一个集合中,一个元素属并集就意味着这个元素只要在某个$A_n$中出现即可.这些例子中集合$A_n$的索引用的是$n\in N$,这样这个$N$就叫做索引集(indexing set).对此进一步泛化,就有了集合${A_i:i\in I}$,其中的$I$就是索引集,这时候的$I$就可以是比自然数$N$更大的集合了,比如实数集$R$.

这样就能定义人以及和的交集和并集了,如下所示: $$ \begin{aligned} x\in \bigcap_{i\in I}A_i\iff \forall i \in I \space x\in A_i;\ x\in \bigcup_{n=0}A_i\iff \exist i \in I \space x\in A_i; \end{aligned} $$

接下来想要有可以用于任意的交集和并集的德摩根定律形式,就需要利用到与上述定量器相关的否定形式.

命题 50 德摩根定律逻辑版本(De Morgan’s Laws — logical version)

设$P(x)$是一个命题族(family of statements),其索引是某个集合$S$的元素$x$.则有:

$$ \begin{aligned} \neg(\forall x\in S\space P(x))\iff \exist x\in S\space \neg P(x)\\ \neg(\exist x\in S\space P(x))\iff \forall x\in S\space \neg P(x) \end{aligned} $$

证明

若要$\forall x\in S \space P(x)$为真,则$P(x)$在整个集合$S$上都为真.这时候只要有一个反例成立,集$x\in S$而$\neg P(x)$为真,上述命题即不成立了. 第二条定律是从第一个退出来的.如果将第一个当中的$P(x)$替换成$\neg P(x)$,就有了:

$\neg(\forall x\in S\space \neg P(x))\iff \exist x\in S\space P(x)$

然后对两边取否就得到第二条定律的形式了.证明完毕.