《集合论与图论》第4讲1
第4讲集合恒等式
内容提要
? 1. 集合恒等式与对偶原理
? 2. 集合恒等式的证明
? 3. 集合列的极限
? 4. 集合论悖论与集合论公理
《集合论与图论》第4讲2
集合恒等式(关于∪与∩)
?等幂律(idempotent laws)
A∪A=A
A∩A=A
?交换律(commutative laws)
A∪B=B∪A
A∩B=B∩A
《集合论与图论》第4讲3
集合恒等式(关于∪与∩、续)
?结合律(associative laws)
(A∪B)∪C=A∪(B∪C)
(A∩B)∩C=A∩(B∩C)
?分配律(distributive laws)
A∪(B∩C)=(A∪B)∩(A∪C)
A∩(B∪C)=(A∩B)∪(A∩C)
《集合论与图论》第4讲4
集合恒等式(关于∪与∩、续)
?吸收律(absorption laws)
A∪(A∩B)=A
A∩(A∪B)=A
《集合论与图论》第4讲5
集合恒等式(关于~)
?双重否定律(double complement law)
~~A=A
?德●摩根律(DeMorgan’s laws)
~(A∪B)=~A∩~B
~(A∩B)=~A∪~B
《集合论与图论》第4讲6
集合恒等式(关于?与E)
?零律(dominance laws)
A∪E=E
A∩?=?
?同一律(identity laws)
A∪?=A
A∩E=A
《集合论与图论》第4讲7
集合恒等式(关于?,E)
?排中律(excluded middle)
A∪~A = E
?矛盾律(contradiction)
A∩~A = ?
?全补律
~? = E
~E = ?
《集合论与图论》第4讲8
集合恒等式(关于-)
?补交转换律(difference as intersection)
A-B=A∩~B
《集合论与图论》第4讲9
集合恒等式(推广到集族)
?分配律
?德●摩根律
)()}{(
α
α
αα
ABAB
S
S
∪=∪
∈
∈
II
)()}{(
α
α
αα
ABAB
S
S
∩=∩
∈
∈
UU
)()}{(
α
α
αα
ABAB
S
S
?=?
∈
∈
UI
)()}{(
α
α
αα
ABAB
S
S
?=?
∈
∈
IU
)(~)}{(~
α
α
αα
AA
S
S
∈
∈
= IU
)(~)}{(~
α
α
αα
AA
S
S
∈
∈
= UI
《集合论与图论》第4讲10
对偶(dual)原理
?对偶式(dual): 一个集合关系式, 如果只
含有∩, ∪,~,?, E,=, ?,那么, 同时把∪与
∩互换, 把?与E互换, 把?与?互换, 得到
的式子称为原式的对偶式.
?对偶原理: 对偶式同真假. 或者说, 集合
恒等式的对偶式还是恒等式.
《集合论与图论》第4讲11
对偶原理(举例)
?分配律
A ∪ (B ∩ C) = (A ∪ B ) ∩ (A ∪ C )
A ∩ (B ∪ C) = (A ∩ B ) ∪ (A ∩ C )
?排中律
A ∪ ~A=E
?矛盾律
A ∩ ~A= ?
《集合论与图论》第4讲12
对偶原理(举例、续)
?零律
A ∪ E =E
A ∩?= ?
?同一律
A ∪?=A
A ∩ E=A
《集合论与图论》第4讲13
对偶原理(举例、续)
? A ∩ B ? A
A ∪ B ? A
? ??A
E ? A
《集合论与图论》第4讲14
集合恒等式证明(方法)
?逻辑演算法:
利用逻辑等值式和推理规则
?集合演算法:
利用集合恒等式和已知结论
《集合论与图论》第4讲15
逻辑演算法(格式)
题目: A=B.
证明: ?x,
x∈A
? …(????)
? x∈B
∴ A=B. #
题目: A?B.
证明: ?x,
x∈A
? …(????)
? x∈B
∴ A?B. #
《集合论与图论》第4讲16
分配律(证明)
? A∪(B∩C)=(A∪B)∩(A∪C)
证明: ?x, x∈A∪(B∩C)
? x∈A ∨ x∈(B∩C) (∪定义)
? x∈A ∨ (x∈B ∧ x∈C) (∩定义)
? (x∈A∨x∈B)∧(x∈A∨x∈C) (命题逻辑分配律)
? (x∈A∪B)∧(x∈A∪C) (∪定义)
? x∈(A∪B)∩(A∪C) (∩定义)
∴ A∪(B∩C)=(A∪B)∩(A∪C)
《集合论与图论》第4讲17
零律(证明)
?A∩? = ?
证明: ?x, x∈A∩?
? x∈A ∧ x∈? (∩定义)
? x∈A ∧ 0 (?定义)
? 0 (命题逻辑零律)
∴ A∩? = ?
《集合论与图论》第4讲18
排中律(证明)
?A∪~A = E
证明: ?x, x∈A∪~A
? x∈A ∨ x∈~A (∪定义)
? x∈A ∨ x?A(~定义)
? x∈A ∨?x∈A (?定义)
? 1 (命题逻辑排中律)
∴ A∪~A = E
《集合论与图论》第4讲19
集合演算法(格式)
题目: A=B.
证明: A
=…(????)
=B
∴ A=B. #
题目: A?B.
证明: A
? …(????)
? B
∴ A?B. #
《集合论与图论》第4讲20
吸收律(证明)
?A∪(A∩B)=A
证明: A∪(A∩B)
= (A∩E)∪(A∩B) (同一律)
= A∩(E∪B) (分配律)
= A∩E(零律)
= A (同一律)
∴ A∪(A∩B)=A
A B
《集合论与图论》第4讲21
吸收律(证明、续)
?A∩(A∪B) = A
证明: A∩(A∪B)
= (A∩A)∪(A∩B) (分配律)
= A∪(A∩B) (等幂律)
= A (吸收律第一式)
∴ A∩(A∪B) = A
A B
《集合论与图论》第4讲22
集合演算法(格式,续)
题目: A=B.
证明: (?) …
∴ A?B
(?) …
∴ A ? B
∴ A = B. #
说明: 分=成?与?
题目: A?B.
证明: A∩B (或A∪B)
=…(????)
= A (或B)
∴ A?B. #
说明: 化?成=
A∩B=A?A?B
A∪B=B?A?B
《集合论与图论》第4讲23
集合恒等式证明(举例)
?基本集合恒等式
?对称差(⊕)的性质
?集族({A
α
}
α∈S
)的性质
?幂集(P( ))的性质
《集合论与图论》第4讲24
补交转换律
?A-B = A∩~B
证明: ?x,
x∈A-B
? x∈A ∧ x?B
? x∈A ∧ x∈~B
? x∈A∩~B
∴A-B = A∩~B. #
《集合论与图论》第4讲25
德?摩根律的相对形式
? A-(B∪C)=(A-B)∩(A-C)
? A-(B∩C)=(A-B)∩(A-C)
证明: A-(B∪C)
= A∩~(B∪C) (补交转换律)
= A∩(~B∩~C) (德●摩根律)
= (A∩A)∩(~B∩~C) (等幂律)
= (A∩~B)∩(A∩~C) (交换律,结合律)
= (A-B)∩(A-C) (补交转换律). #
《集合论与图论》第4讲26
对称差的性质
1.交换律: A⊕B=B⊕A
2.结合律: A⊕(B⊕C)=(A⊕B)⊕C
3.分配律: A∩(B⊕C)=(A∩B)⊕(A∩C)
4. A⊕?=A, A⊕E=~A
5. A⊕A=?, A⊕~A=E
《集合论与图论》第4讲27
对称差的性质(证明2)
?结合律: A⊕(B⊕C)=(A⊕B)⊕C
?证明思路：分解成
“基本单位”, 例如:
1. A∩~B∩~C
2. A∩ B∩~C
3. A∩ B∩ C
4. ~A∩~B∩~C
A
BC
A⊕B⊕C
1
2
3
4
《集合论与图论》第4讲28
对称差的性质(证明2、续1)
?结合律: A⊕(B⊕C)=(A⊕B)⊕C
?证明:首先,
A⊕B = (A-B)∪(B-A) (⊕定义)
= (A∩~B)∪(B∩~A) (补交转换律)
= (A∩~B)∪(~A∩B) (∩交换律) (*)
A⊕B
AB
《集合论与图论》第4讲29
对称差的性质(证明2、续2)
其次,A⊕(B⊕C)
= (A∩~(B⊕C))∪(~A∩(B⊕C)) (*)
= (A∩~((B∩~C)∪(~B∩C)))∪
(~A∩((B∩~C)∪(~B∩C))) (*)
= (A∩(~(B∩~C)∩~(~B∩C)))∪
(~A∩((B∩~C)∪(~B∩C))) (德?摩根律)
《集合论与图论》第4讲30
对称差的性质(证明2、续3)
= (A∩(~(B∩~C)∩~(~B∩C)))∪
(~A∩((B∩~C)∪(~B∩C)))
= (A∩(~B∪C)∩(B∪~C)))∪
(~A∩((B∩~C)∪(~B∩C))) (德?摩根律)
= (A∩B∩C)∪(A∩~B∩~C)
(~A∩B∩~C)∪(~A∩~B∩C) (分配律…)
《集合论与图论》第4讲31
对称差的性质(证明2、续4)
同理, (A⊕B)⊕C
= (A⊕B)∩~C)∪(~(A⊕B)∩C) (*)
= (((A∩~B)∪(~A∩B))∩~C)∪
(~((A∩~B)∪(~A∩B))∩C) (*)
= (((A∩~B)∪(~A∩B))∩~C)∪
((~(A∩~B)∩~(~A∩B))∩C) (德?摩根律)
《集合论与图论》第4讲32
对称差的性质(证明2、续5)
= (((A∩~B)∪(~A∩B))∩~C)∪
((~(A∩~B)∩~(~A∩B))∩C)
= (((A∩~B)∪(~A∩B))∩~C)∪
((~A∪B)∩(A∪~B))∩C) (德?摩根律)
= (A∩~B∩~C)∪(~A∩B∩~C)∪
(~A∩~B∩C)∪(A∩B∩C) (分配律…)
∴ A⊕(B⊕C)=(A⊕B)⊕C. #
《集合论与图论》第4讲33
对称差的性质(讨论)
?有些作者用△表示对称差:A⊕B=A△B
?消去律: A⊕B=A⊕C ? B=C (习题一,23)
A=B⊕C ? B=A⊕C? C=A⊕B
?对称差与补: ~(A⊕B) = ~A⊕B = A⊕~B
A⊕B = ~A⊕~B
?问题: A⊕B⊕C=~A⊕~B⊕~C ?
《集合论与图论》第4讲34
对称差的性质(讨论、续)
?如何把对称差推广到n个集合:
A
1
⊕A
2
⊕A
3
⊕…⊕A
n
= ?
? ?x, x∈A
1
⊕A
2
⊕A
3
⊕…⊕A
n
? x恰好属于A
1
,A
2
,A
3
,…,A
n
中的奇数个
?特征函数表达: χ
A
1
⊕A
2
⊕…⊕A
n
(x)
= χ
A
1
(x)+χ
A
2
(x)+…+χ
A
n
(x) (mod 2)
= χ
A
1
(x)⊕χ
A
2
(x)⊕…⊕χ
A
n
(x)
((mod 2),⊕,都表示模2加法,即相加除以2取余数)
《集合论与图论》第4讲35
特征函数与集合运算:
?χ
A∩B
(x) = χ
A
(x)?χ
B
(x)
?χ
~A
(x) = 1-χ
A
(x)
?χ
A-B
(x) = χ
A∩~B
(x)=χ
A
(x)?(1-χ
B
(x))
?χ
A∪B
(x) = χ
(A-B)∪B
(x)
= χ
A
(x)+χ
B
(x)-χ
A
(x)?χ
B
(x)
?χ
A⊕B
(x) = χ
A
(x)+χ
B
(x) (mod 2)
= χ
A
(x)⊕χ
B
(x)
AB
《集合论与图论》第4讲36
对称差的性质(讨论、续)
?问题: A⊕B⊕C = ~A⊕~B⊕~C ?
答案: A⊕B⊕C = ~(~A⊕~B⊕~C)
= ~(A⊕B⊕~C) = A⊕~B⊕~C
?A⊕B⊕C⊕D = ~A⊕~B⊕~C⊕~D
= A⊕~B⊕C⊕~D = ~(~A⊕~B⊕C⊕~D)
=…
?A = ~(~A)
《集合论与图论》第4讲37
对称差的性质(证明3)
?分配律: A∩(B⊕C)=(A∩B)⊕(A∩C)
?证明
A∩(B⊕C)
= A∩((B∩~C)∪(~B∩C))
= (A∩B∩~C)∪ (A∩~B∩C)
A
BC
A∩(B⊕C)
《集合论与图论》第4讲38
对称差分配律(证明3、续)
(续)(A∩B)⊕(A∩C)
= ((A∩B)∩~(A∩C))∪(~(A∩B)∩(A∩C))
=((A∩B)∩(~A∪~C))∪((~A∪~B)∩(A∩C))
=(A∩B∩~C)∪(A∩~B∩C)
∴ A∩(B⊕C)=(A∩B)⊕(A∩C). #
《集合论与图论》第4讲39
对称差分配律(讨论)
?A∩(B⊕C)=(A∩B)⊕(A∩C) √
?A∪(B⊕C)=(A∪B)⊕(A∪C) ?
?A⊕(B∩C)=(A⊕B)∩(A⊕C) ?
?A⊕(B∪C)=(A⊕B)∪(A⊕C) ?
《集合论与图论》第4讲40
集族的性质
设A,B为集族, 则
?1. A?B ?∪A ?∪B
?2. A∈B ? A ?∪B
?3. A≠? ∧ A?B ?∩B ?∩A
?4. A∈B ?∩B ? A
?5. A≠? ?∩A ?∪A
《集合论与图论》第4讲41
集族的性质(证明1)
? A?B ?∪A ?∪B
证明: ?x,
x∈∪A
??A(A∈A ∧ x∈A) (∪A定义)
? ?A(A∈B ∧ x∈A) (A?B)
? x∈∪B (∪B定义)
∴∪A ?∪B. #
《集合论与图论》第4讲42
集族的性质(证明2)
? A∈B ? A ?∪B
证明: ?x,
x∈A
? A∈B ∧ x∈A (A∈B, 合取)
? ?A(A∈B ∧ x∈A) (EG)
? x∈∪B
∴ A ?∪B. #
《集合论与图论》第4讲43
集族的性质(证明3)
? A≠? ∧ A?B ?∩B ?∩A
说明: 若约定∩?=E, 则A≠?的条件可去掉.
证明: ?x,
x∈∩B ??y( y∈B → x∈y )
? ?y( y∈A → x∈y ) (A?B)
? x∈∩A
∴∩B ?∩A . #
《集合论与图论》第4讲44
集族的性质(证明4)
? A∈B ?∩B ? A
证明: ?x,
x∈∩B ??y( y∈B → x∈y )
? A∈B → x∈ A (UI)
? x∈A (A∈B)
∴∩B ?A . #
《集合论与图论》第4讲45
集族的性质(证明5)
? A≠? ?∩A ?∪A
说明: A≠?的条件不可去掉!
证明: A≠? ? ?y(y∈A), 设A∈A.
?x, x∈∩A ??y( y∈A → x∈y )
? A∈A → x∈A ? x∈A (A∈A)
? A∈A ∧ x∈A ??y( y∈A ∧ x∈y)
? x∈∪A
∴∩A ?∪A . #
《集合论与图论》第4讲46
幂集的性质
1. A?B ? P(A)?P(B)
2. P(A)∪P(B) ? P(A∪B)
3. P(A)∩P(B) = P(A∩B)
4. P(A-B) ? (P(A)-P(B))∪{?}
《集合论与图论》第4讲47
幂集的性质(证明1)
?A?B ? P(A)?P(B)
证明: (?) ?x,
x∈P(A)
? x?A
? x?B (A?B)
? x∈P(B)
∴ P(A)?P(B)
《集合论与图论》第4讲48
幂集的性质(证明1、续)
?A?B ? P(A)?P(B)
证明(续): (?) ?x,
x∈A
? {x}∈P(A)
? {x}∈P(B) (P(A)?P(B))
? x∈B
∴ A?B. #
《集合论与图论》第4讲49
幂集的性质(证明2)
? P(A)∪P(B) ? P(A∪B)
证明: ?x,
x∈P(A)∪P(B)
? x∈P(A)∨x∈P(B)
? x?A∨x?B
? x?A∪B
? x∈P(A∪B)
∴ P(A)∪P(B) ? P(A∪B)
《集合论与图论》第4讲50
幂集的性质(证明2、续)
?P(A)∪P(B) ? P(A∪B)
讨论: 给出反例, 说明等号不成立:
A={1}, B={2}, A∪B={1,2},
P(A)={?,{1}}, P(B)={?,{2}},
P(A∪B)= {?,{1},{2},{1,2}}
P(A)∪P(B) ? {?,{1},{2}}
此时, P(A)∪P(B) ? P(A∪B). #
《集合论与图论》第4讲51
幂集的性质(证明3)
? P(A)∩P(B) = P(A∩B)
证明: ?x,
x∈P(A)∩P(B)
? x∈P(A) ∧ x∈P(B)
? x?A ∧ x?B
? x? A∩B
? x∈P(A∩B)
∴ P(A)∩P(B) = P(A∩B). #
《集合论与图论》第4讲52
幂集的性质(证明4)
?P(A-B) ? (P(A)-P(B))∪{?}
证明: ?x, 分两种情况, (1) x=?, 这时
x∈P(A-B) 并且x∈(P(A)-P(B))∪{?}
(2) x≠?, 这时
x∈P(A-B) ? x? A-B ? x?A∧x?B
? x∈P(A)∧x?P(B) ? x∈P(A)-P(B)
∴ P(A-B) ? (P(A)-P(B))∪{?}. #
A B
《集合论与图论》第4讲53
集合运算的优先级
?分三级: 第一级最高, 依次降低
?第一级: 补~, 幂P()
?第二级: 广义并∪, 广义交∩
?第三级:并∪, 交∩, 相对补-, 对称差⊕
?同一级: 用括号表示先后顺序
《集合论与图论》第4讲54
集合列的极限
A
1
A
2
A
3
A
4
A
5
E
《集合论与图论》第4讲55
集合列的极限
?Infinite often( i.o.):无穷多次
?Almost everywhere(a.e.):几乎处处
《集合论与图论》第4讲56
集合列的极限
?上极限:
?下极限:
.}.|{lim oiAxxA
kk
k
∈=
∞→
.}.|{lim eaAxxA
kk
k
∈=
∞→
《集合论与图论》第4讲57
集合列的极限
?性质:
IU
∞
=
∞
=
∞→
=
1
lim
nnk
kk
k
AA
UI
∞
=
∞
=
∞→
=
1
lim
nnk
kk
k
AA
《集合论与图论》第4讲58
集合论悖论
?罗素悖论(Russell’s paradox)：
S = { x | x?x }
S∈S ?
S∈S ? S?S
S?S ? S∈S
《集合论与图论》第4讲59
集合论公理
?外延公理: 所含元素相同的两个集合是
相等的
?空集存在公理: 空集合?存在
?无序对公理: 对任意集合a,b, {a,b}存在
?并集公理: 对任意集合a,b, a∪b存在
?幂集公理: 对任意集合A, P(A)存在
?联集公理: 对任意集合A, ∪A存在
《集合论与图论》第4讲60
集合论公理(续)
?子集公理模式(分离公理): 对任意集合A, B不
在P(x)中出现,
B = { x∈A | P(x) }存在
?正则公理: 若S≠?,则
?x(x∈S∧?y(y∈S→x?y))
?无穷公理: 无穷集存在
?替换公理: f是定义域为集合A的函数,
{ f(a) | a∈A }存在
《集合论与图论》第4讲61
集合论公理(续)
?选择公理(Zorn引理, 良序原理): A是元素
互不相交的集合,则可以从A的每个元素
中恰好选择一个元素, 构成一个集合
《集合论与图论》第4讲62
总结
?集合恒等式
?集合恒等式的证明
?集合论悖论
《集合论与图论》第4讲63
作业(#2)
?p27,习题一,11,13,14,20
