离 散 数 学
Discrete Mathematics
第五讲:集合论导引
史颖欢
南京大学计算机科学与技术系
201年9月 8 日
前 情 提 要
证明的本质
逻辑推理的形式结构
常用的证明方法与证明策略
直接证明法,间接证明法
归谬法(反证法),穷举法
空证明法,平凡证明法
构造性证明法,反例证明法
前情提要 2
本讲主要内容
引子:数学基础的几次危机
集合的概念
子集、空集与幂集
集合的运算与集合代数
集合公式的几种基本证明方式
本讲主要内容 3
引子:数学基础的几次危机
19世纪早期,发现数学存在缺陷
Н.И.Лобаче́вский,G. Riemann :非欧几何
A. Cauthy等:分析(微积分及其扩展) 的基础
19世纪后期的公理化运动:去除基于直觉或经验
的朴素概念的模糊之处,使数学严密化
G. Peano ,D. Hilbert :算术与几何的公理化
引子 4
数学基础的几次危机(续)
1900年国际数学大会
H. Poincare: “借助集合论…可以建造数学大厦…今天我
们可以宣称绝对的严密已经实现了!”
随后发现了Cantor集合论中的一些悖论:如1901年
的罗素悖论
G. Frege评论:当大厦竣工时基础却动摇了
基础知识 5
数学基础的几次危机(续)
危机的解决:
公 理 化 集 合 论
引子 6
集合的概念
集合没有明确的定义,G. Cantor给出了一种刻划:
“吾人直观或思维之对象,如为相异而确定之物,其总括
“Unter einer Menge verstehen wir jede Zusammenfassung M
之全体即谓之集合,其组成此集合之物谓之集合之元素。
von bestimmten wohlunterschiedenen Objeckten in unserer
通常用大写字母表示集合,如、、等,用小写字母表
Anschauung oder unseres Denkens(welche die Elemente von
示元素,如、、等。若集合系由、、等诸元素所
M genannt werden) zu einem ganzen”
组成,则表如 = {,,,⋯},而为之元素,亦常用 ∈
—— Georg Cantor
之记号表之者, 非之元素,则记如 ∉。”
(肖文灿译于1939年, 《集合论初步》,商务印书馆)
集合的概念 7
集合的概念(续)
例: 1,2,3 为集合, “自然数之全体”为集合;
但诸如 “甚大之数”或 “与点接近之点”则不
能为集合,因其界限不清
集合