证明部分：

定义：

• 可判定全序关系：存在一个有限字母表和其构成的无穷输入序列可以表达所有的元素。存在一台图灵机判定这些无穷序列，即对于任意的，可在有限时间内输出和的大小关系。
• 最密的可判定全序关系：1.该关系属于可判定全序关系2.所有的可判定全序关系可以序嵌入（order-embedding）该关系中。
• 前缀：定义为图灵机判定和的大小关系时，读取的关于和的字符串。
  • 严格定义：在可判定全序关系中，将图灵机改写成为双带图灵机模式，输入分别为表示A的纸带和表示B的纸带，在图灵机运行至结束时，所有图灵机读写头经过的纸带格子对应的A与B的原始字符构成的字符序列为图灵机在判断A和B的大小关系时A与B的前缀。
  • 前缀必然是有限序列，因此可以通过前缀构建可数关系。实数可以通过可数序列逼近来定义，完成这种可数构造是完成序嵌入构造的关键点。
  • 一个元素可以对应多个前缀，例如A可以对应。
  • 无妨设,由于与比较时，只有的前缀参与了计算，因此所有具有的前缀的元素都大于。即
  • 记所有前缀构成的集合为

证明：

实数序是可判定全序关系：

利用函数将实数映射到区间上，然后从小数点后第1位开始逐位比较即可。

构造任意可判定全序到实数的映射：

按照如下规则将所有前缀构成的集合进行排列为：

• 字符少的在字符多的前面。
• 字符数相等的，则按照字符的自然序进行排列。

按照如下规则，将元素映射到三进制实数集上：从第位开始，对于任意一位，可以取得第个前缀为

• 若大于所有以为前缀的元素，则第位为。记为
• 若小于所有以为前缀的元素，则第位为。记为
• 以上两点都不满足，则第位为。记为

由于每个前缀都是从两个元素的比较中得来，因此每个至少存在一个以为前缀的元素，故这种映射规则是明确的。

记这个映射为，第位为。

映射是序嵌入的：

序保持：任取及任意一位:

在任意一位上，都是序保持的；因此映射都是序保持的。

单射：对于任意的,无妨设，存在两个前缀。设对应的位次为，则：

因此。

讨论：

关于哲学：

一个古老的哲学命题在于探讨究竟什么是实在，什么是表象。罗素的理念中，我们对于椅子的视觉，触觉等都是表象而不是椅子的实在。不过这会引入一个问题，那就是如果我们排除掉所有表象的手段，我们有什么手段能够来认识事物的实在？因此，在关于什么是实在的问题上，我的想法是，本来就不存在什么实在，实在就是所有表象的集合。这个观点进入到实践性的领域则演变成了等于号这个概念不是天然的，相反，大于号与小于号才是天然的概念。序关系的定义优先于等于号的定义，这就引发了一个问题。既然序关系如此底层，是不是存在一个最密的序列，我们的所有序关系本质上是这个序关系的衍生品？这是提出这个问题的出发点。我们可以通过一些反例来看到等于号是如何影响这个命题的。举个例子，在空间上构造一个不可判定的全序关系：。这个关系的不可判定性在于，我们如何知道两个元素是相等的，特别是无限不循环小数？

关于可计算性：

我们是不是可以有如下的思路：将np问题的解空间映射到一个全序的空间中，然后给出对于任意一个排序系统，不通过遍历即可以找到这个排序系统中第k个元素的构成。基于此，我们寻找排序系统的构造方式，并找到最优化的排序系统，以此来寻找解决np=p问题的路径。在本文中，我们给出了一个利用排序进行编码的系统，可以通过探讨这个编码系统本身的复杂度，编码系统的最优化来做一些工作。