决定性公理与0-1原理（番外篇）

决定性公理通常被用于形式化逻辑或数学中，例如在欧几里德几何学中，“任意两点之间可以画出一条直线”和“所有直角都相等”这样的命题被认为是决定性公理。

决定性公理的选择通常取决于逻辑或数学体系的目的和性质，不同的公理选择可能导致不同的体系。

考虑以下的“无限博弈”。

有两个局中人A和B，依次各给出一个自然数，例如设A为先手。

这样，他们就会作出一个自然数的无限序列。

如果这个序列是" 最终周期的"、则 A胜、否则 B 胜（一个最终周期序列就是像 1、56、4、5、8、3、5、8、3、5、8，3，5，8、3、…这样的序列，经过一定步数以后就会停留在一个反复的模式上。

不难看到，B有一个致胜策略，因为最终周期序列是很特殊的。

然而，在博弈的任意阶段，A仍然可以制胜（只要B玩得足够糟糕），因为每一个有限序列都是许多最终周期序列的开始的一段。

更一般地说，自然数的无限序列的任意集合S都会给出一个无限博弈：

A的目标是使得所得的序列是S的一个元素，B的目标则相反。

如果两个局中人之一有一个制胜策略，就说这个博弈是决定性的。

我们已经看到，如果S是所有最终周期序列的集合，这个博弈一定是决定性的，而实际上，对于我们不论怎样来写出的S，相应的博弈也一定是决定性的。

但是结果是确有不是决定性的博弈存在。

不难作出非决定性的博弈，但是构造这个博弈要用到选择公理如下：

粗略地说，可以把所有可能的策略的集合良序化（良序原理是等价于选择公理的），所以每一个前面的策略即前置元（predecessor）的个数总少于无限序列的个数、把这样的序列放进S或其余集，就使得每一个策略都不能成为任一个局中人的制胜策略，决定性公理宣称， 每一个博弈都是决定性的。

它与选择公理矛盾，但是如果把它加进没有选择公理的策墨罗-弗朗克尔公理系统。

它就是一个很有趣的公理。

例如，它事实上蕴含了许多实数集合具有惊人的好性质，例如所有的实数集合都是勒贝格可测集合 。

决定性公理与大基数理论有密切关系。

大基数理论是数学中一个分支领域，主要研究无限集合的大小比较问题。

在大基数理论中，把一个无限集合的大小称为它的基数，常用符号为 ℵ（阿列夫零），ℵ1，ℵ2 等。

在大基数理论中，最著名的结论是康托尔-伯恩斯坦定理，该定理说明任意两个无限集合的基数要么相等，要么存在一个比另一个更大的基数。

另一个重要的概念是连续统假设，它是指不存在一个介于 ℵ0 和 ℵ1 之间的基数。

这个假设目前还没有被证明或证伪，是大基数理论中的一个重要问题。

0-1原理(0-1 Principle)是由美国斯坦福大学著名的计算机教授高德纳(Knuth)提出来的，他在他那本那本堪称计算机科学经典之作的《计算机程序设计艺术》的第三卷:排序与选择中，提出并论证了这个原理。

0-1原理：如果一个排序网络能够正确地对任何0-1序列排序，那么它就能对任意数组成的任意序列正确排序。

这条原理的作用是很大的，为了验证一个n输入排序网络的正确性，我们不必检验所有数字构成的任意长为n的序列，而只需检验 2^n个0-1序列就足以验证排序网络是否能正确排序了。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。