数理論理2:意味論

今回は
・言語,構造,割り当てに対して,その言語の項,論理式の値が定まること
そして
・言語に対して,その言語の valid な論理式の全体が定まること
を述べます.

以下,言語を固定します.

(定義2-1)構造は空でない集合D(domainと呼びます)と次のような写像I(解釈と呼びます)の対です.
 fがn項関数記号ならば
  n>0ならば,I(f)はD^nからDへの写像
  n=0ならば,I(f)∈D
 pがn項述語記号ならば
  n>0ならば,I(p)はD^nから{0,1}への写像
  n=0ならば,I(p)∈{0,1}
また,Dの濃度#Dを構造の濃度と呼びます.

なお,構造のことを解釈,或いは,モデルと呼ぶ流儀もあります.

次に,構造(D,I)を固定します.

(定義2-2)割り当てsは変数記号全体からDへの写像です.x,y,...が変数記号,d,e,...∈Dならば,sのx,y,...の像をそれぞれd,e,...に改めた割り当てをs[x→d,y→e,...]で表します.

(定義2-3)付値は(関数,述語,論理記号の出現の個数に関する帰納法により定義される)次のような写像||です.
 sが割り当て,xが変数記号ならば,|x|=s(x)
 gがn項関数または述語記号,t1,...,tnが項ならば
  n>0ならば,|g(t1,...,tn)|=I(g)(|t1|,...,|tn|)
  n=0ならば,|g|=I(g)
 A,Bが論理式ならば
  |¬A|=1-|A|
  |A∧B|=|A|×|B|
  |A∨B|=1-(1-|A|)×(1-|B|)
  |A→B|=1-|A|×(1-|B|)
 sが割り当て,xが変数記号,Aが論理式ならば
  |∀xA|={s[x→d]に対して定義された||による|A|:d∈D}の元の積
  |∃xA|={s[x→d]に対して定義された||による|A|:d∈D}の元の和

この定義において,付値による各元の像を元の値と呼びます.各項の値はDに属し,各論理式の値は{0,1}に属します.また,各割り当てに対して,付値は項と論理式全体の集合からD∪{0,1}への準同型写像になっています.

以下,言語のみを固定します.

(例2-1)A,Bが論理式ならば,任意のS,sに対して
  |((A→B)→A)→A|
 =1-|(A→B)→A|×(1-|A|)
 =1-(1-|A→B|×(1-|A|))×(1-|A|)
 =1-(1-(1-|A|×(1-|B|))×(1-|A|))×(1-|A|)
であり,|A|∈{0,1}により,この値は1です.

(例2-2)xが変数記号,Aが論理式ならば,任意のS,sに対して
  |¬(∀xA)|
 =1-|∀xA|
 =1-({s[x→d]に対して定義された||による|A|:d∈D}の元の積)
 ={1-(s[x→d]に対して定義された||による|A|):d∈D}の元の和
 ={s[x→d]に対して定義された||による|¬A|:d∈D}の元の和
 =|∃x(¬A)|
となります.

(定義2-4)Sが構造,sが割り当て,||が付値,A,Bが論理式,Σが論理式の(有限とは限らない)集合ならば
1.|A|=1を(S,s)|=Aと書き,「S,sはAを充足」と読み,そうしたS,sが存在するようなAを「充足可能」と呼びます.
2.任意のsに対して(S,s)|=AをS|=Aと書き,「AはSにおいてvalid」或いは「SはAのモデル」と読みます.
3.任意のBに対して,B∈ΣならばS|=BをS|=Σと書き,「SはΣのモデル」と読みます.
4.任意のSに対して,S|=ΣならばS|=AをΣ|=Aと書き,「AはΣの意味論的帰結」と読みます.
5.任意のS,sに対して,|A|=|B|をA≡Bと書き,「A,Bは同値」と読みます.

(定義2-4)において

・ Aが閉論理式ならば,|A|は割り当てによらないので,|A|=1はS|=Aであり(単に「SはAを充足」と読みます),Aが充足可能とAがモデルを持つは等価です.
・ Σが有限集合ならば
   {A1,...,An}|=AはA1,...,An|=A
   {}|=Aは|=A
のように{ }を略して書くことがあり
   |=Aを「Aは valid」と読みます.
   A|=Bは|=(A→B)と等価であり,これをA⇒Bと書きます.
   A|=BかつB|=Aは|=(A→B)∧(B→A)と等価であり,これをA⇔Bと書きます.
   A⇔BはA≡Bと等価です.
・  |=Aは,任意のS,sに対して,(S,s)|=Aつまり|A|=1つまり|¬A|=0と書けるので,入力されたAにおいて束縛されない全ての変数記号を定数記号とみなし,それがvalidであることを確かめよう,或いは,|¬A|=1となるS(これをAのカウンターモデルと呼びます)を見付けてvalidでないことを確かめようとする https://www.umsu.de/trees/ のようなツールがあります.
・ 論理式全体は,適当なS,sに充足される(充足可能といいます)論理式全体と,そうでない(充足不可能といいます)論理式全体に分割され,前者の部分集合として適当なSにおいて valid な論理式全体があり,さらにその部分集合として valid な論理式全体があります.

(例2-1)により
 |=((A→B)→A)→A つまり (A→B)→A|=A つまり (A→B)→A⇒A
(例2-2)により
 ¬(∀xA)≡∃x(¬A) つまり ¬(∀xA)⇔∃x(¬A)
となります.

なお,(定義2-4)において,より強く

4.任意のS,sに対して,「任意のBに対して,B∈Σならば(S,s)|=B」ならば(S,s)|=AをΣ|=Aと書き,「AはΣの意味論的帰結」と読みます.

とする流儀もあります.この場合,Σ∪{A}|=B ならば Σ|=A→B(意味論的な演繹定理 )がAが閉論理式でなくても成り立つ(つまり,pが1項述語記号,x,yが変数記号であっても{p x}|=p yとならない)など,構文論との対応が失われますが,閉論理式に限定するなら差異はありません.