集合及其运算.pptVIP

* * * * * * * * * * * * * 文氏图与数学证明 文氏图不能代替数学证明, 但可以帮助推测结论 例子： (A-B)?(A-C)=A? 充要条件：A?B?C=? 用集合定义自然数 设a为集合, 称a?{a}为a的后继, 记为或a+, 或s(a)。 设A是集合，若A满足下列条件，称A为归纳集： ??A ?a(a?A?a+?A) 自然数集合N是所有归纳集的交集。 因此：N = { ?, {?}, {?, {?}}, {?, {?}, {?, {?}}}, … } N的每一个元素称为一个自然数。 ?记为0，0+记为1，1+记为2，2+记为3，余此类推 再具体一点 记号0表示：? 记号1表示0+： ??{?}={?} 记号2表示1+： {?}?{{?}}={?,{?}} 记号3表示2+:{?,{?}}?{{?,{?}}}={?,{?}, {?,{?}}} 3∪2=? 3∩2=? 2?3? 1?3? 1?2? 2?5? 自然数上的小于关系？ 自然数上的运算 加法（递归定义） m+0=m m+n+=(m+n)+ 乘法（递归定义） m*0=0 m*n+=m + m*n 序关系 a?b iff ?c?N. a+c=b 皮亚诺公理(Peano axioms for natural numbers) 零是个自然数. 每个自然数都有一个后继（也是个自然数）. 零不是任何自然数的后继. 不同的自然数有不同的后继. （归纳公理）设由自然数组成的某个集合含有零，且每当该集合含有某个自然数时便也同时含有这个数的后继，那么该集合定含有全部自然数. 备注：另有4个与自然数相等有关的公理 作业 教材内容：[Rosen] 2.1—2.2 节 课后习题： p. 88（英文教材 pp. 120-121 ）: 22, 33 pp. 96 - 97（英文教材 pp. 131-132）: 18, 40, 48, 57 Zermelo–Fraenkel set theory with the axiom of choice 外延公理 正则公理 分离公理模式 配对公理 并集公理 替代公理模式 无穷公理 幂集公理 选择公理（或，良序定理） ZFC公理 外延公理（Axiom of extensionality） 如果两个集合含有同样的元素，则它们是相等的。 正则/基础公理（Axiom of regularity/foundation） 任意非空集x包含一个成员y，x与集合y是不相交的 ZFC公理 分离公理模式（Axiom schema of separation） 对任意集合z和任意对z的元素x有定义的逻辑谓词?(x)，存在z的子集y，使x∈y当且仅当x∈z而且?(x)为真。 配对公理（ Axiom of pairing） 并集公理（Axiom of union ） ZFC公理 替代公理模式（Axiom schema of replacement） 无穷公理（Axiom of infinity ） S(y)是指 y?{y} 幂集公理（Axiom of power set） ZFC公理 选择公理（Axiom of choice ） 任一非空集合族 (Si)i?I , 均存在元素族(si)i?I, ?i?I. si?Si 或，良序定理（Well-ordering theorem ） 参考： Zermelo–Fraenkel set theory @Wiki * * * * ?? * ?? * * * * * A? ?(A) ? B * * * * * * * 定义一个包含所有平凡集的集合 * * * * 集合及其运算 离散数学－集合论 南京大学计算机科学与技术系 回顾 数学归纳法 强数学归纳法 运用良序公理来证明 递归定义 结构归纳法 提要 基本概念 集合及其描述 集合相等、子集关系 幂集、笛卡尔乘积 集合运算 交并补、广义交、广义并 集合恒等式 集合相关命题的证明方式 自然数的构造 集合的定义 直观的定义 一个集合是一组无序的对象，这些对象称为这个集合的元素或成员。 a?A表示a是集合A的一个成员， a?A 表示a不是A的成员。 Georg Cantor的描述 [English translation] A set is a collection into a whole of definite, distinct objects of our intuition or our thought. The objects are called elements (member) of the set. Na?ve set theory，朴素集合论 集合的描述 外延法：罗列、枚举 V={a,