离散数学：集合论基础

发表于 更新于 分类于 Waline： 阅读次数：

Set

Basis

Definition

  • 外延公理
  • 空集存在公理
  • 无序对公理
  • 并集公理
  • 幂集公理
  • 无穷公理
  • 替换公理
  • 正则公理 （以上为ZF公理化集合论）
  • 选择公理 （以上为ZFC公理化集合论）

若a是集合A中的元素，则成a属于A，记为\(s\in A\)

若a不是集合A中的元素，则成a不属于A，记为\(s\notin A\)

Example

枚举法

\(A = \{ a,b,c,d \}\)

\(B = \{ 2,4,6,8,\cdots \}\)

叙述法

通过刻画集合中元素所具备的某种性质或特性来表示一个集合

\(P = \{ x \mid P\left( x \right) \}\)

\(C = \{x \mid x = 2k , k \in N \}\)

文氏图

Base number

集合A中元素个数称为集合中的基数（base number）,记为\(\mid A\mid\)

若一个集合的基数是有限的，称该集合为有限集（finite set）

若一个集合的基数是无限的，称该集合为无限集（infinite set）

\(A = \{ a , \{ b,c \} \} \mid A \mid = 2\)

empty set

不含任何元素的集合叫做空集，记为\(\varnothing\)

空集是绝对唯一的

universal set

针对一个具体范围，我们考虑所有的集合叫做全集，记为U或E.

文氏图一般使用方形表示全集

全集是相对唯一的

eg：

在立体集合中，全集是由空间的全体点构成的

集合的相等关系

集合中的元素是无序的。

集合中的元素是不同的。

外延性原理

两个集合A和B相等，当且仅当它们的元素完全相同，记为A=B，否则A和B不相等，记为\(A \neq B\)

集合的包含关系

设A，B为任意两个集合，

  • 如果B的每个元素都是A的元素，则称B是A的子集，也称作B被A包含或者A包含B，记为\(B \subseteq A\)否则记作\(B \nsubseteq A\)
  • 如果\(B \subseteq A\)并且\(A \neq B\),则称B是A的真子集，也称为B被A真包含或A真包含B，记为\(B \subset A\),否则记作\(B \not\subset A\)

  • \(\subseteq\)关系的数学描述为：\(B \subseteq A \Leftrightarrow 对于 \forall x,如果x \in B,则x \in A\)

  • \(设A,B为任意两个集合，则A=B \Leftrightarrow A \subseteq B并且B \subseteq A\)

    非常重要证明集合相等的一种重要的方式

  • \[ 对于任意n元集合A，它的m元(0 \leq m \leq n)子集个数为 C^n_m个，\\ 所以不同子集个数为：C_n^0+C_n^1+\cdots+c_n^n=2^n. \]

幂集

\[ 设A为任意集合，把A的所有不同子集构成的集合叫做A的幂集(power \space set),记作P(A),即，\\ P(A)= \left\{ x \mid x \sube A\right\}\\ 推论：x \in P(A) \Leftrightarrow x \sube A \]

幂集也叫做集族或者集合的集合

集合的运算

并运算

\[ 设A，B是两个集合，则集合A与B的并集定义为：\\ A \cup B=\left\{ x \mid x \in A 或 x \in B \right\} \]

交运算

\[ 设A，B是两个集合，则集合A与B的交集定义为：\\ a \cap B=\left\{ x \mid x \in A 并且 x \in B\right\} \]

补运算

\[ 设U是全集，则集合A的补集定义为：\\ \overline{a}=\left\{ x \mid x \notin A\right\} \]

差运算

\[ 设A，B是两个集合，则集合A与B的差集定义为：\\ A-B=\left\{ x \mid x \in A 并且 x \notin B\right\} \]

对称差运算

\[ 设A，B是两个集合，则集合A与B的对称差定义为：\\ A \oplus B=\left\{ x \mid (x \in A 并且 x \notin B)或者(x \notin A并且 x \in B) \right\} \]

运算拓展

并集和交集的拓展

\[ 设A_1,A_2,\cdots,A_n是任意n个集合，则这n个集合的并集是包含哪些至少\\是这组集合中一个集合成员的元素的集合，即，\\ \bigcup_{i=1}^n A_i=A_1 \cup A_2 \cup A_3 \cup \cdots \cup A_n=\left\{ x \mid x \in A_1 或者 x \in A_2 \cdots 或者 x \in A_n\right\}\\ \\ 设A_1,A_2,\cdots,A_n是任意n个集合，则这n个集合的交集是包含哪些属于\\这组集合中所有集合成员的元素的集合，即，\\ \bigcap_{i=1}^n A_i=A_1 \cap A_2 \cap A_3 \cap \cdots \cap A_n=\left\{ x \mid x \in A_1 并且 x \in A_2 \cdots 并且 x \in A_n\right\}\\ \\ \]

集合的运算定律

定理

\[ 设U为全集，A,B,C为任意集合。\\ 1、 A \cup A=A , A \cap A =A(幂等率)\\ 2、 A \cup B=B \cup A,A \cap B=B \cap A（交换律）\\ 3、A \cup (B \cup C)=(A \cup B)\cup C,A \cap (B \cap C)=(A\cap B)\cap C(交换律)\\ 4、A \cup \varnothing =A,A \cap U=A(同一律)\\ 5、A \cup U=U,A \cap \varnothing=\varnothing（零律）\\ 6、A \cup(B\cup C)=(A \cup B)\cap(A \cup C),A\cap(B \cup C)=(A \cap B)\cup(A \cap C) (分配率)\\ 7、A\cup(A\cap B)=A,A\cap(A\cup B)=A（吸收律）\\ 8、\overline{A} \cap A=\varnothing,\overline{A} \cup A=U(矛盾律和排中律)\\ 9、 \mathop{A}\limits^{=}=A(双重否定率)\\ 10、\overline{A \cup B}=\overline{A} \cap \overline{B},\overline{A \cap B}=\overline{A} \cup \overline{B}(德摩根律)长杠变短杠，符号变方向\\ \over \]

证明方法

证明框架

证明：

  1. 首先证明 \(A \subseteq B : \forall x \in A,\cdots,x \in B,\therefore A \subseteq B\)

  2. 首先证明 \(B \subseteq A : \forall x \in B,\cdots,x \in A,\therefore B \subseteq A\)

由以上两点，克制A=B。

Example

证明德摩根律的等式之一：\(\overline{A \cup B}=\overline{A} \cap \overline{B}\)

证明：

  1. 首先证明\(\overline{A \cup B}\subseteq\overline{A} \cap \overline{B}\) \[ \begin{align} \forall x \in \overline{A \cup B} &\Rightarrow x \notin A \cup B \Rightarrow x \notin A并且 x \notin B\\ &\Rightarrow x \in \overline{A}并且x \in \overline{B} \Rightarrow x \in \overline{A} \cap \overline{B}\\ \end{align} \]

  2. 其次证明\(\overline{A} \cap \overline{B} \subseteq \overline{A \cup B}\) \[ \begin{align} \forall x \in \overline{A}\cap\overline{B} &\Rightarrow x \in \overline{a} 并且 x \in \overline{B} \Rightarrow x \notin A 并且 x \notin B\\ &\Rightarrow x \notin A \cup B \Rightarrow \overline{A \cup B} \end{align} \]

由以上两点，克制等式\(\overline{A \cup B}=\overline{A} \cap \overline{B}\)成立

可数集合与不可数集合

自然数集的定义

Definition(皮亚诺定理)

1891年，意大利数学家皮亚诺公开发表了基于序数的自然数定义公理。这组公理包括：

  1. 0是自然数
  2. 每个自然数n都有一个后继，这个后继也是一个自然数，记为S（n）；
  3. 两个自然数相等当且仅当它们有相同的后继，即m=n当且仅当S(m)=S(n);
  4. 没有任何自然数的后继为0；
  5. （归纳公理）$ 若，如果1、(0)为真;2、当(n)为真，则有(S(n))为真;则(n)对任意自然数n成立。 $

Definition(冯诺依曼的自然数定义)

20世纪初，集合成为数学的基本概念之后，数学奇才、计算机之父冯诺依曼基于基数，利用一个集合的序列来定义自然数：

  1. \(\varnothing \in N\)

  2. \(若n \in N,则n^\prime \equiv n \cup \{ n\} \in N\)

从而，这个集合序列的基数就可以来定义自然数

  • \(0 \equiv \mid \varnothing\mid;\)
  • \(1 \equiv \mid \varnothing \cup \{ \varnothing \} \mid = \mid \{ \varnothing \} \mid\)
  • \(2 \equiv \mid \{ \varnothing \} \cup \{\{\varnothing\}\}\mid=\mid\{\varnothing,\{\varnothing\}\}\mid\)
  • \(\cdots\)

集合比较

有限集合比较集合的基数

Definition

设A，B为两个集合，若在A，B之间存在一种一一对应的关系：

\(\Psi :A\rightarrow B\)

则称A与B是等势的(equipotential)，记作

\(A\sim B\)

由等势定义可以看书，如果A=B，那么\(A\sim B\),反之却不成立

可数集合

Definition

凡是自然数集合N等势的集合，成为可数集合(countable set),该集合的基数记为\(\aleph_0\)(读作阿列夫零)

正奇数集合是可数集合

素数集合是可数集合

有理数集合Q是可数集合

从有限到无限，不仅仅是简单数量上的变化（量变），而引起了本质的改变（质变）。

  • 两个无限集合的“大小”已经不能使用集合中的元素个数来衡量。\(\aleph_0\)可以表示一切可数集合的基数，是一种抽象的表达。
  • 表面上个数完全不相等的两个集合之间仍可能存在等势关系，如集合与其真子集之间，这体现了有限集合和无限集合的根本差别。

不可数集合

Definition

开区间(0,1)成为不可数集合，凡与开区间(0,1)等势的集合，称为不可数集合，该类集合的基数记为\(\aleph\)

eg:

闭区间[0,1]是不可数集合

实数集合R是不可数集合.\(n\rightarrow \tan(\pi\frac{2n-1}{2})\)