数学联邦政治世界观
超小超大

决定性公理与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),接着再看更方便。

相关小说

快穿之芙蓉帐暖 连载中
快穿之芙蓉帐暖
玉樱樱
(快穿+系统+虐渣+爽文+演戏+大美人+渣女+男主碎片)渣女梨依儿快穿到各个小世界围绕在各个大佬周围。完成任务后就不甩他们了,主搞自己的事业......
3.2万字5个月前
(科幻万人迷)渣女改造系统 连载中
(科幻万人迷)渣女改造系统
吃人不放盐23
—这是一个社会潜在型人渣,被一个莫名奇妙的系统培养成社会栋梁最后成神的故事—林一览一直都知道自己不是个好东西,但从来没有想过,自己会因为渣得......
1.7万字5个月前
镜中渊:忘语 连载中
镜中渊:忘语
晨亦love
在这无限流里存活下去
2.2万字5个月前
前生今世之孽情 连载中
前生今世之孽情
如一念安
《梦中信:前生今世》又名《前生今世之孽情》
8.2万字2个月前
快穿之我在游戏里当大佬 连载中
快穿之我在游戏里当大佬
子非珏
南宫陌离和君沐泽从小是青梅竹马,全球有些人手腕上有倒计时而消失,他们到家KW游戏世界里,一路上一起和伙伴们通关副本,最终得到了真相……(南宫......
0.6万字3周前
慕容归零 连载中
慕容归零
丽夏
慕容前世嫁给了蔡飞,蔡飞家暴直到而死都不明白是,原来蔡飞和慕楠早就勾搭在一起了。原来墨卿才是真正的爱我的,把她抱在怀里哭。蔡飞和慕楠你把墨卿......
6.6万字4天前