述語論理、量子化とは:全称記号(∀)と存在記号(∃)、数学における例と否定

どうも、木村(@kimu3_slime)です。

前回、記号論理学における命題論理とは何か、\(\lor ,\land\)などの論理的接続詞を紹介しました

今回は、記号論理におけるもう一つの重大な分野、述語論理について、量子化、全称記号、存在記号、その数学における例、否定の扱いを解説します。

 

述語論理とは

前回考えた命題は、それ自身で真偽が定まっている文のことでした。例えば

\(9\)は偶数である。

は偽の命題です。このように主語が1つの命題は、単称命題(singular proposition)と呼ばれます。

しかし数学で考えたい命題は、単称命題に限りません。例えば、

\(4x\)は偶数である。

という文を考えたいですが、これは命題ではありません。ただし、\(x=2\)ならば真の命題で、\(x=3\)ならば偽の命題といったように、\(x\)の値を決めれば命題になります。

このように、文中の\(x\)の値を決めることで命題となる文を、(単純な)述語(simple predicate)と呼びます。述語は命題になりかけの文、プレ命題です。

また、\(x\)のように、特定の値を代入する変数を自由変数(free variable)または個体変数(individual variable)と呼びます。代入する数などの値、一般にもの(object)を表す記号は、個体定数(individual constant)と呼ばれます。

何が個体変数、個体定数とされるかは、文脈に依存します。例えば、変数として○や△を使うこともできますし、個体定数として\(a\)や「花」といった文字を代入することもあるでしょう。

○は黄色い。

 

そして述語の扱い方を学ぶのが、述語論理(predicate logic)という分野です。

自由変数\(x\)を含む述語は、記号\(A(x)\)といった記号で表されます。これは「\(x\)は\(A\)という性質を持つ」と読むことができ、\(A(x)\)は「\(x\)はどのような性質であるか」、まさに述語を表しているわけです。

例えば

\[2y =5\]

という文は、自由変数\(y\)を含む述語です。このように、等式「\(=\)を使って項をつないだ文」によって表される述語は、\(x\)についての方程式(equation)と呼ばれます。中学で方程式を最初に習うと思いますが、その明解な定義は述語論理にあります。

 

量化子、全称記号、存在記号

さて、述語からは次のようにして命題を作り出すことができます。

すべての\(x\)に対し、\(4x\)は偶数である。

\(2y =5\)を満たすような\(y\)が存在する。

これはそれぞれの述語に、「すべての~」や「~が存在する」を付け加えたことによって生じました。この述語から命題への変換を量化(quantification)と呼びます。

量化は、自由変数への値の代入ではないことに注意してください。特定の値を指定することなく、命題を作っています。

そして量化するための「すべての~」や「~が存在する」という用語を、量化子(quantifier)と呼び、\(\forall , \exists\)記号で表します。

\(\forall x , A(x)\)

\(\exists y , B(y)\)

\(\forall\)はforAllのAをひっくり返したもので全称量化子・全称記号(universal quantifier)、\(\exists\)はExistsのEをひっくり返したもので存在量化子・存在記号(existential quantifier)と呼ばれます。

こちらの記事でも触れました:集合論のはじまり、全称命題と存在命題、論理記号を知ろう

数学の教科書では、「任意の~」や「条件~を満たす~が取れる」、またはそうした文言すらかかれないが暗黙に、全称量化子や存在量化子を使った命題が述べられています。教科書の文章を、命題論理や述語論理の言葉によって補って、明解な文として読み解けるようになるのは、大学数学の最初のステップと言えるでしょう。

参考:大学数学の教科書の読み方、最初に「定義・命題・証明」を知ろう

 

全称命題\(\forall x , A(x)\)や存在命題\(\exists y , B(y)\)には、変数\(x\)が含まれますが、これは個体変数のように自由にその値を指定できるものではありません。

\(\forall x , A(x)\)を\(\forall y , A(y)\)と書こうが、その意味するところ(真偽)は同一です。つまりここでの\(x,y\)は、見かけ上の変数。このような変数は縛られた変数、束縛変数(bound variable)と呼ばれます。述語において自由変数だった変数は、量化子がついて命題化されると束縛変数になりますね。

全称命題や存在命題において、束縛変数の動く範囲を明示的に定めないと、命題の意味が変わってしまうことがあります。例えば、

\[(\exists x), x^2 =-1\]

という存在命題は、\(x\)が実数\(\mathbb{R}\)の範囲を動くなら偽で、\(x\)が複素数の範囲\(\mathbb{C}\)を動くなら真です。数学、特に集合論ではその範囲を明示します。

\[(\exists x \in \mathbb{R}), x^2 =-1\]

\[(\exists x \in \mathbb{C}), x^2 =-1\]

ここで変数が動きうる集合\(\mathbb{R},\mathbb{C}\)は、量化子の範囲変域(スコープ scope)と呼ばれています。

「今の議論では、この記号は自由変数なのか、束縛変数なのか? 束縛変数だとして、それはどんな値を取りうるのか?」を読み取るのは、数学の議論で非常に重要です。

 

全称命題、存在命題の数学における例、否定の扱い

述語、全称命題、存在命題に対しても、命題論理で扱ったような論理演算子が定義できます。

参考:記号論理、命題論理入門:覚えるべき論理記号(否定、かつ、または、ならば、同値)とは

特に、全称命題と存在命題は、互いに否定命題です。

\[\lnot((\exists x ),A(x) ) \Leftrightarrow (\forall x)(\lnot A(x))\]

この関係を用いれば、命題論理の体系に加えて\(\forall\)という記号さえ導入すれば、存在命題も書き表されることになりますね。

これまで述べてきた記号体系を用いて考える論理は、一階の述語論理(first-order predicate logic)と呼ばれます。「一階の」という部分は、個体の量化のみを許しているからです。命題論理は、量化を許さない論理という意味で、零階の述語論理という見方もできるでしょう。(二階の述語論理は、個体の量化だけでなく、個体の集合も量化の対象としています。高階になれば記述能力は上がりますが、その分、証明可能でない文が登場する可能性があります。)

現代のスタンダードな集合論の公理系であるZFC公理系は、一階の述語論理によって形式化されていて、その意味でも一階述語論理は数学の基礎言語と言えます。(とはいえ、「有限集合であること」「可算集合であること」といった命題は、一階述語論理の範囲では表現できないことが知られています)

 

数学においては、全称命題や存在命題は組み合わせて表れます。全称記号と存在記号の順序が変われば、それは別の命題です。

例えば、

\[(\forall x)(\exists y),\quad y =x^2\]

\[(\exists x)(\forall y),\quad y =x^2\]

という命題の真偽はどうでしょうか(変域は実数とします)。

前者は、与えられた\(x\)に対して\(y= x^2\)とおけば、真であることが示せます。

一方、後者は偽です。もし仮に、条件を満たす\(x\)が存在したとしましょう。それは\(x^2=0\)と\(x^2=1\)の両方を満たします。これは\(0=1\)という矛盾を導きます。

 

この組み合わせを用いる典型例は、微積分学における関数の連続性です。

実数値関数\(f\)が点\(a\in \mathbb{R}\)で連続であるとは、

\[(\forall \varepsilon >0 )( \exists \delta>0 )(\forall x \in \mathbb{R})( |x-a|<\delta \implies |f(x)-f(a)|<\varepsilon)\]

を満たすことです。ここでいう\(\forall \varepsilon >0\)は、\((\forall \varepsilon \in \mathbb{R}) \land \varepsilon >0\)の略記ですね。

さてこの命題の否定を取るのは、述語論理の良い例題です。一行ずつ進んでみていきましょう。

\[\lnot ((\forall \varepsilon >0 )( \exists \delta>0 )(\forall x \in \mathbb{R})( |x-a|<\delta \implies |f(x)-f(a)|<\varepsilon))\]

\[(\exists \varepsilon >0) \lnot ( (\exists \delta>0 )(\forall x \in \mathbb{R})( |x-a|<\delta \implies |f(x)-f(a)|<\varepsilon))\]

\[(\exists \varepsilon >0)  ( \forall \delta>0) \lnot ((\forall x \in \mathbb{R}) (|x-a|<\delta \implies |f(x)-f(a)|<\varepsilon))\]

\[(\exists \varepsilon >0)  ( \forall \delta>0) (\exists x \in \mathbb{R}) \lnot (|x-a|<\delta \implies |f(x)-f(a)|<\varepsilon)\]

\[(\exists \varepsilon >0)  ( \forall \delta>0) (\exists x \in \mathbb{R})  (|x-a|<\delta \land \lnot( |f(x)-f(a)|<\varepsilon)\]

\[(\exists \varepsilon >0)  ( \forall \delta>0) (\exists x \in \mathbb{R})  (|x-a|<\delta \land  |f(x)-f(a)|>\varepsilon)\]

全称命題・存在命題の否定、\(A(x)\implies B(x)\)の否定は覚えていましたか? 左から順に、少しずつ否定を適用していけば、間違えることはないはずです。

 

全称命題や存在命題は、書き下せるだけでなく、「それを示せ」と言われたら、示せるようになっておくのが大事です。ちょっと慣れが必要かもしれませんが。

\(f(x)\)を\(x<0\)で\(0\)、\(x\geq 0\)で\(1\)の値を取る実数値関数とします。このとき、\(f\)は\(x=0\)において連続ではありません。

\(\varepsilon =\frac{1}{2}\)とします。そして、任意の\(\delta >0\)に対し、\(x=\frac{\delta}{2}\)と定めましょう。これは\(|x-0|<\delta\)を満たし、かつ

\[|f(x)-f(0)|= |1-0| >\frac{1}{2} =\varepsilon\]

を満たします。よって、

\[(\exists \varepsilon >0)  ( \forall \delta>0) (\exists x \in \mathbb{R})  (|x-a|<\delta \land  |f(x)-f(a)|>\varepsilon)\]

を満たすので、\(f\)は\(0\)で不連続です。

不連続性の定義を

\[(\exists \varepsilon >0)  ( \forall \delta>0) P(\varepsilon, \delta)\]

と見れば、\(\varepsilon\)を束縛変数で、\(\varepsilon\)を\(\delta\)を使って指定してはいけません。一方で、さらにその内側に注目すると、

\[( \forall \delta>0) (\exists x \in \mathbb{R}) Q( \delta,x)\]

\(x\)の立場からすれば、\(\delta \)は自由変数です。\( (\exists x \in \mathbb{R}) Q( \delta,x)\)は\(\delta\)に応じて決まる命題なので、\(x\)は\(\delta\)に依存して決めることができます。

入れ子構造になっている命題では、どの変数がどの変数に依存して良く、あるいはダメなのか、それに注意することが大事です。

 

以上、述語を使った論理、述語を命題化する量子化、量子化の記号である全称記号と存在記号、その数学における使用例を紹介してきました。

複合的な命題で記号的に否定を取る操作は、慣れるまで難しいかもしれませんが、述語論理の扱いさえわかれば、数学文章の読解で困ることはそうそうなくなるでしょう。ぜひマスターしてください。

木村すらいむ(@kimu3_slime)でした。ではでは。

 

論理と集合から始める数学の基礎
日本評論社 (2018-02-26)
売り上げランキング: 12,368

 

Mathematical Logic (Undergraduate Texts in Mathematics)
H. D. Ebbinghaus
Springer (2012-12-12)
売り上げランキング: 179,586

 

Introduction to Logic (English Edition)
Routledge (2016-09-09)

 

入門!論理学 (中公新書)

入門!論理学 (中公新書)

posted with amazlet at 19.12.24
野矢 茂樹
中央公論新社
売り上げランキング: 10,468

こちらもおすすめ

「AならばB」のよくある誤解から学ぶ、論理学入門(対偶、逆、否定、真偽表)

記号論理、命題論理入門:覚えるべき論理記号(否定、かつ、または、ならば、同値)とは

集合論のはじまり、全称命題と存在命題、論理記号を知ろう

論理学の入門ロードマップ:大学数学に必要な論理学とは

「ゲーデルの不完全性定理」を誤解しないために、数学の歴史的流れを解説