经典逻辑 classical (Stewart Shapiro and Teresa Kouri Kissel)
首次发表于 2000 年 9 月 16 日;实质性修订于 2022 年 6 月 29 日。
通常,逻辑学由形式或非正式语言以及演绎系统和/或模型论语义组成。该语言具有与自然语言(如英语或希腊语)的一部分相对应的组成部分。演绎系统用于捕捉、编码或简单记录适用于给定语言的有效论证,而语义用于捕捉、编码或记录至少部分语言的含义或真值条件。
下面的章节介绍了典型逻辑的基础,有时被称为“经典初等逻辑”或“经典一阶逻辑”。第 2 节发展了一个形式语言,具有严格的语法和语法规则。形式语言是一个递归定义的字符串集合,其没有意义,或者更好地说,其公式的意义由演绎系统和语义给出。一些符号在普通语言中有对应物。我们将一个论证定义为形式语言中的非空句子集合,其中一个句子被指定为结论。论证中的其他句子(如果有)是其前提。第 3 节建立了语言的演绎系统,以自然推理的精神为基础。如果从论证的某些或所有前提到其结论存在演绎,则该论证是可推导的。第 4 节提供了模型论语义。如果在语义中不存在解释,其中论证的所有前提都为真且结论为假,则该论证是有效的。这反映了长期以来的观点,即有效的论证是保真的。
在第 5 节中,我们转向演绎系统和语义之间的关系,特别是推导性和有效性之间的关系。我们展示了只有当一个论证是有效的时候,它才是可推导的。这个愉快的特性,称为健全性,意味着没有推导会从真前提导出一个假结论。因此,推导保持真实。然后我们建立了一个逆命题,称为完备性,即只有当一个论证是可推导的时候,它才是有效的。这表明演绎系统足够丰富,可以为每个有效的论证提供一个推导。因此,有足够的推导:所有有效的论证都是可推导的。我们简要指出逻辑的其他特点,其中一些是健全性和完备性的推论。
最后一节,第 6 节,专门对经典逻辑是“唯一正确的逻辑”这一哲学立场进行了简要的考察。
1. 引言
如今,逻辑学是数学的一个分支,也是哲学的一个分支。在大多数大学中,这两个部门都开设逻辑学课程,并且它们之间通常存在很多重叠。形式语言、演绎系统和模型论语义是数学对象,因此逻辑学家对它们的数学属性和关系感兴趣。下面报告的正确性、完备性和大多数其他结果都是典型的例子。从哲学角度来看,逻辑学至少与正确推理的研究密切相关。推理是一种认识论的、心理活动。因此,逻辑学至少与认识论密切相关。逻辑学也是计算机科学的一个核心分支,部分原因是逻辑系统中有趣的计算关系,部分原因是形式演绎论证和推理与计算机科学的哲学之间存在密切联系(参见递归函数、可计算性和复杂性以及计算机科学哲学的条目)。
这引发了关于逻辑的各种数学方面在哲学上的相关性的问题。作为形式语言的性质,可推导性和有效性如何与正确推理相关联?下面报告的数学结果与关于有效推理的原始哲学问题有什么关系?这是解释数学如何适用于非数学现实的哲学问题的一个例子。
通常,普通的演绎推理发生在自然语言中,或者可能是在自然语言中加入了一些数学符号。因此,我们的问题始于自然语言和形式语言之间的关系。在不试图全面的情况下,对这个问题的几个选项进行概述可能会有所帮助。
一种观点是形式语言准确地展示了某些自然语言片段的实际特征。一些哲学家声称自然语言的陈述句具有潜在的逻辑形式,并且这些形式由形式语言的公式显示出来。其他作者认为(成功的)陈述句表达了命题;而形式语言的公式以某种方式显示了这些命题的形式。在这样的观点下,逻辑的组成部分提供了正确推理的潜在深层结构。自然语言中的一段推理如果底层句子的形式构成了一个有效的或可推导的论证,那么它就是正确的。例如,参见 Montague [1974],Davidson [1984],Lycan [1984](以及关于逻辑形式的条目)。
另一个观点,至少部分由戈特洛布·弗雷格(Gottlob Frege)和威廉·莱布尼茨(Wilhelm Leibniz)持有,认为由于自然语言充满模糊和歧义,应该用形式语言来取代它们。类似的观点,由 W·V·O·奎因(W. V. O. Quine)持有(例如,[1960],[1986]),认为自然语言应该被整理,为严肃的科学和形而上学工作进行清理。该企图的一个要求是,整理语言中的逻辑结构应该是透明的。应该很容易“读出”每个句子的逻辑属性。整理语言类似于形式语言,例如,其语法的明确呈现的严谨性和其真值条件。
在这样的观点下,可推导性和有效性代表了自然语言中正确推理的理想化。只要一段推理与形式语言中的有效或可推导的论证相对应或可以被整理,那么这段推理就是正确的。
当数学家和许多哲学家进行演绎推理时,他们有时会引用形式语言中的公式来帮助消除歧义或澄清他们的意思。换句话说,有时形式语言中的公式被用于普通推理。这表明人们可以将形式语言视为自然语言的附录。那么我们现在的问题涉及这个附录与原始语言之间的关系。在附录中明确定义的可推导性和有效性对于一般正确的演绎推理有什么作用?
另一种观点是,形式语言在某种程度上是自然语言的数学模型,就像一组质点是物理对象系统的模型,而玻尔构造是原子的模型一样。换句话说,形式语言展示了自然语言的某些特征,或者是对其进行理想化的简化,同时忽略或简化了其他特征。数学模型的目的是为了阐明它们所模拟的对象,而不是声称模型在所有方面都准确,或者模型应该取代它所模拟的对象。在这种观点下,可推导性和有效性代表了自然语言中正确推理的数学模型(也许是不同方面的模型)。正确的推理片段大致对应于有效或可推导的论证;不正确的推理片段大致对应于无效或不可推导的论证。例如,参见 Corcoran [1973],Shapiro [1998] 和 Cook [2002]。
在这里没有必要裁决这个问题。也许真相在以上选项的组合中,或者可能还有其他正确或最有启发性的选项。我们提出这个问题只是为了给后面的形式处理提供一些哲学的视角。
2. 语言
在这里,我们发展了一个形式语言的基础,或者更准确地说,一类形式语言。再次强调,形式语言是一个在固定字母表上递归定义的字符串集合。形式语言的某些方面与自然语言(如英语)对应或具有类似之处。从技术上讲,“对应关系”并不是形式发展的一部分,但我们会不时提及它,以激发一些特征和结果的动机。
2.1 基本构件
我们从类似于特指术语的构件开始,这些语言项的功能是指代一个人或物体。我们称这些术语为术语。我们假设有一组个体常量。这些常量是罗马字母表开头附近的小写字母,可以带有或不带有数字下标:
a,a1,b23,c,d22,等等。
我们设想存在无限个个体常量。在当前系统中,每个常量都是一个单个字符,因此个体常量没有内部语法。因此,我们有一个无限的字母表。这可以通过将常量如 d22 视为由三个字符组成,即小写字母 "d" 后跟一对下标 "2" 来避免。
我们还假设存在一组个体变量。这些是小写字母,接近字母表末尾,可以带有或不带有数字下标:
w,x,y12,z,z4,等等。
在普通的数学推理中,术语需要满足两个功能。我们需要能够表示特定但未指定(或任意的)对象,有时我们需要表达普遍性。在我们的系统中,我们使用一些常量来扮演未指定引用的角色,并使用变量来表达普遍性。这两种用法在下面的形式处理中都有所体现。一些逻辑学家使用不同的符号来表示未指定对象(有时称为“个体参数”)和用于表达普遍性的变量。
常量和变量是我们形式语言中唯一的术语,因此我们所有的术语都是简单的,对应于专有名词和一些代词的使用。如果一个术语不是变量,我们称之为封闭的术语。一般来说,我们用 v 表示变量,用 t 表示封闭的术语,即个体常量。一些作者还引入函数符号,允许复杂的术语,如“7+4”和“比尔·克林顿的妻子”,或包含变量的复杂术语,如“x 的父亲”和“x/y”。面向数学家的逻辑书籍可能会包含函数符号,这可能是因为函数在数学论述中的核心地位。面向更广泛受众(或哲学学生)的书籍可能会省略函数符号,因为这简化了语法和理论。我们在这里遵循后一种方式。这是在提供具有更大表达资源的系统与使其形式处理更复杂之间的一种普遍权衡的实例。
对于每个自然数 n,我们引入一个 n 个位置的谓词字母库存。这些是字母表开头或中间的大写字母。上标表示位置的数量,可能有或可能没有下标。例如,
A3,B32,P3 等。
是三个位置的谓词字母。当不会引起混淆时,我们经常省略上标。我们还添加了一个特殊的二元谓词符号“=”表示等同。
零元谓词符号有时被称为“句子符号”。它们对应于内部结构不重要的独立句子。一元谓词符号,称为“一元谓词符号”,对应于表示属性的语言项,如“是一个人”,“是红色的”或“是一个质数”。二元谓词符号,称为“二元谓词符号”,对应于表示二元关系的语言项,如“是...的父母”或“大于”。三元谓词符号对应于三元关系,如“位于两点之间的直线上”。依此类推。
语言的非逻辑术语包括其个体常量和谓词符号。符号“=”表示相等,不是非逻辑符号。将相等视为逻辑,我们在演绎系统和模型论语义中对其进行明确处理。大多数作者也是如此,但对此问题存在一些争议(Quine [1986, 第 5 章])。如果 K 是常量和谓词符号的集合,则我们给出了建立在这组非逻辑术语上的语言 L1K=的基本原理。它可以称为具有相等性的一阶语言。一个类似的语言,缺少相等符号(或将相等视为非逻辑),可以称为 L1K,即没有相等性的一阶语言。
2.2 原子公式
如果 V 是 K 中的 n 元谓词符号,并且 t1,...,tn 是 K 中的项,则 Vt1...tn 是 L1K=的原子公式。注意,项 t1,...,tn 不一定是不同的。原子公式的例子包括:
P4xaab,C1x,C1a,D0,A3abc。
最后一个是关于某个关系(A)在三个对象(a,b,c)之间成立的陈述的类比。如果 t1 和 t2 是项,则 t1=t2 也是 L1K=的原子公式。它对应于 t1 等同于 t2 的断言。
如果一个原子公式没有变量,那么它被称为原子句子。如果它有变量,那么它被称为开放的。在上面的例子列表中,第一个和第二个是开放的;其余的是句子。
2.3 复合公式
现在我们介绍词汇表的最后一部分:
¬, &, ∨, →, ∀, ∃, (,)
我们对 L1K=的公式给出了递归定义:
所有 L1K=的原子公式都是 L1K=的公式。
如果 θ 是 L1K=的一个公式,那么 ¬θ 也是。
对应于 ¬θ 的公式表达的意思是不是 θ。符号“¬”被称为“否定”,是一个一元连接词。
如果 θ 和 ψ 是 L1K=的公式,那么(θ&ψ)也是。
符号“&”对应于英语中的“and”(当“and”用于连接句子时)。因此,(θ&ψ)可以读作“θ 和 ψ”。公式(θ&ψ)被称为 θ 和 ψ 的“合取”。
如果 θ 和 ψ 是 L1K=的公式,则(θ∨ψ)也是。
符号“∨”对应于“要么...要么...要么两者都是”,因此(θ∨ψ)可以读作“θ 或 ψ”。公式(θ∨ψ)被称为 θ 和 ψ 的“析取”。
如果 θ 和 ψ 是 L1K=的公式,那么(θ→ψ)也是。
箭头“→”大致对应于“如果...那么...”,所以(θ→ψ)可以读作“如果 θ 那么 ψ”或“θ 仅当 ψ”。
符号“&”、“∨”和“→”被称为“二元连接词”,因为它们用于将两个公式连接成一个。一些作者将(θ↔ψ)引入为((θ→ψ)&(ψ→θ))的缩写。符号“↔”是“当且仅当”的类比。
如果 θ 是 L1K=的一个公式,v 是一个变量,那么 ∀vθ 是 L1K=的一个公式。
符号“∀”被称为全称量词,类似于“对于所有”;因此 ∀vθ 可以读作“对于所有 v,θ”。
如果 θ 是 L1K=的一个公式,v 是一个变量,那么 ∃vθ 是 L1K=的一个公式。
符号“∃”被称为存在量词,是“存在”或“有”这个概念的类比;因此 ∃vθ 可以读作“存在一个 v 使得 θ 成立”。
就是这样。也就是说,所有的公式都是根据规则(1)-(7)构建的。
条款(8)允许我们对公式的复杂性进行归纳。如果某个属性适用于原子公式,并且在条款(2)-(7)中所呈现的操作下是封闭的,那么该属性适用于所有公式。这里有一个简单的例子:
定理 1. L1K=的每个公式都有相同数量的左括号和右括号。此外,每个左括号对应一个唯一的右括号,该右括号出现在左括号的右侧。同样,每个右括号对应一个唯一的左括号,该左括号出现在给定右括号的左侧。如果一个括号出现在一对匹配的括号之间,则它的配对括号也出现在该匹配的括号内。换句话说,出现在匹配括号内的括号本身也是匹配的。
证明:根据第(8)条,每个公式都是通过使用第(2)-(7)条从原子公式构建起来的。原子公式没有括号。括号仅在第(3)-(5)条中引入,并且每次引入都是作为一对匹配的括号。因此,在构建公式的任何阶段,括号都是成对出现的。
接下来,我们定义了变量在公式中自由或约束出现的概念。紧跟量词之后的变量(如“∀x”和“∃y”)既不是自由的也不是约束的。我们甚至不认为它们是变量的出现。在原子公式中出现的所有变量都是自由的。如果一个变量在 θ 或 ψ 中自由(或约束)出现,则在 ¬θ,(θ&ψ),(θ∨ψ)和(θ→ψ)中,该变量的相同出现也是自由的(或约束的)。也就是说,(一元和二元)连接词不会改变其中出现的变量的状态。在 ∀vθ 和 ∃vθ 中,θ 中的变量 v 的所有出现都是约束的。θ 中的任何自由出现的 v 都由初始量词约束。在 θ 中出现的其他变量都是自由的或约束的,就像它们在 θ 中一样。
例如,在公式(∀x(Axy ∨Bx)&Bx)中,Axy 和第一个 Bx 中的“x”的出现受到量词的约束。而“y”的出现和最后一个“x”的出现是自由的。在 ∀x(Ax→∃xBx)中,Ax 中的“x”受到初始的全称量词的约束,而另一个“x”的出现受到存在量词的约束。上述语法允许这种“双重约束”。虽然它不会产生任何歧义(见下文),但出于品味和清晰度的考虑,我们将避免使用这样的公式。
该语法还允许所谓的虚假约束,例如 ∀xBc。在接下来的内容中,我们也将避免使用这些。一些逻辑的处理方法将虚假约束和双重约束排除在语法之外。这简化了下面的一些处理方法,但也使其他处理方法变得复杂。
自由变量对应于占位符,而约束变量用于表达普遍性。如果一个公式没有自由变量,则称为命题。如果一个公式有自由变量,则称为开放式的。
2.4 语法的特点
在转向演绎系统和语义之前,我们先提到一些已经发展起来的语言特点。这有助于对比形式语言和英语等自然语言之间的差异。
我们首先假设所有的类别是不相交的。例如,没有联结词也是量词或变量,非逻辑术语也不是括号或联结词。此外,每个类别内的项目是不同的。例如,析取符号不会兼作否定符号,而且可能更重要的是,没有二元谓词也是一元谓词。
自然语言(如英语)和形式语言(如 L1K=)之间的一个区别在于后者不应该有任何歧义。不同类别的符号不重叠,也不会有符号兼职,这样可以避免所谓的“模棱两可”(equivocation)现象,即一个词有两个意思的情况:“我会在银行见你。”但是还有其他类型的歧义。考虑英语句子:
约翰已婚,玛丽单身,或者乔疯了。
这句话可以表示约翰已婚,要么玛丽单身要么乔疯了;或者表示约翰已婚并且玛丽单身,要么乔疯了。由于对同一句子有不同的解析方式,这种歧义有时被称为“二义性”。如果我们的形式语言中没有括号,就会出现二义性。例如,会有一个“公式”A&B∨ C。这是应该解析为((A&B)∨C),还是(A&(B∨C))?括号解决了可能出现的二义性。
我们能确定我们的语言中没有其他的歧义吗?也就是说,我们能确定每个 L1K=的公式只能以一种方式组合在一起吗?我们下一个任务是回答这个问题。
让我们暂时使用术语“一元标记”来表示否定符号(¬)或者量词后跟一个变量(例如 ∀x,∃z)。
引理 2. 每个公式由零个或多个一元标记组成,后面跟着一个原子公式或者使用二元连词通过(3)-(5)条款之一生成的公式。
证明:我们通过对公式的复杂性或者换句话说,对应用的形成规则的数量进行归纳来进行证明。引理显然对于原子公式成立。设 n 是一个自然数,并假设引理对于由 n 个或更少的(2)–(7)子句实例构造的任何公式都成立。设 θ 是由 n+1 个实例构造的公式。如果用于构造 θ 的最后一个子句是(3)、(4)或(5),则引理成立。如果用于构造 θ 的最后一个子句是(2),则 θ 是 ¬ψ。由于 ψ 是用规则的 n 个实例构造的,根据归纳假设,引理对于 ψ 成立,因此对于 θ 也成立。类似的推理表明,如果最后一个子句是(6)或(7),引理对于 θ 也成立。根据子句(8),这穷尽了所有情况,因此根据归纳法,引理对于 θ 成立。
引理 3:如果一个公式 θ 包含一个左括号,则它以一个右括号结尾,该右括号与 θ 中最左边的左括号匹配。
证明:在这里,我们也通过对构造公式使用的(2)–(7)实例的数量进行归纳来进行证明。显然,引理对于原子公式成立,因为它们没有括号。假设引理对于使用 n 个或更少的(2)–(7)实例构造的公式成立,并且设 θ 是由 n+1 个实例构造的。如果最后一个应用的子句是(3)–(5),则引理成立,因为 θ 本身以一个左括号开始,并以匹配的右括号结尾。如果最后一个应用的子句是(2),则 θ 是 ¬ψ,并且归纳假设适用于 ψ。类似地,如果最后一个应用的子句是(6)或(7),则 θ 由一个量词、一个变量和一个可以应用归纳假设的公式组成。由此可知,引理对于 θ 成立。
引理 4. 每个公式至少包含一个原子公式。
证明通过对用于构造公式的(2)–(7)的实例数量进行归纳进行,我们将其作为一个练习留给读者。
定理 5. 设 α,β 是我们字母表上的非空字符序列,使得 αβ(即 α 后跟 β)是一个公式。那么 α 不是一个公式。
证明:根据定理 1 和引理 3,如果 α 包含左括号,则与 αβ 中最左边的左括号匹配的右括号位于 αβ 的末尾,因此匹配的右括号在 β 中。所以,α 的左括号比右括号多。根据定理 1,α 不是一个公式。现在假设 α 不包含任何左括号。根据引理 2,αβ 由零个或多个一元标记符组成,后跟原子公式或使用二元连词通过(3)-(5)条款之一生成的公式。如果后者的公式是通过(3)-(5)条款之一生成的,则它以左括号开头。由于 α 不包含任何括号,它必须是一串一元标记符。但是然后 α 不包含任何原子公式,所以根据引理 4,α 不是一个公式。剩下的唯一情况是 αβ 由一串一元标记符后跟一个原子公式组成,可以是 t1=t2 或 Pt1…tn 的形式。同样,如果 α 只包含一元标记符,它将不是一个公式,所以 α 必须由开始 αβ 的一元标记符组成,后跟 t1 本身,t1=本身,或谓词字母 P,以及一些(但不是全部)的术语 t1,…,tn。在前两种情况下,α 不包含原子公式,根据类别不重叠的策略。由于 P 是一个 n 元谓词字母,根据谓词字母不同的策略,P 不是任何 m≠n 的 m 元谓词字母。因此,由谓词字母和术语组成的 α 的部分不是原子公式。在所有这些情况下,α 不包含原子公式。根据引理 4,α 不是一个公式。
我们终于可以证明我们的语言中没有歧义。
定理 6:设 θ 是 L1K=的任意公式。如果 θ 不是原子公式,则在(2)-(7)中只有一个是用于构造 θ 的最后一个子句。也就是说,θ 不能由两个不同的子句产生。此外,由(2)-(7)子句生成的公式都不是原子公式。
证明:根据第(8)条款,θ 要么是原子的,要么是由第(2)-(7)条款之一产生的。因此,θ 中的第一个符号必须是谓词字母、项、一元标记或左括号中的一个。如果 θ 中的第一个符号是谓词字母或项,那么 θ 是原子的。在这种情况下,θ 不是由(2)-(7)中的任何一个产生的,因为所有这样的公式都以谓词字母或项以外的其他东西开头。如果 θ 中的第一个符号是否定符号“¬”,那么 θ 是由第(2)条款产生的,而不是由任何其他条款产生的(因为其他条款产生的公式都以量词或左括号开头)。同样,如果 θ 以全称量词开头,那么它是由第(6)条款产生的,而不是由任何其他条款产生的;如果 θ 以存在量词开头,那么它是由第(7)条款产生的,而不是由任何其他条款产生的。剩下的唯一情况是 θ 以左括号开头。在这种情况下,它必须是由(3)-(5)中的一个产生的,而不是由任何其他条款产生的。我们只需要排除 θ 由(3)-(5)中的多个条款产生的可能性。举个例子,假设 θ 由(3)和(4)产生。那么 θ 既是(ψ1&ψ2),又是(ψ3∨ψ4),其中 ψ1、ψ2、ψ3 和 ψ4 本身就是公式。也就是说,(ψ1&ψ2)和(ψ3∨ψ4)是完全相同的公式。根据定理 5,ψ1 不能是 ψ3 的真子集,ψ3 也不能是 ψ1 的真子集。所以 ψ1 必须是与 ψ3 相同的公式。但是这意味着“&”必须是与“∨”相同的符号,这与所有符号都不同的原则相矛盾。因此,θ 不是由第(3)条款和第(4)条款同时产生的。类似的推理可以处理其他组合。
这个结果有时被称为“唯一可读性”。它表明每个公式都是通过各个子句从原子公式中以唯一的方式产生的。如果 θ 是由子句(2)产生的,则其主联结词是初始的“¬”。如果 θ 是由子句(3)、(4)或(5)产生的,则其主联结词分别是引入的“&”、“∨”或“→”。如果 θ 是由子句(6)或(7)产生的,则其主联结词是初始的量词。我们为这些繁琐的细节道歉。我们包含它们是为了表明语法的精确性和严谨性的水平。
3. 推导
现在我们引入了一个推导系统 D,用于我们的语言。如上所述,我们将一个论证定义为形式语言中的一组非空句子,其中一个被指定为结论。如果论证中还有其他句子,则它们是前提 [1]。按照惯例,我们使用“Γ”、“Γ′”、“Γ1”等来表示句子集合,并使用字母“ϕ”、“ψ”、“θ”(大写或小写,带或不带下标)来表示单个句子。我们用“Γ,Γ′”表示 Γ 和 Γ′的并集,“Γ,ϕ”表示 Γ 与{ϕ}的并集。
我们以 ⟨Γ,ϕ⟩ 的形式写出一个论证,其中 Γ 是一组句子,即前提,ϕ 是一个句子,即结论。请记住,Γ 可能为空。我们写 Γ⊢ϕ 来表示 ϕ 可以从 Γ 推导出来,或者换句话说,论证 ⟨Γ,ϕ⟩ 可以在 D 中推导出来。我们可以写 Γ⊢Dϕ 来强调推理系统 D。我们写 ⊢ϕ 或 ⊢Dϕ 来表示 ϕ 可以从空的前提集合中推导出来(在 D 中)。
D 中的规则被选择为与语言中逻辑术语的英文类比的逻辑关系相匹配。同样,我们通过递归来定义推导关系。我们从一个假设规则开始:
(作为)
如果 ϕ 是 Γ 的成员,则 Γ⊢ϕ。
因此,我们有{ϕ}⊢ϕ;每个前提都可以从自身推导出来。接下来,我们为每个连接词和量词提供两个子句。这些子句指示了如何在每个符号是主要连接词的句子中“引入”和“消除”。
首先,回想一下,“&”是英语连接词“and”的类比。直观上,如果我们推导出 θ 并且推导出 ψ,我们可以推导出形式为(θ&ψ)的句子。反过来,我们可以从(θ&ψ)推导出 θ,并且可以从(θ&ψ)推导出 ψ:
(&I)
如果 Γ1⊢θ 和 Γ2⊢ψ,那么 Γ1,Γ2⊢(θ&ψ)。
(&E)
如果 Γ⊢(θ&ψ),那么 Γ⊢θ;如果 Γ⊢(θ&ψ),那么 Γ⊢ψ。
名称“&I”代表“&-introduction”;“&E”代表“&-elimination”。
由于符号“∨”对应英文中的“or”,所以(θ∨ψ)应该可以从 θ 推导出来,并且(θ∨ψ)也应该可以从 ψ 推导出来:
(∨I)
如果 Γ⊢θ,则 Γ⊢(θ∨ψ);如果 Γ⊢ψ,则 Γ⊢(θ∨ψ)。
消除规则稍微复杂一些。假设“θ 或 ψ”为真。假设还有从 θ 推出 ϕ,以及从 ψ 推出 ϕ。可以推理出如果 θ 为真,则 ϕ 为真。如果相反 ψ 为真,我们仍然有 ϕ 为真。所以无论如何,ϕ 必须为真。
(∨E)
如果 Γ1⊢(θ∨ψ),Γ2,θ⊢ϕ 和 Γ3,ψ⊢ϕ,那么 Γ1,Γ2,Γ3⊢ϕ。
对于下面的子句,要记住符号“→”是英语“if … then …”结构的类比。如果一个人知道或假设(θ→ψ),并且还知道或假设 θ,那么他可以得出结论 ψ。反过来,如果一个人从假设 θ 推导出 ψ,那么他可以得出结论(θ→ψ)。
(→I)
如果 Γ,θ⊢ψ, 那么 Γ⊢(θ→ψ).
(→E)
如果 Γ1⊢(θ→ψ)且 Γ2⊢θ,则 Γ1,Γ2⊢ψ。
这个消除规则有时被称为“假言演绎”。在一些逻辑学文本中,引入规则被证明为“演绎定理”。
我们接下来的子句是针对否定符号“¬”。其基本思想是,一个句子 ψ 与其否定 ¬ψ 是不一致的。它们不能同时为真。我们称这样一对句子 ψ,¬ψ 为矛盾对立。如果可以从假设 θ 推导出这样一对句子,那么可以得出结论 θ 是假的,换句话说,可以得出 ¬θ。
(¬I)
如果 Γ1,θ⊢ψ 和 Γ2,θ⊢¬ψ, 那么 Γ1,Γ2⊢¬θ.
通过(As), 我们有{A,¬A}⊢A 和{A,¬A}⊢¬A. 所以通过 ¬I, 我们有{A}⊢¬¬A. 然而,我们还没有相反的情况。直观上,¬¬θ 对应于“不是这样的情况,即不是这样的情况”。有人可能认为这最后一个与 θ 等价,并且我们有一个规则来表示这一点:
(DNE)
如果 Γ⊢¬¬θ,则 Γ⊢θ。
DNE 这个名字代表着“双重否定消除”。对于这种推理存在一些争议。不认同每个有意义的句子要么为真要么为假的哲学家和数学家会拒绝这种推理。直觉主义逻辑不支持这种推理(参见 Dummett [2000],或直觉主义逻辑条目,或直觉主义逻辑的历史),但是经典逻辑支持。
为了说明迄今为止所呈现的演绎系统 D 的部分,我们展示了 ⊢(A∨¬A):
{¬(A∨¬A),A}⊢¬(A∨¬A),通过(As)
{¬(A∨¬A),A}⊢A,通过(As)。
{¬(A∨¬A),A}⊢(A∨¬A),通过(∨I)从(ii)得出。
{¬(A∨¬A)}⊢¬A,通过(¬I)从(i)和(iii)得出。
{¬(A∨¬A),¬A}⊢¬(A∨¬A),通过(As)得出。
{¬(A∨¬A),¬A}⊢¬A,通过(As)解释
{¬(A∨¬A),¬A}⊢(A∨¬A),通过(∨I)解释,来自(vi)
{¬(A∨¬A)}⊢¬¬A,通过(¬I)解释,来自(v)和(vii)
⊢¬¬(A∨¬A),通过(¬I)从(iv)和(viii)得出。
⊢(A∨¬A),通过(DNE)从(ix)得出。
原则(θ∨¬θ)有时被称为排中律。在直觉逻辑中无效。
让 θ,¬θ 成为一对矛盾的对立面,让 ψ 是任意的句子。根据(As),我们有{θ,¬θ,¬ψ}⊢θ 和{θ,¬θ,¬ψ}⊢¬θ。所以根据(¬I),{θ,¬θ}⊢¬¬ψ。所以,根据(DNE),我们有{θ,¬θ}⊢ψ。也就是说,任何东西都可以从一对矛盾的对立面中推导出来。一些逻辑学家引入了一条规则来编码类似的推理:
如果 Γ1⊢θ 和 Γ2⊢¬θ,那么对于任意的句子 ψ,Γ1,Γ2⊢ψ。
这种推理有时被称为 ex falso quodlibet,或者更有趣的是 explosion。有些人称之为“¬-elimination”,但也许这有点扩大了“elimination”的概念。我们在 D 中没有正式地将 ex falso quodlibet 作为一个单独的规则包含在内,但正如下面将要展示的(定理 10),我们的系统 D 中的每个实例都是可导出的。
一些逻辑学家反对“ex falso quodlibet”,理由是句子 ψ 可能与 Γ 中的任何前提都无关。例如,假设我们从一些关于人性和某些人的事实的前提 Γ 开始,然后推导出“克林顿有婚外性关系”和“克林顿没有婚外性关系”这两个句子。或许我们可以得出结论,前提 Γ 存在问题。但是,我们是否应该允许从 Γ 中推导出任何东西呢?我们是否应该允许推导出“经济是健康的”呢?
少数逻辑学家,被称为二值矛盾论者,认为一些矛盾实际上是真实的。对于他们来说,“ex falso quodlibet”并不保持真实性。
不同于“ex falso quodlibet”的演绎系统被称为“随附性”。大多数相关逻辑都是随附性的。请参阅关于相关逻辑、随附性逻辑和二值矛盾论的条目。或者参阅 Anderson 和 Belnap [1975],Anderson,Belnap 和 Dunn [1992] 以及 Tennant [1997],以获取更详细的相关逻辑概述;以及 Priest [2006a,b],以了解二值矛盾论。涉及到逻辑推论性质的深层哲学问题。虽然哲学百科全书的文章无法避免哲学问题,但出于篇幅考虑,本文无法对此问题进行更详尽的讨论。仅需注意,在经典逻辑系统中,推论“ex falso quodlibet”是被认可的。这对于建立演绎系统和语义之间的平衡至关重要(见下文第 5 节)。
D 的下一部分是量词的子句。设 θ 为一个公式,v 为一个变量,t 为一个项(即一个变量或一个常量)。然后定义 θ(v|t)为在 θ 中的每个自由出现的 v 都替换为 t 的结果。因此,如果 θ 是(Qx&∃xPxy),那么 θ(x|c)就是(Qc&∃xPxy)。最后一次出现的 x 不是自由的。
形式为 ∀vθ 的句子是英语中“对于每个 v,θ 成立”的类比。因此,应该能够从 ∀vθ 推断出 ∀vθ 中的 θ(v|t),对于任何闭合项 t。请记住,在我们的系统中,唯一的闭合项是常量。
(∀E)
如果 Γ⊢∀vθ,则对于任何闭合项 t,Γ⊢θ(v|t)。
这里的思想是,如果 ∀vθ 为真,则无论 t 是什么,θ 都应该成立。
全称量词的引入子句稍微复杂一些。假设一个句子 θ 包含一个闭合项 t,并且 θ 已经从一组前提 Γ 中推导出来。如果闭合项 t 不出现在 Γ 的任何成员中,则无论 t 可能表示哪个对象,θ 都将成立。也就是说,∀vθ 成立。
(∀I)
对于任意封闭术语 t,如果 Γ⊢θ(v|t),那么只要 t 不在 Γ 或 θ 中,就有 Γ⊢∀vθ。
这个规则 (∀I) 对应于数学中的常见推理。假设一个数学家说“设 n 是一个自然数”,然后继续展示 n 具有某个性质 P,而不对 n 做任何假设(除了它是一个自然数)。然后她提醒读者 n 是“任意的”,并得出结论 P 对所有自然数成立。条件 t 不出现在任何前提中是保证它确实是“任意的”。它可以是任何对象,因此我们对它得出的任何结论都适用于所有对象。
存在量词是英语表达“存在”或者仅仅是“有”的类比。如果我们已经建立(或者假设)了给定对象 t 具有给定属性的情况,那么可以推断出存在某个具有该属性的东西。
(∃I)
对于任意封闭项 t,如果 Γ⊢θ(v|t),那么 Γ⊢∃vθ。
对于 ∃ 的消除规则并不那么简单:
(∃E)
对于任意封闭项 t,如果 Γ1⊢∃vθ 且 Γ2,θ(v|t)⊢ϕ,则在 t 不出现在 ϕ、Γ2 或 θ 的前提下,有 Γ1,Γ2⊢ϕ。
这个消除规则也对应于一种常见的推理。假设一个数学家假设或以某种方式得出存在一个具有给定属性 P 的自然数。然后她说“让 n 是这样一个自然数,使得 Pn”,并继续建立一个不提及数字 n 的句子 ϕ。如果 ϕ 的推导没有涉及 n 的任何内容(除了假设它具有给定的属性 P),那么 n 可以是具有属性 P 的任何数字。也就是说,n 是具有属性 P 的任意数字。无论 n 是哪个数字都无关紧要。由于 ϕ 不提及 n,所以从某个东西具有属性 P 的断言中可以推出 ϕ。添加到(∃E)的规定是为了保证 t 是“任意的”。
最后的项目是“=”的规则。引入规则非常简单:
(=I)
Γ⊢t=t,其中 t 是任意封闭项。
这个“推理”对应于一切都等同于自身的真理。消除规则对应于一个原则,即如果 a 等同于 b,则对 a 成立的任何事实也对 b 成立。
(=E)
对于任意封闭术语 t1 和 t2,如果 Γ1⊢t1=t2 且 Γ2⊢θ,则 Γ1,Γ2⊢θ′,其中 θ′是通过将 θ 中的一个或多个 t1 的出现替换为 t2 而获得的。
规则(=E)指示了我们语言表达资源的某种限制。例如,假设 Harry 与 Donald 是相同的(因为他淘气的父母给了他两个名字)。根据大多数人的直觉,从这个事实和“Dick 知道 Harry 是邪恶的”并不意味着“Dick 知道 Donald 是邪恶的”,原因是 Dick 可能不知道 Harry 与 Donald 是相同的。这样的上下文,其中无法安全地将相同的事物互相替换,被称为“不透明”。我们假设我们的语言 L1K=没有不透明的上下文。
最后一个子句完成了对推理系统 D 的描述:
(*)
这就是全部。只有当 θ 根据上述规则从 Γ 的成员中推导出来时,才有 Γ⊢θ。
同样,这个条款允许通过对用于建立论证的规则进行归纳来进行证明。如果论证的所有实例(As 和=I)都具有一个属性,并且其他规则保持该属性,那么在 D 中可推导出的每个论证都具有该属性。
在进入 L1K=的模型理论之前,我们暂停一下,注意一些推理系统的特点。为了说明严密程度,我们从一个引理开始,即如果一个句子不包含特定的闭合项,我们可以对我们从中证明它的句子集进行小的更改而没有问题。在这里,我们允许自己扩展一些先前的符号:对于任何项 t 和 t',以及任何公式 θ,我们说 θ(t|t')是将 θ 中所有自由出现的 t 替换为 t'的结果。
引理 7. 如果 Γ1 和 Γ2 只在于 Γ1 包含 θ 而 Γ2 包含 θ(t|t′)的地方不同,那么对于任意不包含 t 或 t′的句子 ϕ,如果 Γ1⊢ϕ,则 Γ2⊢ϕ。
证明:该证明通过对 ϕ 的证明步骤数进行归纳来进行。该证明的关键在于当 θ 不包含 t 或 t′时,θ=θ(t|t′)。当 ϕ 的证明步骤数为 1 时,这意味着最后(也是唯一)应用的规则是(As)或(=I)。然后,由于 ϕ 不包含 t 或 t′,如果 Γ1⊢ϕ,我们只需将相同的规则((As)或(=I))应用于 Γ2,即可得到 Γ2⊢ϕ。假设在 ϕ 的证明中有 n>1 个步骤,并且引理 7 对于少于 n 个步骤的证明成立。假设第 n 个规则应用于 Γ1 是(&I)。那么 ϕ 是 ψ&χ,并且 Γ1⊢ϕ&χ。但是,我们知道证明中的前面步骤包括 Γ1⊢ψ 和 Γ1⊢χ,并且根据归纳法,由于 ψ 和 χ 都不包含 t 或 t′,我们有 Γ2⊢ψ 和 Γ2⊢χ。因此,我们只需将(&I)应用于 Γ2,即可得到 Γ2⊢ψ&χ,如所需。现在假设在 Γ1⊢ϕ 的证明中最后一步应用的是(&E)。那么,在 ϕ 的证明的前一步中,我们知道 Γ1⊢ϕ&ψ,其中 ψ 是某个句子。如果 ψ 不包含 t,则我们只需将(&E)应用于 Γ2,即可得到所需的结果。唯一的复杂情况是如果 ψ 包含 t。那么我们将有 Γ2⊢(ϕ&ψ)(t|t′)。但是,由于(ϕ&ψ)(t|t′)是 ϕ(t|t′)&ψ(t|t′),而 ϕ(t|t′)就是 ϕ,我们可以直接应用(&E)得到 Γ2⊢ϕ,如所需。其他规则的情况类似。
定理 8. 弱化规则。如果 Γ1⊢ϕ 且 Γ1⊆Γ2,则 Γ2⊢ϕ。
证明:再次,我们按照使用规则的数量进行归纳,以得到 Γ1⊢ϕ。假设 n>0 是一个自然数,并且对于使用少于 n 个规则推导出的任何论证,定理成立。假设 Γ1⊢ϕ 使用了恰好 n 个规则。如果 n=1,则规则要么是(As),要么是(=I)。在这些情况下,通过相同的规则,我们有 Γ2⊢ϕ。如果最后应用的规则是(&I),那么 ϕ 的形式为(θ&ψ),我们有 Γ3⊢θ 和 Γ4⊢ψ,其中 Γ1=Γ3,Γ4。我们对 θ 和 ψ 的推导应用归纳假设,得到 Γ2⊢θ 和 Γ2⊢ψ。然后将(&I)应用于结果,得到 Γ2⊢ϕ。其他大部分情况与此类似。只有在规则(∀I)和(∃E)中才会出现轻微的复杂性,因为我们必须注意规则的条件。
假设最后应用的规则是(∀I),那么 ϕ 是形如 ∀vθ 的句子,我们有 Γ1⊢θ(v|t)且 t 不出现在 Γ1 或 θ 的任何成员中。问题在于 t 可能出现在 Γ2 的某个成员中,因此我们不能仅仅调用归纳假设并将(∀I)应用于结果。因此,让 t'是一个在 Γ2 的任何句子中都不出现的项。让 Γ'是将 Γ2 中的所有 t 替换为 t'的结果。然后,由于 t 不出现在 Γ1 中,Γ1⊆Γ'。因此,归纳假设给出了 Γ'⊢θ(v|t),我们知道 Γ'不包含 t,因此我们可以应用(∀I)得到 Γ'⊢∀vθ。但是 ∀vθ 不包含 t 或 t',所以根据引理 7,Γ2⊢∀vθ。
假设最后应用的规则是(∃E),我们有 Γ3⊢∃vθ 和 Γ4,θ(v|t)⊢ϕ,其中 Γ1 是 Γ3,Γ4,t 不在 ϕ、Γ4 或 θ 中。如果 t 在 Γ2 中不自由出现,我们应用归纳假设得到 Γ2⊢∃vθ,然后应用(∃E)得到 Γ2⊢ϕ。如果 t 在 Γ2 中自由出现,则我们按照类似于 ∀I 的过程使用引理 7。
定理 8 允许我们随意添加前提。由此可得,如果且仅当存在子集 Γ′⊆Γ 使得 Γ′⊢ϕ,那么 Γ⊢ϕ。一些相关逻辑系统没有弱化,亦如非结构逻辑(参见相关逻辑、非结构逻辑和线性逻辑条目)。
根据条款(*),所有的推导都在有限步骤内完成。因此我们有
定理 9. 如果且仅当存在有限子集 Γ′⊆Γ 使得 Γ′⊢ϕ,那么 Γ⊢ϕ。
定理 10. ex falso quodlibet 规则是 D 的“派生规则”:如果 Γ1⊢θ 和 Γ2⊢¬θ,则对于任意的句子 ψ,有 Γ1,Γ2⊢ψ。
证明:假设 Γ1⊢θ 和 Γ2⊢¬θ。根据定理 8,有 Γ1,¬ψ⊢θ 和 Γ2,¬ψ⊢¬θ。因此,根据(¬I)规则,有 Γ1,Γ2⊢¬¬ψ。根据(DNE)规则,有 Γ1,Γ2⊢ψ。
定理 11. Cut 规则:如果 Γ1⊢ψ 和 Γ2,ψ⊢θ,则有 Γ1,Γ2⊢θ。
证明:假设 Γ1⊢ψ 和 Γ2,ψ⊢θ。我们通过对建立 Γ2,ψ⊢θ 所使用的规则数量进行归纳来进行证明。假设 n 是一个自然数,并且对于使用少于 n 个规则推导出的任何论证,定理都成立。假设 Γ2,ψ⊢θ 是使用恰好 n 个规则推导出的。如果最后使用的规则是 (=I),那么 Γ1,Γ2⊢θ 也是 (=I) 的一个实例。如果 Γ2,ψ⊢θ 是 (As) 的一个实例,那么要么 θ 是 ψ,要么 θ 是 Γ2 的成员。在前一种情况下,根据假设我们有 Γ1⊢θ,并且通过 Weakening(定理 8)得到 Γ1,Γ2⊢θ。在后一种情况下,Γ1,Γ2⊢θ 本身就是 (As) 的一个实例。假设 Γ2,ψ⊢θ 是使用 (&E) 获得的。那么我们有 Γ2,ψ⊢(θ&ϕ)。归纳假设给出了 Γ1,Γ2⊢(θ&ϕ),而 (&E) 产生了 Γ1,Γ2⊢θ。其余情况类似。
定理 11 允许我们将推理链接在一起。这符合建立定理和引理,然后随意使用这些定理和引理的做法。有人认为,割断原则对于推理是必不可少的。在某些逻辑系统中,割断原则是一个深刻的定理;在其他系统中,它是无效的。这个系统在设计时,部分是为了使定理 11 的证明变得简单明了。
如果 Γ⊢Dθ,那么我们说句子 θ 是句子集合 Γ 的演绎结果,并且论证 ⟨Γ,θ⟩ 是演绎有效的。如果 ⊢Dθ,那么句子 θ 是逻辑定理,或者是演绎逻辑真理。也就是说,如果 θ 是空集合的演绎结果,那么 θ 是逻辑定理。如果存在没有 Γ⊢Dθ 和 Γ⊢D¬θ 的句子 θ,那么句子集合 Γ 是一致的。也就是说,如果它不涉及一对相互矛盾的句子,那么集合是一致的。
定理 12. 如果存在一个句子 θ,使得不成立 Γ⊢θ,则集合 Γ 是一致的。
证明:假设 Γ 是一致的,令 θ 为任意句子。那么要么不成立 Γ⊢θ,要么不成立 Γ⊢¬θ。反之,假设 Γ 是不一致的,令 ψ 为任意句子。我们有一个句子,使得 Γ⊢θ 和 Γ⊢¬θ 都成立。根据 ex falso quodlibet(定理 10),Γ⊢ψ。
定义语言 L1K=的句子集合 Γ 为最大一致的,如果 Γ 是一致的,并且对于 L1K=的每个句子 θ,如果 θ 不在 Γ 中,则 Γ,θ 是不一致的。换句话说,如果 Γ 是最大一致的,则当且仅当 θ 在 Γ 中时,Γ⊢θ。
定理 13. 林登鲍姆引理。设 Γ 是 L1K=的任意一致的句子集。那么存在一个 L1K=的句子集 Γ′,使得 Γ⊆Γ′且 Γ′是极大一致的。
证明:虽然这个定理在一般情况下成立,但我们在这里假设非逻辑术语的集合 K 要么是有限的,要么是可数无穷的(即自然数的大小,通常称为 ℵ0)。由此可得,存在一个 L1K=句子的枚举 θ0,θ1,…,使得 L1K=的每个句子最终都会出现在这个列表中。通过递归,定义一个句子集的序列如下:Γ0 为 Γ;对于每个自然数 n,如果 Γn,θn 是一致的,则令 Γn+1=Γn,θn。否则,令 Γn+1=Γn。令 Γ′为所有 Γn 集合的并集。直观上,这个想法是遍历 L1K=的句子,如果将每个句子放入 Γ′会产生一致的集合,则将其放入 Γ′中。注意到每个 Γn 都是一致的。假设 Γ′是不一致的。那么存在一个句子 θ,使得 Γ′⊢θ 且 Γ′⊢¬θ。根据定理 9 和弱化(定理 8),存在 Γ′′是 Γ′的有限子集,使得 Γ′′⊢θ 且 Γ′′⊢¬θ。因为 Γ′′是有限的,存在一个自然数 n,使得 Γ′′的每个成员都在 Γn 中。因此,再次通过弱化,有 Γn⊢θ 且 Γn⊢¬θ。所以 Γn 是不一致的,这与构造矛盾。因此 Γ′是一致的。现在假设句子 θ 不在 Γ′中。我们必须证明 Γ′,θ 是不一致的。句子 θ 必须出现在前述的句子列表中;假设 θ 是 θm。由于 θm 不在 Γ′中,那么它也不在 Γm+1 中。这只有在 Γm,θm 是不一致的情况下才会发生。因此,可以从 Γm,θm 中推导出一对矛盾的对立面。通过弱化,可以从 Γ′,θm 中推导出一对矛盾的对立面。因此,Γ′,θm 是不一致的。因此,Γ′是极大一致的。
注意,这个证明使用了与排中律相对应的原则。在构建 Γ'的过程中,我们假设在每个阶段,要么 Γn 是一致的,要么不是。直觉主义者不接受林登鲍姆引理。
4. 语义学
设 K 为非逻辑术语的集合。对于语言 L1K=,一个解释是一个结构 M=⟨d,I⟩,其中 d 是一个非空集合,称为解释的领域,或者简称为领域,I 是一个解释函数。非正式地说,领域是我们对语言 L1K=的解释。它是变量的取值范围。解释函数将适当的扩展分配给非逻辑术语。特别地,
如果 c 是 K 中的一个常量,那么 I(c)是域 d 的一个成员。
因此,我们假设每个常量都表示某个东西。不假设这一点的系统被称为自由逻辑(参见自由逻辑条目)。继续,
如果 P0 是 K 中的一个零元谓词符号,那么 I(P)是一个真值,可以是真或假。
如果 Q1 是 K 中的一元谓词符号,则 I(Q)是 d 的子集。直观地说,I(Q)是谓词 Q 成立的域中的成员的集合。例如,I(Q)可能是域中红色成员的集合。
如果 R2 是 K 中的二元谓词符号,则 I(R)是 d 的一组有序成员对。直观地说,I(R)是域中关系 R 成立的成员对的集合。例如,I(R)可能是一组成员对 ⟨a,b⟩,其中 a 和 b 是域中的成员,且 a 爱 b。
一般而言,如果 Sn 是 K 中的 n 元谓词符号,则 I(S)是 d 的一组有序 n 元组成员的集合。
定义 s 为一个变量赋值,或者简单地说是一个在解释 M 上的赋值,如果 s 是从变量到 M 的域 d 的函数。变量赋值的作用是为开放公式的自由变量分配指称。(在某种意义上,量词决定了约束变量的“意义”。)
让 t 是 L1K=的一个术语。我们根据解释函数和变量赋值来定义 t 在 M 中在 s 下的指称:
如果 t 是一个常量,那么 DM,s(t)是 I(t),如果 t 是一个变量,那么 DM,s(t)是 s(t)。
也就是说,解释 M 将常量赋予指称,而变量赋值则将指称赋予(自由)变量。如果语言包含函数符号,则指称函数将通过递归来定义。
现在我们定义了解释、变量赋值和 L1K=公式之间的满足关系。如果 ϕ 是 L1K=的一个公式,M 是 L1K=的一个解释,s 是 M 上的一个变量赋值,那么我们写作 M,s⊨ϕ 表示 M 在赋值 s 下满足 ϕ。这个想法是 M,s⊨ϕ 类似于“当通过 s 在 M 中解释时,ϕ 为真”。
我们按照 L1K=公式的复杂性进行递归处理。
如果 t1 和 t2 是术语,那么当且仅当 DM,s(t1)与 DM,s(t2)相同时,M,s⊨t1=t2。
这就是最直接的了。当且仅当术语 t1 和 t2 表示相同的事物时,等同式 t1=t2 为真。
如果 P0 是 K 中的零元谓词符号,则当且仅当 I(P)为真时,M,s⊨P。
如果 Sn 是 K 中的 n 元谓词符号,而 t1,…,tn 是项,则当且仅当 n 元组 ⟨DM,s(t1),…,DM,s(tn)⟩ 在 I(S)中时,M,s⊨St1…tn。
这解决了原子公式的问题。我们现在继续处理语言的复合公式,或多或少地遵循逻辑术语的英文对应的含义。
当且仅当不是 M,s⊨θ 时,M,s⊨¬θ。
对于任意模型 M 和状态 s,当且仅当 M,s⊨θ 和 M,s⊨ψ 都成立时,M,s⊨(θ&ψ)成立。
对于任意模型 M 和状态 s,当且仅当 M,s⊨θ 或 M,s⊨ψ 至少有一个成立时,M,s⊨(θ∨ψ)成立。
对于任意模型 M 和状态 s,当且仅当不成立 M,s⊨θ 或成立 M,s⊨ψ 时,M,s⊨(θ→ψ)成立。
对于每个赋值 s',只有当 M,s⊨∀vθ 时才成立,当且仅当 M,s'⊨θ,其中 s'在除了变量 v 可能不同的情况下与 s 一致。
这里的想法是,只有当无论变量 v 被赋予什么值时 θ 都为真时,∀vθ 才为真。最后一个子句类似。
对于某个赋值 s',只有当 M,s⊨∃vθ 时才成立,当且仅当 M,s'⊨θ,其中 s'在除了变量 v 可能不同的情况下与 s 一致。
因此,如果存在一个对 v 的赋值使得 θ 为真,则 ∃vθ 为真。
定理 6,唯一可读性,确保了这个定义的连贯性。在分解公式的每个阶段,只有一个子句可以应用,因此我们永远不会得到关于满足的矛盾判断。
如前所述,变量赋值的作用是给自由变量赋予指称。我们现在要证明变量赋值没有其他作用。
定理 14. 对于任意公式 θ,如果 s1 和 s2 在 θ 的自由变量上一致,则当且仅当 M,s1⊨θ 时,M,s2⊨θ。
证明:我们通过对公式 θ 的复杂性进行归纳来证明该定理。如果 θ 是原子公式,则定理显然成立,因为在这些情况下,只有变量赋值在定义中才起作用。假设对于比 θ 更简单的所有公式,定理都成立。并且假设 s1 和 s2 在 θ 的自由变量上一致。首先假设 θ 是一个否定,¬ψ。然后根据归纳假设,当且仅当 M,s1⊨ψ 时,M,s2⊨ψ。因此,根据否定的定义,当且仅当 M,s1⊨¬ψ 时,M,s2⊨¬ψ。θ 的主要联结词是二元的情况也是类似的。假设 θ 是 ∃vψ,并且 M,s1⊨∃vψ。那么存在一个赋值 s′1,它与 s1 在除了 v 可能不同的变量上一致,使得 M,s′1⊨ψ。令 s′2 是在不在 ψ 中的自由变量上与 s2 一致,在其他变量上与 s′1 一致的赋值。然后根据归纳假设,M,s′2⊨ψ。注意,s′2 与 s2 在除了 v 可能不同的每个变量上一致。因此,M,s2⊨∃vψ。反之亦然,以及以全称量词开始的情况类似。
根据定理 14,如果 θ 是一个句子,并且 s1、s2 是任意两个变量赋值,则当且仅当 M,s1⊨θ 时,M,s2⊨θ。因此,我们可以简单地写作 M⊨θ,如果对于某个或所有的变量赋值 s,M,s⊨θ。因此,我们定义
M⊨θ,其中 θ 是一个句子,当且仅当对于所有变量赋值 s,M,s⊨θ。
在这种情况下,我们称 M 为 θ 的一个模型。
假设 K'⊆K 是两个非逻辑术语的集合。如果 M=⟨d,I⟩ 是 L1K 的一个解释,那么我们将 M 对 L1K'的限制定义为解释 M′=⟨d,I′⟩,其中 I′是 I 对 K'的限制。也就是说,M 和 M′具有相同的域,并且在 K'中的非逻辑术语上达成一致。一个直接的归纳证明得出以下结论:
定理 15. 如果 M'是 M 对 L1K'的限制,则对于 L1K'的每个句子 θ,当且仅当 M⊨θ 时,M'⊨θ。
定理 16. 如果两个解释 M1 和 M2 具有相同的域,并且在句子 θ 的所有非逻辑术语上达成一致,则当且仅当 M1⊨θ 时,M2⊨θ。
简而言之,句子 θ 的满足只取决于论域和 θ 中非逻辑术语的解释。
我们说一个论证 ⟨Γ,θ⟩ 是语义上有效的,或者只是有效的,写作 Γ⊨θ,如果对于语言的每个解释 M,如果 M⊨ψ,对于 Γ 的每个成员 ψ,那么 M⊨θ。如果 Γ⊨θ,我们也说 θ 是 Γ 的逻辑结果,或语义结果,或模型论结果。这个定义对应于非正式的观点,即如果论证的前提都为真且结论为假是不可能的,那么该论证是有效的。我们对逻辑结果的定义也支持了一个常见的论点,即有效的论证是保真的——在满足表示真实的程度上。正式地说,如果一个论证在 L1K=中的每个解释中,其结论在前提为真的情况下都为真,那么该论证是有效的。有效性是模型论中推导性的对应。
如果对于每个解释 M,M⊨θ,那么一个句子 θ 在逻辑上是真的,或者有效的。一个句子在逻辑上是真的,当且仅当它是空集的结果。如果 θ 在逻辑上是真的,那么对于任何句子集合 Γ,Γ⊨θ。逻辑真是定理性的模型论对应。
如果存在一个解释 M,使得 M⊨θ,那么一个句子 θ 是可满足的。也就是说,如果存在一个解释使得它满足。如果存在一个解释 M,使得对于 Γ 中的每个句子 θ,M⊨θ,那么句子集合 Γ 是可满足的。如果对于 Γ 中的每个句子 θ,M⊨θ,那么我们说 M 是 Γ 的一个模型。因此,如果一个句子集合有一个模型,那么它是可满足的。可满足性是一致性的模型论对应。
注意,当且仅当集合 Γ,¬θ 不可满足时,才有 Γ⊨θ。由此可知,如果集合 Γ 不可满足,则对于任意句子 θ,都有 Γ⊨θ。这是对应于 ex falso quodlibet 的模型论对应物(见定理 10)。我们有以下类似于定理 12 的结论:
定理 17. 设 Γ 为一组句子。以下各条件等价:(a)Γ 可满足;(b)不存在句子 θ 使得 Γ⊨θ 且 Γ⊨¬θ;(c)存在某个句子 ψ 使得 Γ⊨ψ 不成立。
证明:(a)⇒(b):假设 Γ 可满足,设 θ 为任意句子。存在一种解释 M,使得对于 Γ 中的每个成员 ψ,都有 M⊨ψ。根据否定的子句,我们不能同时有 M⊨θ 和 M⊨¬θ。因此,要么 ⟨Γ,θ⟩ 不成立,要么 ⟨Γ,¬θ⟩ 不成立。(b)⇒(c):这是显然的。(c)⇒(a):假设不成立 Γ⊨ψ。那么存在一种解释 M,使得对于 Γ 中的每个句子 θ,都有 M⊨θ,并且不成立 M⊨ψ。更进一步,M 满足 Γ 的每个成员,因此 Γ 可满足。
5. 元理论
我们现在介绍一些将演绎概念与模型论对应概念联系起来的结果。第一个结果可能是最直接的。我们通过英语术语的含义(或多或少地,在两种情况下都有相同的简化)来解释演绎系统 D 的各种规则和满足性定义中的各种子句。因此,人们期望只有当一个论证在语义上有效时,它才是可演绎的或演绎有效的。
定理 18. 健全性。对于任意的句子 θ 和句子集合 Γ,如果 Γ⊢Dθ,则 Γ⊨θ。
证明:我们通过对用于建立 Γ⊢θ 的子句数量进行归纳来进行。设 n 是一个自然数,并假设对于任何通过少于 n 步推导有效建立的论证,定理成立。假设 Γ⊢θ 是通过恰好 n 步建立的。如果最后应用的规则是(=I),那么 θ 是形式为 t=t 的句子,因此 θ 在逻辑上是真的。因此,Γ⊨θ。如果最后应用的规则是(As),那么 θ 是 Γ 的成员,因此当然满足 Γ 的每个成员也满足 θ。假设最后应用的规则是(&I)。那么 θ 具有形式(ϕ&ψ),我们有 Γ1⊢ϕ 和 Γ2⊢ψ,其中 Γ=Γ1,Γ2。归纳假设给出了 Γ1⊨ϕ 和 Γ2⊨ψ。假设 M 满足 Γ 的每个成员。那么 M 满足 Γ1 的每个成员,因此 M 满足 ϕ。类似地,M 满足 Γ2 的每个成员,因此 M 满足 ψ。因此,根据满足定义中“&”的子句,M 满足 θ。所以 Γ⊨θ。
假设最后应用的子句是(∃E)。那么我们有 Γ1⊢∃vϕ 和 Γ2,ϕ(v|t)⊢θ,其中 Γ=Γ1,Γ2,且 t 不出现在 ϕ、θ 或 Γ2 的任何成员中。
我们需要证明 Γ⊨θ。根据归纳假设,我们有 Γ1⊨∃vϕ 和 Γ2,ϕ(v|t)⊨θ。设 M 是一种解释,使得 M 使得 Γ 的每个成员为真。因此,M 使得 Γ1 和 Γ2 的每个成员为真。然后,对于所有变量赋值 s,M,s⊨∃vϕ,因此存在一个 s'使得 M,s'⊨ϕ。设 M'与 M 仅在 IM'(t)=s'(v)方面不同。那么,M',s'⊨ϕ(v|t)且 M',s'⊨Γ2,因为 t 不出现在 ϕ 或 Γ2 中。因此,M',s'⊨θ。由于 t 不出现在 θ 中且 M'与 M 仅在 IM'(t)方面不同,M,s'⊨θ。由于 θ 是一个句子,s'无关紧要,因此 M⊨θ,如所需。注意这里对(∃E)的限制的作用。其他情况都差不多直接。
推论 19. 设 Γ 是一个句子集合。如果 Γ 是可满足的,则 Γ 是一致的。
证明:假设 Γ 是可满足的。因此,设 M 是一个解释,使得 M 满足 Γ 中的每个成员。假设 Γ 是不一致的。那么存在一个句子 θ,使得 Γ⊢θ 和 Γ⊢¬θ。根据正确性(定理 18),有 Γ⊨θ 和 Γ⊨¬θ。因此,我们有 M⊨θ 和 M⊨¬θ。但是,根据满足的定义中否定的子句,这是不可能的。
尽管演绎系统 D 和模型论语义是根据逻辑术语的含义开发的,但我们不能自动期望正确性的逆(或推论 19)成立。就我们目前所知,我们可能没有包含足够的推理规则来推导出每个有效的论证。正确性和推论 19 的逆是数理逻辑中最重要和最有影响力的结果之一。我们从后者开始。
定理 20. 完备性. 哥德尔 [1930]. 设 Γ 是一个句子集合。如果 Γ 是一致的,那么 Γ 是可满足的。
证明: 完备性的证明相当复杂。我们在这里只概述一下。设 Γ 是 L1K=的一致句子集。同样,为了简单起见,我们假设非逻辑术语集 K 要么是有限的,要么是可数无穷的(尽管即使 K 是不可数的,该定理仍然成立)。我们的任务是找到一个解释 M,使得 M 满足 Γ 中的每个成员。考虑通过在 L1K=中添加一个可数无穷的新个体常量 c0,c1,…而得到的语言。我们规定常量 c0,c1,…互不相同,并且它们都不出现在 K 中。这个构造的一个有趣特点是,由于 Leon Henkin,我们从语言本身构建了语言的一个解释,使用一些常量作为论域的成员。设 θ0(x),θ1(x),…是扩展语言中至多有一个自由变量的公式的一个枚举,以便每个至多有一个自由变量的公式最终都会在列表中出现。通过递归,定义一个句子集(扩展语言的)的序列 Γ0,Γ1,…如下: Γ0=Γ; Γn+1=Γn,(∃xθn→θn(x|ci)),其中 ci 是上述列表中第一个不出现在 θn 或 Γn 的任何成员中的常量。这里的基本思想是,如果 ∃xθn 成立,那么 ci 就是这样的 x。令 Γ 为集合 Γn 的并集。
我们概述一个证明,证明 Γ'是一致的。假设 Γ'是不一致的。根据定理 9,存在 Γ 的一个有限子集是不一致的,因此 Γm 中的一个集合是不一致的。根据假设,Γ0=Γ 是一致的。设 n 是最小的数,使得 Γn 是一致的,但 Γn+1=Γn,(∃xθn→θn(x|ci))是不一致的。根据(¬I),我们有
(1)Γn⊢¬(∃xθn→θn(x|ci)).
根据 ex falso quodlibet 定理(定理 10),Γn,¬∃xθn,∃xθn⊢θn(x|ci)。因此根据(→I),Γn,¬∃xθn⊢(∃xθn→θn(x|ci))。由此和(1),我们有 Γn⊢¬¬∃xθn,通过(¬I),并且通过(DNE)我们有
(2)Γn⊢∃xθn。
通过(作为), Γn,θn(x|ci),∃xθn⊢θn(x|ci)。因此通过(→I),Γn,θn(x|ci)⊢(∃xθn→θn(x|ci))。由此和(1),我们有 Γn⊢¬θn(x|ci),通过(¬I)。让 t 是一个在 θn 或 Γn 的任何成员中都不出现的术语。通过将 t 均匀替换为 ci,我们可以将 Γn⊢¬θn(x|ci)的推导转化为 Γn⊢¬θn(x|t)。通过(∀I),我们有
(3)Γn⊢∀v¬θn(x|v)。
通过(作为),我们有{∀v¬θn(x|v),θn}⊢θn,并且通过(∀E),我们有{∀v¬θn(x|v),θn}⊢¬θn。因此{∀v¬θn(x|v),θn}是不一致的。让 ϕ 是语言中的任何句子。通过 ex falso quodlibet 定理(定理 10),我们有{∀v¬θn(x|v),θn}⊢ϕ 和{∀v¬θn(x|v),θn}⊢¬ϕ。因此,结合(2),我们有 Γn,∀v¬θn(x|v)⊢ϕ 和 Γn,∀v¬θn(x|v)⊢¬ϕ,通过(∃E)。通过割接定理(定理 11),Γn⊢ϕ 和 Γn⊢¬ϕ。因此,Γn 是不一致的,与假设相矛盾。因此,Γ′是一致的。
应用林登鲍姆引理(定理 13),让 Γ′′成为一个包含 Γ′的最大一致句子集(扩展语言的句子集)。因此,当然,Γ′′包含 Γ。我们现在可以定义一个解释 M,使得 M 满足 Γ′′的每个成员。
如果语言中没有一个表示身份的符号,我们将让 M 的域成为新常量的集合{c0,c1,...}。但是由于 Γ′′中可能存在形式为 ci=cj 的句子,其中 i≠j。如果是这样,我们不能同时在解释的域中有 ci 和 cj(因为它们是不同的常量)。因此,我们将 M 的域 d 定义为集合{ci | 没有 j<i 使得 ci=cj 在 Γ′′中}。换句话说,如果 Γ′′没有声明常量 ci 与列表中的先前常量相同,那么常量 ci 就在 M 的域中。请注意,对于每个新常量 ci,存在一个 j≤i 使得 cj 在 d 中,并且句子 ci=cj 在 Γ′′中。
现在我们定义解释函数 I。让 a 是扩展语言中的任意常量。根据(=I)和(∃I),Γ′′⊢∃xx=a,因此 ∃xx=a∈Γ′′。根据 Γ′的构造,存在一个形式为(∃xx=a→ci=a)的句子在 Γ′′中。我们有 ci=a 在 Γ′′中。如上所述,存在一个 cj 在 d 中,使得 ci=cj 在 Γ′′中。令 I(a)=cj。请注意,如果 ci 是域 d 中的常量,则 I(ci)=ci。也就是说,域 d 中的每个 ci 都表示它自己。
设 K 中的零元谓词字母为 P。那么如果 P 在 Γ′′中,I(P)为真;否则,I(P)为假。设 K 中的一元谓词字母为 Q。那么 I(Q)是常量集合{ci|ci 在 d 中且 Qc 在 Γ′′中}。设 K 中的二元谓词字母为 R。那么 I(R)是常量对的集合{⟨ci,cj⟩|ci 在 d 中,cj 在 d 中且 Rcicj 在 Γ′′中}。三元谓词等类似地解释。实际上,I 将非逻辑术语解释为它们在 Γ′′中的样子。
证明的最后一项是一个引理,对于扩展语言中的每个句子 θ,当且仅当 θ 在 Γ′′中时,M⊨θ。这是通过对 θ 的复杂性进行归纳来进行的。当 θ 是原子时,根据 M(即域 d 和解释函数 I)的定义可得。其他情况则根据满足定义中的各个子句得出。
由于 Γ⊆Γ′′,我们知道 M 满足 Γ 中的每个成员。根据定理 15,将 M 限制在原始语言 L1K=和 s 上也满足 Γ 中的每个成员。因此,Γ 是可满足的。
与正确性(定理 18)相反的是一个直接的推论:
定理 21. 对于任意的句子 θ 和句子集合 Γ,如果 Γ⊨θ,则 Γ⊢Dθ。
证明:假设 Γ⊨θ。那么不存在解释 M,使得 M 满足 Γ 的每个成员但不满足 θ。因此,集合 Γ,¬θ 是不可满足的。根据完备性(定理 20),Γ,¬θ 是不一致的。因此存在一个句子 ϕ,使得 Γ,¬θ⊢ϕ 和 Γ,¬θ⊢¬ϕ。根据(¬I),Γ⊢¬¬θ,根据(DNE),Γ⊢θ。
我们的下一个项目是定理 9 的推论,即正确性(定理 18)和完备性:
推论 22. 紧致性. 如果一个句子集合 Γ 是可满足的,那么当且仅当 Γ 的每个有限子集都是可满足的。
证明:如果 M 满足 Γ 的每个成员,那么 M 满足 Γ 的每个有限子集的成员。对于逆命题,假设 Γ 不可满足。然后我们证明 Γ 的某个有限子集不可满足。根据完备性(定理 20),Γ 是不一致的。根据定理 9(和弱化),存在一个 Γ 的有限子集 Γ',使得 Γ'是不一致的。根据推论 19,Γ'是不可满足的。
健全性和完备性共同意味着一个论证是可推导的当且仅当它是有效的,而一组句子是一致的当且仅当它是可满足的。因此,我们可以在模型论和证明论的概念之间来回转换,将一个的属性转移到另一个上。紧凑性在模型论中成立,因为所有的推导只使用有限数量的前提。
回想一下在完备性的证明(定理 20)中,我们做了一个简化的假设,即非逻辑常量集合 K 要么是有限的,要么是可数无穷的。我们产生的解释本身要么是有限的,要么是可数无穷的。因此,我们有以下结论:
推论 23. Löwenheim-Skolem 定理。设 Γ 是语言 L1K=的一个可满足的句子集。如果 Γ 要么是有限的,要么是可数无穷的,则 Γ 有一个模型,其域要么是有限的,要么是可数无穷的。
一般来说,设 Γ 是 L1K=的可满足句子集,κ 是 Γ 的大小和可数无穷中较大的一个。那么 Γ 有一个模型,其域的大小最多为 κ。
有一个更强的推论 23 的版本。设 M1=⟨d1,I1⟩ 和 M2=⟨d2,I2⟩ 是语言 L1K=的解释。如果对于每个常量 c,d1⊆d2 且 I1(c)=I2(c),且 I1 是 I2 在 d1 上的限制,则定义 M1 是 M2 的子模型。例如,如果 R 是 K 中的二元关系符号,那么对于 d1 中的所有 a、b,当且仅当 ⟨a,b⟩ 在 I2(R)中时,⟨a,b⟩ 在 I1(R)中。如果我们在非逻辑术语中包含了函数符号,那么我们还需要要求 d1 在 M2 中的解释下是封闭的。注意,如果 M1 是 M2 的子模型,则 M1 上的任何变量赋值也是 M2 上的变量赋值。
如果两个解释 M1=⟨d1,I1⟩ 和 M2=⟨d2,I2⟩ 是等价的,那么它们中的一个是另一个的子模型,并且对于语言中的任何公式和子模型上的任何变量赋值 s,当且仅当 M2,s⊨θ 时,M1,s⊨θ。注意,如果两个解释是等价的,则它们满足相同的句子。
定理 25. 下降的 Löwenheim-Skolem 定理。设 M=⟨d,I⟩ 是语言 L1K=的一个解释。设 d1 是 d 的任意子集,κ 是 K 的大小、d1 的大小和可数无穷的最大值。那么存在一个子模型 M′=⟨d′,I′⟩,满足以下条件:(1) d′不超过 κ,(2) M 和 M′是等价的。特别地,如果非逻辑术语的集合 K 是有限的或可数无穷的,那么任何解释都有一个等价的子模型,其域要么是有限的,要么是可数无穷的。
证明:像完备性一样,这个证明是复杂的,我们只给出一个概要。下降的 Löwenheim-Skolem 定理涉及到选择公理,并且实际上等价于选择公理(参见选择公理的条目)。因此,设 C 是 d 的幂集上的选择函数,对于每个非空子集 e⊆d,C(e)是 e 的一个成员。我们规定,如果 e 是空集,则 C(e)是 C(d)。
设 s 是 M 上的变量赋值,θ 是 L1K=的一个公式,v 是一个变量。定义 θ 在 s 上的 v-见证,记作 wv(θ,s),如下所示:设 q 是所有元素 c∈d 的集合,使得存在一个变量赋值 s′在 M 上与 s 在除了 v 以外的每个变量上都一致,满足 M,s′⊨θ,且 s′(v)=c。那么 wv(θ,s)=C(q)。注意,如果 M,s⊨∃vθ,则 q 是域中可以替代 θ 中的 v 的元素的集合。实际上,当且仅当 q 非空时,M,s⊨∃vθ。因此,如果 M,s⊨∃vθ,则 wv(θ,s)(即 C(q))是域中可以替代 θ 中的 v 的元素的一个选择。在某种意义上,它是验证 M,s⊨∃vθ 的一个“见证”。
如果 e 是域 d 的非空子集,则定义变量赋值 s 为 e-赋值,如果对于所有变量 u,s(u)属于 e。也就是说,如果 s 将 e 的元素分配给每个变量,则 s 是 e-赋值。定义 sk(e),即 e 的 Skolem 壳,为集合:
e∪{wv(θ,s)|θ 是 L1K=中的公式,v 是变量,s 是 e-赋值}。
也就是说,e 的 Skolem 壳是 e 与每个 e-赋值上的每个公式的 v-见证的集合。粗略地说,这个想法是从 e 开始,然后加入足够的元素使得每个存在量词的公式都成立。然而,我们不能满足于 Skolem 壳。一旦我们将“见证”投入到域中,我们就需要处理 sk(e)的赋值。实际上,我们需要一个集合,它是自己的 Skolem 壳,并且还包含给定的子集 d1。
我们按照以下方式定义一个非空集合序列 e0,e1,...:如果给定的子集 d1 为空,并且 K 中没有常量,则令 e0 为 C(d),即应用于整个域的选择函数;否则,令 e0 为 d1 和 K 中常量在 I 下的指称的并集。对于每个自然数 n,en+1 为 sk(en)。最后,令 d'为 en 的并集,令 I'为 I 在 d'上的限制。我们的解释是 M' = ⟨d',I'⟩。
显然,d1 是 d'的子集,因此 M'是 M 的子模型。设 κ 为 K 的大小、d1 的大小和可数无穷的最大值。计算表明,d'的大小最多为 κ,这基于以下事实:最多有 κ 个公式,因此每个阶段最多有 κ 个见证人。顺便提一下,这个计算依赖于可数个大小不超过 κ 的集合的并集本身不超过 κ 的事实。这也依赖于选择公理。
最后一项是要证明 M'等价于 M:对于每个公式 θ 和 M'上的每个变量赋值 s,
M,s⊨θ 当且仅当 M′,s⊨θ。
证明通过对 θ 的复杂性进行归纳进行。不幸的是,空间限制要求我们将此步骤留作练习。
紧致性的另一个推论(推论 22)是 Löwenheim-Skolem 定理的相反:
定理 26. 上升的 Löwenheim-Skolem 定理。设 Γ 是 L1K=的任意一组句子集合,对于每个自然数 n,存在一个解释 Mn=⟨dn,In⟩,使得 dn 至少有 n 个元素,并且 Mn 满足 Γ 的每个成员。换句话说,Γ 是可满足的,并且满足 Γ 的解释的大小没有有限的上界。那么对于任意的无限基数 κ,存在一个解释 M=⟨d,I⟩,使得 d 的大小至少为 κ,并且 M 满足 Γ 的每个成员。
证明:向语言中添加一个大小为 κ 的新常量集合{cα|α<κ},使得如果 c 是 K 中的一个常量,则 cα 与 c 不同,并且如果 α<β<κ,则 cα 与 cβ 是不同的常量。考虑由 Γ 和集合{¬cα=cβ|α≠β}组成的句子集合 Γ′。也就是说,Γ′由 Γ 和关于任意两个不同的新常量表示不同对象的陈述组成。设 Γ′′是 Γ′的任意有限子集,m 是 Γ′′中出现的新常量的数量。然后,通过将 Γ′′中的每个新常量解释为域 dm 中的不同成员,将解释 Mm 扩展为新语言的解释 M′m。根据假设,dm 中有足够的成员来做到这一点。其他新常量可以任意解释。因此,Mm 是 M′m 的限制。根据假设(和定理 15),M′m 满足 Γ 的每个成员。此外,M′m 满足 Γ′′中的{¬cα=cβ|α≠β}的成员。因此,M′m 满足 Γ′′的每个成员。根据紧致性定理,存在一个解释 M=⟨d,I⟩,使得 M 满足 Γ′的每个成员。由于 Γ′包含{¬cα=cβ|α≠β}的每个成员,M 的域 d 的大小必须至少为 κ,因为每个新常量必须具有不同的指称。根据定理 15,M 对原始语言 L1K=的限制满足 Γ 的每个成员。
综合来看,下行和上行 Löwenheim-Skolem 定理的证明表明,对于任何可满足的句子集合 Γ,如果 Γ 的模型没有有限的界限,那么对于任何无限基数 κ,存在一个 Γ 的模型,其域的大小恰好为 κ。此外,如果 M 是任何一个域为无限的解释,那么对于任何无限基数 κ,存在一个解释 M',其域的大小恰好为 κ,使得 M 和 M'是等价的。
这些结果表明了一阶语言(如 L1K=)的表达资源的不足之处。没有一个可满足的句子集合能够保证其模型都是可数无穷的,也没有一个可满足的句子集合能够保证其模型是不可数的。因此,在某种意义上,一阶语言不能在模型论中表达“可数无穷”的概念。(参见关于二阶和高阶逻辑的条目。)
设 A 是一阶语言 L1K=中的任意一组句子的集合,其中 K 包括算术术语,并假设 A 的每个成员都对自然数成立。我们甚至可以让 A 成为 L1K=中对自然数成立的所有句子的集合。那么 A 具有不可数的模型,事实上具有任意无限基数的模型。这些解释有时被称为意外的或非标准的算术模型之一。设 B 是对实数成立的一阶句子的任意集合,C 是集合论的任意一阶公理化。那么如果 B 和 C 在无限解释中是可满足的,那么它们每个都有可数无限的模型。也就是说,任何一阶可满足的集合论或实数理论都具有(意外的)与自然数大小相同的模型。尽管在大多数集合论中,有一个(表面上)断言宇宙是不可数的可证明的句子。这种情况被称为斯科勒姆悖论,引发了很多讨论,但我们必须将读者引向其他地方以了解其中的一部分(参见斯科勒姆悖论和 Shapiro 1996)。
6. 唯一正确的逻辑?
当然,逻辑与正确推理有某种关系,或者至少与正确的演绎推理有关。这种关系的细节是微妙而有争议的-参见 Harman [1984] 的一项有影响力的研究。通常会说,如果某人没有逻辑推理,他们的推理就是不好的,或者如果一个(演绎)论证被证明是无效的,那么它必须被撤回。
一些哲学家和逻辑学家坚持认为存在一个唯一正确的逻辑系统,其在描述有效性方面具有独特的角色。其中,一些人,也许是大多数人,认为经典的一阶逻辑是唯一正确的,是唯一真正的逻辑。例如,参见奎因 [1986]、雷斯尼克 [1996]、朗菲特 [2015]、威廉姆森 [2017] 等众多学者。
经典的一阶逻辑被赋予这个角色或许并不令人意外。它具有更或多或少直观的规则,并且在强大的同时也很简单。正如我们在第 5 节中所看到的,经典的一阶逻辑具有有趣且重要的元理论性质,如完备性和一致性,这些性质导致了许多重要的数学和逻辑研究。
然而,正如前面所提到的,经典的一阶逻辑的主要元理论性质导致了形式语言和模型论语义的表达限制。关键概念,如有限性、可数性、最小闭包、自然数等等无法被表达。
巴尔维斯 [1985 年,5] 曾经说过:
作为逻辑学家,我们通过让别人相信逻辑是一阶的,然后又让他们相信现代数学的几乎所有概念实际上都无法用一阶逻辑来捕捉,对我们的学科造成了不利影响。
王 [1974 年,154] 也曾说过:
当我们对集合论或经典分析感兴趣时,通常将 Löwenheim-Skolem 定理视为一种缺陷...第一阶逻辑...所建立的不是第一阶逻辑是唯一可能的逻辑,而是当我们在某种意义上否认 [不可数的] 概念的现实性时,它是唯一可能的逻辑...
对经典的第一阶逻辑也提出了其他批评。它在处理某些悖论时存在问题(例如,参见 Russel 悖论的条目),它表面上产生了过多的信念(参见逻辑的规范地位的条目),有人认为它有一些与我们通常认为的思维方式不符的论证(例如,参见相关逻辑的条目)。
对于那些对经典的第一阶逻辑作为唯一真理逻辑持批判态度的人来说,有两个主要选择。一个是提出其他逻辑作为唯一真理逻辑。Priest [2006a] 描述了一个可能用来确定唯一真理逻辑的方法。
另一个主要选择是简单地否认存在一个合格为唯一真正逻辑的逻辑。其中一种情况是一种逻辑虚无主义,即不存在正确的逻辑的论点。另一种是逻辑多元主义,即多种不同的逻辑都被认为是正确的、最好的,甚至是真正的逻辑,至少在不同的语境中。
当然,这不是详细讨论这个问题的地方。参见 Beall 和 Restall [2006] 以及 Shapiro [2014],了解多元主义的例子,以及关于逻辑多元主义和逻辑虚无主义的概述。
我们以简要概述一些与经典一阶逻辑的主要替代方案,并提供其他工作和本百科全书条目的参考。另请参阅 Shapiro 和 Kouri Kissel [2022] 的后半部分。
6.1 经典逻辑的竞争对手
近似
近年来,一些工作已经开始“近似”经典逻辑。其思想是尽可能接近经典逻辑,以保留一些好处,同时消除经典逻辑的一些限制,比如更接近直观推理或适用于模糊和悖论等问题。
例如,Barrio、Pailos 和 Szmuc [2020] 表明我们可以在称为 ST 层次结构(ST 代表严格容忍,来自 Cobreros、Egre、Ripley 和 van Rooij [2012a,b])中近似经典逻辑。这使他们能够在层次结构的每个层次上避免某些经典问题,如一些悖论,同时在考虑完整的层次结构时保持许多经典逻辑的优势。
Dave Ripley [2013] 提供了一个“经典逻辑”的多序列演算版本,他认为这解决了一些悖论。值得注意的是,他声称至少解决了 Sorites 悖论和 Liar 悖论(请参阅关于 Sorites 悖论和 Liar 悖论的条目)。该系统保守地扩展了经典逻辑。Ripley 声称这就是使它成为经典的原因。然而,该系统不具有传递性,也没有割除规则。
当然,关于这些新逻辑是否真正是经典的问题还有一些疑问,但这仍然是有启发性的工作。
扩展
扩展经典的一阶逻辑的一种方法是在基础形式语言中添加额外的运算符。模态逻辑添加了指定必然性和可能性的运算符。因此,我们可以说一个命题可能为真,或者必然为真,而不仅仅是真。
W. V. O Quine [1953] 曾经争论过,在模态运算符内部绑定量词是不连贯的,但是对于这个问题的观点已经发生了相当大的变化(参见,例如,Barcan [1990])。现在有一个蓬勃发展的行业致力于发展模态逻辑来捕捉各种形式的模态和时间运算符。请参阅模态逻辑的条目。
上述所描绘的所有形式语言只有一种变量类型。有时候这些变量被称为一阶变量。语言的每个解释都有一个域,即这些一阶变量的范围。根据给定的解释,这就是语言所涉及的内容。二阶变量的范围包括该域中的属性、集合、类、关系或函数。三阶变量的范围包括二阶变量的范围中的属性、类、关系等。以此类推。
如果一个形式语言具有二阶变量和一阶变量,并且没有其他变量,则称为二阶语言;如果它具有三阶、二阶和一阶变量,并且没有其他变量,则称为三阶语言,依此类推。如果一个形式语言至少是二阶的,则称为高阶语言。
正如已经指出的,毫不夸张地说,经典的一阶逻辑是当代逻辑理论的范式。大多数教科书根本不提及高阶语言,而其余的大部分只是简单地提及一下。
已经为二阶及更高阶语言提出了许多不同的演绎系统和模型论语义。对于语义而言,模型论的主要附加特征是指定了更高阶变量的范围。
在亨金语义中,每个解释都指定了更高阶变量的特定范围。对于单调二阶变量,每个解释都指定了域的幂集的非空子集,对于二元二阶变量,指定了域成员的有序对的非空集合,等等。该系统具有所有上述限制性元理论结果。存在一个对于亨金语义而言既完备又正确的演绎系统;逻辑是紧凑的;并且下降和上升的勒文海姆-斯科勒姆定理都成立。
在所谓的标准语义中,有时也称为完全语义,单调二阶变量的范围涵盖整个域的幂集;二元二阶变量的范围涵盖整个域成员的有序对类,等等。可以证明,具有标准语义的二阶语言可以表征许多数学概念和结构,直到同构为止。例如,有限性、可数性、良基性、最小闭包以及自然数、实数和复数等结构。因此,经典的一阶逻辑的限制性定理都不成立:没有一个既完备又正确的有效演绎系统,逻辑不是紧凑的,而且勒文海姆-斯科勒姆定理都不成立。一些人,如奎因 [1986],认为具有标准语义的二阶逻辑实际上不是逻辑,而是一种数学形式,特别是集合论。有关更多信息,请参见 Shapiro [1991] 和关于高阶逻辑的条目,以及其中引用的许多参考文献。
人们还可以将广义量词视为经典一阶逻辑的扩展(参见广义量词条目)。这些量词允许在经典的“所有”和“一些”之间进行扩展,并可以容纳像“大多数”、“少于一半”、“通常”等量词。它们在逻辑和语言学角度上都很有用。例如,肯尼迪和瓦纳宁 [2021] 使用广义量词来论证“不可数”是一个逻辑概念。
6.2 经典一阶逻辑的子逻辑
一些哲学家和逻辑学家认为经典一阶逻辑太强了:它宣称一些论证形式是有效的,但实际上并不是。在这里,我们概述两种提议。
直觉逻辑
直觉逻辑的拥护者否定(所谓的)排中律的有效性:
Φ∨¬Φ,
以及与此相关的其他推论,例如双重否定消除(DNE):
如果 Γ⊢¬¬Φ,则 Γ⊢Φ
粗略地说,这些限制有两个主要动机。传统直觉主义者 L. E. J. Brouwer(例如,[1964a],[1964b])和 Arend Heyting(例如,[1956])认为数学的本质是理想化的心智构建。例如,考虑命题:对于每个自然数 n,存在一个大于 n 但小于 n!+2 的素数 m。对于 Brouwer 来说,这个命题涉及一个过程,给定任何自然数 n,产生一个大于 n 但小于 n!+2 的素数 m。该命题表达了这样一个过程的存在。在这种取向下,我们没有理由认为对于任何数学命题 Φ,我们可以建立与 Φ 相关的过程或与 ¬Φ 相关的过程。
迈克尔·达姆特(例如,[1978])提供了关于语言如何作为沟通工具发挥功能的一般论证,以证明直觉逻辑是唯一正确的、唯一真正的逻辑,不仅适用于数学。
有关直觉逻辑及其哲学动机的概述,请参阅有关直觉逻辑的条目。
关于相关性和超一致性的解释
这次目标推理,被宣布无效的是我们上面称之为 ex falso quodlibet(EFQ)的推理:如果 Γ1⊢Θ 和 Γ2⊢¬Θ,则 Γ1,Γ2⊢Ψ 我们可以关注这种情况的一种实例:Φ,¬Φ⊢Ψ,有时被称为“爆炸”。它表明任何事物都可以从矛盾中推导出来。
将(EFQ)视为无效的逻辑学被称为可矛盾逻辑学。广义上讲,有两派逻辑学家主张可矛盾系统,要么作为唯一真正的逻辑学的候选,要么作为多元论的实例。其中一派由坚持在有效的论证中,前提必须与结论相关的逻辑学家组成。通常,相关逻辑学家也不同意某些被称为材料蕴涵悖论的经典逻辑真理,例如(Φ→(Ψ→Φ))和(Φ→(Ψ→Ψ))。
更多信息,请参阅关于相关逻辑的条目,或参考 Kerr [2019]。经典著作包括 Anderson and Belnap [1975],Anderson Belnap and Dunn [1992],以及 Read [1988]。Neil Tennant 的 [2017] 核心逻辑既是相关逻辑又是直觉主义逻辑。
另一个主要的逻辑学派别是偏好矛盾逻辑(或矛盾逻辑学)的逻辑学家,他们是二值逻辑的拥护者,即一些形式为(Φ∧¬Φ)的句子是真的观点。一个被认为是例子的情况是当 Φ 是一个语义悖论的陈述,比如说谎者悖论。例如,考虑一个句子 Φ,它说 Φ 不是真的。
在一个满足(EFQ)的系统中,任何真正的矛盾都会蕴含形式语言的每个句子,从而使语言和理论变得琐碎。因此,显然,任何支持矛盾逻辑的逻辑学都必须是偏矛盾的。请参阅关于矛盾论的条目。这里的经典著作是普里斯特 [2006a]。
当然,这里所呈现的小样本并不包括每个被提出作为古典一阶逻辑的竞争对手的逻辑系统,无论是作为唯一真正的逻辑的候选,还是作为逻辑多元主义的进一步实例。例如,请参阅关于子结构逻辑、模糊逻辑和其他许多逻辑的条目。
Bibliography
Anderson, Alan and Nuel Belnap, 1975, Entailment: The logic of relevance and necessity I, Princeton: Princeton University Press.
Anderson, Alan, Nuel Belnap, and J. Michael Dunn, 1992, Entailment: The logic of relevance and necessity II, Princeton: Princeton University Press.
Barcan Marcus, Ruth. 1990, “A Backwards Look at Quine’s Animadversions on Modalities,” in R. Bartrett and R. Gibson (eds.), Perspectives on Quine, Cambridge: Blackwell.
Barrio, Eduardo Alejandro., Federico Pailos, and Damian Szmuc, 2020, “A Hierarchy of Classical and Paraconsistent Logics”, J Philos Logic, 49: 93–120. doi:10.1007/s10992-019-09513-z
Barwise, Jon, 1985, “Model-theoretic logics: background and aims”, in Model-theoretic logics, edtied by Jon Barwise and Soloman Feferman (eds.), New York, Springer-Verlag, pp. 3–23.
Beall, Jc and Greg Restall, 2006, Logical Pluralism, Oxford: Oxford University Press.
Brouwer, L.E.J., 1949, “Consciousness, Philosophy and Mathematics”, Journal of Symbolic Logic, 14(2): 132–133.
–––, 1964b, “Intuitionism and Formalism”, in Philosophy of mathematics: selected readings edited by P. Benacerraf and H. Putnam, Englewood Cliffs, NJ, Cambridge University Press, (eds.), 77–89.
Cobreros, Pablo, Paul Egré, David Ripley, and Robert van Rooij, 2012, “Tolerance and Mixed Consequence in the S’valuationist Setting”, Studia logica, 100(4), 855–877.
–––, 2012, “Tolerant, classical, strict”, Journal of Philosophical Logic, 41(2), 347–385.
Cook, Roy, 2002, “Vagueness and mathematical precision”, Mind, 111: 227–247.
Corcoran, John, 1973, “Gaps between logical theory and mathematical practice”, The methodological unity of science, ed. by M. Bunge, Dordrecht: D. Reidel, 23–50.
Davidson, Donald, 1984, Inquiries into truth and interpretation, Oxford: Clarendon Press.
Dummett, Michael, 2000, Elements of intuitionism, second edition, Oxford: Oxford University Press.
–––, 1978, “The philosophical basis of intuitionistic logic”, in Truth and other enigmas, Cambridge, MA, Harvard University Press, 215–247.
Gödel, Kurt, 1930, “Die Vollständigkeit der Axiome des logischen Funktionenkalkuls”, Montatshefte für Mathematik und Physik 37, 349–360; translated as “The completeness of the axioms of the functional calculus of logic”, in van Heijenoort 1967, 582–591.
Harman, Gilbert, 1984, “Logic and reasoning”, Synthese, 60, 107–127.
Heyting, A., 1956, Intuitionism, Amsterdam: North-Holland Publishing.
Kerr, Alison Duncan, 2019, “A plea for KR”, Synthese, 198(4): 3047–3071.
Lycan, William, 1984, Logical form in natural language, Cambridge, MA: The MIT Press.
Montague, Richard, 1974, Formal philosophy, ed. by R. Thomason, New Haven: Yale University Press.
Kennedy, Juliette, and Jouko Väänänen, 2021, Logicality and modelclasses. Bulletin of Symbolic Logic, 27(4): 385–414.
Priest, Graham, 2006a, In contradiction, a study of the transconsistent, second, revised edition, Oxford: Clarendon Press.
–––, 2006b, Doubt truth to be a liar, Oxford: Clarendon Press.
Quine, W. V. O., 1960, Word and object, Cambridge, MA: The MIT Press.
–––, 1953, “Three grades of modal involvement”, Proceedings of the XIth International Congress of Philosophy, 14, Amsterdam, North Holland Publishing Company, 65–81.
–––, 1986, Philosophy of logic, second edition, Cambridge, Massachusetts: Harvard University Press.
–––, 1986, Philosophy of logic, second edition, Englewood Cliffs: Prentice-Hall.
Read, Stephen, 1988, Relevant logic, Oxford: Oxford University Press.
Resnik, Michael, 1996, “Ought there to be but one true logic”, in Logic and Reality: Essays on the Legacy of Arthur Prior, J. Copeland (ed.), Oxford: Oxford University Press, 489–517.
Ripley, David, 2013, “Paradoxes and Failures of Cut”, Australasian Journal of Philosophy, 91(1): 139–164.
Rumfitt, Ian, 2015, The Boundary Stones of Thought: An Essay in the Philosophy of Logic, Oxford: Oxford University Press.
Shapiro, Stewart, 1991, Foundations without Foundationalism, Oxford: Clarendon Press.
–––, 1996, The limits of logic: Second-order logic and the Skolem paradox, The international research library of philosophy, Dartmouth Publishing Company, 1996. (An anthology containing many of the significant later papers on the Skolem paradox.)
–––, 1998, “Logical consequence: models and modality”, in The philosophy of mathematics today, edited by M. Schirn, Oxford: Oxford University Press, 131–156.
–––, 2014, Varieties of Logic, Oxford: Oxford University Press.
Shapiro, Stewart and Teresa Kouri Kissel, Classical, first order logic, Cambridge Elements, Cambridge, Cambridge University Press.
Tennant, Neil, 1997, The taming of the true, Oxford: Clarendon Press.
Van Heijenoort, Jean, 1967, From Frege to Gödel, Cambridge, Massachusetts: Harvard University Press. An anthology containing many of the major historical papers on mathematical logic in the early decades of the twentieth century.
Wang, Hao, 1974, From Mathematics to Philosophy, London, Routledge and Kegan Paul.
Williamson, Timothy, 2017, “Semantic paradoxes and abductive methodology”, in Reflections on the liar edited by Bradley Armour-Garb, Oxford, Oxford University Press, 325–346.
Further Reading
There are many fine textbooks on mathematical logic. A sample follows.
Boolos, George S., John P. Burgess, and Richard C. Jeffrey, 2007, Computability and logic, fifth edition, Cambridge, England: Cambridge University Press. Elementary and intermediate level.
Bergmann, Merrie, James Moor, and Jack Nelson, 2013, The logic book, sixth edition, New York: McGraw-Hill. Elementary and intermediate level.
Church, Alonzo, 1956, Introduction to mathematical logic, Princeton: Princeton University Press. Classic textbook.
Enderton, Herbert, 1972, A mathematical introduction to logic, New York: Academic Press. Textbook in mathematical logic, aimed at a mathematical audience.
Forbes, Graeme, 1994, Modern Logic, Oxford: Oxford University Press. Elementary textbook.
Mendelson, Elliott, 1987, Introduction to mathematical logic, third edition, Princeton: van Nostrand. Intermediate.
Academic Tools
Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO). | |
Enhanced bibliography for this entry at PhilPapers, with links to its database. |
Other Internet Resources
[Please contact the author with suggestions.]
Related Entries
logic: free | logic: infinitary | logic: intuitionistic | logic: linear | logic: modal | logic: paraconsistent | logic: relevance | logic: second-order and higher-order | logic: substructural | logic: temporal | logical consequence | logical form | logical truth | model theory | model theory: first-order | paradox: Skolem’s | proof theory: development of
Copyright © 2022 by Stewart Shapiro <shapiro.4@osu.edu> Teresa Kouri Kissel <tkouri@odu.edu>
最后更新于