|| 述語と数学
一言で言うなら、こいつは数学の「言語」ですね。
「命題論理」に『述語を加えた』ものがこれになります。
スポンサーリンク
目次
・数学の言語
一階述語論理「数学の基礎知識（五十音的な）」
二階述語論理「一階述語論理より量化できる範囲が広いやつ」
高階述語論理「表現の制限がほぼ無いやつ」
・無限論理「無限に長い文を許しちゃう理屈」
・量化記号の代表例
全称量化「全ての（もの）は（条件）を満たす」
存在量化「（条件）を満たす（もの）が存在する」
一階述語論理 First-Order (PL)
|| 数学で使うアルファベット的なもの
「命題論理」を拡張した述語論理のこと。
「述語論理」っていうと
だいたいこれのことを指してると思ってOKです。
「二階述語論理」も少しは見ますが、
基本的に扱うのは「一階」のものだけ。
だいたいは「二階」の範囲で表現できてしまうので、
「三階」以降を扱うことはほとんどありません。
一階述語論理がメインの理由
これだけ「完全性」と「健全性」が証明されていて、
「実効性」ってやつも保証されている。
以上が理由なわけですが、
まあこれだけ言われてもって話ですよね。
「完全性」「健全性」「実効性」
どれも馴染みのない単語だと思います。
「完全性」は「正しけりゃ証明できちゃうぜ」って感じで、
「健全性」は「証明できるなら正しいぜ」って感じなんですが、
これを知ってたって人は少数でしょう。
とはいえ、理由はただこれだけで、
それ以上でも以下でもありません。
『量化の範囲』と「健全性・完全性」に着目し、
「二階」「高階」の範囲を削っていって、
これはだめあれもだめをひたすら繰り返して、
色々と性質を確認して、ようやく得られた最小限の範囲
それが「一階」の「述語論理」であり、
数学が示した『成果』の一つで、
この「一階」の範囲でだけ、
「健全性」「完全性」「実効性」が両立する。
だから、これがメインになっています。
二階述語論理 Second-Order (PL)
|| もっと量化していいよって感じのやつ
「個体（変数）」だけじゃなく
「関数」と「述語」も『量化』していい
そんな範囲の述語論理を、
「二階」述語論理と言います。
割と実用的で、
推論は妥当（正→正）なので「健全性」は確か。
なので、これをベースに推論を行っても基本的には大丈夫です。
ただ「完全性」は今のところ保証されてなくて、
「実効性」の面でも、今後も保証されない可能性が高いです。
なので、なんで正しいのかを「証明」することはできません。
「正しいっていうのは分かる」んですが、それだけ。
『なんで正しいかを証明する』
この点で、不備が出てしまいます。
実効性
「実効性」（決定可能性）については、
詳しくは「再帰理論」で解説します。
ざっと言うと、
「正しいかどうか確実に確認できる」みたいな性質なんですが、
これだけだとちょっと説明不足ですよね。
「確認できるってどういうこと？」とか
「確実にってどう判断すんの？」とか
いろいろ疑問が出てくると思います。
二階の文法規則（量化して良いやつについて）
「二階」で拡張される範囲は、
『変数を含む集合』『k変数関数』『k項関係』の３つで、
\begin{array}{lllllll} t\mathrm{\,\, is \,\, Term} \\ \\ & t∈S \\ \\ t_k\mathrm{\,\, is \,\, Term} \\ \\ &f(t_1,t_2,...,t_n) \\ \\ & R(t_1,t_2,...,t_k) \end{array}
これら「 S,f,R 」を『原子論理式とする』ことで、
この３つを『量化可能』に。
「個体」の範囲を飛び越えて、
「集まり・出力方法・関係」も量化できるようになります。
二階言語で表現可能な具体例
「一階」の範囲では『中身が確定していない』なら、
『集合・関数・関係』は「量化」できません。
つまり『変数が量化されて定項になっていない』状態で、
「全ての関係」とか「全ての関数」とか、
こういうことが言えないわけです。
\begin{array}{llllll} \forall S &&t∈S \\ \\ \displaystyle \forall f(t) && f(t) \end{array}
しかし「二階」の範囲では、これが許されます。
なので例えば
「全ての関数 f はこういう感じで微分可能」みたいな表現を
\begin{array}{llllll} \displaystyle \forall f(t) &&\Bigl[ \displaystyle -\infty<\frac{df(t)}{dt}<\infty \Bigr] \end{array}
こんな風に表現したり、
\begin{array}{llllll} \displaystyle \forall S && S⊂\mathrm{R} \end{array}
「全ての S は実数の部分集合である」とかを
こんな風に表現できたり、
「個体の量化」を『省略できる』ので、
わりと柔軟な表現が可能に。
『個体の中身が確定していない』状態でも、
「上から無理矢理確定させる」ことができます。
これがダメな理由の感覚
『量化する』ということは
「真偽が確定する」ということ。
この点を理解していれば、
\begin{array}{llllll} \displaystyle \forall f(t) &&\Bigl[ \displaystyle -\infty<\frac{df(t)}{dt}<\infty \Bigr] \end{array}
例えばこれがちょっとまずいってことが
なんとなーく分かると思います。
というのもこれ、
「関数」も量化によって範囲が限定されていますが、
自動的に『項・個体 t 』もまた「範囲を限定」されていて、
\begin{array}{rlc} \displaystyle f&:&\mathrm{R}&→&\mathrm{R} \end{array}
関数がこの範囲なら「実数の範囲内」
こういう制約を確かに受けてるじゃないですか。
\begin{array}{llllll} \displaystyle \forall f(t) &&\Bigl[ \displaystyle -\infty<\frac{df(t)}{dt}<\infty \Bigr] \end{array}
この論理式は宣言である以上
「確実に真」となるので、
\begin{array}{llllll} t∈S&&\mathrm{Unknown} \\ \\ t∈\mathrm{N} && \mathrm{False} \\ \\\displaystyle t∈\mathrm{R} && \mathrm{True} \\ \\ t∈\mathrm{C} &&\mathrm{False} \end{array}
項・個体 t には
このような「束縛（範囲の限定）」が確実に存在しています。
しかし、どうでしょう。
この t の範囲は『実数の範囲のみ』
という「限られた領域」に限定されているんでしょうか？
「もっと広い範囲」かもしれないし、
『奇妙なルールが採用されている』場合、
「もっと複雑になる」かもしれない。
\begin{array}{llllll} \displaystyle \forall f(t) &&\Bigl[ \displaystyle -\infty<\frac{df(t)}{dt}<\infty \Bigr] \end{array}
「自然数・有理数に限定」されるのはダメだし、
「大小比較ができる」以上、複素数もダメだけど、
『実数より小さな範囲に収まるかもしれない』
いや、そんなん分かるはずないじゃん
と思うかもしれませんが、
その通り、この論理式の主張には、
そんな可能性を否定する要素は無いんですよ。
個体 t の量化がされていない以上、
この項・個体 t の取り得る範囲は
『どこまで制限されているか』曖昧なままなんです。
とまあこんな感じで、
『項 t の範囲』を確認していくと、
「局所的な範囲は確実にわかる」わけですが、
『全体的な範囲』の話となると、
これが途端によく分からなくなる。
この点で「証明」が難しく、
そのせいで、これは基礎としては扱えない
とまあそういうわけです。
高階述語論理 Higher-Order (PL)
|| 量化可能な範囲に特に制限が無いやつ
↑で話したような「拡張」を延々と繰り返したやつがこれ。
抽象的過ぎて、ちょっとよく分かんないです。
あれもそれもこれも、
なんでも「量化」してOKですから、
\begin{array}{rlc} \displaystyle t \mathrm{\,\, is \,\, Term} \\ \\ &\displaystyle \forall f\Bigl( g(t) \Bigr) &&\displaystyle 0<f\Bigl( g(t) \Bigr) <1 \end{array}
こういう意味があるんだか無いんだか
『特に範囲を限定しない』量化も許容します。
見ての通り
この「項 t の制約」は「関数 f,g 」に依存しますから、
『考慮される関数 f,g によって範囲が変わる』ので、
\begin{array}{llllll} \displaystyle f&:&\mathrm{R}&→&(0,1) \end{array}
\begin{array}{lllllll} \displaystyle g(t)&=&t \\ \\ &&&t∈\mathrm{R} &\mathrm{True} \\ \\ &&&t∈\mathrm{C} & \mathrm{False} \\ \\ \\ \displaystyle g(t)&=&|t| \\ \\ &&&t∈\mathrm{R} &\mathrm{True} \\ \\ &&&t∈\mathrm{C} & \mathrm{True} \end{array}
確かな制約は存在しても、
分かりやすい制約は存在しません。
「限定のパターン」は無数に存在してしまいます。
はい。とまあそんな感じなので、
ぶっちゃけほとんど使いません。
なので、なんとなくこういうのがある
くらいに思っておけばこれは大丈夫です。
無限論理 Infinitary Logic
|| その点々のとこどうなってんの？
これは「書き方」を認める感じの話で、
\begin{array}{llllll} \displaystyle 1,&2,&3,&... \\ \\ a_0,&a_1,&a_2,&... \\ \\ x_0,&x_1,&x_2,&... \end{array}
例えばこういうのを式として許容して、
「省略できるようにする」ために必要になります。
\begin{array}{lllllll} \displaystyle A_0&\land&A_1& \land& A_2& \land& ... \\ \\ A_0&\lor&A_1& \lor& A_2& \lor& ... \end{array}
これはもちろん
「言明（はっきりした主張）」の連なりである
「証明」でも採用されることがあって、
\begin{array}{llllll} \displaystyle \mathrm{Cardinal}(\mathrm{Natural \,\, Number})&=&ω_0 \\ \\ \mathrm{Cardinal}(2^{ \mathrm{Natural \,\, Number} })&=&ω_1 \\ \\ &\vdots \\ \\ \mathrm{Cardinal}(2^{2^{2^{\cdots 2^{ \mathrm{Natural \,\, Number} }}}})&=&ω_{n+1} \\ \\ &\vdots \end{array}
主に「正則（ちゃんと規則がある）」
という性質を持つ「無限」の範囲内で許容され
完全性を確保できるような工夫をされた上で
「省略」あるいは「必要になる場合」で使われたりします。
規則の概要
『無限』の部分がちょっとややこしいので
その辺りちょっとよく分かんないと思いますが、
ここではとりあえず流してください。
\begin{array}{llllllllll} \displaystyle A_0&∧&A_1&∧&A_2&∧&... \\ \\ A_0&∨&A_1&∨&A_2&∨&...\end{array}
\begin{array}{lllllllll} \displaystyle \forall x_0& \forall x_1& \forall x_2& ... & P(x) \\ \\ \exists x_0& \exists x_1& \exists x_2& ... & P(x) \end{array}
これらを「式」だと認める。
これが無限論理の中でもよく見る
「一階」無限論理の採用によって保障されるもので、
\begin{array}{llllllllll} \displaystyle A_0&∧&A_1&∧&A_2&∧&... \\ \\ A_0&∨&A_1&∨&A_2&∨&... \end{array}
認めたいのはだいたいはこの二つの形。
こういう「書き方」を認めるものだと思ってれば
その認識でだいたい合ってます。
\begin{array}{llllllllll} \displaystyle \bigvee_{k<ω} A_{k} \\ \\ \displaystyle \bigwedge_{k<ω} A_{k} \end{array}
「無限」の制約として
厳密にはこういう宣言もなされてるんですが、
まあこれはとりあえずスルー
\begin{array}{lllllll} \displaystyle A∧(B_0∨B_1)&=&(A∧B_0)∨(A∧B_1) \\ \\ \\ (A_0∨A_1)∧(B_0∨B_1)&=&(A_0∧(B_0 ∨ B_1))∨(A_1∧(B_0 ∨ B_1)) \\ \\ &=& (A_0∧B_0)∨(A_0∧B_1) ∨ (A_1∧B_0)∨(A_1∧B_1) \end{array}
\begin{array}{lllllll} \displaystyle \bigwedge_{i<ω}\bigvee_{j<ω} A_{ij} &\displaystyle = \left( \bigvee_{j<ω} A_{0j} \right) &∧& \displaystyle \left( \bigvee_{j<ω} A_{1j} \right) &∧& \cdots \end{array}
\begin{array}{llllll} \displaystyle \left( \bigvee_{j<ω} A_{0j} \right) &∧& \displaystyle \left( \bigvee_{j<ω} A_{1j} \right) &\displaystyle = \left( A_{00}∧ \bigvee_{j<ω} A_{1j} \right) &∨& \displaystyle\left( A_{01}∧ \bigvee_{j<ω} A_{1j} \right) &∨&\cdots \end{array}
「基数」だったり「集合」だったり
この辺りの知識が必要なので、
分かるようになったら見返してみてください。
量化子 Quantifier
|| 量を表す言い回し
なにかの「量を指定する言い回し」
これを「量化子」と呼ぶことがあります。
具体的には、
「あれが少なくとも1つある」の「少なくとも～ある」とか
「全てのものには意味がある」の「全て～である」とか
「ほとんどいけるって」の「ほとんど～」とか
「何個かちょうだい」の「何個～」とか
こういう感じのやつが
「量を指定する言い回し」ってやつですね。
基本量化子
|| 真偽が確定する量についての言い回し
「自然言語」の範囲だと↑みたいに色々ありますが、
「数学の範囲」では、これは主に2つに絞られます。
\begin{array}{llllll} \displaystyle \forall x & A(x) \\ \\ \exists x &P(x) \end{array}
「全称化 \forall \,\, \mathrm{All} 」と「存在 \exists 」ってやつがそうなんですけど、
まあこれだけ言われてもなんのことやらって感じですよね。
というわけで説明してみようと思うんですが、
そのために、とりあえず記号の設定をしておきます。
なんらかの条件（命題）を「 A （～は趣味であるとか）」
その条件を満たすものを「 x （読書とか）」
よく見る慣例から、
「主張・文」の構成のために、こんな感じにしておきます。
全称量化 \mathrm{All,Any}
|| ある範囲のものは全部そうだよ、という宣言
「全ての～は～である」みたいな「量化子」を
数学では『全称量化』なんて呼んだりします。
\begin{array}{lllll} \displaystyle ∀x&A \\ \\ ∀x&A(x) \\ \\ ∀x&(A) \\ \\ ∀x&[A(x)] \end{array}
記号ではこんな感じに書かれることが多いですね。
最初は意味わかんないと思いますが、
慣れるとそんな難しくないです。
というのも、これの意味は
「 全ての x は、条件（命題） A を満たします」とか
「 全ての x は A （命題）という条件を満たす」とか
こんな感じの言い回しを「省略」してるだけなので、
別にそう難しいことを言ってるわけじゃないんですよ。
よく見る形式的な言い回しで
「全ての x に対して、 A が成立する」とか
「全ての x について、 x は P である」とか
こういう言い回しだと難しく感じるかもしれませんが、
基本は「全ての x は A だよ」っていう
ただそれだけのことを主張してるだけなので、
いやほんと、難しく考えないでください。
存在量化 \mathrm{Exist}
|| 条件を満たすやつが存在するよ、という宣言
「～な～が少なくとも１つはあるよ」みたいな量化子を、
『存在量化子』なんて呼ぶことがあります。
\begin{array}{lllll} \displaystyle ∃x&A \\ \\ ∃x&A(x) \\ \\ ∃x&(A) \\ \\ ∃x&[A(x)] \end{array}
書かれ方はこんな感じ。
全称量化もそうですが、どれを選ぶかは好みです。
（自分は一番下のが好きです。紛れが無いんで）
意味はそのまま
「条件 A を満たす x が存在しますよ」とか
「条件 A に合う x はある」とか
意訳するとこんな感じで、
まあ、全称量化と感覚はほぼ同じ。
特に難しくはないと思います。
形式的には
「 A を満たす x は存在する 」とか
「 A が成り立つ x が存在する」とか
こんな風な言い回しが採用されてますが、
ぶっちゃけ意訳もこれもそう大した差は無いので、
分かりやすい意味で覚えてればだいたいOK
なんにしてもそうですが、
難しく考えないでください。
より詳しくは「量化子」の別記事にて行います。
興味があれば参考にどうぞ。