集合论 王智慧 复旦大学计算机学院
1 集合论 王智慧 复旦大学计算机学院
集合代数 ·集合的基本概念 集合的运算 有穷集的计数 集合恒等式
2 集合代数 • 集合的基本概念 • 集合的运算 • 有穷集的计数 • 集合恒等式
集合的基本概念 集合(Set)是一些个体汇集在一起所组成整体通 常把整体中的个体称为集合的元素或成员.例如 方程x2-1=0的实数解集合,1和-1是该集合的元素; >26个英文字母的集合,a,b,…是该集合的元素; 坐标平面上所有点的集合; ,,是该集合的元素; 常用的集合名称 N:自然数集合(本课程中认为0也是自然数) Z:整数集合Q:有理数集合 R:实数集合C:复数集合 3
3 集合的基本概念 z 集合(Set)是一些个体汇集在一起所组成整体.通 常把整体中的个体称为集合的元素或成员. 例如: ¾方程x2 - 1 = 0的实数解集合, 1和-1是该集合的元素; ¾26个英文字母的集合, a, b, …, z是该集合的元素; ¾坐标平面上所有点的集合; , , 是该集合的元素; z 常用的集合名称 ¾N: 自然数集合(本课程中认为0也是自然数) ¾Z: 整数集合 Q: 有理数集合 ¾R: 实数集合 C: 复数集合
集合的表示法 集合有两种常用的表示方法:列元素法和谓词表示法. 列元素法:列出集合中的所有元素,各元素之间用逗号隔开, 并把它们用花括号括起来例如 A={a,b,C,…,z}Z={0,±1,±2,…} 谓词表示法:用谓词来概括集合中元素的属性.例如: B={x|x∈R且x2-1=0} 集合B表示方程x2-1=0的实数解集 ·许多集合可用两种方法来表示,如:B={-1,1} 有些集合不能用列元素法表示,如:实数集合,不能列举出所有 集合中的所有元素 此外,也有用一个圆来表示,圆中的点表示集合中的元素这 样方法称为图示法
4 集合的表示法 z 集合有两种常用的表示方法:列元素法和谓词表示法. z 列元素法:列出集合中的所有元素, 各元素之间用逗号隔开, 并把它们用花括号括起来.例如: ¾ A = { a, b, c, …, z } Z = { 0, ±1, ±2, … } z 谓词表示法: 用谓词来概括集合中元素的属性.例如: ¾ B = { x | x ∈ R 且 x2 - 1 = 0 } ¾ 集合B表示方程x2 - 1 = 0的实数解集. z 许多集合可用两种方法来表示, 如: B = { -1, 1 }. z 有些集合不能用列元素法表示, 如: 实数集合, 不能列举出所有 集合中的所有元素. z 此外, 也有用一个圆来表示, 圆中的点表示集合中的元素.这 样方法称为图示法
集合的元素 ●集合的元素是彼此不同的 ●若同一个元素在集合中多次出现,则只认为其是 个元素 如:{1,1,2,2,3}={1,2,3} 集合的元素是无序的,如 {3,1,2}={1,2,3 ●本课程规定:集合的元素都是集合. 5
5 集合的元素 z 集合的元素是彼此不同的. z 若同一个元素在集合中多次出现, 则只认为其是 一个元素 ¾ 如: { 1, 1, 2, 2, 3 } = { 1, 2, 3 } z 集合的元素是无序的, 如: ¾ { 3, 1, 2 } = { 1, 2, 3 } z 本课程规定: 集合的元素都是集合
集合的元素 元素(E|emen)和集合之间的隶属关系:“属于”或“不属于” “属于”关系记作∈,“不属于”记作g.例如 A={a,{b,c},d,{{d}}}. a∈A,{b,c}∈A,d∈A,{{d}}∈A, bEA, d)eA. b和{d}是A元素的元素 为了体系的严谨性,规定:对任何集合A,都有:AgA
6 集合的元素 z 元素(Element)和集合之间的隶属关系: “属于”或“不属于”. z “属于”关系记作∈, “不属于”记作∉. 例如: A = { a, { b, c }, d, { { d } } }. a∈A, { b, c }∈A, d∈A, { { d } }∈A, b∉A, { d }∉A. b和{ d }是A元素的元素. z 为了体系的严谨性, 规定: 对任何集合A, 都有: A∉A
集合之间的关系 设A和B为集合,若B中的每个元素都是A的元素,则称B是A的子 集合,简称子集( Subset,也可称B被A包含,或A包含B,记作BsA. 如果B不被A包含,则记作B实A 包含的符号化表示为BcA分x(x∈B→x∈A) 例如: NCZEQCR三C. 显然,对任何集合A,都有:AcA 注意 包含关系表示集合之间的关系 隶属关系表示元素和集合之间的关系,但也可表示某些集合之间 关系.如: {a}e{a,{a}}(看作两个不同层次上的集合) {a}s{a,{a}(看作同一层次上的两个集合) 7
7 集合之间的关系 z 设A和B为集合, 若B中的每个元素都是A的元素, 则称B是A的子 集合, 简称子集(Subset), 也可称B被A包含, 或A包含B, 记作B ⊆ A. z 如果B不被A包含, 则记作B ⊆ A. z 包含的符号化表示为 B ⊆ A ⇔ ∀x(x∈B → x∈A) ¾ 例如: N ⊆ Z ⊆ Q ⊆ R ⊆ C. z 显然, 对任何集合A, 都有: A ⊆ A. 注意: z 包含关系表示集合之间的关系; z 隶属关系表示元素和集合之间的关系, 但也可表示某些集合之间 关系. 如: ¾ { a }∈{ a, { a } } (看作两个不同层次上的集合) ¾ { a } ⊆ { a, { a } } (看作同一层次上的两个集合)
集合相等 设A和B为集合,如果AcB且BgA,则称A与 B相等,记作:A=B 若A与B不相等,则记作:A≠B 相等的符号化表示为 A=BAcB∧BcA →Vx(x∈A→>x∈B)∧yx(x∈B→>X∈A) 8
8 集合相等 z 设A和B为集合, 如果A ⊆ B且B ⊆ A, 则称A与 B相等, 记作: A = B. z 若A与B不相等, 则记作: A ≠ B. z 相等的符号化表示为 ¾ A=B ⇔ A⊆B∧B⊆A ⇔ ∀x(x∈A → x∈B)∧∀x(x∈B → x∈A)
真子集 设A和B为集合,如果BgA且B≠A,则称B是 A的真子集( Proper Subset,记作BcA 若B不是A的真子集,则记为:B￠A 真子集的符号化表示为: BcA台 BCAMB≠A ●例如: NCZCQCRCO,但,NN
9 真子集 z 设A和B为集合, 如果B ⊆ A且B ≠ A, 则称B是 A的真子集(Proper Subset), 记作B ⊂ A. z 若B不是A的真子集, 则记为: B ⊄ A. z 真子集的符号化表示为: ¾ B ⊂ A ⇔ B ⊆ A∧B ≠ A z 例如: N ⊂ Z ⊂ Q ⊂ R ⊂ C, 但, N⊄N
空集 不含任何元素的集合叫做空集,记作:φ 空集可以符号化表示为:φ={xx≠x}.例如 {x|x∈R∧x2+1=0}是方程x2+1=0的实数解集,因为该方程 无实数解,所以,其解集是空集. 定理空集是一切集合的子集 推论空集是唯一的. 10
10 空集 z 不含任何元素的集合叫做空集, 记作: φ. z 空集可以符号化表示为: φ = { x | x ≠ x }. 例如: ¾ { x | x∈R∧x2+1=0 }是方程x2+1=0的实数解集, 因为该方程 无实数解, 所以, 其解集是空集. 定理 空集是一切集合的子集. 推论 空集是唯一的