1、离散数学无穷 离散数学论文 袁骁 00804173 物理学院说明：在文章中楷体是数学例子，宋体是正文一 数学总说 数学的建立总体上存在一个规律：先给出最最基本的假设，再由人自带的逻辑体系（不好说是不是真正正确的）给出一些推导，而接下来就是由这些推论和逻辑一起推导出我们想要了解的命题了。 我总是喜欢在学习一个理论之前先考虑这个理论的合法性（也就是我找不出它的矛盾），所以我也想分析一下数学体系的合理性。上面的数学体系有几个关键的地方，错了任何一个都意味着理论的面貌全非：1. 假设的正确和合理性，我总是喜欢用感觉来验证它们，这就导致我可能会阐述不清楚，但我还是要试一下。分析一下最简单的数学理论：欧几
2、里得几何。它给出了5条公理，从最简单的两点可以通过一条直线连接到最有争议的平行公理，它们的理解简直是直接得不能再直接了，我们无法想象违背这些公理时所表现出的情况，但结果却证明当我们给出完全对立的公设的时候却得到了并无法否认的理论，那就是非欧几何。我并不了解非欧几何的原理，我只是想引出一个问题，基本的假设再基本也需要推敲，而如果一味通过自己的感觉检验假设的正确性那绝对是不行的。若一个理论通过采用奇怪的假设，但只要保证了理论的自洽性，就应当承认它的正确性，至于有无用处就另当别论了。 这样一来那是不是数学家都得重新把所有的数学的最基本假设检验一遍呢？事实上数学家干了这么一件事，我知道数学家在20世纪
3、初进行了数学的公理化，用完全的形式推导代替了之前的感觉验证，取而代之的确是更加基本的假设和模型，而我又非常不幸地没有研究过这些模型，所以也无法得知它们的正确性。但是问题依然存在，即使我无法得知它们的具体形式，但是我也知道我还是无法完全验证它们是否正确，因为我无法验证我的验证理论是否正确，可恶的上帝就用这个循环给了我们一个最大的难题，他用他残忍的怜悯造就了我们，却又将我们丢到了无尽的黑暗当中，而我们用那可怜的智慧所点燃的星星之火发出了一点光亮，却仍无法看清世界。（我不信上帝，只是用这么一个词来说明人类所处的困境） 回到了原先的论点，我明白了我无法验证假设的合理和正确性，但是人的伟大就在于人不服输
4、，我们可以先从世界的经验中提取最基本的假设，而由最基本的假设作为基础来完成我们的研究，或许是不完善的，但是它确实符合我们生存的世界的，而事实证明这很成功。 2. 人自带的逻辑的合理性，我的朋友曾经跟我说加入我们建立另外一套逻辑体系会不会得到更加优化的理论体系呢？首先我不排除这种可能性，但是我并不对此报任何希望。理由很简单，假如可以的话为什么没有人去做呢？当然这只是一个说辞，我还是想好好地说一下这个问题，而这也正好回到了本文的一个中心：逻辑的分析。 首先分析为什么不建立其它的逻辑体系：提出这一点的人的确很有想法和创造力，为什么人要提倡创造力呢，其实是因为人还没有完全搞懂一个问题或者人无法搞懂一个
5、问题，所以人需要打破传统观念的束缚假设一些ridiculous的观点，因为传统观点并不是完全正确的，所以这就保证了新观点了可行性。但是在逻辑这个词上，我并不提倡创新。因为首先，其实逻辑完全是人的内在的正误判断器和运输器的结合（把人当做电脑了），而这两个东西其实都是人在一生的成长当中建立起来的，也就是说外界的因素决定了逻辑（当然也包含一点人本身的因素，把人也纳入整个环境因素就ok了），而本来万物的本性就是人无法探知的，人的传统方法就是通过自己的感官得到信息，再由大脑处理信息和利用信息，把人加入整个环境因素，也就是逻辑其实应该是符合这个环境的一个解释。而如果要建立其他的逻辑体系的话，那么就应当包含
6、已知的体系或者可以推出现有的体系，而新体系所带来的新的推论只可能在思考上简化而不会带来内容上的增加。因为即使增加了新的内容是无法由原有体系推出的，但是由于原来的体系是由外界环境所构造的，那么也就是说新的内容是无法由外界环境所推导出的（不然新增的内容就可以由原体系推出，就和其是新内容矛盾），那么这些新推导出的内容是不是可以说成是对我们毫无意义呢！例如：我们假设命题的正确性有3中可能性，A，B，C。A代表对，B代表错，C代表新的逻辑符号（其意义像虚数i一样）也就是C对于我们是毫无意义和不可理解的，而由它推出的理论中所包含的C呢，对于我们也是毫无意义和不可理解的，把所有的C都去掉之后，发现和原理论是
7、完全等价的。 可是我却自己举出了一些反例：数学的理论建立中总是感觉越是高级的理论给出问题的解释越是深刻，例如我们无法用初等数学解决1+这个级数，但是却可以由高等数学完成，显然上面的级数值存在是一个事实，而无法由基本理论解出和可以用高等理论解出也是事实，那么其中的矛盾是什么呢？在于高等数学的基本假设：极限假设。原来其实并不是建立了新的理论体系，而是新的假设，表明上新的假设带来了新的生命力，和更强的推导能力；本质上，新的假设规定（涉及）了之前没有定义的无穷，给其计算级数带来可行性（因为级数涉及到了初等数学么没有涉及的无穷概念）。这正是数学发展的范式，但是逻辑却不应该是这样的。对于逻辑，如果是等价代
8、换，那么显然是没什么意义，只可能是变换了一种说明方式，并不会提供新的理论依据，而人作为进化物种，我相信选择的必然是最简单自然的逻辑体系。而若在逻辑里面增加了新的内容，那么它必定是极其抽象和基础的概念，因此对于现实问题的研究基本没有任何贡献，它带来的只会是繁琐的换算和现实化。 纵观数学逻辑，我总是很少发现说谁建立了新的逻辑体系，其实，既然人要做理论，人就应当用自己自带的逻辑体系，建立了新的逻辑体系是麻烦而琐碎的，但它并不一定是毫无意义的，或许当数学需要更加抽象的概念时这就成了大势所趋。我们并没有什么优越的，上帝把我们关在黑暗的世界里，我们也只有用光明一点一点地照亮才知道可不可以，而这也是人无法避
9、免的。 3. 剩下的就很好说明了，就是这种链式理论发展模型是不是可行的（我只讨论了可行性，而不是优越性）。事实证明是可行的，人们总是习惯于接受下面的假设：与同一事物相等的事物相等；相等的事物加上相等的事物仍然相等； 相等的事物减去相等的事物仍然相等；一个事物与另一事物重合，则它们相等。而这也是可行的，在于一个很简单的逻辑或者方式，我们可以不厌其烦地每次都用最基本的假设来推出理论，但是其实当把一些非常常见的推导做好标记放在一起的时候，事情就得到了简化。而这也是还原法的本质，其在于用毫不相干的标记代替重复出现的事物，而若我知道这个代换是可逆的，是不是就是说我可以做这么一件事呢。好比说有A-B,B-
10、C,C-D,D-E，（A是基本假设）若我假设已经做了A-B,B-C,C-D也就是假设承认D的正确性，我完全可以直接用D-E得到E的正确性，而这就是整个代换过程的原理所在。二 集合在高中的时候就学过了集合了，当时理解集合比较简单，觉得集合就是一个容器，把一些东西放在一起，也没有怎么深刻地理解它，只知道集合的简单运算，竟然就学过来了，而这常常是应试教育的悲剧！因为我没时间来考虑这个事情，并且考试不考！而现在，我对集合有了更加深刻的理解。集合的作用其实很简单的，就是把一些具有相同性质的东西放在一起。而这个解释又是那么笼统，集合的作用仅仅是这样么，把那句话好好分析一下，发现其实集合放的事东西，其实体现
11、的是性质。集合有两种，简单的就是把一堆毫无意义的东西放在一起，可以把它当做一种简单的标记，而更加深刻的其实应该还是集合所体现的它所包含的数据所体现的性质，如果我知道了一个很好的方式来描述这个性质，我当然可以用这个它来代替原来的集合（元素列举的集合），这也就是集合的列举法和描述法，而它们所体现的本质却是那么不相同。所以，集合的本质应该是体现性质，那么我着重来分析一下这个。最简单的，如果一种性质的拥有者只是有限的元素，那么把这些元素放在一起，就构成了这种性质的表述了（这个等价很明显）。而对于无穷的元素呢？若是还用刚才的方法，把所有的元素都放在一起（理论上是可行的），那么我们也会得到一种性质的理论描
12、述，尽管它没有什么实用性，但是它却是一种实实在在的性质描述。而常常，对于一种性质我们喜欢用它的定义式来写出描述关系，只要满足了它的定义式，那么显然就满足了这种性质，那么集合就是这种性质的体现了。其实对于简单的性质做集合的描述没有多大的体现出集合的作用，例如x| x0 这个和它本身的意义没有什么区别。但是集合的作用远不止这种简单的定义，例如，它可以定义二元关系：（x，y）= x y ，或者二元序关系：(x，y）= x x, y 。由于集合是很好的性质描述，所以用集合定义性质对于性质的应用和验证是很方便的，这些将在关系里面还有所提及。总而言之就是：集合的重要作用是它是一种性质的描述，最简单的我们可
13、以用列举法把所有的满足此性质的元素列举出来然后放在一起规定为一个性质集，而更常规的是用数学的语言或者性质的定义来用集合描述性质。集合的作用在于描述性质，那么是不是所有的数学性质都可以用集合描述呢？这是一个值得深思的问题。很明显，之前的说明中对此问题的回答是肯定的，因为只要把满足此性质的所有元素放在一起，然后命名为一个性质集，就得到了此性质的集合描述，但是这种做法是不是一定可行呢？集合难道就是最基本的定义，它可以描述一切么？问题的最简单过渡应该是考虑集合是不是可以表示集合自己。为什么呢？因为在以前的大多数理论（我学过的所有理论）中，最基本的定义和假设可以推导出很复杂的命题，但是它绝不会推导出自己
14、的正确性或错误性（除开悖论，至少推出正确性是没有的）。而对于集合，如果它可以说明自己，那么只要我假设集合的正确性，然后集合又可以说明集合自己，也就是定义了自己，不就是证明了集合的假设的正确性么！也就是说，只要我承认了集合的正确性，那么我就可以推出集合是正确的，这是在其它数学理论中没有的现象。那么结论就是集合并不可以表示集合自己，也即是说，在集合表示自己的时候一定有相关的关节处了问题，接下来我就分析这个问题。反证法：假设存在那样的集合A，使得A=B| B是任意集合，我希望推出矛盾。首先需要注意一个问题，对于无穷集合，如何确定两个集合相等呢？我采取的办法是验证它们所表达的性质是不是相等的，只要它们
15、所描述的性质是一样的（也即是两个所包含的元素都具有相同的性质），我们就说集合是相等的，不过之后的分析不会用到这一点。要推出矛盾当然是要利用这里的任意性了，取A的幂集P（A），由定理知道：Card(P(A) card(A) ,而又由于A的定义可知A是包含P(A )的，所以必然有Card(P(A) card(A),等号是保守估计，所以矛盾出现了。也就是说集合不可能表示集合这个概念！这也是对于数学一般理论的性质的符合。但是在上面的证明当中却也有值得商榷的地方，用集合的势来说明这个问题。P（A）的势必定是不大于A的势的，而反之呢？就需要考究定理：P（A）的势大于A的势的证明了。仔细地分析一下书上的证明
16、过程，会发现证明的本质其实是用到了罗素悖论，也就是构造了一个罗素悖论集合来达到证明的，那么也就是说无穷集A的矛盾之处可以由罗素悖论的矛盾导出，因此仔细地分析罗素悖论可以对无穷集A的分析得到更加细致的结论，但这里就不说明了。三 关系和函数 关系是数学研究的一个很重要的话题，因为它是一个如此简单的概念，而以至于无论数学的那个角落，总是可以找到它的影子。 关系的概念其实是一总自然的思想体现，因为世界存在物体，那么物体与物体之间的作用就可以理解为关系，而研究关系便是无论数学还是物理等众多伟大学科的重要主题，这里也简单地分析一下关系的基本因素。 关系从某种角度来说其实就是性质，而只不过是体现在两个或者多
17、个物体之间的性质，体现性质的东西总是可以由集合来表示的，所以关系也是可以用集合来表示。简单的二元序关系可以写作：(x，y）= x x, y ，但这种表示其实只体现了序的本质，并没有涉及到关系的自身概念，所以要讨论关系则就需要具体的关系定义，笼统地当然可以写作一个 x y，y=f（x） ，而这里用f（x）来表示只是一个记号罢了。 关系的最简单的也是最基础的应用就在于函数，函数是映射的体现，其实就是一种特殊的关系描述，这种特殊的序关系所具备的特点有：有序，单一，确定而研究这种简单的关系便是数学的重中之重了。 作为关系的一种特殊描述映射，它所体现出的性质值得研究。 映射的描述方式一般来说是函数，将一
18、个集合通过法则f对应到另外一个集合，这是见过的最多的方式。下面用图形的映射来代替函数的映射，并说明其等价性。 考虑将一条线段映射到一个曲线段，如图所示，由于线段可以和实数构成对应关系，所以函数的表示通过直线到曲线的映射来完成，而事实上这正是直角坐标系的作用。接下来将问题变成曲线到曲线的映射，这样其实问题就转化成了二维函数关系，或者说是复变函数，而复变函数所体现出来的复杂性是远比一元函数高，这当然也是可以理解的。 其实这里只是想说明一个观点，就是函数的思想。对于表示对应关系，函数仅仅是很有限的方式，对于集合到集合的映射，但是其他的很多关系也常常可以转化成函数，这就是函数思想。函数思想总是希望通过
19、y=f（x）的关系来表示对应过程，而通过分析其过程得到相关问题的解决。 而解决映射问题并不总是可以通过函数来解决，当遇到一些映射关系并不是很明确的一些问题时，也可以通过分析或者其他方式来解决问题。（当然下面的问题可以通过变分来解决） 例如要解决这样一个问题，将有限长的线段围成一个闭合曲线，问最大的面积。 这可以算是一个映射关系，但是解决的是像具有某种性质情况下的映射，而并不好通过简单的函数来解决，因为其实我需要找的就是这个函数，便是泛函的问题，但是也可以通过调整分析来解答。（下面的具体做法可以略去不看） 如图所示：先解决如何找到连接A、B的曲线l和AB围成的图形的面积最大值，使得l的长度不变。
20、当然先考虑简单的线段情况，也就是找到最小的折线段（只有两条）使得其面积最大。这样，问题就转化为了（2）中求椭圆上一点使得和A、B所连接的三角形面积最大。这个问题比较简单，当然是对称的情况了。所以就得到临时曲线AC1B，重新取A1、B1，这样又可以用上面的方法找到新的C2，所以只要没有得到稳定的映射图形，那么这种变化就是可以进行的，那么是不是有解答方案呢？必然是有的，就是圆了，而圆就刚好满足了稳定情况。 上面这个问题说明了解决映射问题的多样性，映射问题作为一种基本的问题往往是很复杂的，就例如希望将多维图形映射到多维图形，这样就对应到了相关的多维函数，而多维函数的复杂性是可想而知的。 映射是一种变
21、换，是性质的关系所以映射相当于有三个重点（差不多可以理解为函数的三要素），而往往知道其中一点而讨论剩余的就会得到有意思的问题了。 因此映射（对应）作为性质的关系，其意义是重大的，不仅有函数关系（简单的线对应），还可以是图形的对应关系，例如拓扑学的一些内容。而映射往往也是解决问题的手段，应为映射经常带来一些很有意思的性质变换，也是一种问题的转换，常常是很有效的手段。（最简单的例子就是高中学过的数形结合了）。 总之关系是很重要的一个数学概念，是非常基础的数学内容，这里也只能十分笼统地分析一下了。四 无穷 无穷是一个很有意思的东西，高中的时候思考的最多的就是它，总感觉无穷带来的就是逻辑的错误和荒谬的
22、结果。举个简单的例子吧：取自然数数列1，2，3和偶数数列2，4，6考虑他们两个数列的个数的时候会得到一个矛盾。首先当然可以建立自然数列到整数列的对应，自然数x对应到偶数列的2x，那么既然这是一个一一对应，那么就可以说它们的个数是相等的；而另一方面，自然数列个数总应该是偶数列的2倍吧，矛盾出在哪里呢？ 以前的想法是无穷的相等和小数（就是有限的数）的相等时不一样的定义。其实人的脑袋中的确只可以接受小数的大小和相等的比较，而对于无穷，可以说完全是人的思维抽象，这不是可以由现实数（也就是有限数）的规则来统一的，既然不是现实中的东西，所以就应当建立新的规则，而作为数学抽象的一般意义，就应当满足它的合理性
23、，当然这就是现在学的无穷理论了。 想了这些，我对待无穷总是怀着小心的态度，不敢用最基本的想法来思考它，而总是想着合理性，而我对无穷的观点则是，只要符合逻辑的合理性，那么就应当是正确的，因为无穷本来就是一个思维的抽象，而作为思维抽象，它就应当符合人的最基本的思考逻辑。所以，在下面的讨论总，我尽可能地用合理性代替显然的假设（当然，其实所谓的合理性也就是表面上找不出问题罢了，毕竟我没学过数理逻辑，所以我也不知道哪些最基本的假设是可以接受的，至少我感觉没错的我就用）。 接下来要来分析一个问题：设a=，b= 然后证明a、b之间没有其他的基数，也就是说：设存在集合A、B和基数a、b使得a=card（A），
24、b=card（B），则证明的是不存在集合C使得其card在A和B之间。 证明不存在问题，当然是用反证法比较方便了，所以假设存在C使得其card在A，B之间，暂时不考虑在之间的约束，则必然应当有：C和A，C和B不等势。而考虑基数的大小问题就应当是C可以到A有满射，B到C有满射。 总结一下就是问题转化为：不存在集合C，使得其与A和B不等势且C到A和B到C存在满射（或者是a c ，则C和A不等势；（3） 若b=，c，那么c b；（4） 集合C的基数总是可以由集合A的基数的相关函数表示，即存在函数f（x）使得：c=f（a）。 用以上三个引理就可以得到证明：证明：首先有b=，由引理（3）可知，存在函数f
25、（x）和g（x）使得c=f（a），b=g（c）。继续设，所以有GF =。由于对称性可以设G ，由无穷数的运算可以知道，所以f（a） ，由引理（3）推出和已知矛盾。 证毕。分析：先不考虑四个引理的正确性，从证明的过程出发来分析一下这个命题。 这种证明方法的要点在于用函数的方法结合基数的运算代替了基数的大小和等势的概念。尽管引理（1）没有用到，但是为了说明清楚其中的逻辑，还是很有必要写出来的。可以这么看： 分析基数到基数的函数，可以发现形如f（x）=总是使得两个基数相等，而形如f（x）= 的函数则总是使得两个基数不等势（a，b为非无穷数）。而要证明的就是其中不存在其他类型的函数了，这个分析是简单为
26、轻松的，所以可以得到问题的证明。 因此，问题的关键在于引理（4）是否成立。这是值得深思的，为了方便，我从先后顺序证明引理。引理证明：（1） 由书上93页的定理5.24可以推出：a=（一下讨论的a都是无穷基数，m、n都是自然数），所以可以推出a=（两边同时开方n次，其实这里需要开方的定义），从而a=，所以a=（、为有理数），而需要证明实数的正确性就需要极限的步骤了，在这里省略去。所以成立（2） 有自然数到实数集的关系对应可以知道（2）的正确性是很明显的。或者因为C是和P（A）等势的，而A和P（A）必定不等势，同样也可以得到证明。（3） 这个引理其实很显然，只是为了说明的需要给出。（4） 剩下的便
27、是最关键的证明了，只要这个引理是正确的，那么希尔伯特第一问题就解决了，多么令人兴奋的时刻啊。 简单想一下便发现，其实这个命题是在是太简单了（不是容易证明，而是太基础了，感觉似乎没法证明似的），那么便应当从基本的定义出发证明。转化一下命题，将一个集合设为自然数集，寻找其它集合到它的对应，从而根据对应来得到函数。下面简单分析一下： 函数f（x）的定义应该从对应得到，其中的道理可以从自然数到自然数、有理数、实数的对应（不是一一对应）来得到一些启示：（a） 先考虑将自然数对应到自然数自己，这个对应是在是太简单了，就a到a吧：所以有函数f（x）= x，因为一个数对应一个数，所以认为数的个数是相同的；（b
28、） 接下来是自然数到有理数，把整个有理数域分解到 m，m+1，先让每一个域对应到自然数m，接下来将每一个 m，m+1一一对应到自然数，所以可以认为f（x）=，因为认为有理数到自然数是做了两次一一对应才得到的；（c） 然后对于自然数到有理数，可以想象成有理数的构造：有理数的每一位都是由10位构成的，所以可以得到f（x）=，因为从小数点后第一位开始，每一位都有10中选择。 分析发现，其实上面的对应很杂乱无章，都不是简单的数到数的对应关系得到，而是一种特殊的映射关系，为了方便分析，必须将这种对应关系统一化。 基数c到a的关系f（x）的标准决定应该就是基数的关系，但是可以扩展开这个概念，就是如下的定义
29、： 设集合A的元素为a1，a2，a3 将集合A对应到集合B中去，a1对应B中的m1个数，a2对应B中的m2个数，以此类推，所以通过这种映射的构造方法，认为B的基数b=m1+ m2+ m3+ 对于上面的（a）中，最简单的就是自然数m对应到m自己，那么显然可以得到f（x）= x。若考虑偶数到自然数的映射，可以建立为：m m,m+1，这样，可以认为f（x）=2x。而已经知道了自然数到偶数是可以建立一一映射的，所以认为函数f（x）= x和g（x）=2x的效果是一样的。（b）的分析也是可以进行的：把自然数集合映射到有理数集0，1，然后可以建立集合集m，m+1到自然数的映射，这样就可以认为自然数集合的每一
30、个元素都映射到了自然数集个数的元素，也就是f（x）=。同样，由书上建立的一一映射可以知道，函数f（x）=和f（x）= x起的作用是相同的，所以认为他们是等价的，而这些都是引理1的更好的说明。也即是说函数f（x）=（，为非无穷数）所对应的基数都是相等的。 考虑（c），其实完全可以用上面相同的方法来得到f（x）的说明。但是这并不是想要的结果，还是希望像定义一样得到元素到几个元素的对应，这样对之后的类比才会有帮助。而最简单的做法就是将先对应到，因为可以认为数是用二进制表示的，接下来将用二项式定理展开（先不考虑正确性），这样就可以得到每一个元素对应的就是相应的展开之后的那一项了。尽管在展开这个地方很是
31、不严格，但其实这只是一个说明，只是想说明同样可以通过元素对应的方法来做到函数f（x）的解释。 通过前面的分析，现在思路也要清晰一些了，接下来要做的就是怎么解决将任意一个集合A的基数a通过对应的方法对应到集合C的基数c中，得到对应关系c= f（a），而手段则是通过建立元素到元素的多对应关系。 真正在证明这个问题的时候发现其实手段还是很少，只能通过简单的说明性验证。 首先，任意一个函数f（x）（在与之间，、 0），总是认为它可以成为一个集合到另外一个集合的基数对应关系，为什么呢？应为从最简单的自然数到其他集合对应出发（其实也只需要考虑自然数集到小于有理数集的所有集合的对应关系），自然数到自然数集的关系是自己到自己的对应，得到函数f（x）= x，自然数到有理数的对应可以通过每一个数对应自己数字大小那么多个数来得到f（x）=，而到最大的实数集，则可以通过上面的映射得到f（x）=，所以在x到之间的函数，总是可以通过调整每个数对应的数字个数的多少来得到自然数集到一个特定集合的对应，尽管这是很自然的道理，但是其逻辑关系似乎并不是很
