离散数学
第一章集合论基础
我们首先讨论集合论基础是基于如下两个原因：一是集合是现代数学的基础之一，也是计算机科学的基础之一,几乎所有数学理论和计算机科学的理论都可以在集合论中找到解释。二是已在引论中讲过，计算机科学面对的是最自然、最一般的实际问题，讨论离散结构是从最自然、最一般的概念开始，离散结构中的一切概念都是从集合出发通过关于集合的性质和表示关系的集合的陈述来确定，或通过操作用构造的方法而得到。通过对这个过程的讨论分析计算机科学的基本思维方法之一——基于离散结构的构造性思维方法，集合是用符号表示的最自然的对象。因此，在这一章要解决如下的两个问题：一是确立将集合作为一个独立的数学对象来讨论的思想和讨论从集合出发构造新的集合的方法，命题法和元数学法在计算机科学中具有普遍的意义，奠定了依据性质和关系确定结构和利用操作来确定结构的基本思想；二是如何从集合论出发构造其它的数学理论和形式结构，又古典的数学理论作为现代数学和计算机科学的基础，而且它是以自然数为出发点的，所以着重讨论自然数和自然数集的构造，以及自然数集的线性结构特性，而且指出利用线性结构的第一归纳法和第二归纳法在基于离散结构的构造性思维方法中的意义，然后略论其它数和数系的构造。换言之，从所有可能的对象的构造中如何选出满足后继结构和稠密结构的对象来，并在其中进行完全归纳的构造性思维。三是集合可以作为在符号处理层面上的最一般、最通用、最自然的计算对象。
§1.1一般集合概念
首先考虑集合的一般概念。众所诸知，要建立一个数学理论，总是利用已知的概念定义新的概念。但任何一种数学理论中，不可能对其中的每一个概念都有严格的定义。比如说，数学的第一个概念就无法定义，因为已没有能用于定义这个概念的更原始的概念了。我们称这种不能严格地定义的概念为该数学理论的原始概念，而称由此原始概念生成的其它概念为派生概念。把“集合”也看作不能严格定义的原始概念。最为原始的东西最具有同一性，最简单的、最少约束的概念为最广泛的概念，才能对这个概念作最普遍的理解，才能使今后所产生的概念具有最自然的普遍意义。除此之外，在确立集合这个原始概念时，只由一个最基本的逻辑原则——排中律所约束，排中律同样具有原始的意义。正因为如此，集合才能作为离散结构和其它数学对象中的最简单、最基本、最原始、而又最广泛的概念。
1.1.1集合及其表示
用直观陈述的方法建立集合和集合的元素这两个概念，建立这两个概念的思维基础是“排中律”，集合和集合的元素的概念是“排中律”所允许的最原始的概念。因为集合是不能严格定义地原始概念，所以它只能对它作直观的描述。这种直观的描述在逻辑上是必须基于排中律的。通俗地讲，排中律是“非此即彼”、“二者必居其一”、“三者必居其一”等意义。所谓集合，乃是由某些可以互相区分的任何客观存在的对象，如数、变量、函数、符号、字母、数字、图、语言、程序或事件等或者没有任何对象，汇集在一起所组成一个整体。在这里我们并不需要排中律的全部内容，集合概念的陈述只需满足可区分性（可识别性）。在汇集客观存在的对象情况下的可区分性有两方面的意义：(1)这个汇集的整体中的任何两个对象，都有一个方法在有限步内区分其相同或不同；(2)任何对象(若干个