哥德尔不完备定理
哥德尔不完备定理（）是数理逻辑中的两条定理，探讨了形式化公理系统中可证明性的局限性。这些结果由库尔特·哥德尔于1931年发表，在数理逻辑和数学哲学领域都具有重要意义。人们普遍认为，这些定理表明希尔伯特计划——即为所有数学寻找一套完备且一致的公理系统——是不可能实现的。 第一定理指出： 这是形式逻辑中的定理，容易被错误表述。有许多命题听起来很像是哥德尔不完备定理，但事实上并不是。具体实例见对哥德尔定理的误解。 把第一条定理的证明过程在系统…
标签：#模型论
共 21 篇文章
布尔值模型
在数理逻辑中，布尔值模型是普通的塔斯基主义者的结构或模型概念的推广，在其中命题的真值不被限定为"真"和"假"，而是从某个固定的完全布尔代数中取值，布尔值模型是 Dana Scott、Robert M. Solovay 和 Petr Vopěnka 在1960年代为了帮助理解 Paul Cohen 的力迫方法而介入的。 定义 固定一个完全布尔代数 B 和一阶语言 L，后者由一组常量符号、函数符号和关系符号构成。L 的布尔值模型因此就由全集…
泛函谓词
在形式逻辑和相关的数理逻辑系统中，泛函谓词（functional predicate）或函数性谓词，是一种描述元素间关系的特殊谓词，其使得对于给定论域内的每一个元素，都有且仅有一个对应元素，满足该谓词所定义的逻辑关系。从直观上看，它在逻辑结构中起到了函数的作用，在特定的理论或公理化系统中满足唯一性与存在性约束。因此，泛函谓词在逻辑效果上类似于数学中的函数，其代表符号——谓词符号（predicate symbol）等价于函数符号。 函数符…
超積
數學上，超積（）是常見於抽象代數和數理邏輯（尤其模型論和集合論）的構造。超積是一族無窮多個结构之直積的商結構，不過要求該族結構具有相同的。超冪（）則是超積中各因子為同一個結構的特殊情況。 舉例，給定一個域，可以用超冪構造出新的域。超實數域便是實數域的超冪之一。 超積有一些出奇的應用。用超積，可以寫出紧致性定理與完備性定理的優雅證明。的超冪定理，從代數角度刻劃了「初等等價」此種語義概念。亞伯拉罕·魯濱遜和埃利亞斯·扎孔（）用超結構及其單同…
非标准模型
在数理逻辑的模型论中，称某理论的模型为非标准模型（），如果它与预期模型（或称标准模型）不同构。如果预期模型是无限的, 且使用的语言是一阶的，则非标准模型的存在性由勒文海姆–斯科伦定理保证。非标准模型可被选为预期模型的初等扩张或初等子结构。 非标准模型在集论、非标准分析，以及非标准算术模型中有所研究。
保守扩展
保守扩展是逻辑中的一个概念。一个知识库K'是K的扩展，如果K是K'的一个子集；K'是K的保守扩展，如果对所有-{只}-用K中的名字构造的命题\alpha, K'\vDash \alpha 当且仅当 K\vDash \alpha。换句话说，保守扩展不会改变原有的知识库的结构。保守扩展在许多领域都有应用，如模块化本体和敏感知识的保护。 在逻辑和推导机制中，I和J分别是一个解释(Interpretation),如果J是I的保守扩展，必须满足以…
选择公理
R为指标集的集族；也就是说，对每一个实数i，均存在一个集合 Si，如图所示。每一个集合包含至少一个（可能是无限个）元素。选择公理可以断言，我们可以从每一个集合中选择一个元素，组成一个在R上的索引族(xi)，这里xi∈Si，i∈R。一般情况下，指标集可以是任意集合I，而不仅仅是R。]] 选择公理（，縮寫AC）是数学中的一条集合论公理，用來證明一些難以明確構造的物件的存在性。选择公理最早于1904年，由恩斯特·策梅洛为了证明良序定理而作為一…
勒文海姆–斯科伦定理
在数理逻辑中，经典勒文海姆–斯科伦定理（）声称对于标识（signature）为 的任何可数一阶逻辑语言 L 和 L-结构 M，存在一个可数无限基本子结构 N \subseteq M。 这个定理的自然和有用的推论是所有一致的 L-理论都有可数的模型。 这里的标识由常量集合 \mathbf{C}、函数集合 \mathbf{F}、关系符号集合 \mathbf{R}、和表示函数和关系符号的元数的函数 \sigma: \mathbf{F} \cu…
模型论
模型论（）一般是指数学中集合论的论述角度对数学概念表现（representation）的研究，或者说是对于作为数学形式系统基础的“模型”的研究。粗略地说，该学科假定有一些既存的数学抽象对象(abstract objects)，然后研究：当这些对象之间的一些运算或者一些关系乃至一组公理被给定时，可以相应证明出什么，以及如何证明。 比如实数理论中一个模型论概念的例子是：我们从一个任意集合开始，作为集合元素的每个个体都是一个实数，其间有一些关…
基本子结构
在模型论，给定在同一个语言 L 中的两个结构 M 和 N，我们称 M 是 N 的基本子结构（）如果 1. M 是 N 的子结构，且 2. 对于所有有限元组 a\in M，对于所有语言 L 的公式 \varphi(x)，我们有 M\models \varphi(a) 当且仅当 N\models \varphi(a)。 我们称 N 是 M 的基本扩展当且仅当 M 是 N 的基本子结构。 等价条件 有时对第二个条件使用一个等价的陈述。我们可以…
前束范式
在谓词演算中，如果一个公式可以被写为量词在前，被称为母体的无量词部分在后的形式，则称其为前束范式的，所有经典逻辑公式都逻辑等价于某个前束范式公式。 可以用公式在如下重写规则下的逻辑等价来证实： :\forall x ( P(x) ) \land Q \equiv \forall x ( P(x) \land Q ) :\forall x ( P(x) ) \lor Q \equiv \forall x ( P(x) \lor Q ) :…
可靠性定理
可靠性定理是数理逻辑的最基本结果。它们有关于某个形式逻辑语言与这个语言的形式演绎系统的特定语义理论。可靠性定理有两种主要变体：弱可靠性的和强可靠性的。“强”与“弱”的意义在于，强可靠性考虑句子的任意集合，而与弱可靠性有关的句子的空集是这种集合之一。大多数的演绎系统，强可靠性和弱可靠性都成立，但並非全部的演繹系統都如此。 論證可靠性 邏輯論證可靠若且唯若 論證有效。 所有前提皆已被證實為真。 弱可靠性定理 演绎系统的弱可靠性定理声称，在这…
斯科伦范式
如果一阶逻辑式的前束范式只有全称量词，则称其为是符合Skolem 范式的。一个公式可以被Skolem 化，就是说消除它的存在量词并生成最初的公式的等价可满足的公式。Skolem 化是如下二阶逻辑的等价应用： :\forall x \exists y R(x,y) \Leftrightarrow\forall x R(x,f(x)) Skolem 化的本质是对如下形式的公式的观察 :\forall x_1 \dots \forall x_…
斯科伦悖论
在数理逻辑中，特别是集合论中，Skolem 悖论是向下 Löwenheim-Skolem定理的直接结果，它声称所有一阶语言的句子的模型都有一个初等等价的可数子模型。 这个悖论见于Zermelo-Fraenkel 集合论中。康托尔在 1874年发表的更早的结果是，存在不可数集合比如自然数的幂集，实数的集合，和著名的康托爾集。这些集合存在于任何 Zermelo-Fraenkel 全集中，因为它们的存在可从公理得出。使用 Löwenheim-…
哥德尔完备性定理
哥德尔完备性定理是数理逻辑中重要的定理，在1929年由库尔特·哥德尔首先证明。它的最熟知的形式声称在一阶谓词演算中所有逻辑上有效的公式都是可以证明的。 上述词语“可证明的”意味着有着这个公式的形式演绎。这种形式演绎是步骤的有限列表，其中每个步骤要么涉及公理要么通过基本推理规则从前面的步骤获得。给定这样一种演绎，它的每个步骤的正确性可以在算法上检验（比如通过计算机或手工）。 如果一个公式在这个公式的语言的所有模型中都为真，它就被称为“逻辑…
紧致性定理
紧致性定理是符号逻辑和模型论中的基本事实，它断言一阶句子的（可能无限的）集合是可满足的（就是说有一个模型），当且仅当它的所有有限子集是可满足的。 命题演算的紧致性定理是吉洪诺夫定理（它声称紧致空间的积是紧致的）应用于紧致Stone空间的结果。 应用 从这个定理可以得出，如果某个一阶句子对于特征值为零的所有域都成立，则存在着一个常量p，使得这个句子对特征值大于p的所有域都成立。这可以被看作为如下：假定S是要考虑的句子。那么它的否定~S，和…
结构 (数理逻辑)
在数学学科模型论中，语言 \mathcal{L} 的结构 \mathfrak{A}(也叫做 '\mathcal{L}-结构'，并通常写为哥特体大写)是一个有序对，它的第一个成员是论域或全集 \mathit{A} \ (对应于可能带有定义在其上的关系和函数的集合，并通常写为相应于结构名字的罗马体大写)，它的第二个成员是一个释义 \mathcal{I}，就是 \mathcal{L} 的一个偏函数，它完全定义在 \mathcal{L} 的非逻…
选择函数
選擇函數是一個函數f，其定義域X為一堆非空集合組成的集合，且對每一個在X內的S，均有f(S)∈S。換句話說，f會在X的每一集合中恰好選取一個元素。 選擇公理（AC）斷言，每一非空集合組成的集合都會有一選擇函數。另一較弱的選擇公理－可數選擇公理（CC）則斷言每一非空集合組成的可數集合都會有一選擇函數。但無論如何，即使沒有AC或CC，某些集合還是可以有選擇函數。 若X為一非空集合組成的有限集合，則可以建立一選擇函數，由每一個X的元素內選取一…
賦值 (邏輯)
在逻辑和模型论中，賦值（valuation）是从一阶语言的变量的集合到这个语言的某个释义的全集的映射。 非形式的说，它是把一个特定的值指派（赋值）给一个数学陈述或等式中的变量。例如陈述 "x = y" 满足于（就是说，为真于）在其中 "x" 被映射到同 "y" 相同的值的求值，而不满足于（就是说，为假于）所有其他賦值。在这种简单情况下这好像是平凡的，但它是使用数学符号公式化逻辑论证的过程的一部分。
初等等价
在数学中，特别是模型论中，给定语言的两个结构被称为初等等价的，如果它们的理论相同，就是说任何被一个模型满足的句子也被另一个模型满足。 例子 考虑带有二元关系符号 '