
信息与计算科学导论Introduction to ICS
(2026秋) (Fall, 2026)
授课教师 Instructor:仲盛 Sheng Zhong
教材:《离散数学:思维与挑战》,清华大学出版社
Textbook (English version): Mathematical Foundations for Computing and Cryptography.
课程QQ群 QQ group for this class:629429901
关于本课程 About this course.
友情提醒A Friendly Reminder: 教科书中含有一些错误,请看勘误表。There are some errors in the textbook. Please see the Errata.
作业1 Homework Assignment 1 (Due Oct 12)
关于最佳作业讲解奖About Best Homework Presentation Awards
提交你的作业讲解Submit Your Homework Presentation---立刻开始Immediately!
作业2 Homework Assignment 2 (Due Oct 26)
关于例1.8.4中初始段的构造(课本第38页底部)About the construction of intial segment in Example 1.8.4: 参看本图 。See this picture.
关于左恩引理(课本第39页)的直觉解释An intuitive explanation of Zorn's Lemma: 显然,你可以把一个偏序集看成由一些链组成,虽然其中有些链可能只有一个元素。倘若其中任何一条链没有上界,那么显然整个偏序集不可能有极大值。左恩引理恰好给出了以上命题的逆命题,也就是说,倘若每条链都有上界,那么整个偏序集就有极大值。Obviously, you can view a POSET as a collection of chains, although some chains may have only a single element. If any chain does not have an upper bound, then clearly the entire POSET can't have a maximal. Zorn's Lemma is the converse of the above proposition: If all chains have upper bounds, then the entire POSET does have a maximal.
关于左恩引理证明(课本第39页)的直觉解释An intuitive explanation of the proof of Zorn's Lemma: 简单而言,我们在偏序集里制造一个逐渐长大的链,直到这条链变得比偏序集本身还大,从而得到矛盾。具体而言,在链第$\alpha$次长大时,如果$\alpha$是个后继序数,那么我们只需要往当前链里面加一个比所有已有元素都大的元素----为了达到这个目标,我们先找到链的上界。如果上界在当前链之外,那么我们正好把它加进去;否则,我们只需要加入一个更大的元素(其存在性由偏序集不存在极大值的假设来保证)。而当$\alpha$是一个极限序数时,我们只需要取所有以前的链的并集即可。Basically we are growing a chain in the POSET, until it becomes larger than the POSET itself, which is a contradiction. For the $\alpha$th growth, where $\alpha$ is a successor ordinal, we just need to add an element greater than all elements in the current chain---which is achieved by finding the upper bound of the current chain. If the upper bound is outside of the current chain, we just add it to the chain; otherwise, we add an even larger element (whose existence is guaranteed by the assumption that there is no maximal). In case $\alpha$ is a limit ordinal, we take a union of all previous chains.
关于选择公理、良序定理、左恩引理三者的等价性(课本第39页)About the equivalence of the Axiom of Choice, the Well-ordering Theorem, and Zorn's Lemma: 我们已经证明选择公理蕴含左恩引理,而良序定理蕴含选择公理则是显然的(因为只需要取每个集合的最小值即可)。因此,为了证明三者的等价性,缺失的唯一一环为左恩引理蕴含良序定理。我们在这里为感兴趣的同学提供了一个证明。We have shown that the Axiom of Choice implies Zorn's Lemma, while the Well-ordering Theorem obviously implies the Axiom of Choice (because we can simply choose the minimum of each set involved). Therefore, to show the equivalence of the three propositions, we only need to prove that Zorn's Lemma implies the Well-ordering Theorem. Please click here to find a proof.
关于定理1.8.1的往返法证明(课本第41页最后一行至第42页)About the back-and-forth proof of Theorem 1.8.1: 参看本图 。See this picture.
作业3 Homework Assignment 3 (Due Nov 15)
课程竞赛规则 Rules of in-class Competition
课程竞赛补充规定More about the in-class competition:如果你选择了在任何一次课程竞赛中担任吃瓜群众,那么你就必须参加替代性测验。If you choose to be a mathspectator in any in-class competition, then you have to sit for an alternative test.
竞赛日程安排(暂时) Dates of in-class competitions (temporary):
第一次课程竞赛 12月7日;First in-class competition December 7;
第二次课程竞赛 12月21日。Second in-class competition December 21.
©2026 - 使用 Strikingly 制作
