数理論理４：等号

今回は
・等号の公理
と
・理論と構造の濃度との関係
について述べます．

以下，２項述語記号＝を等号と呼び，これを元にもつ言語を固定，ｔ１，ｔ２がその項ならば
　＝（ｔ１，ｔ２）をｔ１＝ｔ２
　￢（＝（ｔ１，ｔ２））をｔ１≠ｔ２
とそれぞれ略記します．

まず，等号の公理を導入します．

（定義４－１）適当な変数記号ｘによって
　　∀ｘ（ｘ＝ｘ）
或いは，ｔ，ｔ’がＡのｘに代入可能である（つまり，新たな束縛が生じない）適当な項ｔ，ｔ’，変数記号ｘ，論理式Ａによって
　　ｔ＝ｔ’→（→）の全称閉包
と表せる論理式を等号の公理と呼びます．

ここで，， はＡ内のｘの全ての自由出現をぞれぞれｔ，ｔ’に置き換えたものです．

また，次のような流儀もあります．

（定義４－２）適当な変数記号ｘ，ｙ，ｚによって
　　∀ｘ（ｘ＝ｘ）
　　∀ｘ∀ｙ（ｘ＝ｙ→ｙ＝ｘ）
　　∀ｘ∀ｙ∀ｚ（ｘ＝ｙ→（ｙ＝ｚ→ｘ＝ｚ））
或いは，適当なｎ（＞０）項関数記号ｆ，適当な項ｔ１，...，ｔｎ，ｔ１’，...，ｔｎ’によって
　　ｔ１＝ｔ１’∧...∧ｔｎ＝ｔｎ’→ｆ（ｔ１，...，ｔｎ）＝ｆ（ｔ１’，...，ｔｎ’）の全称閉包
或いは，適当なｎ（＞０）項述語記号ｐ，適当な項ｔ１，...，ｔｎ，ｔ１’，...，ｔｎ’によって
　　ｔ１＝ｔ１’∧...∧ｔｎ＝ｔｎ’→（ｐ（ｔ１，...，ｔｎ）→ｐ（ｔ１’，...，ｔｎ’））の全称閉包
と表せる論理式を等号の公理と呼びます．

このとき

・　（定義４－２）の各公理は（定義４－１）の公理全体の集合から証明可能
・　（定義４－１）の各公理は（定義４－２）の公理全体の集合から証明可能

であり，（定義２－１）に

　とくに
　Ｉ（＝）はＤ上の相等関係，つまり，任意の（ａ，ｂ）∈Ｄ＾２に対して，ａ＝ｂ（この＝はＤ上の等号）ならば１，そうでないならば０となる写像

を追加すると

・　（定義４－１），（定義４－２）の各公理は valid

です．

以下，（定義２－１）に上記を，（定義３－１）に

Ｋが（定義４－１）の等号の公理ならば
０．｛｝｛Ｋ｝

をそれぞれ追加し，理論と構造の濃度との関係を見て行きます．

まず
　　∀ｘ∀ｙ（ｘ＝ｙ） ⇔ ∃ｘ∀ｙ（ｘ＝ｙ）
であり，２つの理論｛∀ｘ∀ｙ（ｘ＝ｙ）｝，｛∃ｘ∀ｙ（ｘ＝ｙ）｝はどちらも濃度が１の任意の構造のみをモデルにもちます（domain が空である構造を許す流儀では，∀から始まる任意の論理式はその構造において valid なので，前者は濃度が２より小の任意の構造のみをモデルにもちます）．

同様に，２つの理論
　　｛∃ｘ１∃ｘ２（ｘ１≠ｘ２）∧∀ｘ１∀ｘ２∀ｘ３（ｘ１＝ｘ２∨ｘ１＝ｘ３∨ｘ２＝ｘ３））｝
　　｛∃ｘ１∃ｘ２（ｘ１≠ｘ２∧∀ｙ（ｘ１＝ｙ∨ｘ２＝ｙ））｝
はどちらも濃度が２の任意の構造のみをモデルにもちます．

そして，２以上の任意の整数ｎに対して，φｎを
　　∀ｘ１...∀ｘｎ（１≦ｉ＜ｊ≦ｎを満たす各整数の対（ｉ，ｊ）に対するｘｉ＝ｘｊを∨で結んだもの）
とおくと，それぞれ
　　｛φｎ｝は濃度がｎより小
　　｛￢φｎ｝ は濃度がｎ以上
　　｛￢φｎ，φ(ｎ＋１)｝ は濃度がｎ
の任意の構造のみをモデルにもちます．

このように任意の正の整数ｎに対して，理論Ｔｎが存在して
　　任意の構造Ｓに対して，Ｓの濃度がｎとＳ|=Ｔｎとは等価
ですが
　　任意の構造Ｓに対して，Ｓの濃度が有限とＳ|=Ｔとは等価
となる理論Ｔは存在しません（そのようなＴがあるとＴ’＝Ｔ∪｛￢φｊ：ｊ≧２｝の任意の有限部分集合がモデルをもつのでコンパクト性定理（ https://en.wikipedia.org/wiki/Compactness_theorem ）によりＴ’もモデルをもちますが、その濃度は有限かつ無限となり不合理です）．

これと双対的に，無限濃度については，上記のφにより
　　任意の構造Ｓに対して，Ｓの濃度が無限とＳ|=｛￢φｊ：ｊ≧２｝とは等価
ですが，任意の無限濃度ｍに対して，濃度ｍの任意の構造のみをモデルにもつ理論は存在しません（無限濃度の任意の構造Ｍ，Ｍをモデルにもつ任意の理論Ｔ，言語の濃度以上の任意の濃度ｋに対して，Ｔは濃度ｋの（Ｍと初等的同値な）モデルをもつことが，レーベンハイム－スコーレムの定理（ https://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_theorem ）として知られています）．