書記が数学やるだけ#906 ストラクチャー，モデル

ストラクチャー，モデルに関する用語を整理する。

問題

説明

構造（ストラクチャー，Structure) とは、議論の対象となる集合（ドメイン/台集合 D）と、その集合上で言語の記号（定数記号、関数記号、述語記号）を具体的にどのように割り当てるか、すなわち解釈を定めたものである。

• 充足 (Satisfiability)： ある論理式 ϕ が、特定のストラクチャー M およびある変数の割り当て S のもとで「真」となるとき、「M と S は ϕ を充足する」（M,S⊨ϕ と表記）と言う。

• モデル (Model)： ストラクチャー M が、ある論理式 ϕ（または論理式の集合 Σ）に対して、すべての変数の割り当てのもとで ϕ を真にするとき、 M は ϕ の「モデル」であると言う（M⊨ϕ または M⊨Σ と表記）。

• 恒真（トートロジー, Tautology)： いかなるストラクチャー M およびいかなる変数の割り当て S のもとでも常に真となる論理式のことである。

• 論理的帰結 (Logical Consequence)： 論理式の集合 Σ のすべてのモデルが、論理式 ϕ のモデルでもあるとき、「ϕ は Σ の論理的帰結である」と言う（Σ⊨ϕ と表記される）。

• 論理的同値 (Logical Equivalence)： 二つの論理式 ϕ と ψ が、いかなるストラクチャー（モデル）といかなる変数の割り当てのもとでも同じ真理値を持つとき、これらは論理的に同値であると言う（ϕ⇔ψ と表記される）。

解答

数理論理学における項の解釈は、以下の規則に従う。

• 定数記号の解釈： 定数記号の解釈は、変数の割り当て S には依存せず、ストラクチャー M の定義のみに依存する 。

• 変数記号の解釈： 変数記号の解釈は、割り当て S の定義（すなわち、 S がその変数に割り当てるドメインの要素）に直接従う 。

• 関数項の解釈： 関数項 f(t1​,…,tn​) の解釈は、まず内側の項 ti​ の解釈を求め 、その結果に関数記号 f のストラクチャー M における解釈 fM を適用することで得られる 。

論理式 ϕ=P(f(x),y) が充足されるか は、ペア (f(x)M[S′],yM[S′]) 、すなわち (2,2) が述語の解釈 PM に含まれるかで判定される 。PM={(1,2),(2,3)} に (2,2) は含まれないため 、 ϕ は M と S′ によって充足しない (偽となる) 。

論理式 ψ=∃xP(f(x),y) を評価するため、自由変数 x にドメイン D={1,2,3} の各要素 d を代入した割り当て S′′[x→d] のもとで、内側の論理式 P(f(x),y) が真となるか試みる 。x=3 を代入した割り当て S′′[x→3] のもとで P(f(x),y) が真となったため 、論理式 ψ は充足される。

ストラクチャー N は、公理系 Σ の3つの公理すべてを満たすため 、N は Σ のモデルである 。

ストラクチャー Mは、公理2に反するためΣ のモデルでない 。

公理系 Σ に含まれる公理1 ∀x¬(S(x)=0) は、任意の項（ここでは定数記号 0）に対して ¬(S(0)=0) を導く。したがって、Σ のすべてのモデルは必ず Ψ を満たす。ゆえに、Σ は Ψ を論理的に含意する (Σ⊨Ψ)。

論理式 θ=∀x(x=x) は、等号 = の標準的な解釈において、いかなるストラクチャー M およびいかなる割り当て S のもとでも常に真となる。したがって、θ は恒真である。

Φ:=S(S(0))=0 について、自然数モデル N では、S(S(0))=S(1)=2 であり、 0でないので N は Φ を充足しない (N⊨¬Φ、すなわち Φ は N で偽である)。N は Σ のモデルであるにもかかわらず Φ を満たさない反例であるため、 Σ は Φを論理的に含意しない。

本記事のもくじはこちら：