固定点算子

我们知道，哥德尔用编码的方法在数学语言中巧妙地实现了自指，而且不会带来矛盾。哥德尔的方法用到了一阶算术，如果只用命题语言，如何实现自指呢？本文讨论这个问题。

苹果在桌子上，并且梨子在桌子上。这句话我们用p∧q表示。

而有的命题用符号表示比较困难。比如，本语句成立，并且梨子在桌子上。这句话出现自指，本语句指的是“本语句成立，并且钱包在桌子上”这句话。“本语句”是否成立，取决于“本语句成立，并且钱包在桌子上”是否成立。两者的逻辑性质是相同的。

那它用符号如何表示呢？它肯定是：__∧q。关键是我们在上面的空白处应该用什么来表示“本语句”？填入不同的命题时，__∧q有不同的性质。我们需要找到命题s，使得s↔s∧q，即s和s∧q具有相同的逻辑性质。这时“本语句”就是s，也可以说s是__∧q的固定点。

我们扩充原来的命题逻辑语言，增加一个固定点算子，使得它对任意命题都能实现自指。

对任一个命题公式 $\varphi$ (p),我们如果想说本语句具有性质 $\varphi$ ，我们用fix p. $\varphi$ (p)表示“本语句”。在上面的例子，“本语句”是fix p (p∧q)，它有以下的性质：

(fix p (p∧q)) ↔ (fix p (p∧q)∧q)

式子右边表示“本语句成立，并且梨子在桌子上”。

为了避免矛盾，我们需要做一些限制， $\varphi$ (p)中的p前面只能出现偶数个否定号﹁，而不能出现奇数个﹁，即p在 $\varphi$ 中是正出现的。

比如﹁p是没有固定点的，因为p不是正出现。假如它有固定点的话，固定点就是fix p(﹁p)，所以fix p(﹁p) ↔﹁fix p(﹁p)，而这个式是矛盾式，不可能成立的。

   在判断p是否正出现时，需要把p→q变形成﹁p∨q，使得 $\varphi$ 中不出现蕴涵符号→。

固定点算子的语义

还有个任务，我们要给fix p.j(p)赋值，使得fix p. $\varphi$ (p) ↔ $\varphi$ (fix p. $\varphi$ (p)/p)是有效式，即这个式子在语义上总是为真。方法如下：

V(fix p. $\varphi$ ) = V( $\varphi$ (0/p))

V是任意的赋值函数，在给fixp. $\varphi$ 赋值时，其他命题变元可赋任何值，但p的值必须是0。

例子：

fix p (p∧q)，当V (q)=1时，V (fix p (p∧q))= 0∧V(q) =0。V(fix p (p∧q)∧q) = V(fix p (p∧q))∧V(q) = 0∧V(q) = 0∧1 = 0。

当V(q)=0时，V(fix p (p∧q))= V(0∧q) =0。V(fix p (p∧q)∧q) = V(fix p (p∧q))∧V(q) = 0∧0 =0。

所以V (fix p (p∧q)) =V (fix p (p∧q)∧q)。

现在需要证明：

V (fix p. $\varphi$ (p)) = V ( $\varphi$ (fix p. $\varphi$ (p)/p))

分两步证明。第一步先证明V ( $\varphi$ (0/p))≤V ( $\varphi$ (1/p))，即赋值函数相对自变量p是单调增的。对 $\varphi$ 的结构进行归纳可证明这一点。

第二步证明等式成立，分两种情况讨论：

当V (fix p. $\varphi$ (p))=0时，V ( $\varphi$ (fix p. $\varphi$ (p)/p))= V ( $\varphi$ (0/p))，而这就是V (fix p. $\varphi$ (p))的定义。所以在这情况下等式成立。

当V (fix p. $\varphi$ (p))=1时，根据定义，V ( $\varphi$ (0/p))=1，而V ( $\varphi$ (0/p))≤V ( $\varphi$ (1/p))，所以V ( $\varphi$ (1/p))=1，所以等式成立。