数理逻辑五个部分:逻辑演算、证明论、公理集合论、递归论、模型论
逻辑演算 古典二值外延系统、非古典的构造性逻辑、多值逻辑、模态逻辑、规范逻辑
第一阶段 用数学的方法研究思维的规律
逻辑代数/布尔代数
关系逻辑
如何用数学方法处理古典形式逻辑
古典形式逻辑(源自亚里士多德)
- 每一简单命题分析为只有一个主词和一个谓词;主谓词逻辑
- 使用符号表示命题和推理的结果
- 基本内容是关于三段论结构和假言推理、选言推理的结构等的理论
- 不足:不能包括关系推理、不区别单称和全称命题等
莱布尼茨:表意的符号语言和思维的演算
- 将命题形式表达为符号公式
- 构成一个关于两个概念相结合的演算 $$
布尔代数:构造一个演绎思维的演算
逻辑关系和某些数学运算甚为类似,代数系统可以有不同的解释,把解释推广到逻辑领域就可以构成一思维的演算
构成一抽象代数系统
- 四种解释:一种类的演算、两种命题演算、一种概率演算
关系逻辑与德摩根
提出并研究类似三段论而不能包括在亚里士多德三段论中的推理形式
提出关系命题和关系推理,突破古典主谓词逻辑的局限性
第二阶段
集合论:关于无穷集合和超穷数的数学理论
康托尔
无穷集的分类
“函数展开为三角级数的唯一性”
数学分析中间断函数求积分问题和三角级数收敛性问题
- 从某一区间的所有点分离出另一无穷点集
- 无穷点集的性质各不相同
设给定的集合P,使P的一阶导出集为 P’,二阶导出集为 P’’,v阶导出集为 $P^{(v)}$
- 定义一:P为第二种集合,若 $P’, P’’, …, P^{(v)}, …$ 皆为无穷
- P’ 可不包含与P,但P’’,P’’’,…中的点皆属于 P’
- 定义二:P为第一种第v类集合,若 $P^{(v)}$ 只含有有穷多个点
康托尔的第二种分类法:
- 一切代数实数和一切正整数有一一对应
- 一线段上的实数与正整数没有一一对应
证明了一切代数数是可数的
- 证明了一线段上的实数不可数
- 证明了超越数不可数
- 说明了并非一切无穷集都可数,无穷集是有区别的,有大小的
- 应用一一对应的概念
多维连续统
自然数集和连续统是两个不同的无穷集
康托尔得出 线性连续统n维空间有一一对应 的结果
一维连续统不能和二维连续统有连续的一一对应
n维空间不是更大的无穷
更大的无穷
从已知的无穷集根据确凿的数学运算形成更大的无穷
- 根据序数理论从序数集形成更大的无穷
- 用一集合的幂集形成较原结合更大的无穷
有穷集和无穷集的重要差别在于:在有穷集的情况下,不论其中元素的顺序如何,所得的序数相同;对无穷集,由于元素顺序不同,从一无穷集可以形成无穷多个不同的良序集,得到不同的序数
- 第一数类是一切有穷序数的类
- 第二数类包括其“权”或基数为可数($\aleph_0$)的超穷序数
- 由此逐步上升可得第三数类、第四数类等
从给定序数得出新序数,引入两个构成原则:
- 第一构成原则:对一给定的数,可增加一单位;如从 $\omega$ 可得 $\omega + 1$
- 第二构成原则:给定任一已有特定顺序,但其中无最大元素的集合,可以作为原集合的极限或后继者而得一新数
根据此二原则从 $\omega$ 开始可构成无穷多个序数如 $\omega, \omega+1, …, \nu_0 \omega^{\mu} + \nu1 \omega^{\mu - 1} + … + \nu{\mu - 1} \omega + \nu_{\mu}, …, \omega^{\omega}, …$
- 这些序数的权都是可数的
- 一切这些序数的集合就是第二数类
康托尔定理
利用幂集构成一个比一个大的集合和权
用对角线法证明
- 没有最大的权,即给定任一集合L,总有另一集合M,其权较L之权为强
- 一切只取0或1为值的单值实变函数 $f(x)(0 \leq x \leq 1)$ 的权大于线性连续统的权。 如果把这类函数的权记作f,把线性连续统的权看作c,则f>c
康托尔定理:一集合的一切子集所构成的集合,即一集合的幂集,其权较原集合的权为大
- 没有最大的集合,也没有最大的权
两个系列的权或无穷基数:
- 第一系列: $\aleph_0, \aleph_1, \aleph_2, …$
- 第二系列: $\aleph_0, 2^{\aleph_0}(=c), 2^{2^{\aleph_0}}(=f), …$
良序定理 连续统假设
凡良序即都能比较,若一切集合都能良序,则一切集合都能比较
良序定理:每一集合都能良序
连续统假设:$\aleph_0$和c之间是否还有一无穷数,即 $2^{\aleph_0}$ 是否就等于 $\aleph_1$
实无穷与潜无穷
实无穷论:无穷(在数学中表现为无穷集)是一个现实的、完成的、存在着的整体,是可以认识的
潜无穷论:否认实无穷,认为无穷并不是已完成的而是就其发展来说是无穷的,无穷只是潜在的
有关实无穷问题康托尔的观点:
- 数学理论必须肯定实无穷
- 不能把有穷所具有的性质强加于无穷,无穷有其固有的本质
- 有穷的认识能力可以认识无穷,哲学的无穷和数学的无穷
公理方法的发展
源自欧几里得《几何原本》:实质公理学;所处理的对象(公理的对象域)已先于公理而给定,公理是关于这类对象的认识,表达这类对象的重要性质
到希尔伯特《几何基础》充分发展:形式公理学;基本上也是从某类对象得到,但公理本身并不要求先给定一类具体的对象,可以没有或许多个对象域,表示可能对象域的重要性质和关系
《几何原本》
实质公理系统
23个定义,五条公设,五条公理
- 证明有欠严谨,定义不够恰当
非欧几何
《几何原本》的第五公设(平行公设)并不自明
- 平面上通过不在已知直线上的一点,只能有一条直线与已知直线平行
换之以相反的公设:
- 通过已知直线外一点,不只有一直线与已知直线平行。等价于“三角形三角之和小于二直角”,锐角假设
通过直线外一点,不存在与已知直线平行的直线。等价于“三角形三角之和大于二直角”,钝角假设
- 锐角假设未导致矛盾,与其他公理、公设可能是一致的
射影几何和度量几何
经过射影而不变的空间性质称为射影性质
研究射影性质的几何是射影几何
度量性质经过射影不能保留,欧氏集合和非欧几何都是度量几何
- 可以在射影性质的基础上陈述和定义度量性质,角度和长度;射影几何在逻辑上更为根本
几何基础
具体解决公理方法的一些逻辑理论问题
几何概念的直观意义不作为推导的根据,看重公理赋予它们的各种联系
三种事物体系:点、线和面(没下定义)
相互关系(严格涵义):“在…之上”,“在…之间”,“合同于”,“平行”和“连续”
五组公理:联结公理(8个),顺序公理(4个),合同公理(5个),平行公理,连续性公理(2个)
逻辑理论问题
公理的一致性问题:希尔伯特在实数算术理论中为欧式集合构造一模型(笛卡尔几何),证明欧氏几何对实数算术的相对一致性
公理的相互独立性:希尔伯特利用克莱因的一个非欧几何模型说明了平行公理独立于其它公理
模型方法:若能给出一模型使得对此模型而言,某一公理为假而其它公理皆真,则此特定公理独立于其它公理
逻辑演算
数学的严格性和数学基础问题
弗雷格(德),皮亚诺(意)和罗素(英) 建立一个初步自足的完全的逻辑演算:一个二值外延逻辑的公理系统
完全:包括在此范围内的一切逻辑规律和推理形式;也包括除模态逻辑以外的古典三段论和假言推理
初步自足:以数学的逻辑为研究对象,不能再用数学定理作为推导根据,只能按照少数逻辑原则或语言变形规则进行推导
推理的严格性:不是简单的逻辑错误,主要之点在于数学论证不能以几何或物理直观为依据
弗雷格
分析的算术化最后必然建立在自然数理论之上,而自然数理论的探讨又必然要研究数的概念以及正整数命题的性质
弗雷格严格区分对于命题的表达与断定。命题表达思想
- 明确提出真值蕴涵的思想并指出与日常语言的不同
- 把数学中的函数概念引入逻辑演算从而建立量词的理论
- 构成一个初步自足的逻辑演算,一阶谓词演算
皮亚诺
- 发明一种表意语言,符号简单清晰,易于辨认和阅读
用此语言进行大量数学各分支的命题,说明此语言表达数学思维和内容是足够而可行的
算术公理
罗素
- 建立一个完全的命题演算和谓词演算
- 发展并给出一个完全的关系逻辑和抽象的关系理论
- 摹状词理论
- 悖论和类型论
- “一切不是自己分子的类所合成的类”所引起的自相矛盾
- 悖论产生的根源在于假定:一类事物可以包括本类的整体作为分子
- 简单类型论 把类和谓词分别为不同的类型,不能考虑某一类是否为其本身的分子
- 简单类型论可以排除康托尔悖论和罗素悖论,但不能排除瑞恰德悖论(一切可以用有穷字母来定义的小数)
- 类型支论:同一类型的谓词可以分别为不同的层次,高层次谓词不能再作为低层次谓词看待,否则将造成“不合法全体”,导致恶性循环的错误
- 逻辑与数学
- 无穷公理:若n为一归纳基数,则至少有一n元的个体类。(一个关于客观世界的断定而不是一个思维规律)
- 乘法公理(选择公理):设给定互不相交的子类所构成的一类,其中无一为空类,则至少存在一类,此类和每一子类恰好有一分子相同(与无穷有关的断定,和数量有关的存在假定,而不是思维的规律)
- 单纯从逻辑推不出数学,必须再增加这两个公理
构造主义和证明论
数学基础问题的争论
希尔伯特提出如何论证形式公理系统的一致性的证明论理论,即用有穷方法去论证具有无穷对象域的古典数学的形式系统不可能导致逻辑矛盾
证明论中心思想:如果从符号组合的形式方面考虑,某一组公理都具有某种“均齐性”,且推理规则保留此种“均齐性”,则此组公理构成一无矛盾的系统
H.Poincare(法)的思想:
- 数学归纳法是一种直观的数学思维方法,是对于无穷递进可能性的直观认识
- 数学不能归结为逻辑
- 悖论由于恶性循环
- 没有实无穷
20世纪初数学基础问题:
- 如何解决已发现的悖论和如何进一步保证在公理系统中不出现任何形式的自相矛盾
- 如何理解“数学的存在”
- 有没有实无穷和如何认识实无穷
- 数学的基础是什么
直觉主义 构造主义和构造倾向
构造主义:自然数及其某些规律,尤其是数学归纳法,是数学最根本的和直观(不附带有鲜明的或系统的哲学见解)上最可信的出发点,其它一切数学对象都必须能从自然数构造出来,否则不能作为数学对象
直觉主义:直觉或直接感知是认识的根本来源,是必然性知识的保证(哲学范畴)
构造倾向:致力于构造性数学的研究和发展,不否认非构造性数学的科学性
布劳维尔(荷)的思想:
- 直觉主义的数学观
- 基本上承袭康德的理论,数学来源于“直觉的先验形式”
- 数学的直观主义必然导致构造主义的数学观
- 排中律不普遍有效
- 古典逻辑来源于有穷事物的思维,对于无穷事物不见得适用
- 否认排中律对古典数学的影响很大;波尔察诺-魏尔斯特思定理、戴德金实数连续性定理的证明都是运用了古典的排中律
- 数学对象必须是可构造
- 能具体地给出或者能给出一个可以得到某一对象的计算方法
- 否认间接的存在证明,不承认不能具体给出的纯存在定理
- 直觉主义的逻辑
希尔伯特方案
- 形式化
- 形式公理学的对象及其性质和关系并不先行给定,而完全通过一组公理或假设得到精确的刻画;公理限制了对象域及其中关系的解释,同时还必须包括在本系统里定理的推导过程中所需要的一切前提
- 语法规则:先有一系列关于符号的规定,规定初始符号或称字母表,规定何种类型的符号序列是合式的序列或称公式,规定一些作为出发点的公式或称公理,最后给出如何变换公式的规则
- 语义规则:符号解释的规则
- 必须能在有穷步骤内根据已给定的机械方法判定几个问题
- 一符号是否为本系统的初始符号
- 一符号序列是否合式
- 一公式是否为一公理
- 从一组公式是否可以变换为某一公式
思想或命题是抽象的,语言为思想的外壳,语言必须用符号,而符号是具体的事物,符号序列根据语法规则一步一步地形成,是一个可数无穷集,适用于用有穷观点研究
- 有穷观点
- 古典数学的一致性问题由于实无穷引起,古典的逻辑演算也假定了实无穷,因而在论证古典数学无矛盾时,不能应用以实无穷为前提的思想方法或工具,而只能依赖直观上明显可靠的于古典逻辑和一般数论不同的方法,否则就有循环论证的错误
- 有穷方法:所谓的能行方法,较一般递归为狭
理想元素和理想命题
- 无穷不能在经验中直接验证(在思维过程被嵌入或外推的,不可缺少的),理想元素
- 理想命题以实无穷的存在为前提,现实(real)命题则是有直观意义的
- 如果一理想元素不导致逻辑矛盾,它就是数学的存在
哥德尔定理 数理逻辑发展的第三阶段
过渡时期
希尔伯特提出试图解决数学基础问题的证明论方案:用能行的有穷方法研究包括古典逻辑和古典数学的形式系统,并论证其一致性等
哥德尔定理
完全性定理:逻辑谓词演算公理的完全性
不完全性定理:
- PM及其有关系统中的形式不可判定命题
- 第一不完全性定理:一个包括初等数论的形式系统P,如果是一致的,那么就是不完全的
- 第二不完全性定理:如果这样的系统是一致的,那么其一致性在本系统中不可证
- 直观初等数论不可能完全形式化,形式系统固有的局限性(如何把元数学表示在数学系统本身之中)
一般递归和能行可计算:
递归函数和谓词是能行可计算的或能行可判定的,合乎有穷观点
- 能行可计算理论:
- 一般递归(艾尔伯朗-哥德尔-克林尼)
- $\lambda$-转换演算(丘奇、克林尼)
- 理想计算机理论(图灵)
- 几个严格定义几乎全被证明为相等
数理逻辑发展的第三阶段
证明论、集合论、递归论、模型论
逻辑演算
引用
- 《数理逻辑引论》,王宪钧,北京大学出版社