二阶逻辑允许有各种解释;它经常被认为包含在域的
子集上,或在来自这个域到自身的函数上的量化,而不只是在这个域的个别成员之上。例如,如果这个域是所有
实数的
集合,通过如下书写你可以在
一阶逻辑中断言每个实数的加性逆元的存在性
基本定义
二阶逻辑的各种形式的表达力密切的连系于
计算复杂性理论。特别是:
NP是用存在性二阶逻辑可表达的语言集合。 co-NP是用全称二阶逻辑可表达的语言的集合。 PH是用二阶逻辑可表达的语言的集合。
PSPACE是用带有增加的
传递闭包算子的二阶逻辑可表达的语言的集合。EXPTIME是用带有增加的最小不动点算子的二阶逻辑可表达的语言的集合。 在这些语言类之间的联系直接影响了逻辑的相对的表达力;例如,如果PH=PSPACE,则向二阶逻辑增加的传递闭包算子不使它更有表现力。
历史和价值
当
谓词逻辑被
弗雷格(独立的和更有影响力的 Peirce,他提出了术语二阶逻辑)介绍给数学社区的时候,他确实使用不同的变量来区分在物体上量化和在属性和集合上的量化;但是他自己没有去区分出两类不同的逻辑。在发现
罗素悖论之后,认识到了他的系统有些毛病。最终逻辑学家建立了以各种方式做限制的 Frege 逻辑— 叫做
一阶逻辑—除去了这个问题: 集合和谓词在一阶逻辑中不能被单独量化。标准的逻辑的阶数等级就是从那时开始的。
发现了
集合论可以在一阶逻辑的设施内公式化为公理化系统(损失了某种
完备性,但是不至于向罗素悖论那么糟糕),并且真就这么做了(参见Zermelo-Fraenkel 集合论),因为集合是数学的关键。算术、mereology 和各种其他强力逻辑理论可以被公理化的公式化,而不用使用比一阶量化更多的逻辑设施,随着哥德尔和 Skolem 忠于一阶逻辑,导致了对二(或更高)阶逻辑的工作的普遍放弃。
这种舍弃由一些逻辑学家活跃的推动着,最著名的是
蒯因弗雷格自己对概念-物体区别的讨论是非常一致的)。所以要使用一个谓词作为变量就要让它占据只有个别的变量可以占据的一个名字的位置。这种推理被 Boolos 拒绝了。
现状
但是,已经说过在有些数学分支中比如
拓扑学中,需要二阶逻辑的能力来做完整的表达。这方面的工作已经由 Stephen G. Simpson 在逆数学的名义下完成了。已经证明了二阶逻辑不只对表达经典数学的某些重要部分是必须的,而且它也可以用做
模型论和数学基础的工具。
数学命题例子
黎曼猜想是一个二阶逻辑问题
黎曼猜想的:所有 “零点” 是一个集合,零点是这个对象上的函数,按照通常数学中定义,一个n元函数就是从论域A的个体的所有n元组的集合至A的一个映射。当我们用“所有个体”“存在个体”,量词加在论域的个体上,称为一阶量词。“
” 所有函数”,“存在函数”,“所有关系”,“存在关系”是二阶量词,即二阶逻辑。黎曼所说的“所有零点”就是“所有函数”的二阶量词。
黎曼猜想已经超出了G弗雷格建立的一阶逻辑形式系统(即谓词演算),涉及极为复杂的逻辑系统,一般的数学家对此毫无所知。
如果你不能理解二阶逻辑,我做一个比喻,“加速度”不是一个基本量(例如长度或者质量什么的),它是二阶变化率,即变化率的变化率。物理学二阶逻辑问题还有三体问题(月球、地球、太阳)和多体问题,都是无法一次性解决的问题。
黎曼猜想即:所有A(零点)成立的充分必要条件是包含A之中的B(s=x+yi时x=1/2成立)成立。
当所有的主项能够成立必须依赖于谓项成立的命题就是二阶逻辑命题。所有的数学定理都是一阶逻辑问题。
超越数问题是二阶逻辑问题
数学中有所谓“超越数”,就是比无理数还要无理的数,例如圆周率:π = 3.1415926535898....和e= 2.718281828459.....。
为什么人们无法得出一个精确的数值?
割圆术中,不断地利用勾股定理,来计算正N边形的边长,N每增加一个数值(一阶变化率),就会引起二阶变化。因为,它们是二阶变化率,例如只要知道计算圆周率的过程就自然而然知道了为什么。
货郎担问题
千禧年p=np问题就是二阶逻辑问题
弗里曼-戴森在【青蛙和鸟】中写道:持续探索混沌和许多被电子计算机打开的新领域时,数学在变得越来越复杂。数学家发现了可计算性的中心谜团,这个猜想表示为P不等于NP。
这个猜想声称:存在这样的数学问题,它的个案可以被很快解决,但没有适用于所有情形的快速算法可解决所有问题。
这个问题中最著名的例子是旅行销售员问题,即在知道每两个城市之间距离的前提下,寻找这位销售员在这一系列城市间旅行的最短路径。所有的专家都相信这是猜想是正确的,旅行销售员的问题是P不等于NP的实际问题。但没有人知道证明这一问题的一点线索。在赫尔曼-外尔19世纪的数学世界中,这个谜团甚至还没有形成。
这里的问题就是二阶逻辑问题,城市数n每增加一个就是一阶变化率,城市间距离就发生二阶变化率。