4.1 集合集合set是若干对象object或元素element或成员member汇集在一起形成的整体。集合通常用大写字母表示如A、B、C…元素通常用小写字母表示如a、b、c…集合中某个元素被列出多次或元素之间调换顺序并不改变集合体现了集合的互异性与无序性。【补充】该定义对集合的表述是直观的但后来导致了著名的罗素悖论Russells Paradox。该悖论的核心问题是设有一个集合A它包含所有不包含自身的集合那么A是否包含自身显然无论怎样回答均会导致逻辑矛盾。罗素悖论的发现对数学基础产生了深远影响被认为是数学史上的第三次重大危机促使数学家发展更严格的公理化集合论如ZFC公理系统等。必须存在一个底层全集Uuniversal set它可以被明确声明也可以是默认隐含的。全集是当前讨论范围内所有对象构成的集合所有讨论的集合都是全集的子集。常用的全集有实数集R自然数集N整数集Z正整数集Z有理数集Q复数集C等。集合有两种最基本的表示方法列举法roster method将集合中所有的元素逐一写在大括号 {} 中注在列举无穷或数量较多但有规律的项时使用 ... 来明确表示规律的延续描述法set builder通过谓词来指定集合S{x∣P(x)}S 等于所有满足P(x) 的 x 构成的集合【提醒】集合的元素可以是集合。例如对于集合 A{1,{1}} 有1∈A{1}∈A。集合A与集合B相等equal当且仅当∀x(x∈A↔x∈B)记作AB。集合A是集合B的子集subset即A包含于B或B包含A当且仅当∀x(x∈A→x∈B)记作A⊆B。集合A是集合B的非子集当且仅当∃x(x∈A∧) 记作。任何集合是自身的子集。集合A是集合B的真子集proper subset即A真包含于B或B真包含A则有A⊆B但当且仅当∀x(x∈A→x∈B)∧∃x(x∈B∧)记作A⊂B。空集void set / null set / empty set是没有任何元素的集合具有唯一性记作 {} 或∅。空集是任何集合的子集。【例】空集是任何集合的子集断言 x∈∅ 总是假的因此∀x[x∈∅→x∈A] 总是真的所以 ∅⊆A 即空集是任何集合的子集。集合A的所有子集构成的集合即为A的幂集power set记作P(A)则有P(A){x∣x⊆A}。【提醒】某个集合既可以作为其他集合的元素也可以作为其他集合的子集。例如对于集合A{∅,{∅}}有∅∈A∅⊆A{∅}∈A{∅}⊆A{{∅}}⊆A。集合A中不同元素的个数即为A的基数cardinality记作∣A∣ 。如果集合的基数为自然数则该集合为有限集finite否则该集合为无限集infinite。【结论】如果∣A∣n那么。从组合数学角度解释若A有n个元素当构造A的子集时对于A中的每个元素都有“选”或“不选”两种选择。依据乘法原理共有种不同的选择方式每种选择方式对应唯一的子集。【辨析】对于 n∈N 一个有序 n 元组ordered n-tuples或序列sequence或长度为 n 的列表list of length n记作。它的第一个元素是​以此类推。相较于集合有序n元组中某个元素重复出现或元素之间调换顺序会改变该有序n元组。给定一个谓词P与一个论域DP(x) 的真值集truth sets of predicates记作 {x∈D∣P(x)}。真值集本质是满足谓词与论域条件的元素的集合。集合表示与量词结合的简写方式∀x(x∈S→P(x))可简写为∀x∈S(P(x))∃x(x∈S∧P(x)) 可简写为∃x∈S(P(x))4.2 集合运算集合论set theory中的运算子是依据命题演算propositional calculus中相应的运算子来定义的。4.2.1 并集、交集、补集、差集、对称差在全集U的基础上定义如下集合A与集合B的并集union记作A∪B是集合{x∣x∈A∨x∈B}集合A与集合B的交集intersection记作A∩B是集合{x∣x∈A∧x∈B}如果交集是空集则称A和B不相交disjoint集合A的补集complement记作或是集合{x∣¬(x∈A)}集合A与集合B的差集difference或集合B相对于A的补集记作 A−B是集合{x∣x∈A∧}集合A与集合B的对称差symmetric difference记作 A⊕B是集合 (A−B)∪(B−A){x∣(x∈A∧)∨(x∈B∧)}这五种运算与逻辑等价式的联系集合运算符号逻辑运算逻辑等价式并集A∪B析取 (OR)P∨Q交集A∩B合取 (AND)P∧Q补集Ā否定 (NOT)¬P差集A−B合取 (AND)否定 (NOT)P∧¬Q对称差A⊕B异或 (XOR)P⊕Q4.2.2 广义并集与广义交集由于并集与交集满足交换律与结合律可将它们从作用于集合的有序对A,B推广到作用于集合的序列A,B,C…甚至作用于无序的集合族sets of setsX{A∣P(A)}。【补充】集合族X{A∣P(A)}X是集合的集合即X中的每个元素A 均为集合集合P(A) 是筛选出满足条件的集合的谓词。广义并集与广义交集的表示集合族X中所有集合的并集合族X中所有集合的交4.2.3 加法原理加法原理the addition principle或容斥原理the inclusion-exclusion principle如果 A 和 B 是有限集那么∣A∪B∣∣A∣∣B∣−∣A∩B∣。推广到n个集合如果为有限集那么4.2.4 笛卡尔积集合A与集合B的笛卡尔积cartesian product是所有有序对 a,b 构成的集合其中 a∈A 且 b∈B顺序固定记作A×B即A×B{a,b∣a∈A∧b∈B}。笛卡尔积本质是一个集合其内部元素为有序对。任何集合与空集的笛卡尔积均为空集。如果A{a,b}B{x,y,z}则A×B{a,x,a,y,a,z,b,x,b,y,b,z}。【提醒】A×B与B×A一般不相等除非AB或A、B中某个集合为空集。【结论】如果∣A∣m且∣B∣n那么∣A×B∣m×n∣A∣×∣B∣。从组合数学角度解释A有m个元素每个元素都可以作为有序对的第一个分量对于 A 中的每个元素B有n个元素可以作为第二个分量。依据乘法原理共有m×n种组合方式每种组合方式对应唯一的有序对。集合的笛卡尔积为n元笛卡尔积cartesian product of n sets记作是有序 n 元组构成的集合其中即。【提醒】(A×B)×C与A×B×C一般不相等前者的元素为a,b,c后者的元素为a,b,c。4.2.5 集合运算的代数性质定律名称公式表达式交换律结合律分配律吸收律幂等律零律同一律补律排中律矛盾律余补律德摩根律【结论】证明集合恒等式AB的三种方法双向包含法分别证明A⊆B和B⊆A逻辑等价变换法用描述法表示集合A、B将集合运算翻译为逻辑运算使用命题逻辑的等价变换将A、B化简为相同的逻辑表达式成员表法使用类似于命题逻辑中的真值表证明【例】用双向包含法证明(A∩B)∪(A∩C)A∩(B∪C):【例】用逻辑等价变化法证明【例】用成员表法证明(A∪B)−C (A−C)∪(B−C)