二阶逻辑

编辑 锁定
数理逻辑中,二阶逻辑是命题逻辑或一阶逻辑的扩展,它包含在谓词位置上(而不是像一阶逻辑那样只能在项的位置上)的变量,和约束它们的量词。所以: 我们可以表达关于 Jones 的二值原理: 对于所有性质,Jones 要么有它要么没有它。
中文名
二阶逻辑
外文名
Two order logic
提出者
弗雷格
应用学科
逻辑学
适用领域范围
学术研究

基本定义 编辑

作为另一个例子,我们用一阶逻辑可以把一个句子/断定写成:
但是我们不能对谓词做同样的事情。就是说,下列表达式:
不是一阶逻辑的句子。但它是二阶逻辑的合法的句子。

解释和运用 编辑

二阶逻辑允许有各种解释;它经常被认为包含在域的子集上,或在来自这个域到自身的函数上的量化,而不只是在这个域的个别成员之上。例如,如果这个域是所有实数的集合,通过如下书写你可以在一阶逻辑中断言每个实数的加性逆元的存在性
但你需要使用二阶逻辑来断言实数的最小上界性质:
并在点的位置插入一个陈述,如果 A 是非空并且它在 R 中有一个上界,则A 在 R 中有一个最小上界。
应用于复杂性理论
二阶逻辑的各种形式的表达力密切的连系于计算复杂性理论。特别是:
NP是用存在性二阶逻辑可表达的语言集合。 co-NP是用全称二阶逻辑可表达的语言的集合。 PH是用二阶逻辑可表达的语言的集合。 PSPACE是用带有增加的传递闭包算子的二阶逻辑可表达的语言的集合。 EXPTIME是用带有增加的最小不动点算子的二阶逻辑可表达的语言的集合。 在这些语言类之间的联系直接影响了逻辑的相对的表达力;例如,如果 PH=PSPACE,则向二阶逻辑增加的传递闭包算子不使它更有表现力。

历史和有争议的价值 编辑

谓词逻辑弗雷格(独立的和更有影响力的 Peirce,他提出了术语二阶逻辑)介绍给数学社区的时候,他确实使用不同的变量来区分在物体上量化和在属性和集合上的量化;但是他自己没有去区分出两类不同的逻辑。在发现罗素悖论之后,认识到了他的系统有些毛病。最终逻辑学家建立了以各种方式做限制的 Frege 逻辑— 现在叫做一阶逻辑—除去了这个问题: 集合和谓词在一阶逻辑中不能被单独量化。现在标准的逻辑的阶数等级就是从那时开始的。
发现了集合论可以在一阶逻辑的设施内公式化为公理化系统(损失了某种完备性,但是不至于向罗素悖论那么糟糕),并且真就这么做了(参见Zermelo-Fraenkel 集合论),因为集合是数学的关键。算术、mereology 和各种其他强力逻辑理论可以被公理化的公式化,而不用使用比一阶量化更多的逻辑设施,随着哥德尔和 Skolem 忠于一阶逻辑,导致了对二(或更高)阶逻辑的工作的普遍放弃。
这种舍弃由一些逻辑学家活跃的推动着,最著名的是蒯因。蒯因推进了这种观点,在谓词语言句子比如 Fx 中,"x" 被认为是一个变量或指称一个物体的名字,所以可以被量化,如"对于所有的东西,情况是 . . ." 。但是 "F" 被认为是一个不完整句子的一个缩写,不是一个物体(甚至不是抽象的物体如性质)的名字。例如,它可能意味着" . . . 是个狗",认为在这种事物上可以做量化是没有什么意义的。(这种立场同弗雷格自己对概念-物体区别的讨论是非常一致的)。所以要使用一个谓词作为变量就要让它占据只有个别的变量可以占据的一个名字的位置。这种推理被 Boolos 拒绝了。

近年来恢复二阶逻辑 编辑

近年来二阶逻辑有某种程度的恢复,由 George Boolos 把二阶量化解释为在同一阶量化一样的域上的复数量化所支持。Boolos 进一步指出句子的非一阶可表达性,比如 "有些罪犯只相互倾慕" 和 "有些 Fianchetto 人进入仓库而没有任何别人陪同"。 这只能用二阶量化的完全力量来表达。(实际上这不是真的,因为一般性的量化和偏序的(或分支的)量化同样足以表达特定类的非一阶可表达的句子而不使用二阶量化)。
但是,已经说过在有些数学分支中比如拓扑学中,需要二阶逻辑的能力来做完整的表达。这方面的工作已经由 Stephen G. Simpson 在逆数学的名义下完成了。已经证明了二阶逻辑不只对表达经典数学的某些重要部分是必须的,而且它也可以用做模型论和数学基础的工具。
词条标签:
科技 理学
谁去过渑池皇宫仙指