論理学をつくる 第4部-論理学はここから先が面白い 非古典論理 読書メモ

論理学をつくる 第4部-論理学はここから先が面白い 非古典論理 読書メモ

論理学は、人間が考える方法や議論の方法について研究する学問分野であり、特に、命題や推論に関する基本的な概念を扱うものとなる。

論理学の基本的な概念として、命題や命題論理、論理学の記号体系などがある。命題とは、真偽が決まる文句であり、真か偽かが確定するものとなる。命題論理は、命題を扱う論理学の分野であり、論理的な関係を表すための論理演算子が用いられる。論理学の記号体系は、論理的な演算を表すための記号を定めた体系であり、命題論理においては「否定」「論理積」「論理和」などの論理演算子が用いられる。

論理学には、命題論理以外にも、一階述語論理や高階論理などの分野もある。一階述語論理は、命題論理に述語や変数を導入することで、より複雑な論理的な関係を表現することができるものとなる。高階論理は、集合や関数などの数学的概念を含む論理を扱うものとなる。

論理学には、命題の真偽を決定する方法や、正しい推論を行うための方法についても研究されている。例えば、命題の真偽を決定する方法として、真理値表や証明という方法がある。真理値表は、命題に対して全ての可能な真偽の組み合わせを試して、命題の真偽を決定する方法となる。証明は、命題が正しいことを示すための論理的な手順であり、公理や推論規則を用いて、命題の真偽を導き出す。

論理学は、哲学や数学、人工知能などの分野にも深く関わっている。哲学においては、論理学の概念を用いて論理的な議論を行い、数学においては、論理学を用いて数学的な命題を導出するための基礎的な体系を構築する。人工知能においては推論技術や知識情報処理技術のベースとなっている。

論理学のベースとなっている数学的理論としては、”集合論の概要と参考図書“に記載している集合論、”構造とアルゴリズムと関数“で述べている代数学、”形式言語と数理論理学“で述べている形式言語学や意味論等があり、そちらも参照のこと。

今回は数理論理学の著名な教科書である「論理学をつくる」より、読書メモを示す。

前回の第3部論理学をもう一つの目で見るに続き、今回は第4部-論理学はここから先が面白い 非古典論理の読書メモについて述べる。

第Ⅳ部　論理学はここから先が面白い！　進んだ話題のロードマップ

第11章　めくるめく非古典論理の世界にようこそ！

はじめに
ここまで展開してきた論理学は 「古典論理学(classical logic)」
昔の論理学という意味ではない
「クラシカル・ロジック」の「クラシカル」は
「基本的」とか「標準的」といった意味
古典論理が一応の完成を見たもの
フレーゲの「概念記法」1879
古典論理が標準的とされているのはなぜか?
基礎的で美しい体型になるように理想化されている
理想化の例
(1)古典論理学では、「真理関数でない結合子は扱わない」
結合子はどれも真理表で定義できる
(2)古典論理学は、2価原理を採用していた
ある(閉)論理式は必ず真か偽のいずれかの値を持つ
この章ではこの理想化に待ったをかける
その結果わかること
論理は一つではない

11.1　古典論理は神の論理である —— 2値原理と排中律のいかがわしさ

はじめに
古典論理は、全ての論理式が真偽のいずれかの値を取るという2値原理を採用している
これがストレートに現れるのが排中律(PⅤ¬Pがトートロジーになる)ということ
排中律はPがどのような命題であってもいつでも文句なしに真と認めて良いのか?
未来は開かれていてほしい
未来についての命題「クリスは明日のご飯にベーコンレタスバーバーを食べる」は真か偽か?
どちらかに決まるとすると、未来のことは決まっていることになる
決定論は「偶然的真理」とか「自由意志」を無にする
構成主義からの疑念
「aもbも無理数なのにabが有理数になるようなa,bがある」
「√2√2は有理数なのか、無理数なのか」決着をつけずに、排中律の形をしているだけで判断する
「√2√2は有理数なのか、無理数なのか」どちらか
なのか?
人間がそれを作ることができるのか?
数学的な事柄は我々がそれを知ることができるかどうかにかかわらずすでに決まっている
我々ら作ることのできる数学的対象だけが存在する
神の論理学から人間の論理学へ
古典理論理は、時間を超えて、宇宙の歴史を一覧でき、 物忘れもなく、無限の仕事も完了でき、 どんな命題の真偽も知りうる神の視点に立った論理学
古典論理の美しさは、神の視点が持つ明確さが反映したもの
有限な人間の立場に立った論理学はないのか?

11.2　多値論理

11.2.1 ウカシェヴィッツの古典理論批判と3値論理
はじめに
論理から排中律を取り除く方法は? – 2値原理をやめる
ウカシェヴィッツ(Ukasiewicz)の3値論理学 (three valued logic) – 真と偽と第三の真理「可能」
論理結合子の定義と3値トートロジー
真(1)、偽(0)、可能(0.5)の3つの真理値を持つ論理
¬
→
なぜこう定義したか?
Ⅴ
AⅤB=df(A→B)→B
Λ
AΛB=df¬(¬AⅤ¬B)
↔︎
A↔︎B=df(A→B)Λ(B→A)
3値論理において常に真理値1を取る論理式を3値トートロジー (three-valued tautology)
A→A
排中律はトートロジーにはならない
A:0.5
¬A:0.5
AⅤ¬A:0.5
論理結合子の定義の正当化
なぜ結合子「→」を上記のように定義したのか?
以下のように解釈する
1:「すでに真と決まっている」
0:「すでに偽と決まっている」
0.5:「これから真になるかもしれないし、偽になるかもしれない」
「0→0.5」は
「0→0」かもしれないし「0→1」かもしれない
どちらも1なので「0→0.5」は1になる
「0.5→1」は
「0→1」かもしれないし「1→1」かもしれない
「0.5→1」は0かもしれないし、1かもしれない、よって0.5となる
「0.5→0.5」は
おそらくP→Pを3値トートロジーにしたくて1としている
0.5という値は「可能」という意味を持っているのか?
例
Aを「明日私のコンピューターのハードディスクが壊れる」とする
今の段階ではAは真とも偽とも決まっていない
¬Aも真とも偽とも決まっていない
明日私のコンピュータのぱどディスクは壊れ、しかも壊れない
偽であるように思われる
0.5ではないように思われる
11.2.2 ファジー論理
はじめに
多値論理体系は – 3値、4値といくらでもたくさんの真理値を考えることができる
論理結合子の定義の仕方もたくさんある
多値論理はあまりに人工的すぎて1920年代から30年代の成立期ののちあまりパッとしなくなった
ファジー理論(fuzzy logic)の分野が発展して、 再び関心の的になった
連鎖推論のパラドクス
例:次の3つの命題を考える
(a)頭髪が0本の人はハゲである
(b)頭髪が100万本の人はハゲではない
(c)全ての自然数nについて、頭髪がn本の人がハゲなら、頭髪がn+1本の人もハゲであるが成り立つ
(c)を連続して推論していくと、全ての本数でハゲになり、(b)と矛盾する
ファジーな述語とクリスプな述語
こうしたパラドクスは「ハゲである」のような いわゆるファジーな述語(fuzzy predicate)を含んでいる
英語の「ファジー」
綿毛のように毛羽立った、というような意味
ぼやけた写真や絵、はっきりしない考えに「ファジー」という形容詞が使われる
ファジーな述語は「曖昧な述語(vague predicate)」と言われることもある
「曖昧」という言葉は意味がいくつもあってどの意味で使われているかわからない
ファジーは多義的ということではない
例:「重い」という述語の意味ははっきりしているが
どこからが重いかの境目があるわけではない
ファジーな述語は以下の意味でもない
「人によって境目をどこに置くかが異なるので、全体として境目がはっきりしない」
Bがファジーな述語のとき∃n(B(n)Λ¬B(n+1))が偽になる
ファジーな述語への反対な概念
クリスプ(crisp)な述語
明確な境界を持っている
クリスプ:食べ物に使われる形容詞
シャキシャキ、バリバリしている(そしてそれゆえ美味しい)
述語のファジー性・2値原理・連鎖推論のパラドクスとの関係
古典論理のセマンティクス
2値論理の枠組みでのファジーな述語
真理の度合い
ファジーな述語に対して扱いたい形
真理値として1と0の2種類だけではなく、無数の中間的な真理の度合いを認める必要がある
ファジー論理は無限多値論理の一種
ファジー論理のセマンティクス
ファジー命題論理の間でセマンティクスを与える
FPLの原子式への真理値割り当てVを次のように定義する
定義:FPLの原子式からなる集合をFとする
Fに対する真理値割り当てVは次のような関数である
V : F→[0,1] 古典論理では{1,0}だが[1,0]になる
例:単一論理式
「頭髪が0本の人はハゲである」
「頭髪が500本の人はハゲでる」
「頭髪が5000本の人はハケである」
複合的論理式への真理値の定義
帰納的定義を使う
Fに含まれる原子式から帰納的に定義された論理式全てからなる集合をḞとする
Ḟに含まれる全ての論理式に対して真理の度合いを割り当てる関数Ṽ:Ḟ→[0,1]を作ってやれば良い
そのときの定義は(F-atomic)
Aが原子式のとき、Ṽ(A)=V(A)とする
任意の複合的な論理式A、Bに対し、 首尾一貫した形で真理の度合いを割り当てるには、 次のように定義する
(F¬) Ṽ(¬A) = 1 – Ṽ(A) (FΛ) Ṽ(AΛB) = min(Ṽ(A), Ṽ(B)) (FⅤ) Ṽ(AⅤB) = max(Ṽ(A), Ṽ(B))
min[x,y]はxとyのうち小さい方
max[x,y]はxとyのうち大きい方
(F→) Ṽ(A→B) = {1 – (Ṽ(A) -Ṽ(B)) Ṽ(A)>Ṽ(B)の時 　　　　　　　　 {1 それ以外の時
古典論理の場合はAが1、Bが0の時A→Bが0になる
前件が1だったのに、後件が0になってしまって
真理の度合いが1-0=1だけ減ってしまったので
全体の真理の度合いも1だけ減って1-1=0になってしまった
意味論的帰結の定義
セマンティクスを完成させるには意味論的帰結の概念を定義する必要がある
式集合Γから論理式Cが意味論的に帰結するということをどのように捉えるのか
単純化のために式集Γは有限集合とする
Ṽ(Γ)をΓに属する論理式の真理の度合いのうち最小のもの、と定義する
定義1:Γ⊨C ⇔ Ṽ(Γ)=1かつṼ(C)=0であるような真理値割り当てṼは存在しない
ファジー論理ではそのまま使えない
Γの要素となっている論理式の真理の程度が全て0.9であり、 Cの真理の程度が0.1の場合もこの定義は満たされる
しかし、前提の真理の度合いは結論で著しく減る
真理の度合いが保たれない
ファジー論理向け
定義2:Γ⊨C ⇔ Ṽ(Γ)=1かつṼ(C)<0であるような真理値割り当てṼは存在しない
定義3
Γ⊨C ⇔ Ṽ(C)<Ṽ(Γ)であるような真理値割り当てṼは存在しない
より厳しい条件
連鎖推論のパラドクスの分析
以上のセマンティクスにより、連鎖推論のパラドクスはどのように解消されるのか
(1) 連鎖推論は成功していない
(F→)によって次のことが言える
問題となっていた推論に含まれる炭酸の前提(B(n)→B(n+1)の真理値は1ではない
述語Bのファジー性によりB(n)の真理の程度はいつもB(n+1)よりも高い
Ṽ(B(n))>Ṽ(B(n;1))
Ṽ(B(n)→B(n+1))=1-(Ṽ(B(n))-Ṽ(B(n+1)))<1
推論は妥当だとしても、結論は1(真)だと受け入れる必要はない
(2) 強い論理的帰結の定義を取れば連鎖推論は妥当ですらない
連鎖推論は基本的には「A→B、A従って、B」という形式の推論(MP)の繰り返し
上記の推論は定義2では妥当だが、定義3を採用すると非妥当になる

11.3　直観主義論理

11.3.1 直観主義論理学の成立
数学に対して、構成主義的立場をとったときも、排中律に対する疑念が生じる
ブラウワー(Luitzen Egbertus Brouwer)による「直感主義数学」
数学をもっと人間の精神活動に結びついてものと考える
排中律や背理法の無制限の使用を排除したもの
数学の本質は心の構成的働きにあるので
心の働きに基づいて数学をやり直すべき
例:πの少数展開を全てやり遂げることはできない
直観主義数学では、実数のような数学的対象は完結した対象ではなく
生成されつつあるものとして考える
例2:πの少数展開の中に7が100個続く箇所はまだ見つかっていない
事実として現れるか現れないかのどちらかに決まっているはず
Pなのか¬Pなのかは分からなくても、我々はPⅤ¬Pを主張して良い
という具合に排中律を無制限に適用するのは、論理の濫用
直観主義数学の論理を取り出した
直観主義論理(intuizionisti logic)
11.3.2 直観主義論理のための自然演繹
どの規則を修正したら排中律を捨てられるか
直観主義論理は
排中律がtheoremとして出てこないようにするという方向で、
排中律の排除を目指したもの
どのようにして行うのか?
古典論理のための自然演繹ND(ただし矛盾記号を使うやつ)の推論規則
(1) →ΛⅤ→に対する導入規則と除去規則
(2) ¬intro*と¬elim*
(3) 2重否定除去則
自然演繹での排中律のproof
ポイントは最後にDNを使って2中否定をとることにある
DNがないと排中律は出てこない
DNという推論規則を捨てる
DN
「¬」は2個つけるとつけていない時と同じになる(規則)
DNを定義することで「¬」に否定の意味を与える
DNを単純に捨てるだけでは何が困るのか?
¬intro*と¬elimの中には「¬」と「⊥」の2つの記号が出てくる
DNを定義しないと「¬」と「⊥」の意味が固定できない
¬intro*は
Aから⊥が出てきたら¬Aを導いて良い
¬elim*は
Aと¬Aが同時に言えたなら⊥を導いても良い
DNを取り除いた上で、排中律のproofを作れない程度の弱い規則を入れる
矛盾規則: (absurdity rule : AB)
| ⊥ | B
⊥からは何でも出てくる
NJ(直観主義論理のための自然演繹)の推論規則
(1) →ΛⅤ→に対する導入規則と除去規則
NDと共通
(2) ¬intro*と¬elim*
NDと共通
(3) 矛盾規則(AB)
ABの代わりにDNでも演繹できる(逆はだめ)
11.3.3 NDではprovableだがNJではそうではない式
NJでprovableな式は全てNDでもprovable
その逆(NDでprovableな式はNJでもprovable)は意味しない
そのほかのNDではprovableだがNJではprovableではない例
排中律
⊬NJPⅤ¬P
⊢NJ¬¬(PⅤ¬P)
¬(PΛ¬P)
2重否定について
(1) ¬¬PからPは演繹できない
(2) Pから¬¬Pは演繹できる
(3)NJでは2重否定をはずことはできないのに、3重否定を1重否定にはできる
ド・モルガンの法則をめぐって
ド・モルガンの法則の片方はNJでも成立する
連言と宣言を取り替えたバージョンは不可
対偶法則
対偶法則の半分だけがNJでprovable
結合子相互の定義可能性について
NJでは→を¬とΛで大儀したり、↔︎をⅤ、Λ、¬で定義することができない
土モルガンの法則の不成立により、Λを¬とⅤで定義することもできない
NJでは結合子はそれぞれ独立の意味を持っており、互いに定義できない
11.3.4 2重否定と同等な規則
次のどちらかをNJに加えるとNDに戻る
(1)公理として排中律を認める
AⅤ¬Aの形の式をいつでも書いて良い
(2)背理法(reduction ad absurdum:RAA)
Aの否定を仮定して矛盾を導くことができたら
Aを導いても良い
排中律を公理として認めれば2重否定除去とおなじ効果がある
11.3.5 直観主義のセマンティクス
多値論理と直観主義論理
多値論理と直観主義的論理はともに排中律への疑問から生まれた
両者の排中律の捨て方は異なっている
多値論理では2価原理を捨てる
直観主義的論理は、自然演繹で排中律の証明ができなくなるように推論規則を変更した(NDからAB)
両者は同じ論理体系にならない
¬¬P→Pは
3値論理ではトートロジー
直観主義論理ではtheoremにならない
証明解釈とその限界
直観主義的論理のセマンティクスを見る
直観主義的論理の根本的な思想
我々には証明も反証もできないが「数の世界」では真か偽に決まっている、と考えるのはおかしい
我々の認識能力とは無関係に成り立っている真偽を考えるのは無意味
その事実を確認する方法(数学で言えば証明)を持っているかどうかが重要
古典論理のセマンティクス
我々が知ろうが知るまいがお構いなしに成り立っている「Aは真である」を基本概念にとらえる
直観主義的論理のセマンティクス
「Aを証明する方法を持っている」をベースにしたセマンティクス
ハイティンクによる直観主義的論理のセマンティクス
ハイティンクの与えた結合子の意味
(1) AⅤB: Aを証明する方法を持っているか、またはBを証明する方法を持っている
(2) AΛB:Aを証明する方法を持っており、かつBを証明する方法を持っている
(1) A→B:Aの証明が仮に与えられたとしたら、それをもとにBの証明を作り出す方法を持っている
(1) ¬A:Aの証明が与えられたと仮定し、それをもとに矛盾を導き出す方法を持っている
証明解釈を使うと、直観主義論理の禁じ手がなぜそうなのかわかる
(1)排中律:AⅤ¬A
Aを証明する方法を持っているか、またはAから矛盾を導き出す方法を持っている
どんな命題も証明か反証を持っている
(2)背理法:¬ A
¬Aから矛盾を導き出すことができたとしても、直接にAを証明する方法が手に入ったわけではない
証明解釈の限界
¬¬¬A→¬Aが直感主義的論理で許される理由を証明解釈で説明できない
クリプキ・セマンティクスの基本的アイデア
ソール・クリプキ(Saul Kripke)によるクリプキ・セマンティクス
(1)基本アイデア
数学や論理をある程度理想化して捉えた人間の心の中で行われる活動と考える
この人をαとする
(2)αの認識活動は時間に沿って生じる
ある時点でαは何らかの事実を証明したり検証したりして知っていく
ただし、αは完璧な記憶を持っており、ある時点で知ったことはその後もずっと忘れないものとする
時間は自然数のように飛び飛びになっているものとする
(3)αは各時点で常に、知識を増やしていく可能性を持っていると考える
αの知識の道筋は上手のように枝分かれしている
各ノードσはαの可能な知識状態(possible state of knowledge)を表す
Σ1がσ2より段階σiがσjより時間的に前であることを、σi≤σjで表す
全ての段階の集合Sはこの≤に関して一方向だけに枝分かれしたツリー構造になる
こうした構造を持った集合を数学では「部分順序集合」と言う
量化子を持った直感主義述語論理を考えるときは
Αは各時点で知識を増やしていくだけではなく
次の素数を作ったり、数列の次の項を計算したりして、いろいろな対象を構成していく
(4)各段階においてαに知られている原子式をそのノードに沿えて書き込むことにする
例
Σiで原子式Aが知られている(証明されている・検証されている)かつ、σi≤σj ⇒ σjでもAが知られている
モデル構造の定義
定義
m=<σ0,S, ≤>をモデル構造という
σ0は出発点
Sは段階の集合
≤はS上で定義される部分順序集合である
例
モデル構造m上のモデルM
定義
モデル構造m=<σo, S, ≤>上のモデルMとは
次の3つ組である
M=< m, V, ⫦ >
V:とのそれぞれの要素σに原子式の集合を割り当てる関数
⫦:段階σと論理式Aとの関係
段階σにおいて論理式Aが知られている
Aが複合的な式の場合
(1) σ⫦AΛB ⇔ σ⫦A かつ σ⫦B (2) σ⫦AⅤB ⇔ σ⫦A または σ⫦B (3) σ⫦A→B ⇔ すべてのσ≤σ’なるσ’について、σ’⫦A ならば σ’⫦B (4) σ⫦¬A ⇔ すべてのσ≤σ’なるσ’について、σ’⊮A
定義の狙いを理解しよう
なぜこのような定義をしたのか?
(!),(2)はそりゃそうだ
(3),(4)について
(3) A→Bを段階σで知っているということは
その段階でAやBについて何か確定的なことを知っていることを意味しない
言えるのは
もしもっと後の段階σ’でAの証明が手に入ったなら
段階σで手に入れていたA→Bの証明と組み合わせて
Bの証明も手に入る
Aの証明が与えられた時に、それをもとにBの証明を作り出す方法を持っている
(4)について
直観主義論理では¬AはA→⊥と同じ働きをする
直観主義論理では¬Aを「Aの証明が与えられた時にそれをもとに矛盾を導き出す方法を持っている」
言えるのは
もしもっと後の段階σ’でAの証明が手に入ったなら
段階σで手に入れていた¬Aの証明(Aから矛盾を導く方法)と組み合わせて
段階σ’で矛盾が生じてしまう
もっと後の段階σ’でAの照明が手に入ることはあり得ない
モデルの例
例
(1)出発点のσ0という段階で照明されている原子式はPだけ
さらに情報を手に入れる可能性は開かれている
(2)段階σ0ではQは証明されていない
(3)σ0⫦¬Qとなるには、段階σ0以降のどこの段階でもQが照明されてはならない
σ2以降でQが照明されているのでσ0⊮¬Qとなる
(4)σ1以降のどの段階でもQは照明されていないので、σ1⫦¬Q
(5)σ2とσ4について、同じように見えるが、 σ4ではRを照明するという選択肢を閉ざす情報が付け加わっている
(6)σ2⊮Rであり、σ2⊮RⅤ¬R
段階σ2ではRが正しいかどうかの判断がつかない
段階σ4では、σ4⫦¬Rなので、σ4⫦RⅤ¬R
直観主義的に妥当な式・直観主義論理における意味論的帰結
直観主義論理の観点から見た論理的真理の定義
直観主義的に妥当な式 (intuitionistically valid wff.)
定義
Aが直観主義的に妥当
⇔
あらゆるモデル構造m=<σ0, S,≤>上の あらゆるモデルMのすべての段階σ∈Sにおいて、 σ⫦A
ある論理式Aが直観主義的に妥当な式ではないことを照明したいなら
σ⊮Aとなるような何らかの段σを含んでいるモデルを作れば良い
ある論理式Aが直観主義的に妥当な式であることを証明したいなら
そのようなモデルがあるとして仮定して矛盾を導けば良い
このようなモデルを「Aの反証モデル(counter model)」という
直観主義論理では論理的帰結はどのように定義できるのか
シンタクスの立場から定義される構文論的帰結の概念は、NHJにおけるdeductionがある
定義
Γ⊨C(論理的Cが論理式の集合Γから直観主義的・意味論的に帰結する)
すべてのモデルのすべての段階σにおいて次が成り立つ
Γの要素の全ての論理式Aについてσ⫦Aである ⇒ σ⫦C
この後の展開は?
直観主義論理の公理(自然演繹NJ)とセマンティクスを導入した
この後やるべき2つの課題
(1)直観主義論理の完全性証明
直観主義論理に関しても
NJのtheoremの集合と直観主義的に妥当な式の集合とが一致し
さらに「論理式の集合ΓからCへdeductionがある ⇔ 論理式Cが論理式の集合Γから直観主義的・意味論的に帰結する」という完全性を照明できる
(2)直観主義論理の決定手続き
古典命題論理のタブローにあたるもの(機械的手続き)
直観主義論理にも、任意の論理式が直観主義的に妥当であるかないかを有限のステップで教えてくれるアルゴリズムはある

11.4　古典論理の拡張としての様相論理

11.4.1 古典論理への代替案か古典論理の拡張か
古典論理にはたくさんの公理がある(例APL, ND)
そこからtheoremとして出てくる論理式の範囲は同じ
両方とも一つの同じ古典論理の公理系である
APLとNDは見かけは異なるが同じ論理の体系
非古典論理では
古典論理で真理とみなされたもののいくつかが論理的真理とみなされない
排中律
例
古典論理NDのtheoremの範囲と直観主義論理NJのtheoremの範囲は食い違っている
直観主義論理は古典論理にとって変わろうとする「代替案(alternative)としての非古典論理」
別の非古典論理
古典論理で真理とみなされる式はすべて論理式真理と認めた上で
さらに古典論理では扱えない論理的真理を扱えるようにする
様相論理(modal logic)
古典論理に2つの様相オペレータを付け加えてできる論理
◇(可能性演算子 possibility operator)
◇P(Pということは可能である)
□(必然性演算子 necessity operator)
□P(Pということは必然である)
この演算子を使うと
「偶然Pである」という命題は
「現にPであるが、Pでないこともある」
PΛ◇¬P　と表現できる
11.4.2 様相論理には公理系が山のようにある
様相論理にはtheoremの集合を異とするたくさんの体系(公理系)がある
100以上
初期は様相オペレータを含む論理式に対して どのように真理の定義を与えたら良いのかわからなかった
様相論理の場合、何が論理的真理か格段にぼやける
例
(a) □P→¬◇¬P(必ずPというのは、Pでないことがあり得ないということだ)
(b) ◇P↔︎¬□¬P(Pでありうるというとは、Pでないと決まっているわけではない
(c) □P→P(必ずPんなのだったら現にPである)
(d) P→◇P(現にPである以上Pでありうる)
まずはシンタクスの立場から構文論的に特徴づける
様相を含む論理的真理の全体を公理的方法で列挙する
いくつかのスタンダードな体系だけを取り上げてみておく
公理系K
すべての公理系の土台になっているもの
[公理] A1 〜 A3 APLの公理図式 A4 □(A→B)→(□A→□B) この公理図式そのものもKと呼ぶ [変形規則] R1 MP R2 ⊢A ⇒ ⊢□A (この規則は必然化規則(Necessitation)と呼ばれる。 　　　　　　　　隠された気持ちとしては、 「Aがtheoremとして出てきたら、それは論理的真理なのだから 　　　　　　　　必然的に真だろう。 　　　　　　　　だから□をつけちゃっていいや」というもの)
◇は定義により導入される
無論◇P=df¬□¬Pである
Kでprovableな論理式
(1) □(PΛQ) ↔︎ (□PΛ□Q) (分配法則) (2) ◇(PⅤQ) ↔︎ (◇PⅤ◇Q) (分配法則) (3) □P ↔︎ ¬◇¬P
公理系T
定義
公理系Kに次の公理を付け加えた公理系をTと呼ぶ □A → A (この公理じしんもTと呼ぶ)
KではprovableではなくてTで初めてprovableになる論理式
(4) P→◇P (5) ◇(P→□P)
還元法則とS4・S5
公理系Tではすべての様相が異なっている
□、□□、□□□、◇、◇◇、◇◇◇、◇□などはみんな異なる様相
なぜなら
Tからは次のような還元法則(多重様相の種類を減らす効果を持つtheorem)がひとつも出てこないため、
Tには無限に多くの多重様相がある
(1) ◇P ↔︎ □◇P (2) □P ↔︎ ◇□P (3) ◇P ↔︎ ◇◇P (4) □P ↔︎ □□P
いくつかの還元法則をTに付け加えて多重様相の種類を減らす
(5) ◇P → □◇P (6) ◇□P → □P (7) ◇◇P → ◇P (8) □P → □□P
次のような新しい公理系が生まれる
定義
Tに(8) □A → □□A(この公理図式を4と呼ぶ)を付け加えた公理系をS4という Tに(5) ◇A → □◇A(この公理図式を5と呼ぶ)を付け加えた公理系をS5という
公理4はS5ではtheoremとして導かれる
TのtheoremはすべてS4のtheoremでもある
S4のtheoremはすべてS5のtheoremでもある
もう一つの公理系の導入
定義
Tに A→□◇A (この公理をBと呼ぶ)を付け加えた公理系をBと呼ぶ
A→□◇はS5ではtheoremとして導くことができるが、S4ではできない
TのtheoremはすべてBのtheoremでもある
BのtheoremはすべてS5のtheoremでもある
それぞれの相関関係
S4では様相は7種類になる
S4では、次のtheoremが導かれる
(6) □P ↔︎ □□P (7) ◇P ↔︎ ◇◇P (8) □◇P ↔︎ □◇□◇P (9) ◇□P ↔︎ ◇□◇□P
これらのtheoremのおかげでS4は次の7種類に絞られる
なし、□、◇、□◇、◇□、□◇□、◇□◇
S5では様相は3種類
S5では、次のtheoremが導かれる
(6) ◇P ↔︎ □◇P (7) □P ↔︎ ◇□P (8) ◇P ↔︎ ◇◇P (9) □P ↔︎ □□P
S5では次の3種類となる
なし、□、◇
S5を別の仕方で特徴づける
P→□◇P(つまりB)と◇□P→Pは共にS5のtheoremであるが、S4のtheoremではない
S4にこれらのどちらかを加えるとS5になる
S4より弱いTにBを付け加えるとS5には届かない
Lemmon code
様相論理にはたくさんの公理系があるので
その相互関係をきちんと表すことのできる分類コードがあると良い
様相論理の初期の研究者レモン(E.J.Lemmon)が1977年の論文で レモンコードと呼ばれる洋装論理体系を分類するコードを提案した
K…という形をしている
例
「KXYZ」は「APL」の公理に「K,X,Y,Z」を公理として付け加えた公理
K □(A→B)→(□A→□B) T □A→A 4 □A→□□A B A→□◇A 5 ◇A→□◇A
レモンコードを使うとこれまでに出てきた公理系を次のように名前を付け替えて整理できる
K = K T = KT S4 = KT4 B = KTB S5 = KT5 = KT4B
11.4.3 様相論理のセマンティクス
はじめに
次のステップ
公理系のtheoremがすべて妥当となるようなセマンティクスを作り
その公理系のtheoremの集合と、作られたセマンティクスにおいて妥当なる集合とがぴったり重なること証明(完全性証明)
両方(シンタクスとセマンティクス)のアプローチがうまい具合に洋装についての論理的真理を捉えていたことを示す
多値論理はセマンティクスが先に作られたが
様相論理ではシンタクスがやたら発達して、たくさんの公理ができてしまった
様相論理ではコアとなる公理系Kに次々と公理を足して作られる
それぞれの公理系に対するセマンティクスも、 すべての公理系に共通したセマンティクスに次々と条件を付け加えて それぞれの公理系に対するセマンティクスが得られれば良い
クリプキ(Saul Kripke)が高校生の時に作り上げた 可能世界意味論(possible-worlds semantics)は
T, B, S4, S5などの異なった論理体系のすべてに
初めて意味論を与えることができた非常に見通しの良いセマンティクス
様相論理のスタンダードな意味論になっている
可能世界意味論
可能世界意味論の基本的なアイデア
必ずPってことは、この世界だけじゃなくって、 「どんな世界だって」Pが成り立っていること
Pが可能だってことは、この世界ではPじゃないとしても、 「どこかの世界では」Pが成り立っているということ
<基本的アイデア>
(1)
複数の世界を考える。
それぞれの世界を可能世界(possible World)という。
可能世界のうちの一つを現実世界という
論理式はそれぞれの可能世界で真理値を持つ
それは世界によって異なっていても構わない
(2)
可能世界の間には到達可能性(accessibility)という関係が定義される
世界wからみて世界w’が到達可能であるとは、
世界wをちょっと変えることによって世界w’に映ることができることと考えて良い
Wからw’が「見える」ということだと考えても良い
(3)
このうえで、各可能世界における「□A」「◇A」の真偽を次のように定義する
可能世界wにおいて□Aが真
⇔
Wから到達可能なすべての可能世界においてAが真
可能世界wにおいて◇Aが真
⇔
Wから到達可能な可能世界のうちのどれかにおいてAが真
可能世界間の到達可能性という関係に様々な制約を課すことで 様々な公理系に対するセマンティクスを得ようととする
定義:クリプキフレーム(Kripke Frame)
空でない集合WとW上の2項関係RのペアF=<W,R>をフレームという
Wの要素を「可能世界」と呼ぶ
Rを到達可能性関係と呼ぶ
定義:フレームFに基づくクリプキ・モデル
フレームF=<W,R>に対して
3つ組M=<W,R,V>をフレームFに基づくクリプキ・モデルMという
ここでVは付値関数といい。各可能世界に応じて原始式のそれぞれに真理値を割り当てる関数
VがモデルMノ可能世界wにおいて原子式Aに与える真理値をVM(w,A)と表す
またモデルの名前をいちいち区別する必要がない時は単にV(w,A)と書く
クリプキ・モデルは次の3つ化の要素からなる
(1)可能世界の集合W
(2)その可能世界同士の到達可能性関係R
(3)現式のそれぞれに、それぞれが各可能世界のとる真理値を割り当てる付値関数V
フレームが同じでもVが異なれば、それぞれの可能世界でどのような原子式が真なのかがコチなるからモデルとしては違うモデルになる
モデルにおける真理の定義
複合的なものも含む一般の論理式AがモデルMの可能世界wでとる真理値ṼM(w,A)を定義する
定義
(1) Aが原子式の時、 ṼM(w,A)=1 ⇔ VM(w,A)=1 (2) Aが¬Bという形の論理式の時、 ṼM(w,A)=1 ⇔ ṼM(w,B)=0 (3) AがB→Cという形の論理式の時、 ṼM(w,A)=1 ⇔ ṼM(w,B)=0またはṼM(w,C)=1 (4) Aが□Bという形の論理式の時、 ṼM(w,A)=1 ⇔ wRw’であるようなすべての可能世界w’において、ṼM(w’,B)=1 (5) Aが◇Bという形の論理式の時、 ṼM(w,A)=1 ⇔ wRw’であるような少なくとも一つの可能世界w’において、ṼM(w’,B)=1
モデルの例
フレームF=<W,R>が W={w1,w2,w3}、 R={<w1,w2>,<w2,w3>} で与えられているとする
このフレームFの可能世界に、 それぞれの原子式がその世界でとる真理値を割り当てれば、 モデルM=<W, R, V>が確定する
V(w1,P)=1 V(w2,P)=1 V(w3,P)=0
(1) 論理式P→□Pは可能世界w1で真かどうか?
W1から到達可能な世界はw2のみ
W2でP=1(真)だから
□ Pは可能世界w1で真
したがって
¬□Pは可能世界w1で偽
Pは可能世界w1で真だから、P→¬□Pは可能世界w1で偽
(2) 同じ式が可能世界w2で真かどうか?
W2から到達可能な世界はw3のみ
W3でPはP=0(偽)だから
□Pは可能世界w2で偽
したがって
¬□Pはw2では真
Pは可能世界w2で真だから、P→¬□Pは可能世界w2では真
(3) この式がw3でとる真理値はどうか?
W3ではPは偽だから¬□PがどうであろうとP→¬□Pは真に決まってしまう
W3での□Pの真理値は?
W3から到達可能な世界がない
このような世界では□Aや◇Aはどのような真理値を取るのか
定義の文より
任意の世界w’について、wRw’であるならば、ṼM(w’,B)=1
Wから到達可能な世界w’がないなら、「ならば」の前件が偽であることから空虚に成り立ってしまう
Wがどん詰まりの時はどんな論理式Aでも□Aは真である
W3での◇Pの真理値は?
どん詰まり世界ではどんな論理式に対しても◇Aは偽になる
どん詰まり世界では◇Aは偽なのに□Aは真になる
最終的な結果
様相論理における妥当性
次に論理的真理「妥当式」を定義する
様相論理のセマンティクスでは
フレームがあって、その上にモデルが乗っかるという2段構えになっている
「妥当」の概念も2ステップで考える必要がある
モデルにおいて妥当性 (valid in a model)の定義
上記のモデルにおいて、¬P→¬□Pはすべての可能世界で真である
このモデルにおいて妥当な式
定義
論理式AはモデルM=<W, R, V>において妥当である
Wに属するすべての世界wについて、VM(w,A)=1
フレームにおいて妥当
上記のモデルのフレームを残して付値関数V岳へ軟化させると異なったモデルになる
このモデルでは¬P→¬□PはW2で偽になる
¬P→¬□Pはこのモデルで妥当ではない
フレームが変わらない限りどのモデルでも真になる式も考えられる
フレームは共有するが付値関数が異なるようなすべてのモデルで妥当な式を
それぞれの可能世界でどのような事態が成り立っているかということには無関係に 可能世界の全体が持つ構造によって真になる式
定義
論理式AはフレームF=<W,R>において妥当である
AはフレームF=<W,R>に基づくすべてのモデルM=<W.R.V>で妥当である
11.4.4 論理式と到達可能性関係との対応
到達可能性関係が反射性∀x(wRw)を満たしている
各可能世界は自分自身に到達可能
どの可能世界でも、□Aが真なら、
その世界から到達可能な世界の中に自分獅子を含んでいるので
Aはその世界で真になる
Rが反射性を満たすようなモデルでは常に□A→Aは妥当になる
定理46
□A→AがフレームF=<W,R>で妥当である
⇔
Rが反射的である
論理式の妥当性と、到達可能性関係の間には対応関係がある
対応関係を詳しく調べる分野
対応理論の代表的な結果
定義
(1) 到達可能性関係Rがserialである ⇔ ∀w∃w'(wRw’) (つまりどの到達可能世界もそこから到達可能な世界が少なくとも一つある、 つまりそのフレームはどん詰まり世界が存在しない) (2) Rが反射的(reflexive)である ⇔ ∀w(wRw) (3) Rが対照的(symmetric)である ⇔ ∀w∀w'(wRw’ → w’Rw) (4) Rが推移的8transitive)である ⇔ ∀w∀w’∀w”[(wRw’ Λ w’Rw)→Rw’] (5) Rがユークリッド的である ⇔ ∀w∀w’∀w”[(wRw’ Λ wRew”)→w’Rw”] つまり、ある世界から到達可能である世界同士も到達可能である
代表的な公理と到達可能性関係の間に は次のような対応関係がある
定理47
(1) トートロジーは如何なるフレームでも妥当である (2) K: □(A→B)→(□A→□B)は如何なるフレームでも妥当である (3) D: □A→◇AがフレームF=<W,R>で妥当である ⇔ Rがserialである (4) T: □A→AががフレームF=<W,R>で妥当である ⇔ Rが反射的である (5) 4: □A→□□AががフレームF=<W,R>で妥当である ⇔ Rが推移的である (6) B: A→□◇AががフレームF=<W,R>で妥当である ⇔ Rが対照的である (7) 5: ◇A→□◇AががフレームF=<W,R>で妥当である ⇔ Rがユークリッド的である
11.4.5 様相論理の公理系の完全性
論理式の妥当性と フレームの到達可能性関係の条件との間には 綺麗な対応関係がある
(A)
(B)
定理48
(1) ⊢KA ⇔ Aは任意のフレームで妥当 (2) ⊢TA ⇔ Aは任意の反射フレームで妥当 (3) ⊢S4A ⇔ Aは任意の反射的かつ推移的なフレームで妥当 (4) ⊢BA ⇔ Aは任意の反射的かつ対照的なフレームでかつ妥当 (5) ⊢S5A ⇔ Aは任意の反射的、推移的かつ対照的なフレームで妥当
S5の様相が単純であることをセマンティクスの観点から捉えてみると

第12章　古典論理にもまだ学ぶことがたくさん残っている
12.1　完全武装した述語論理の言語FOL

12.1.1 言語FOL
関数記号の導入
単純な言語Lから始まって日常言語に近づけていく
量化子を導入したMPL
多重量化を導入したPPL
同一性を付け加えたIPL
最後にもう一つだけ論理言語を拡張する
確定記述句について
「「ターミネーター」の監督」
「「七人の侍」の監督」
「〜の監督」
名前(映画名)を別の名前(人の名前)に変換するオペレータ
Name-makerを関数として使う
「〜の監督」というname-makerは、
「ターミネーター」にはジェームス・キャメロン、「七人の侍」には黒澤明という具合に、
それぞれの映画にただ一つずつ特定の人間を対応させる関数になる
2つ以上の空所のあるname-makerも考えられる
例
〜と….の間に生まれた子供
言語FOLの語彙
関数記号を付け加えた論理言語の拡張
FOLの語彙
f11, f12, f13,… f21, f22, f23,… f31, f32, f33,,…
上の添字はそれがn変数の関数であることを示す
下の添字はn変数関数のグループの中の番号
任意のn変数関数を表す図式記号として𝞿nを使う
項の定義
関数記号を導入すると、項の定義が大きく変わる
これまでは
個体変項と個体定項の2つしかなかった
FOLでは
関数記号の導入により
個体を名指す項事態が複合表現になってくる
例
F11a, f11f11a, f12ab, f12f11bf11a
項の定義も帰納的になる
項の定義
(1) 個体定項、個体変項は項である。これを「原子項(atomic term)」と呼ぶ (2) τ1,…,τnを項とすると、φnτ1,…,τnは項である。 つまり、n変数関数記号φnの後ろにn個の項を並べたものは項である。 (3) (1)(2)によって項とされるもののみ項である。
タブローもそのまま使える
タブローの規則の変更はほとんどない
展開規則を当てはめる順序に特別の約束事項が必要になる)
12.1.2 FOLのセマンティクス
FOLのセマンティクスは、 関数記号とそれを含む項に意味づけを行う部分を追加するだけ
Vは関数記号φnにD上のn変数関数を割り当てる
すなわち
V(φn)=次のような関数f、
f:Dn→D
(ただし、関数fはDnのすべての要素に対して定義されているものとする)
これに伴ってアサインメントの定義もちょっとした変化が生じる
FOLには項としては、関数記号を含む複合的な項もある
そこで
個体変項へのアサインメントσを拡張してσ’を定義し
個体変項だけではなく、これらの複合的項への割り当てもやらせる
定義
FOLのあらゆる個体変項𝛏について
論議領域Dの個体を割り当てるアサインメントσが与えられているとする
この時、
σの拡張: σ’:T→D(ただしTはFOLで作ることのできるすべての項)を
次のように帰納的に定義する
(!) 個体変項𝛏に関しては、σ'(𝛏)=σ(𝛏)
つまり元々のアサインメントに一致する
(2) 個体定項αについては、σ'(α)=V(α)
(3) τ1,τ2,…,τnが項、φnがn変数関数記号であるとする
この時
σ'(φnτ1τ2・・・τn)=V(φn)(σ'(τ1),σ'(τ2),…,σ'(τn))
セマンティクスの次の仕事は
それぞれの論理式Aに対して
「モデルMはアサインメントσによってAを満たす」ということがどういうことかを定義すること
この充足関係が定義されると
閉論理式Aに対して「AはモデルMの元で真である」と定義避ける
妥当式、論理式帰結、論理的同値などが次々と定義される
言語をFOLにしても上記は全く変更なしにそのまま使える
ただし
定義の中に出てくる「項τ」の中に、複合的な項も含めて考えることになったというだけの違い

12.2　AFOLの完全性とそこから得られるいくつかの結果

12.2.1 述語論理の完全性証明
次に行われるべきことはAFOLの完全性
定理49:強い完全性定理
Γ⊢AFOLA ⇔ Γ⊨A
完全性定理はどのように証明されるか(方針)
述語論理の完全性定理を最初に証明したのはゲーテル
以下にアウトラインを説明する証明法は、1949年にヘンキンが証明し直したバージョン
基本方針は命題論理の完全性証明と変わらない
(1)まず証明すべきことを次の2つの方向に分ける
[定理49-1] Γ⊢A ⇒ Γ⊨A (健全性)
[定理49-2] Γ⊢A ⇐ Γ⊨A (完全性)
(2)このうち健全性は簡単に証明できる
AFOLの無公理がすべて妥当式であること
変形規則が意味論的帰結という性質を保存すること
つまり
A、A→B ⊨ BとA→B ⊨ A→∀𝛏Bを示せば良い
(3)完全性の証明の方が難しい
ここでも命題論理の場合と同じように、定理49-2と同値な結果を証明する
定理50:ヘンキンの定理
論理式の集合Γが構文論的に無矛盾 ⇒ Γは充足可能
(4)で、その証明をどのようにするのか
命題論理の場合と基本アイデアは同じ
Γから直接モデルを作ることは難しいので、
Γを含む都合の良い集合(極大無矛盾集合)Γ*にΓを拡大したのちに
そのΓ*を充足するモデルを作れば良い
具体的には次の2つの補助定理を証明する
[補助定理50-1:リンデンバウムの補助定理] ΓがFOLの論理式の無矛盾な集合である時
Γを部分集合にする極大無矛盾な集合Γ*が少なくとも一つ存在する
[補助定理50-2] 極大無矛盾集合Γ*が与えられると
それに含まれるすべての論理式を充足するモデル(とアサインメント)を作ることができる
つまり、極大無矛盾集合は充足可能である
このようなモデルを作る材料をどこから調達すれば良いのか?
補助定理50-1の証明プラン(Γの膨らませ方)
ΓからΓ*への拡大は次のように3ステップを踏んで行われる
(1) ΓをFOLの論理式の無矛盾な集合とする
Γに含まれている式に出てくる語彙の数が 要求されるようなモデルを作るのに充分なだけたくさんあるとは限らない
Γの論理式たちを作っている語彙に、「可算無限個」の個体定項を付け加える
こんなふうに言語を膨らませても、まだΓは無矛盾なままである
元の語彙に含まれる個体定項だけを使ってΓからAと¬Aの両方を導き出すことはできないのだったら
演繹の過程で使って良い個体定項をこんな具合に増やしてもやっぱり矛盾を導き出すことはできない
(2)言語が拡大されたが、次にさらに、 この言語に含まれる各論理式Aと各個体定項𝛏に対し、 次の形の論理式をΓに付け加える
¬∀𝛏A→¬A[α/𝛏] (ただしαは、この拡大された言語に付け加えた 個体定項のうちのいずれかであるとする)
このような論理式を付け加える狙いは
Γに「すべてのものがAというわけではない」という内容の論理式が入っていたら
Γを拡大した集合の中には何らかの判例「αがAじゃない」が入っているようにしましょうね、ということ
この段階で新しく加える式の集合をΔとする
Γ∪Δも無相関ということが証明できる
(3)こうしてできたΓ∪ΔをAPLの完全性を証明した時と同じような手続きで拡大していく
つまり、論理式を列挙した列から一つずつ論理式をとってきて
それを付け加えても矛盾しないなら、付け加えるというやり方
その上で拡大し切った集合(これをΓ*とする)について次の事実が成り立つことを証明する
(a) Γ⊆Γ* (b) Γ*は無矛盾である (c) Γ*は極大である。 つまり任意の論理式Aについて、A∈Γ*または¬A∈Γ*が成り立つ (d) Γ*には、任意の論理式Aと個体定項𝛏に対し、 ¬∀𝛏A→¬A{α/𝛏]の形ず必ず少なくとも一つは含まれている (e) 任意の論理式Aについて、Γ*⊢A ⇒ A∈Γ*
補助定理50-2の証明プラン(モデルの作り方)
Γ*から、次のようにモデルとアサインメントを構成する
まずモデルを決めるには論議領域を決めないといけない
論理式を作っている記号そのものに記号を割り当ててしまえというのがそもそもの狙い
(1) モデルMの論議領域は、拡大した言語におけるすべての項の集合とする
論議領域をこのように定めるのは、
どの項にもその項じしんを割り当てるようなアサインメントを定義して使っていこうと狙っているから
つまり
任意の項τに対してσ'(τ)=τとなるようなアサインメントである
(2) アサインメントというのはすべての個体定項𝛏についてモデルMの論議領域D内の何らかの個体を割り当てる関数σのくらすの
σ(𝛏)=𝛏として与える
次にこのアサインメントσを拡張してσ’を定義し、個体変項だけではなく、個体定項や複合的な項への割り当てもさせる
帰納的に定義する
その定義に従ってσとσ’に拡大したときに、どの項にもその項地震が割り当てられるようにするには
V(α)とV(Φn)の定義を工夫しなければならない
(3)それは次のようにする
(A) 個体定項については、V(α)=αとすれば良い
これによりσ'(α)=V(α)=αとなってくれる
(B) 関数記号については、σ'(Φn,τ1,…,τn)=V(Φn)(σ'(τ1),…,σ'(τn))=V(Φn)(τ1,…,τn)=Φnτ1…τnとしたいのだから
V(Φn)を、V(Φn)(τ1,τ2,…,τn)=Φnτ1τ2…τnを満たす関数だと定めておけば良い
(4)述語記号への意味づけは次のように行う
V(Φ)は次のような条件を満たす集合とする
<τ1,…,τn>∈V(Φn) ⇔ Φnτ1…τn∈Γ n
このように定義するのは、今作っているモデルとアサインメントには、Γnに含まれている式全てを充足するものにしたい、という狙いがある
(5)最後に同一性記号への意味づけが残っている
IPLのセマンティクスだと左右に同じ高崖並んだときにしか成り立たなくなる
VM,σ(τ1=τ2)=1 ⇔ σ(τ1)=σ(τ2) ⇔項τ1とτ2とが同じ項である
例
成り立つ例
a=a
fx=fx
成り立たない例
1+1=2
(1) それぞれの項にその項じしんを割り当てるようなモデルを考える (2) 「=」は同一性関係として解釈する。 つまりその両辺におかれた項が一つの同じものを表すときに満たされる関係として解釈する (3)Γ*には「=」の両辺に異なった項がくるような式「a=b」や「x=fx」　なども入っているだろう。 このような式も充足されるようにしておきたい
3つの要求は両立しない
とりあえず(2)を捨てる戦略を採択
便宜的に「=」は正真正銘の同一性関係ではなく
それよりゆるい何らかのどう血関係を表す2項述語ということにする
V(=)を次のような条件を満たす集合とする
<τ1,τ2>∈V(=) ⇔ τ1=τ2∈Γ*
Τ1=τ2という式がΓ*に入っているとき
その時だけに、τ1とτ2の間に成り立つ関係が「=」の意味するものだと定める
(3)は満たされるがV(=)と言った関係は同一関係ではなくなる
「推移性」(τ1=τ2、τ2=τ3ならば、τ1=τ3)が成り立つ
反射性と対称性も成り立つ
Γ*から構成するモデルとアサインメント
<モデルM> (!) 論議良識D=拡大した言語におけるすべての項の集合 (2) 述語記号Φnへの意味づけ V(Φn)は、<τ1,τ2,…,τn>∈V(Φn) ⇔ Φnτ1τ2…τn∈Γnを満たす集合とする (3) 2項述語記号「=」への意味づけ V(=)は、<τ1,τ2>∈V(=) ⇔ τ1=τ2∈Γ*を満たす関係とする (4)個体定項αへの意味づけ V(α)はαじしんとする (5) 関数記号Φnへの意味づけ V(Φn)は、V(Φn)(τ1,τ2,…τn)=Φnτ1τ2…τnを満たす関数とする このモデルに基づくアサインメントσは、 各個体変項にその個体変項にその個体変項自信を割り当てる関数であるとする。 すなわちσ(𝛏)=𝛏
補助定理50-2の証明プラン・その2(「=」を同一性記号に戻す)
(1)以上のようにして作ったモデルMとアサインメントσに関して
MはσによってΓ*に含まれる式だけをすべて充足するということ
次のことが成り立つ
VM,σ(A)=1 ⇔ A∈Γ*
(2)しかし以上のようにして作ったモデルは「=」を正真正銘の同一性関係として解釈していないものにとどまっている
Mヲテナオシシテ「=」がきちんと同一性関係として定義されているモデル(正規なモデルnormal model)としなければならない
そのためのアイデア
(A) モデルMでは、異なる2つの個体の間にも関係V(=)が成り立ってしまった
このため「=」が正真正銘の同一性記号として解釈されていない
しかし、この関係は既に述べたように同値関係ではある
同値関係の特質として、関係V(=)はモデルMの論議領域を　いくつかの排他的な同値類に分類する(付録Aの2.5)
(B)そこで、新しいモデルとして、各項にその項じしんを割り当てるものではなく、
各項にそれが属している同値類を割り当てるモデルを考える
古いモデルMで、項τ1とτ2の間に関係V(=)が成り立っている
つまり<τ1,τ2>∈V(=))ときには、2つの項は同じ同値類に属する
今、τ1が属する同値類を[τ]と書くことにすると
この発想に基づく新しいモデルでは、項τ1とτ2には同じ一つの対象[τ1]が割り当てられることになる
(C) この新しいモデルの論議領域は、 古いモデルの論議領域|M|の個体を関係V(=)で分類して作った同値類の集まり、 つまり|M|のV(=)による「商集合」になる
(3)このようにして、 述語記号その他への割り当ても適時変更して 新しいモデルMとそれに基づくアサンイメントσ’を 作ってもやはり上記が成り立つ
完全性定理は「驚くべき」定理だ
完全性定理は
以下の概念がその広がりにおいて過不足なく重なること意味している
Theoremという信託すめんから捉えた論理的真理の概念と
妥当式というセマンティクス面から捉えた論理的真理の概念とが
妥当性とか充足可能性といった概念は
モデルを使って定義される
論議領域には無限らたくさんの個体が含まれていて良い
そのモデル自体も無限にたくさんする
それら無限にたくさんのものをいっぺんにお見通しとしいう視点で定義されている
Theoremとかproofといったシンタクス由来の概念は
有限個の式から出発してステップ・バイに式を変形して行く
有限な立場から定義される概念
同じものを捉えていることは、驚くべきこと
高いところからいっぺんに見渡すことができるセマンティクスの概念と
シャクトリムシのように地べたを一歩一歩這い回るような新タクスの概念が
12.2.3 コンパクト性定理とレーヴェンハイム・スコーレムの定理
はじめに
完全性定理により
述語論理についても、命題論理の場合と同様のコンパクト性定理が成り立つことが簡単にかける
定理5:コンパクト定理
FOLの論理式の集合Γのあらゆる有限部分集合が充足可能 ⇒ Γは充足可能
このコンパクト性定理から次の定理も簡単に出てくる
定理52
論理式の集合Δは、いくらでも大きな集合を論議領域とするモデルによっても充足可能だとしよう
この時、Δは無限集合を論議領域とするモデル(面倒なので無限モデルとする)によって充足可能である
レーヴェンハイム・スコーレムの定理
完全性定理の証明で構成したモデルMについて振り返る
Mの論議領域は、以下の項からなる
そもそものΓに含まれていた項と
それに付け加えた加算無限個の個体定項から作られるだけ作った項
FOLに含まれる項の数は加算無限個だから
Mの論議領域は加算無限の濃度を持っている
Mをある意味で縮めて最終的に作ったモデルM’の論議領域の濃度は、明らかにMの濃度と同じかそれよりも小さい
以上より次の定理が導かれる
定理53: レーヴェンハイム・スコーレムの定理
論理式の集合Δは充足可能だとする
この時、Δを充足するモデルで高々加算個の個体からなる論議領域を持つようなものが存在する
この論議領域を加算モデル(countable model)と呼ぶ

12.3　第1階の理論

述語論理に公理系を作ることができるのか
一例
公理系AFOL
[公理] A1〜A3 APLに同じ (ただし、そこでの図式文字「A」「B」に鯛゛にゅうされるのはFOLの論理式である) A4 ∀𝛏A→A[τ/𝛏] (ただし、ここでτに代入して良い項にはある制限がある。でも省略) A5 ∀𝛏(𝛏=𝛏) A6 (𝛏=𝛇)→(φn(…𝛏…)=φn(…𝛇….)) (ただし、φnは任意のn変数関数記号で、Φn(…𝛏…)は項φn(….𝛇….)の　個体変項𝛏の現れの一つ以上(幾つでも良い)を𝛇で置き換えて得られる項とする) [変形規則] R1 MP AとA→Bが与えられたら、Bを導き出して良い R2 GEN (Generalization) A→Bが与えられたら、A→∀𝛏Bを導き出しても良い (ただしAはxを自由変項として含んではならない)
APLのと吉同じようにAFOLにおけるproof,trheorem,仮定からのdedictionが定義でき、
APLと同様の演繹定理が成り立つ　公理的理論とは
第1階の理論(first order theory)
FOLで許される語彙と、FOLで定義できる論理式を使って
ある分野の基礎的知識を公理系のかたちでまとめることができる
注意
理論と論理をごちゃごゃにしないように
理論の例
ロビンソン算術 (Robinson arithmetic)
Qの文法
(1)語彙
(1)原子項 個体定項 () 個体変項 x, y, z, .. (2) 述語論理は使わない (3) 関数記号 　　1変数関数記号 S 2変数関数記号 +, * (4) 論理定項 　　結合子 →、Ⅴ、Λ、¬ 　　量化子 ∀、∃ 　　同一性記号 = (5) 補助記号 　　(, )
(2) 項、論理式の定義
これらの語彙から、FOLの項、論理式の定義沿って作られる記号列が、Qの論理式である
Qの式
「Qでprovableとか、Qの公理になっている式」ではない
Qの語彙で作流ことのできる式
Qの公理
Qの公理は次の2つのグループからなる
(1) 論理公理(logical axiom)
どんな第1階の理論も共通に持っている公理
具体的にはAFOLの6つの公理をQの論理公理とすれば良い
ただし、AFOLの図式文字(A、𝛏、τ)に代入して考えて良い記号は
Qの語彙とそれに基づいて作られるQの項と論理式に限られる
(2) 固有公理(proper axiom)
それぞれの理論に固有な公理
これによりその理論に固有な記号(関数記号以外の個体定項、述語記号)に「意味」が与えられる
この部分は理論ごとに異なる
ロビンソン算術Qでは次の7つの公理をおく
Q1 ∀𝛏∀𝛇(𝛏≠𝛇 → S𝛏≠S𝛇) Q2 ∀𝛏(0≠S𝛏) Q3 ∀𝛏(𝛏≠0 → ∃𝛇(𝛏=S𝛇) Q4 ∀𝛏(𝛏+0=𝛏) Q5 ∀𝛏∀𝛇(𝛏+S𝛇=S(𝛏+𝛇) Q6 ∀𝛏(𝛏*0=0) Q7 ∀𝛏∀𝛇(𝛏・S𝛇=((𝛏・𝛇)+𝛏))
Qのモデル
数学で「算術」といった時
それは「読み書き算盤」のことではなく
自然数と加法、乗法という演算についての理論を意味する
Qはその意味での算術を公理的理論の形に整備したもの
Qの固有公理は次のモデルで真になる
<モデルM> 論議領域=自然数の集合 V(S):任意の自然数nにその次の自然数n+1を対応させる関数 (これを後続車関数successor functionという) V(+): 自然数nとmの組にその和を対応させる関数 V(*):自然数nとmの組にその積を対応させる関数 V(0):自然数0
このモデルMで解釈すると以下のようなことを述べてものだと言える
Q1は「異なる自然数の後続車同士もまた異なる」
Q2は「0はいかなる自然数の後続車でもない」
Q3は「0以外の自然数には、それぞれ直前の自然数がある」
定義
理論QにとってのモデルMのように
理論Kのすべての公理を真にするモデルを、単に「理論Kのモデル」という
または理論KはモデルMを持つという
Theorem、無矛盾などの定義
AFL、AFOLなどに定義されてきたいくつかの概念は同じように公理的理論に対しても定義できる
定義
以下の条件を満たす
Qの論理式の有限個の列Bq,B2,..,Bn(この最後のBnがCであるとする)
条件Bi (ただし1≤i≤n)は次のいずれかである
(1) Qの公理である
(2) 先行するB1,B2から変形規則(MP)によって引出された式である
Cのproofが存在する時
CはQのtheoremである
または、CはQにおいてprovable(証明可能)であるといい、⊢QCと書く
Qのtheoremの例
「1+1=2」をQからtheoremとして導けるのか?
Qは1とか2の記号を持っていない
1は0の後者 S0
2は SS0
導き出す式は「S0+S0=SS0」
⊢QS0+S0=SS0であることを示す (1) ∀x∀y)x+Sy=S(x+y)) Q5 (2) ∀y(S0+Sy=S(S0+y)) (1)A4 (3) S0+S0=S(S0+0) (2)A4 (4) ∀x(x+0=x) Q4 (5) S0+0=S0 (4)A4 (6) S0+S0=SS0

12.4　モデル同士の同型性

12.4.1 互いによく似たモデルとそうでないモデル
<モデルM1> D=N(自然数全体の集合、0も含むものとする) V(P)=(0,3,6,9,…)、つまり3の倍数の集合 V(f)=後続車関数 V(g)=xとyにそれらの和x+yを対応させる関数 V(a)=0
<モデルM2> D={1, 1/2, 1/4, 1/8,…}、つまり{1/2n |n∈N} V(P)={1, 1/8, 1/64, 1/512,…}、つまり{1/23n|n∈N} V(f)=xにx/2を対応させる関数 V(g)=xとyにそれらの積x×yを対応させる関数 V(a)=1
上記の2つのモデルで、 以下の論理式がとる真理値を比べる
(1) Pa
(2) Pfa
(3) gaffa=ffa
(4) a≠fffa
(5)∃x∀y(fy≠x)
12.4.2 同型なモデル
似ているのは構造
M1とM2のどこが似ているのか?
似ているのはモデルが何からできているのではなく
モデルの構造が似ている
どちらのモデルも次の特徴を持っている
(1)
論議領域は、個体定項aが名指ししているある一つの出発点(M1では0、M2では1)から始まって
それ以外の要素が、その次、そのまた次問い具合に無限に続く列の形で現れる集合になっている
どちらのもでるでも関数fはその「〜の次」を与える関数になっている
(2)
述語Pはどちらのもでるでも、ω列の中で出発点を含めて2つおきに現れる要素の全て、そしてそれだけに当てはまる
(3)
関数gは、ω列において、n番目とm番目の要素に対し、n+m-1番目の要素を割り当てる関数になっている
定義
(1)
M=<D,V>とM’=<D’,V’>をそれぞれFOLの論理式の集合Γに対して与えられたモデルとする
今、2つのモデルの論議領域DとD’の間に写像h:D→D’があり、次の条件を満たしている時
この写像hを、モデルMからM’の中への準同型写像(homonorphism)という
(A)
各n項述語記号ΦnとDの要素の任意の順序n組<a1,…,an>とに対し
<a1,…,an>∈V(Φn) ⇔ <h(a1),…,h(an)>∈V'(Φ)
(B)
各n項述語記号ΦnとDの要素の任意の順序n組<a1,…,an>とに対し
h(V(Φn)(a1,…,an))=V(Φn)(h(a1),…,h(an))
(C)
各個体定項αに対し
h(V(α))=V(α)
(2)
以上の条件に加え、写像hが1対1写像であるとき
hを同型写像(isomorphism)という
(3)
また、モデルM=<D,V>からモデルM'<D’,V’>への「上への同型写像」がある時
モデルMとM’は同型(isomorphic)であるといい、M≡M’と書く
2つのモデルが同型だというのは、
乱暴に言えば
両者には構造の上で違いがないということである
定理54:同型性定理 (isomorphism theorem)
モデルMとM’が同型であるとする
つまり、両者の間に上への同型写像があるとする
σを個体定項𝛏にモデルMの論議領域D内の個体を割り当てるアサインメントであるとする
この時次が成り立つ
任意の論理式Aについて、MがσによってAを満たす
⇔
M’がh=σによってAを満たす
h=σはアサインメントσと準同型写像hの合成写像を表す
個体変項𝛏にまず、σで対応づけられるD中の個体を対応させる
それをhでD’中の個体にさらに対応づける
12.4.3 理論の規範性とノン・スタンダードなモデル
理論の範疇性の定義
同型なモデルは同じ論理式の集合を充足する
この逆は成り立つのか?
ある論理式の集合を充足するモデルは互いに皆同型なのか?
答えは
そういう時もあるし、そうでない時もある
定義
理論Kがm-範疇的(m-categorical)である(mは任意の基数)
⇔
論議領域の濃度がmであるようなKのどの2つの正規な (つまり「=」が同一姓と解釈される)モデルも常に互いに同型である
例
「Kの語彙」 個体定項なし、述語記号なし、関数記号なし 「Kの公理」 (1) 論理公理 　　AFOLの公理 (2) 固有公理 　　K1 ∃𝛏∃𝛇(𝛏≠𝛇Λ∀𝜼(𝛏=𝛈Ⅴ𝛇=𝜼))
この理論Kは2-範疇的
Kのどんな正規モデルも2つの個体からなる論議領域を持つ
ロビンソン算術は範疇的ではない
ロビンソン算術Qをもう一度振り返る
Qを作った狙い
自然数の集合を論議領域として持つ
S,+,*,0のそれぞれの記号に後続車関数、加法関数、乗法関数、0を割り当てるモデル(これをMとする)
その公理が全て真となる
Qの得手不得手
「SS0+S0=SSS0」のような個別の数値についての命題は導き出せる
一般命題に関しては弱いところがある
例
「0+S0=S0+0」「0+SS0=SS0+0」といった個別れは全てprovable
それを一般化した「∀x(x+y=y+x)」つまり加法の交換法則は「Qのtheoremではない」
Qでprovableでない主な論理式
(A) ∀x(0+x=x)
(B) ∀x(x+y=y+x)
(C) ∀x(x≠Sx)
(D) ∀x∀y∀z(x+(y+z)=(x+y)+z)
(E) ∀x(0*x=0)
(F) ∀x∀y(x*y=y*x)
(1) (a)〜(f)はモデルMで真になる
(2) でも、これらはQのtheoremではない
例
⊬Q∀x(x+y=y+x)
Qの公理は全て真になるのに、∀x(x+y=y+x)は偽になるようなモデルがあることを意味している
ロビンソン算術には自然数全体の集合とは同型ではなく、異なる構造を持つモデルもある
このようなモデルを 「非標準的モデル(non-standard model)」と呼ぶ
ロビンソン算術だけが悪いのではない
非標準的モデルの存在はQが第1階の理論であることの宿命
定理55
自然数全体の集合に同型なモデルだけを持つような第1階の算術の理論はあり得ない
つまり、第一階の算術の理論には必ず非標準モデルがある

12.5　第2階の論理

12.5.1 FOLでは表現できない命題がある?
閉鎖的な批評家たち
フル装備した言語としてFOLを導入したが
FOLを持ってしてもどうにも表現できない命題が存在する
例
お互いしか褒めないような批評家たちがいる
FOLの語彙だけでは書くことができない
∃xMxΛ∀x∀y((MxΛAxy)→(x≠yMy))
Mx:Xはマロン派に属する
Axy:xはyをほめる
論議領域は批評家全体の集合
∃xMx:マロン派に属する人がいる
これを言っておかないと マロン派に属する人がいないときに Λの後ろは無条件にしんとなってしまう
∃X(∃xXxΛ∀x∀y((XxΛAxy)→(x≠yΛXy)))
MPL,PPL,IPL,FOLでは作ることができない
通常の量化子の他に、∃Xのように述語記号の位置を量化している記号が出てきているから
述語を量化する変項(X,Yなど)と量化子を許すような論理言語
これに対して
個体への量化しか表現できない言語
無限にたくさんのものがある
第2階の言語は第1階の言語よりも豊かな表現力を持っている
FOLの表現
少なくともn個のものがある
第2階の言語
無限にたくさんのものがある
無限にたくさんのものがあるということをどのように表現するのか
次のように考える
神様がこの世にあるものを一列に並べてそれを順に触って行く
Rxyという述語で「神はxを触ったのちにyを触る」を意味するものとする
この列に終わりがなければこの世には無限にたくさんのものがあるといって良い
Rに関しては上記が成り立たないといけない
神が順繰りに触って行くということが成り立つために欠かせない条件
これだけで無限にものがあるとは言えない
「3つのものに触ってそれで終わり」でも真になってしまう
ものが無限にあるというためには
神がどれだけ触って次がある、と言わなければならない
ドーナッツ構造の場合(有限)でも上記の条件は成り立つ
xを触ったのちに(一周してきて)またxを触る
上記を否定すればせ良い
(1)(2)(3)を連言にしたものは、無限たくさんある場合に真になる
Rという特定の関係について語っている
無限にたくさんのものがある
例えばRみたいな、何らかの最終元のない順序づけがある
(5) ∃X[∀x∀y∀z((XxyΛXyz→Xxz)Λ∀x∃yXxyΛ∀x¬Xxx] 12.5.2 第2階の論理のセマンティクス
述語記号が占めていた箇所を束縛する∀Xとか∃Xとかいった量化を 許す方向で論理言語を拡張してできる「第二階の言語」を「SOL」と名付ける
SOLで付け加わったのは
∀Xとか∃Fのような量化
どうすれば良いのか?
∀xとか∃yのような従来の量化(第1階の量化)の意味づけをヒントにして考える
(1)まずモデルを定める。
議論領域Dを決め、述語記号その他への意味づけを行う
(2) 次にアサインメントを定義する
アサインメントとはあらゆる個体変項𝛏について、議論領域D内の何らかの個体を割り当てる関数である
(3) 次に原子式Aに対し、モデルMがアサインメントσによりAを満たすことの定義を行う
(4) 以上の定義をBasisにして、結合子や量化子を含む複合的論理式に対する充足関係を機能的に定義する
ここで量化子への意味づけが行われたことになる
量化を含む式に充足関係を定義するときには「アサインメントの変種」を用いる
これを第2階の量化を含む言語にまで拡張するには?
(1)はそのまま
(2)は
第1項の変項(x,y,z,..)に個体を割り当てるアサインメントσはそのまま使う
第1項はDの要素、すなわち個体をどれとは決めずに指す
第2項の量化に意味づけをするには、第2項の変項(X,Y,…)に対して使えるアサインメントが必要
このアサインメントをσ2と書く
σ2は第2項の変項のそれぞれに一体何を割り当てれば良いのか?
第2項は、性質、関係を指すものとして考えられる
モデルによる解釈では、これら全てDを材料に作り出さなければいけない
性質はDの部分集合、n項関係はDnの部分集合と考えきたことを思い出す
求めるアサインメントは
定義
SOLのあらゆる第2項の変項に対して
それが第n項述語変項の場合は
Dnの何らかの部分集合を割り当てる関数σ2を考える
このσ2をモデルに基づく第2項のアサインメントとする
第2階の論理は、個体でけだなく、個体の集合もあるとかないとか語る論理
これまでの個体に対するある・なしの言及から、個体の集合に対するある・なしを言及する
第2階の論理の嫌なところ
第1階の世界
この世界には色々なものがあるだろう
とにかく存在指定るものはみんな個体だ
だから、個体の人間は存在しているといって良い
例
3人の人間が存在しているといって良い
第2階の世界
「3人の人間からなる集合」といったものは存在しない
抽象的な一種のフィクション
個体はあるが、個体の集まりといったものはないと考える人
12.5.3 第2のベアノ算術
SOLに与えられた表現手段を使って公理系の形にまとめた理論
代表例
第2階のペアノ算術 (Second order Peano arithmetics:PA2)
PA2の固有公理はロビンソン算術Qの固有公理に上記の公理を加えたもの
MI2:この公理が第2階の数学的帰納法の原理(mathematical induction)と呼ばれるから
第一階のペアノ算術(PA1)
MI1 xを自由項として持つPA1の任意の論理式Axについて(A0Λ∀x(Ax→ASx))→∀xAx)
定理56
第2階のペアノ算術PA2の任意の2つのモデルは互いに同型である
つまり、PA2は範疇的である
12.5.4 第2階の論理の特質
第1階の論理でできて、第2の階の論理でできないこと
定理57
第2階の論理についてはコンパクト性が成り立たない
つまり、そのいかなる有限集合も充足可能なのに
それ自体は充足可能でない論理式の無限集合が存在する
定理58
第2階の言語の式で、非可算無限濃度の論議領域を持つモデルで初めて真になるようなものがある
レーヴェンハイム・スコーレムの定理が成り立たない
定理59
第二階の論理に対する標準的なセマンティクスにおいて立とうとされる論理式のすべてがtheoremとして出てくるような公理系は作れない
第二階の論理には完全性定理が成り立たない

第Ⅳ部のまとめ

付 録
A. A little bit of mathematics

1. いろいろな種類の数について
1.1 自然数から有理数まで
1.2 実数
2. 集合論についての基礎知識
2.1 集合とその表記法
集合(set)とは「もの」の集まり
「もの」はなんでも良い
「もの」がその集合に属しているかどうかだけははっきり定義できないといけない
集合を表す2つの方法
要素を書き並べるやり方
A={2,5,8,11,14,17,20,23,26,29}
要素が共通した性質を持っている場合に、その性質により集合を表す
A={n|nは30よりも小さく3で割ると2余る自然数である}
aという「もの」が集合Aの要素であることをa∈Aと書く
a∈A出ないことをa∉Aと書く
2.2 集合のアイデンティティは何か
空集合
いかなる要素を持たない集合を 「空集合(empty set)」という
空集合を𝛟で表す
∀x(x∉𝛟)
集合の外延性
<定義>集合Aと集合Bがあった時に、 それぞれが含む要素が全て共通であるとき、 つまり∀x(x∈A⟷x∈B)であるとき、 集合AとBは同一であるといい、A=Bと書く
2つの集合が同じ集合であるかどうかは、 それらが同じ要素だけからなるかどうかによって決まり、 それがどのように定義されてきたかには寄らない
A={x|xは6の倍数である}と B={x|xは3で割り切れる偶数である}と C={x|xは3と2の公約数である}は 集合の定義としては異なるが要素が同じなので同じ集合
2.3 集合に対する演算
部分集合
<定義>集合AとBがあった時に、 Aの要素が全てBの要素でもある時、 AはBの「部分集合(sbuset)」であるといい、A⊆Bと書く。 つまりA⊆B ⇔ ∀x(x∈A→x∈B)
x∈B→x∈Bは常に成り立つ。よって集合B自身もBの部分集合である。
空集合𝛟は任意の集合Aの部分集合である
集合Aが集合Bの部分集合であるが、 A=Bでない時、 AはBの「真部分集合」であるといい、 A⊂Bで表す
共通集合
<定義>集合AとBがあった時に、 そのどちらにも含まれている要素だけを集めて作った集合を、 AとBの共通集合(inetrsection)といい、A⋂Bで表す つまり、A⋂B={x|x∈A∧x∈B}
合併集合
<定義>集合Aと集合Bがあった時に、 その少なくともどちらかに含まれている要素だけを集めて作った集合を、 AとBの合併集合(union)といい、A⋃Bで表す。 つまりA⋃B={x|x∈A∨x∈B}
無限にたくさんの集合の共通集合と合併集合
共通集合や合併集合は3つ以上の集合についても考えることができる
2.4 順序対とデカルト積
順序対
要素の並ぶ順番を無視しないで考えたペアを「順序対」
座標データ等
順序n組
順序込みで考えたn個の要素の組み
デカルト積
A={1, 2}, B={a, b,c}の2つの集合から前にAの要素、 後ろにBの要素がくるような順序対を作成
<1,a><1,b><1,c><2,a><2,b><2,c>
またはデカルト積(Cartesian product)と呼んでAXBで表す
べき集合
<定義>集合Aがあるとする。 この時、集合Aの部分集合の全てを集めて作った集合(正確には集合の集合)を Aのベキ集合(powerset)と呼びP(A)で表す
2.5 同値関係と同値類
同値関係
反射性、対称性、推移性を満たす関係
1つのサブグループの中の要素は全てお互い関係Rで結ばれていて、 サブグループ内のあるものと関係Rで結ばれているものは 必ず同じサブグループに属している
同値類
集合Sを同値関係Rで分割した時に得られる サブグループP1,..,Pn..のそれぞれを同値類(equivalence class)
商集合(quatinentb set)
同値類P1,…,Pn,..を全部集めた集合
3 関数
3.1 関数の定義
式は関数の表現１つに過ぎない
<定義> 集合AとBがあり、 Aの各要素にBの各要素を割り当てる対応づけfで次の条件を満たすものがある時、 fを集合AからBへの関数(function)とか写像(mapping)という (1) fはAに含まれるどの要素にもBの何らかの要素を割り当てる (2) fはAのどの要素にも、それぞれただ１つずつのBの要素を割り当てる
<定義> (1) AからBへの関数fがAの要素aに割り当てるBの要素をf(a)と書き、関数f(a)によるaの写像(iamge)という (2) またfが集合AからBへの関数であることを、f:A→Bと書く。集合Aをfの定義域(domain)、Bをfの値域(range)という (3) また次の集合をAからBへの関数fによるAの像といい、f(A)と書く f(A)={b|f(a)=bとなるa∈Aがある} つまりBの要素のうち、 　　Aの何らかの要素のfによる像になっているものだけを全て集めて作った集合が 　　f(A)である。もちろんf(A)⊆Bが成り立つ
3.2 関数のいろいろ
単射・1対1写像
<定義> 関数f:A→Bが、次の性質を持つ時、 fをAからBへの単射(injection)とか1対1写像(one-to-one mapping)という fはAの異なる要素にはBの異なる要素を割り当てる、つまり、x≠y ⇒ f(x)≠f(y) FがAからBへの単射であることをf:A(1-1)→Bとかいたりする
全射・上への写像
<定義> 関数f:A→Bが次の性質を持つ時、 fをAからBへの全射(surjection)とかBの上への写像(onto-mapping)という Bのどの要素も何らかのAの要素fによる写像である。f(A)=B
中への写像
<定義> 関数f:A→Bが、次の性質を持つ時、 fをBへの中への写像(into-mapping)という f(A)⊂B, つまりBの要素の中には、 いかなるAの要素のfによる像にもなっていないものが少なくとも１つある
全単射・双射
<定義> f:A→Bが単射であり、かつ全射であるとき、 fをAからBへの全単射とか双射(bijection)という
4 集合の大きさをはかる
4.1 集合の濃度
4.2 可算集合と非可算集合
4.3 基数の系列
4.4 全ての論理式は列挙可能である

B. 練習問題解答
C. ブックガイド