一階述語論理の論理式に、具体的な世界についての意味と真偽を与える方法。

$$\boxed{ \text{シグネチャ} +\text{対象領域} +\text{記号の解釈} =\text{構造} }$$

# 対象領域

対象領域 $D$ は、その構造において変数が指し得る対象全体。
標準的な一階述語論理では、対象領域は空でない集合とする。

例えば、

$$D=\mathbb Z$$

なら、量化子 $\forall x$ や $\exists x$ の $x$ は整数全体を動く。

例えば $L=\{<\}$ という同じシグネチャから、次のような異なる構造を作れる。

• $(\mathbb N,<)$
• $(\mathbb Z,<)$
• $(\mathbb Q,<)$
• $(\mathbb R,<)$

# 構造

シグネチャ $L$ に対する構造 $\mathcal M$ は、次のものからなる。

1. 対象領域 $D$
2. $L$ に含まれる各記号の解釈

対象領域を $D$ とすると、各記号は次のように解釈される。

• 定数記号 $c$
  • $D$ の一要素 $c^{\mathcal M}\in D$
• $n$ 引数の関数記号 $f$
  • 関数 $f^{\mathcal M}:D^n\to D$
• $n$ 引数の述語記号 $P$
  • 関係 $P^{\mathcal M}\subseteq D^n$

例えば $L=\{0,+,\mathrm{Even}\}$ を整数上で解釈する構造は、

$$\mathcal M= (\mathbb Z,0^{\mathcal M},+^{\mathcal M}, \mathrm{Even}^{\mathcal M})$$

と表せる。

• $0^{\mathcal M}$：整数の $0$
• $+^{\mathcal M}$：通常の整数の加算
• $\mathrm{Even}^{\mathcal M}$：偶数全体の集合

# 変数割り当て

変数割り当て $s$ は、各変数に対象領域の要素を対応させるもの。

$$s:\mathrm{Var}\to D$$

例えば、

$$s(x)=2$$

なら、論理式 $\mathrm{Even}(x)$ の $x$ を整数 $2$ として評価する。

自由変数を含む式の真偽は、構造 $\mathcal M$ だけでなく変数割り当て $s$ にも依存する。

# 項の解釈

項 $t$ がどの対象を指すかを、

$$t_{\mathcal M,s}$$

と表す。

例えば、$s(x)=2$ なら、整数の構造において、

$$x+0_{\mathcal M,s}=2$$

となる。

# 充足関係

構造 $\mathcal M$ と変数割り当て $s$ のもとで論理式 $\varphi$ が真であることを、

$$\mathcal M,s\models\varphi$$

と書き、「$\mathcal M,s$ は $\varphi$ を満たす」という。

# 述語

$$\mathcal M,s\models P(t_1,\ldots,t_n)$$

であるのは、項が指す対象の組が、$P$ の解釈する関係に属するとき。

$$(t_1_{\mathcal M,s},\ldots, t_n_{\mathcal M,s}) \in P^{\mathcal M}$$

# 等号

$$\mathcal M,s\models t_1=t_2$$

であるのは、$t_1$ と $t_2$ が対象領域内の同じ要素を指すとき。

$$t_1_{\mathcal M,s} = t_2_{\mathcal M,s}$$

したがって等号は、対象領域 $D$ 上の対角関係として解釈される。

$$(=)^{\mathcal M}=\{(d,d)\mid d\in D\}$$

これはシグネチャ内の述語の解釈には依存しない。

# 量化子

全称量化は、対象領域のすべての要素について式が成り立つことを表す。

$$\mathcal M,s\models\forall x\,\varphi(x)$$

であるのは、すべての $d\in D$ について、$x$ に $d$ を割り当てたときに $\varphi(x)$ が真になる場合。

存在量化は、式を満たす対象が少なくとも1つ存在することを表す。

$$\mathcal M,s\models\exists x\,\varphi(x)$$

であるのは、ある $d\in D$ について、$x$ に $d$ を割り当てたときに $\varphi(x)$ が真になる場合。

# 文とモデル

自由変数を持たない論理式を文という。文の真偽は変数割り当てに依存しないため、

$$\mathcal M\models\varphi$$

と書ける。

論理式の集合を理論 $T$ とする。構造 $\mathcal M$ が $T$ に含まれるすべての文を満たすとき、

$$\mathcal M\models T$$

と書き、$\mathcal M$ を $T$ のモデルという。

# 構文と意味論

• 構文
  • シグネチャを使って、どのような項・論理式を書けるかを定める
• 意味論
  • 構造と変数割り当てを使って、各記号が何を指し、論理式がいつ真になるかを定める

シグネチャだけでは論理式の真偽は決まらない。同じ論理式でも、解釈する構造が変われば真偽が変わり得る。

このように、形式言語とその解釈の関係を研究する分野がモデル理論である。