20201209『数理論理学』輪講のノート

●項と論理式の違いについて：
例えば「(2次式)=0」という形に整理できる方程式を「2次方程式」と呼んだと思いますが、「2次式」は項の例、「2次方程式」は論理式の例です。これらはどちらも\(x\)などで書かれる変項が含まれていますが、2次式（項）に現れる変項に値を代入すると、そのつど計算された値が得られるのに対し、2次方程式（論理式）の変項に値を代入すると、そのつど「成り立つ・成り立たない」つまり真偽が定まります。「項」は「モノっぽいもの」、「論理式」は「主張っぽいもの」と言ってもよいかもしれません。

●自由変項／束縛変項について：
論理式に現れる変項には自由／束縛の両方がありえますが、項に現れる変項は（定義5.17を見れば分かるとおり）すべて自由変項です。あるいは「自由・束縛の区別は論理式における出現にのみ意味をなすのであり、項における出現に自由も束縛もない」と考えてもかまいません。ただし、項に束縛出現を考える体系もあるそうです。

そもそも自由／束縛の区別は、変項自体というより「その出現の、全体における位置付け」についての分類であり、同じ記号で書かれた変項でも出現箇所によって異なったり、同じ出現でも「何を全体と見るか」で変わってきたりします。例えば論理式\(\forall x[F(f(x))\vee \forall x(G(g(x)))]\)において、ふたつの\(x\)はともに束縛出現していますが、頭の\(\forall x\)の中身である\(F(f(x))\vee \forall x(G(g(x)))\)だけを取り出して考えれば、ひとつ目は自由変項、ふたつ目は束縛変項です。さらに\(F(f(x))\)や、\(\forall x(G(g(x)))\)の中身の\(G(g(x))\)においては\(x\)は自由変項です。また項\(f(x)\)や項\(g(x)\)、あるいは\(x\)自身（2箇所）も項ですが、これらにおいて\(x\)は自由変項です。このように論理式や項を分解していってもそのつど自由／束縛の別をきちんと定めていることが、定義5.16~5.19のような再帰的定義のよりどころとなっています。

●「項の代入」に関しては、まず解説5.28を読み、練習5.27を解いたうえで定義5.22~解説5.26を読むのが分かりやすいと思います。

●定義5.25の構文的同値関係（いわゆる\(\alpha\)同値性）は、これも高校数学で言えば「2次方程式\(ax^2+bx+c=0\)が実数解を持つ」という例が分かりやすいです。これが\(ay^2+by+c=0\)になっていようと\(a\heartsuit^2+b\heartsuit+c=0\)になっていようと、実数解を持つ条件は\(b^2-4ac\geq0\)であることに変わりはなく、ここに\(x\)や\(y\)や\(\heartsuit\)は登場しません。すなわち\[\begin{eqnarray}&&\exists x\in\mathbb{R}(ax^2+bx+c=0)\\&\equiv&\exists y\in\mathbb{R}(ay^2+by+c=0)\\&\equiv&\exists \heartsuit\in\mathbb{R}(a\heartsuit^2+b\heartsuit+c=0)\\&\equiv&\cdots\end{eqnarray}\]が成り立っています。

●解説5.24の「代入を行うことができない」という箇所は、単に「定義に書かれていないから代入できない」という意味ではなく、実際に無理やり代入しようとすると不都合が起こることに注意が必要です。例えば

係数が\(a,b,c\)の2次方程式が実数解を持つ条件が\(b^2-4ac\geq0\)だったのであれば、係数が\(v,w,x\)なら\(w^2-4vx\geq0\)になるはずだ。

などと議論したいところです。これは上の論理式の\(a,b,c\)に\(v,w,x\)を代入することに相当しますが、たまたまその論理式が\(\exists x\in\mathbb{R}(ax^2+bx+c=0)\)と書かれていたら、\(x\)を\(c\)に代入する際に束縛が発生し、意図したとおりの論理式が得られません。ところが、\(x\)を\(y\)に貼り替えただけの\(\exists y\in\mathbb{R}(ay^2+by+c=0)\)であれば問題は起こらない。このような事情があるので、もともと束縛変数は何でもよかったのだから、衝突が発生する場合には受け側の束縛変数を前もって貼り替えておこう、というのが解説5.26の主旨です。