南京大学：《离散数学》课程教学资源（PPT课件讲稿）Lecture 04 集合及其运算

1 集合及其运算

集合及其运算 1

回顾 问题1：什么叫证明？ -表明定理为真的有效论证（演绎推理) 问题2：常见的证明方法有哪些？ ~直接证明、间接证明、归谬法、分情形证明、等价性证 明、存在性证明、唯一性证明 问题3：什么是猜想？有哪些有意思的猜想？ -尚未被证明的可能为真的陈述：费马大定理、四色定理、 哥德巴赫猜想、庞加莱定理、黎曼猜想

回顾 问题1：什么叫证明？ - 表明定理为真的有效论证（演绎推理） 问题2：常见的证明方法有哪些？ - 直接证明、间接证明、归谬法、分情形证明、等价性证 明、存在性证明、唯一性证明 问题3：什么是猜想？有哪些有意思的猜想？ - 尚未被证明的可能为真的陈述：费马大定理、四色定理、 哥德巴赫猜想、庞加莱定理、黎曼猜想

本节提要 问题1：什么是集合？ 问题2：集合的基本概念有哪些？ 问题3：如何进行集合运算与集合公式证明？

本节提要 问题1：什么是集合？ 问题2：集合的基本概念有哪些？ 问题3：如何进行集合运算与集合公式证明？

引言 4 口集合论说是现代数学的基础理论 口集合、关系、函数、无穷等 口1900年国际数学大会 口H.Poincare::“借助集合论..可以建造数学大厦..今天我 们可以宣称绝对的严密已经实现了！” 口随后发现了Cantor集合论中的一些悖论 口如1901年的罗素悖论：“要给所有不自己理发的人理 发，不给所有自己理发的人理发” 口G.Frege评论：当大厦竣工时基础却动摇了

引言  集合论说是现代数学的基础理论  集合、关系、函数、无穷等  1900年国际数学大会  H. Poincare:“借助集合论…可以建造数学大厦…今天我 们可以宣称绝对的严密已经实现了!”  随后发现了Cantor集合论中的一些悖论  如1901年的罗素悖论：“要给所有不自己理发的人理 发，不给所有自己理发的人理发”  G. Frege评论：当大厦竣工时基础却动摇了 4

罗素悖论 5 罗素悖论：{x|P(x)}未必产生集合，令 R={x|x庄x,则若R为集合则R∈RR庄R矛盾， 故R不为集合 口考虑一切集合的集合A,这个集合A本身也是集合， 所以属于本身A 口 除A以外的集合构成集合R={x|x庄x},R表示不属 于自已的集合的集合：若集合R属于R,根据定义R 不属于R;若R不属于R,根据定义R属于R。即这样 的集合R不存在。 ▣这与朴素集合论的概括原则相矛盾

罗素悖论  罗素悖论：{𝑥|𝑃(𝑥)}未必产生集合，令 𝑅={𝑥|𝑥∉𝑥}，则若𝑅为集合则𝑅∈𝑅↔𝑅∉𝑅矛盾， 故𝑅不为集合  考虑一切集合的集合A，这个集合A本身也是集合， 所以属于本身A  除A以外的集合构成集合R={𝒙|𝒙 ∉ 𝒙}，R表示不属 于自己的集合的集合：若集合R属于R，根据定义R 不属于R；若R不属于R，根据定义R属于R。即这样 的集合R不存在。  这与朴素集合论的概括原则相矛盾 5

公理化集合论 6 危机的解决： 公理化集合论 在朴素集合论基础上，通过公理对集合加以限制。 例如：ZF公理化集合论的正则公理避免了罗素悖论 正则公理：每一个非空集合x,总包含着一元素y,使 x与y为不相交。 对于集合x,根据正则公理有：{x}里面有一个元素跟 {x}交集为空，即x∩{x}=0,即x庄X

公理化集合论 6 危机的解决： 公理化集合论 在朴素集合论基础上，通过公理对集合加以限制。 例如：ZF公理化集合论的正则公理避免了罗素悖论 正则公理：每一个非空集合x，总包含着一元素y，使 x与y为不相交。 对于集合x，根据正则公理有：{x}里面有一个元素跟 {x}交集为空，即𝒙∩{𝒙} = ∅，即𝐱 ∉ 𝐱

集合的概念 集合没有明确的定义，G.Cantor给出了一种刻划： 吾人直观或思维之对象，如为相异而确定 之物，其总括之全体即谓之集合，其组成此 集合之物谓之集合之元素。 通常用大写字母表示集合，如A、B、C等， 用小写字母表示元素，如a、b、c等。若集 合A系由a、b、c等诸元素所组成，则表如 A={a,b,c,…,而a为A之元素，亦常用a∈A之 记号表之者，a非A之元素，则记如aEA。” (肖文灿译于1939年，《集合论初步》，商务印书馆

集合的概念  集合没有明确的定义，G.Cantor给出了一种刻划： 7 “吾人直观或思维之对象，如为相异而确定 之物，其总括之全体即谓之集合，其组成此 集合之物谓之集合之元素。 通常用大写字母表示集合，如𝐴、𝐵、𝐶等， 用小写字母表示元素，如𝑎、𝑏、𝑐等。若集 合𝐴系由𝑎、𝑏、𝑐等诸元素所组成，则表如 𝐴={𝑎,𝑏,𝑐,⋯}，而𝑎为𝐴之元素，亦常用𝑎∈𝐴之 记号表之者，𝑎非𝐴之元素，则记如𝑎∉𝐴。” （肖文灿译于1939年，《集合论初步》，商务印书馆）

例 8 口1,2,3为集合，“自然数之全体”为集合；但诸如 “甚大之数”或“与P点接近之点”则不能为集 合，因其界限不清 口集合中的元素互异，我们把元素的重复看作一次 出现，如{2,23,3}={2,3} 口Cantor提到的“总括之全体”之“总括”，可由 集合的外延公理和概括原则来描述

例  1,2,3为集合，“自然数之全体”为集合；但诸如 “甚大之数”或“与𝑷点接近之点”则不能为集 合，因其界限不清  集合中的元素互异，我们把元素的重复看作一次 出现，如{2,2,3,3}={2,3}  Cantor提到的“总括之全体”之“总括”，可由 集合的外延公理和概括原则来描述 8

集合的大小 9 口有限集合及其基数 口若S恰有个不同的元素，n是自然数，就说S是有限集合， 而n是S的基数，记作|S|=n 口无限集合 ▣如果一个集合不是有限的，就说它是无限的

集合的大小  有限集合及其基数  若S恰有n个不同的元素，n是自然数，就说S是有限集合， 而n是S的基数，记作|S|=n  无限集合  如果一个集合不是有限的，就说它是无限的。 9

外延公理与概括原则 10 口(ZF)外延公理：集合由其元素完全决定 A=BVxx∈Ax∈B) 故证明集合A=B只需证明x(x∈A→x∈B) 口概括原则：对于人们直观或者思维之对象x的任 一性质P(x),存在集合S的元素恰为具有性质P 的那些对象，记为S={x|P(x)}。从而对任何a, a∈SP(a),例如{1,2,3}={xx=1Vx=2vx=3}

外延公理与概括原则  (ZF.1)外延公理：集合由其元素完全决定 𝐴=𝐵↔∀𝑥(𝑥∈𝐴↔𝑥∈𝐵) 故证明集合𝐴=𝐵只需证明∀𝑥(𝑥∈𝐴↔𝑥∈𝐵)  概括原则：对于人们直观或者思维之对象𝑥的任 一性质𝑃(𝑥)，存在集合𝑆的元素恰为具有性质𝑃 的那些对象，记为𝑆={𝑥|𝑃(𝑥)}。从而对任何𝑎， 𝑎∈𝑆↔𝑃(𝑎)，例如{1,2,3}={𝑥|𝑥=1∨𝑥=2∨𝑥=3} 10