【Under Construction】一些逻辑话题:递归论初步与哥德尔不完备定理
Abstract. 离散数学与结构作业出了一个题考察对哥德尔不完备定理的深度理解,但是他上课实在是讲得过于粗糙,于是我们被迫完整阅读一遍相关理论。参考资料是 Dirk van Dalen, Logic and Structure(Fifth Edition), Springer(2013) Chapter 8 Godel’s Theorem。
常微分方程(1.5)应用举例
Abstract. 本文讨论几个拥有前置知识初等积分法之后可以解决的问题。解决问题的过程中用到了一些建模技巧和神秘手法,具有一些学习价值。此外后面几个关于生态的模型导出的结果是富有趣味和现实意义的,可供消遣。
一些逻辑话题:如何证明自然演绎系统的一致性、完备性,以及直觉主义逻辑
Abstract. 本文讨论了几个形式系统的语法和语义之间联系的问题,包括证明自然演绎系统的一致性和完备性,以及直觉主义逻辑中不能推导出 $(\neg\neg P)\rightarrow P$。阅读本文需要的对数理逻辑的理解大概与清华大学出版社的“数理逻辑与集合论”前三章一致,如果没有相关知识可以参考这篇笔记。但本文不采用其中定义的公理系统和证明方式,这点在“声明与记号”中有所说明。
一些集合论内容的笔记
Abstract. 因为本学期的离散数学课程讲了一些集合论但是留了很多悬念,所以将暑假时候学习的一些集合论笔记整理之后发出。本篇笔记参考 李文威,代数学方法(第一卷)基础架构,高等教育出版社(2019) 的第一章,刨去了 1.5 Grothendieck 宇宙 一节,因为我也没有看懂。
本文中的观点相比真正的公理化集合论尚属表层,有很多问题在这一层次难以解决,但仅作诸如离散数学、代数与分析之类科目的前置已经足够,仅供参考。
The Schreier-Sims Algorithm
Abstract. 本文将浅谈计算群论中的 Schreier-Sims 算法,该算法的核心思想是将群 $G$ 的信息表示为一列正规子群 $1 = G_1 \subset G_2 \subset \cdots \subset G_k = G$,通过 $G_i$ 在 $G_{i+1}$ 中的截面,回答一些重要的问题如某元素是否在群当中、某给定生成元的有限群的阶数是多少等。
本文的第二节介绍该算法使用的重要技术截面(Transversal)和 Schreier 引理,第三节介绍该算法的核心技术 BSGS,但是很遗憾我们暂时没能看懂如何求解一组 BSGS,只能给出一类大多数应用问题的简单快速的下替算法(参见第 3.3 节)。