数理論理1:言語
ちょっとした経緯があり,数理論理(古典一階論理)の基本事項を少し書きます.
今回は
・言語に対して,その言語の項,論理式の全体が定まること
を述べます.
(定義1-1)言語は,次のような互いに区別できる記号の集合です.
n項関数記号 (各nは非負整数)
n項述語記号 (1個以上,各nは非負整数)
変数記号 x1 x2 … (可算個)
論理記号 ¬ ∨ ∧ → (結合子とも呼びます) ∀ ∃ (量化子とも呼びます)
補助記号 ( , )
ここで,関数記号,述語記号は言語を特徴付けるもので
・それぞれの全体(と各記号に上記のnを対応させる関数)の組をその言語のシグネチャーと呼びます.
なお
・関数記号,述語記号を非論理記号,その他(つまり,全ての言語に共通するもの)を論理記号と呼ぶ流儀,また,等号=を論理記号に含める流儀もあります.
言語を固定すると,その言語の項,論理式が以下のように定まります.
(定義1-2)項は
0項関数記号 (定数記号とも呼びます)
変数記号
適当なn(>0)項関数記号f,n個の適当な項t1,...,tn,補助記号によってf(t1,...,tn)と表せるもの
のいずれかです.
(例1-1)xが変数記号,cが定数記号,fが2項関数記号ならば,f(x,c)は項です.
なお,(定義1-2)では「逆にこれらはいずれも項です.」を略しており,正確には,現れる定数記号でない関数記号の個数に関する帰納法により
T(0)=変数記号の全体と定数記号の全体との和集合
任意の非負の整数jに対して
T(j+1)=∪_{n≧1}{f(t1,...,tn):fはn項関数記号,t1,...,tnはそれぞれT(m_1),...,T(m_n)の元.ただし,m_1,...,m_nは和がjである非負の整数.}
と定め,項全体を
∪_{j≧0}T(j)
と定めます.
そして,f(t1,...,tn)は,項の個数に関する帰納法により
f(t1,...,t1)=f(t1)
任意の正の整数jに対して
f(t1,...,t(j+1))=f(t1,...,tj)の最後の ")" を ",t(j+1))" に置き換えたもの
と定めます.
同様に(定義1-3),(定義2-3)は関数,述語,論理記号の出現の個数,(定義3-1)は推論規則を適用した回数に関する帰納法による定義です.
(定義1-3)論理式は
0項述語記号 (命題記号とも呼びます)
適当なn(>0)項述語記号f,n個の適当な項t1,...,tn,補助記号によってp(t1,...,tn)と表せるもの
のどちらか(これらを原子論理式と呼びます),或いは,適当な変数記号x,論理式A,Bおよび論理記号,補助記号によって
¬(A)
(A)∧(B)
(A)∨(B)
(A)→(B)
(∀x)(A) (この∀xのx,および,A内の各xをxの(全称)束縛出現といいます)
(∃x)(A) (この∃xのx,および,A内の各xをxの(特称)束縛出現といいます)
のいずれかと表せるものです.
ここで
・論理式に現れる個々の変数記号をその変数記号の出現
・束縛出現でない変数記号の出現を自由出現
・各変数記号の出現がすべて束縛出現である論理式を閉(じた)論理式,そうでない論理式を開(いた)論理式
そして
・閉論理式以外の元をもたない集合を理論
と呼びます.
なお,A,Bが論理式ならな
(A)(B)は((A)→(B))∧((B)→(A))
の略記とします.
また,言語の定義において,論理記号は,例えば ¬ ∧ ∃ のみとして
(A)∨(B)は ¬((¬(A))∧(¬(B)))
(A)→(B)は ¬(A∧(¬(B)))
(∀x)(A)は ¬((∃x)(¬(A)))
それぞれの略記と定義する流儀もあります.
(例1-2)x,yが変数記号,fが1項関数記号,pが1項述語記号,rが2項述語記号ならば
r(f(x),y)
((∀x)(p(x)))→(p(x))
はどちらも論理式,そして
(∃x)((p(x))→((∀x)(p(x))))
は閉論理式です.
(例1-2)の論理式をそれぞれ
rfxy
(∀xpx)→px 或いは (∀x(p(x)))→p(x)
∃x(px→∀xpx) 或いは ∃x(p(x)→∀x(p(x)))
などのように記すこともあり,本稿もその作法に従います.
(定義1-4)Aが論理式,x,y,..がAに現れる束縛されていない全ての変数記号ならば,Aの全称閉包は閉論理式∀x∀y...(A)です.
論理式を"閉じる"方法としては,各変数の自由出現を各変数ごとに新たな定数記号に置き換えるというものもあり,本稿のメタ論理でも暗にそれを採用しています.
(参考)
https://www.encyclopediaofmath.org/index.php/Formalized_language