Skip to content

满足关系

Satisfaction relation · Tarski semantics

用对公式构造的递归定义刻画结构与赋值何时满足一阶公式。

条目类型
定义

形式陈述

满足关系 M,sφ一阶公式的结构递归定义。原子关系满足当且仅当项值元组属于 RM;等式满足当且仅当两项值相等。联结词按经典真值规则解释,量词满足

M,sxφaM, M,s[xa]φ,M,sxφaM, M,s[xa]φ.

φ 是句子,真值与 s 无关,写作 Mφ;结构满足理论 T 表示满足其中每个句子。

直觉

满足关系 M,sφ 把语法公式、结构解释与变量赋值连接起来。语法树从叶到根获得意义:先在结构和赋值中计算项、检查原子事实,再按真值规则组合联结词;量词则改变某个变量的赋值并遍历论域。句子没有自由变量,其真假因而只依赖结构。

例子与边界

在自然数结构中,x(x+x=4) 为真,而 xy(x<y) 也为真。量词顺序不可交换:xyx<yyxx<y 真值不同。满足关系由外部元语言定义,不是结构内部自动拥有的谓词;Tarski 不可定义性说明足够强结构中一般不能无条件内部定义自身全部真理。

在整数结构中,赋值 s(x)=2 时满足 x+1=3M,sxφ 表示存在与 s 只可能在 x 上不同的赋值 s 使 φ 成立;不能把量词简单理解成替换某个固定常元。对自由变量不出现的公式,改变该变量赋值不影响真假。

推论与应用

一阶结构提供符号解释,变量赋值提供自由变量取值。满足关系由此定义模型、可定义集合、初等等价和语义蕴涵,是一阶可靠性、完备性乃至整个模型论的语义基础;它的结构递归形式也使关于公式的归纳证明成为可能。

参考资料
  • David Marker, Model Theory: An Introduction, Springer, 2002,§1.1, truth definition and satisfaction。
  • Wilfrid Hodges, Model Theory, Cambridge University Press, 1993,Ch. 1, semantics and satisfaction relation。
关系图谱25 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系