自由変数と束縛変数(free and bound variables)とは、論理式の中の変数の出現が、同じ変数についての量化記号の作用域に入らないか入るかによる区別であり、自由変数は外から値を受け取る入力、束縛変数は作用域の中だけで動く場所取りにあたる。論理式の真偽は自由変数の値だけで決まり、束縛変数は作用域に現れない新しい名前に付け替えても意味が変わらない。項の代入は、項の変数が量化記号に捕まらない(代入可能な)ときに意味を保ち、付け替えによってこの捕獲はいつでも避けられる。和の添字、積分変数、内包記法の変数も同じしくみである。
和 $\sum_{k=1}^{n}k^2$ の値は $n$ によって変わるが、$k$ によって変わることはない。$k$ を $j$ に書き換えても同じ和である。式の中の文字には、外から値を受け取る文字と、式の中だけで動く文字の 2 種類がある。論理式 $\exists y\,(x< y)$ でも同じで、真偽は $x$ の値で決まり、$y$ の名前を $z$ に替えても意味は変わらない。前者を自由変数(free variable)、後者を束縛変数(bound variable)という。
この区別は、論理式の組み立てに沿って正確に定義できる。区別が本当に必要になるのは代入のときである。束縛変数と同じ名前の変数を含む項を不用意に代入すると、その変数が量化記号に捕まって意味が変わってしまう。この記事では、自由変数と束縛変数を定義し、代入が意味を保つ条件を調べ、束縛変数の名前を付け替えても意味が変わらないこと、付け替えによって捕獲がいつでも避けられることを示す。
一階言語 $L$ を固定する。項と論理式は 論理式 の記事の定義による。項は変数と定数記号から関数記号で作り、論理式は原子論理式 $t_1=t_2$、$R(t_1,\dots,t_n)$ から $\lnot$、2 項結合子 $\ast\in\{\land,\lor,\to\}$、量化記号で作る。項 $t$ に現れる変数の集合を $\operatorname{var}(t)$ と書く。以下 $Q$ は $\forall$ か $\exists$ を表す。論理式の組み立て方はただ 1 通りに読めるので、組み立てに沿った再帰で定義をしてよい。
論理式 $\varphi$ の組み立ての途中に $Qx\,\psi$ という部分論理式が現れるとき、その $\psi$ の部分を量化記号 $Qx$ の作用域(scope)という。
論理式 $\varphi$ の中の変数 $x$ の 1 つの出現が、$\varphi$ の部分論理式 $\forall x\,\psi$ または $\exists x\,\psi$ の中にあるとき(量化記号の直後の $x$ も含む)、その出現は束縛されているという。そうでない出現は自由であるという。
$\varphi$ に自由な出現をもつ変数を $\varphi$ の自由変数、束縛された出現をもつ変数を $\varphi$ の束縛変数という。それぞれの全体を $\operatorname{FV}(\varphi)$、$\operatorname{BV}(\varphi)$ と書く。$\operatorname{FV}(\varphi)=\emptyset$ である論理式を文(sentence)という。
束縛された出現を含む $Qx\,\psi$ が入れ子になっているときは、いちばん内側の $Qx$ がその出現を束縛しているという。$\operatorname{FV}(\varphi)\subset\{x_1,\dots,x_n\}$ であることを明示して $\varphi(x_1,\dots,x_n)$ と書くことが多い。
自由変数・束縛変数は「変数の性質」ではなく「論理式の中の出現の性質」から定まる。したがって、同じ変数が 1 つの論理式の自由変数でも束縛変数でもありうる(ex-fbv-both)。
$\operatorname{FV}$ と $\operatorname{BV}$ は次の再帰で計算できる。
| $\varphi$ | $\operatorname{FV}(\varphi)$ | $\operatorname{BV}(\varphi)$ |
|---|---|---|
| $t_1=t_2$ | $\operatorname{var}(t_1)\cup\operatorname{var}(t_2)$ | $\emptyset$ |
| $R(t_1,\dots,t_n)$ | $\bigcup_i\operatorname{var}(t_i)$ | $\emptyset$ |
| $\lnot\psi$ | $\operatorname{FV}(\psi)$ | $\operatorname{BV}(\psi)$ |
| $(\psi\ast\chi)$ | $\operatorname{FV}(\psi)\cup\operatorname{FV}(\chi)$ | $\operatorname{BV}(\psi)\cup\operatorname{BV}(\chi)$ |
| $Qy\,\psi$ | $\operatorname{FV}(\psi)\setminus\{y\}$ | $\operatorname{BV}(\psi)\cup\{y\}$ |
要点:量化記号で始まらない論理式では、各出現の自由・束縛の別は成分の中での別と同じであり、$Qy\,\psi$ では $y$ の出現だけがすべて束縛に変わる。
原子論理式には量化記号がないので、どの出現も自由である。
$\lnot\psi$ と $(\psi\ast\chi)$ の部分論理式 $Qx\,\theta$ は、全体が量化記号で始まらないので、$\psi$ か $\chi$ の部分論理式である。よって各出現の自由・束縛の別は成分の中での別と同じである。
$\varphi=Qy\,\psi$ とする。$y$ の出現は量化記号の直後のものも含めてすべて $\varphi$ 全体の中にあるので束縛されている。とくに $y\in\operatorname{BV}(\varphi)$ で $y\notin\operatorname{FV}(\varphi)$ である。$y$ と異なる変数 $x$ については、$Qx\,\theta$ の形の部分論理式は全体ではなく $\psi$ の部分論理式なので、$x$ の各出現の別は $\psi$ の中での別と同じである。$\square$
束縛変数は「場所取り」である。$\forall x\,(\cdots x\cdots)$ の $x$ は、作用域の中の決まった場所を「ここに値を次々と入れて確かめる」と指しているだけで、外から見える値をもたない。一方、自由変数は論理式の入力である。自由変数が $n$ 個の論理式は $n$ 個の値を受け取って真偽を返し、量化記号を 1 つ付けるごとに入力が 1 つ減る。入力のない論理式が文で、構造を決めると真偽が定まる。
順序の言語で $\varphi=(\exists y\,(x< y)\land\forall x\,(y< x))$ とする。$x$ の 1 つ目の出現($x< y$ の中)は自由で、$\forall x$ の直後と $y< x$ の中の出現は束縛されている。$y$ の $\exists y$ の直後と $x< y$ の中の出現は束縛され、$y< x$ の中の出現は自由である。prop-fbv-recursion で計算しても
$$
\operatorname{FV}(\varphi)=(\{x,y\}\setminus\{y\})\cup(\{x,y\}\setminus\{x\})=\{x,y\},\qquad\operatorname{BV}(\varphi)=\{x,y\}
$$
である。$\forall x\,\forall y\,\varphi$ は文である。
量化記号のほかにも、変数を束縛する記法は多い。どれも束縛された文字の名前を(ほかの文字と重ならないように)替えても意味が変わらない。
| 記法 | 束縛される文字 | 自由な文字 | 作用域 |
|---|---|---|---|
| $\exists y\in\mathbb R,\ y^2=x$ | $y$ | $x$ | $y^2=x$ |
| $\{x\in\mathbb R\mid x>a\}$ | $x$ | $a$ | $x>a$ |
| $\sum_{k=1}^{n}a^k$ | $k$ | $n,a$ | $a^k$ |
| $\int_0^{x}f(t)\,dt$ | $t$ | $x,f$ | $f(t)$ |
| $\lim_{h\to0}\frac{f(x+h)-f(x)}{h}$ | $h$ | $x,f$ | 分数の全体 |
| $\max_{0\le y\le1}xy$ | $y$ | $x$ | $xy$ |
| $\lambda y.\,x+y$ | $y$ | $x$ | $x+y$ |
積分の上端の $x$ と積分変数 $t$ は別の役なので、$\int_0^xf(x)\,dx$ のように同じ文字で書くと、1 つの文字が自由と束縛の 2 つの役を同時に担い、読み取りにくくなる。
$x>-1$ について
$$
\int_0^1t^x\,dt=\frac{1}{x+1}
$$
である。左辺の $t$ は束縛されていて、右辺に $t$ は残らない。残るのは自由変数 $x$ だけである。$\exists y\,(y\cdot y=x)$ を実数体で読むと $x\ge0$ という $x$ についての条件になるのも同じ現象である。
この節の項の記号は $u$ とする。論理式 の記事の代入 $\varphi[s/x]$ の $s$ にあたるが、一階述語論理 の記事では $s$ が割り当てを表すので、それと区別する。
項 $t$ の中の $x$ をすべて $u$ に置き換えた項を $t[u/x]$ と書く。論理式 $\varphi$ の自由な出現の $x$ だけを $u$ に置き換えた論理式 $\varphi[u/x]$ を、次の再帰で定める。原子論理式では各項の $t_i$ を $t_i[u/x]$ に替え、$\lnot$ と $\ast$ では成分ごとに代入し、量化記号では
$$
(Qy\,\psi)[u/x]=\begin{cases}Qy\,\psi&(y=x),\\Qy\,(\psi[u/x])&(y\ne x)\end{cases}
$$
とする。
$u$ が $\varphi$ の $x$ に代入可能であることを次の再帰で定める。原子論理式ではいつも代入可能とする。$\lnot\psi$ ではそれが $\psi$ で代入可能であること、$(\psi\ast\chi)$ では $\psi$ と $\chi$ の両方で代入可能であることとする。$Qy\,\psi$ では、$x\notin\operatorname{FV}(Qy\,\psi)$ であるか、または「$y\notin\operatorname{var}(u)$ かつ $u$ が $\psi$ の $x$ に代入可能」であることとする。
1:原子論理式では量化記号がないのでどちらも成り立つ。$\lnot$ と $\ast$ では成分に帰着する。$\varphi=Qy\,\psi$ とする。$x\notin\operatorname{FV}(\varphi)$ なら自由な出現がないのでどちらも成り立つ。$x\in\operatorname{FV}(\varphi)$ なら $y\ne x$ であり、$x$ の $\varphi$ での自由な出現は $\psi$ での自由な出現と同じで、1 つ以上あり、どれも $Qy$ の作用域に入っている。よって読み替えた条件は「$y\notin\operatorname{var}(u)$ かつ $\psi$ で同じ条件が成り立つ」と同じであり、帰納法の仮定により再帰の定義と一致する。
2:1 から直ちに従う。$\square$
$\varphi=\exists y\,\lnot(x=y)$ は「$x$ と異なる元がある」を表す。$y$ は $\varphi$ の $x$ に代入可能でない。実際に置き換えた $\varphi[y/x]=\exists y\,\lnot(y=y)$ は論理式ではあるが、どの構造でも偽であり、$\varphi$ の $x$ に $y$ の値を入れた内容(台集合が 2 元以上なら真)と違う。代入可能性を外すと、「$\varphi[u/x]$ は $x$ に $u$ の値を入れた $\varphi$ と同じ意味をもつ」という含意が成り立たない。
同じことは記法でも起きる。$F(x)=\int_0^1xt\,dt=x/2$ の $x$ に文字 $t$ を形だけ入れると $\int_0^1t\cdot t\,dt=1/3$ となり、$F(t)=t/2$ と違う。$\sum_{k=1}^{3}(k+n)=6+3n$ の $n$ に $k$ を形だけ入れると $\sum_{k=1}^{3}2k=12$ となり、$6+3k$ と違う。どちらも、入れた文字が積分や和の束縛変数に捕まっている。
$x$ を変数、$u$ を項、$\varphi$ を論理式とする。
項 $t$ については、$x\notin\operatorname{var}(t)$ なら $t[u/x]=t$、$x\in\operatorname{var}(t)$ なら $\operatorname{var}(t[u/x])=(\operatorname{var}(t)\setminus\{x\})\cup\operatorname{var}(u)$ である。項の組み立てに沿って確かめられる。原子論理式と $\lnot$・$\ast$ の場合は、成分についての式の和集合をとればよい($x$ を含まない成分では 1 を使う)。
$\varphi=Qy\,\psi$ とする。
1:$y=x$ なら定義により $\varphi[u/x]=\varphi$ である。$y\ne x$ なら $x\notin\operatorname{FV}(\psi)$ なので、帰納法の仮定により $\psi[u/x]=\psi$ であり、$\varphi[u/x]=\varphi$ である。
2:$x\in\operatorname{FV}(\psi)\setminus\{y\}$ なので $y\ne x$ であり、代入可能性の定義により $y\notin\operatorname{var}(u)$ かつ $u$ は $\psi$ の $x$ に代入可能である。帰納法の仮定により
$$
\operatorname{FV}(\varphi[u/x])=\operatorname{FV}(\psi[u/x])\setminus\{y\}=\bigl((\operatorname{FV}(\psi)\setminus\{x\})\cup\operatorname{var}(u)\bigr)\setminus\{y\}
$$
であり、$y\notin\operatorname{var}(u)$ なので右辺は $(\operatorname{FV}(\psi)\setminus\{x,y\})\cup\operatorname{var}(u)=(\operatorname{FV}(\varphi)\setminus\{x\})\cup\operatorname{var}(u)$ に等しい。$\square$
代入可能であれば、代入の結果は変数の値を項の値に入れ替えたものと同じ意味をもつ。これが 一階述語論理 の記事の補題「代入補題」である。
論理式の中の部分論理式 $Qy\,\psi$ を $Qz\,(\psi[z/y])$ に置き換える操作を束縛変数の付け替えという。ただし $z$ は $\psi$ に(自由にも束縛されても)現れない変数とする。付け替えとその逆を有限回($0$ 回でもよい)行って $\varphi$ から $\varphi'$ が得られるとき、$\varphi$ と $\varphi'$ は α 同値(alpha-equivalent)であるといい、$\varphi\equiv_\alpha\varphi'$ と書く。
逆の操作も許すのは、付け替えの逆が付け替えになるとは限らないからである。$\forall y\,(\exists y\,P(y)\land P(y))$ を $z$ に付け替えると $\forall z\,(\exists y\,P(y)\land P(z))$ になるが、後者から前者への書き換えは「$y$ が作用域に現れない」という条件を満たさない。
$\forall x\,\exists y\,(x< y)$ の内側を $v$、外側を $u$ に付け替えると $\forall u\,\exists v\,(u< v)$ になる。ここから同様に $\forall y\,\exists x\,(y< x)$ が得られるので、$\forall x\,\exists y\,(x< y)\equiv_\alpha\forall y\,\exists x\,(y< x)$ である。一方、$\forall x\,\exists y\,(y< x)$ はこれらと α 同値でない。$(\mathbb N,<)$ で前者は真、後者は偽であり、これは次の定理の 2 に反するからである。
$\varphi\equiv_\alpha\varphi'$ ならば次が成り立つ。
付け替え 1 回について示せばよい。逆の操作も同じ結論を与える(どちらの結論も対称な形をしている)ので、有限回の繰り返しについても従う。
まず部分論理式そのものを比べる。$z$ は $\psi$ に現れないので、$\operatorname{BV}(\psi)\cap\{z\}=\emptyset$ であり、prop-fbv-free-for の 2 により $z$ は $\psi$ の $y$ に代入可能である。
1:$y\in\operatorname{FV}(\psi)$ なら、prop-fbv-substitution-fv の 2 により
$$
\operatorname{FV}(Qz\,(\psi[z/y]))=\bigl((\operatorname{FV}(\psi)\setminus\{y\})\cup\{z\}\bigr)\setminus\{z\}=\operatorname{FV}(\psi)\setminus\{y\}=\operatorname{FV}(Qy\,\psi)
$$
である。$z\notin\operatorname{FV}(\psi)$ を使った。$y\notin\operatorname{FV}(\psi)$ なら、prop-fbv-substitution-fv の 1 により $\psi[z/y]=\psi$ なので、$\operatorname{FV}(Qz\,\psi)=\operatorname{FV}(\psi)=\operatorname{FV}(Qy\,\psi)$ である。
2:$Qy\,\psi$ と $Qz\,(\psi[z/y])$ の論理的同値は、一階述語論理 の記事の系「束縛変数の付け替え」である($z=y$ なら両者は同じ論理式である)。
最後に、部分論理式を置き換えた全体を比べる。$\operatorname{FV}$ は prop-fbv-recursion により成分の $\operatorname{FV}$ から決まり、充足関係は成分の充足から再帰で決まる。よって、ある部分論理式を、自由変数の同じ論理的に同値な論理式に置き換えても、全体の $\operatorname{FV}$ は変わらず、全体は論理的に同値のままである。論理式の組み立てに沿った帰納法で確かめられる。$\square$
変数は無限個あるので、付け替えに使う新しい変数はいつでも見つかる。このことから捕獲は必ず避けられる。
論理式 $\varphi$ と変数の有限集合 $X$ に対し、$\varphi\equiv_\alpha\varphi'$ かつ $\operatorname{BV}(\varphi')\cap X=\emptyset$ となる論理式 $\varphi'$ がある。とくに、任意の項 $u$ と変数 $x$ について、$\varphi$ と α 同値な論理式で、$u$ がその $x$ に代入可能なものがある。
$\varphi$ の組み立てに関する帰納法で示す。原子論理式では $\varphi'=\varphi$ とすればよい。$\lnot$ と $\ast$ では成分ごとに $\varphi'$ を作って組み立て直す。
$\varphi=Qy\,\psi$ とする。帰納法の仮定で、$\psi\equiv_\alpha\psi'$、$\operatorname{BV}(\psi')\cap X=\emptyset$ となる $\psi'$ をとる。$\psi'$ に現れず $X$ にも属さない変数 $z$ をとる。$\psi'$ に現れる変数も $X$ も有限個なので、そのような $z$ がある。$\varphi'=Qz\,(\psi'[z/y])$ とおく。$\psi$ の内部の付け替えと最後の付け替えで $\varphi\equiv_\alpha\varphi'$ である。変数を変数に置き換える代入は量化記号を変えないので $\operatorname{BV}(\psi'[z/y])=\operatorname{BV}(\psi')$ であり、$\operatorname{BV}(\varphi')=\operatorname{BV}(\psi')\cup\{z\}$ は $X$ と交わらない。
後半は $X=\operatorname{var}(u)$ として prop-fbv-free-for の 2 を使う。$\square$
$\varphi\equiv_\alpha\varphi'$ で、項 $u$ が $\varphi'$ の $x$ に代入可能であるとする。構造 $\mathcal M$、割り当て $s$ について $b:=u^{\mathcal M}[s]$ とおくと、
$$
\mathcal M\models\varphi'[u/x][s]\iff\mathcal M\models\varphi[s_x^b]
$$
である。したがって、このような $\varphi'$ をどう選んでも、$\varphi'[u/x]$ は互いに論理的に同値である。
一階述語論理 の記事の補題「代入補題」により $\mathcal M\models\varphi'[u/x][s]\iff\mathcal M\models\varphi'[s_x^b]$ である。thm-fbv-alpha-invariance の 2 を割り当て $s_x^b$ に使えば、右辺は $\mathcal M\models\varphi[s_x^b]$ と同値である。後半は、最後の式が $\varphi'$ の選び方によらないことから従う。$\square$
このため実際の数学では、「代入の前に束縛変数を新しい文字に替えておく」と了解して、代入可能性をいちいち断らない。ex-fbv-capture の $\varphi$ なら、$\exists z\,\lnot(x=z)$ と付け替えてから $x$ に $y$ を代入し、正しい結果 $\exists z\,\lnot(y=z)$ を得る。α 同値な論理式は、どの出現がどの量化記号に束縛されているかの対応が同じで、変数の名前だけが違うものと考えてよい。
論理式の真偽は自由変数に割り当てた値だけで決まる(一階述語論理 の記事の補題「一致補題」)。とくに文の真偽は割り当てによらない(同記事の系「文の真偽は割り当てによらない」)。自由変数をもつ論理式の「成り立つ」には、次の読み方がある。
$\operatorname{FV}(\varphi)\subset\{x_1,\dots,x_n\}$ とする。構造 $\mathcal M$ について、すべての割り当て $s$ で $\mathcal M\models\varphi[s]$ が成り立つことと、文 $\forall x_1\cdots\forall x_n\,\varphi$ が $\mathcal M$ で真であることは同値である。
$n=0$ なら $\varphi$ は文であり、文の真偽は割り当てによらない。$n\ge1$ のとき $\theta=\forall x_n\,\varphi$ とおくと $\operatorname{FV}(\theta)\subset\{x_1,\dots,x_{n-1}\}$ である。割り当て $s$ と $a\in M$ に対し $s_{x_n}^a$ もまた割り当てであり、すべての割り当てはこの形に書ける。よって「すべての $s$ で $\mathcal M\models\varphi[s]$」は、充足の定義により「すべての $s$ で $\mathcal M\models\theta[s]$」と同値である。あとは帰納法の仮定を $\theta$ に使う。$\square$
一方、$\exists$ の場合は入力を射影で消すことにあたる。$\varphi(x_1,\dots,x_n)$ が構造 $\mathcal M$ で定める集合を、$x_i$ に $a_i$ を割り当てて充足する $(a_1,\dots,a_n)\in M^n$ の全体とすると、$\exists x_n\,\varphi$ の定める集合は、この集合の最後の座標を忘れる射影の像である(定義可能集合)。
$(\mathbb N,<)$ で $\varphi(x)=\exists y\,(y< x)$ は、$x$ の値が $0$ なら偽、それ以外なら真である。したがって prop-fbv-closure により、文 $\forall x\,\varphi$ も文 $\forall x\,\lnot\varphi$ も偽である。自由変数をもつ論理式には、値によって真偽が分かれる場合がある。
「$P(x)$ を仮定すると $P(x)$ が言えるから、$x$ は任意なので $\forall x\,P(x)$」は正しくない。仮定の中の $x$ は 1 つの値に固定された自由変数であって、任意ではない。台集合 $\{0,1\}$、$P=\{0\}$、$s(x)=0$ で $P(x)$ は真、$\forall x\,P(x)$ は偽である。一階論理の証明体系 の記事の定理「汎化定理」が「$x$ が前提に自由に現れない」ことを条件にするのはこのためである。満たす性質は「結論が仮定から導出される」、成り立たない含意は「導出できるなら全称化できる」である。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| prop-fbv-substitution-fv の 2 の「代入可能」 | $\varphi=\forall y\,(x=y)$、$u=y$ | 代入後の自由変数の式 |
| prop-fbv-substitution-fv の 2 の「$x\in\operatorname{FV}(\varphi)$」 | $\varphi=(y=y)$、$u=z$ | 代入後の自由変数の式 |
| def-fbv-alpha の「$z$ が $\psi$ に自由に現れない」 | $\exists y\,(x< y)$ の $y$ を $x$ に替える | thm-fbv-alpha-invariance の 1・2 |
| def-fbv-alpha の「$z$ が $\psi$ で束縛されない」 | $\forall y\,\exists z\,(y< z)$ の $y$ を $z$ に替える | thm-fbv-alpha-invariance の 2 |
| def-fbv-substitution の「自由な出現だけを置き換える」 | $\forall x\,(x=x)$ のすべての $x$ を定数記号 $c$ に替える | 代入の結果が論理式であること |
1 行目:$\varphi[y/x]=\forall y\,(y=y)$ は文だが、右辺は $(\{x\}\setminus\{x\})\cup\{y\}=\{y\}$ である。
2 行目:$\varphi[z/x]=\varphi$ の自由変数は $\{y\}$ だが、右辺は $\{y\}\cup\{z\}=\{y,z\}$ である。
3 行目:$\psi=(x< y)$ に $x$ は自由に現れ、束縛されてはいない。$\psi[x/y]=(x< x)$ で、得られる $\exists x\,(x< x)$ は文である。もとの自由変数 $\{x\}$ は保たれない。$(\mathbb N,<)$ で $x$ の値を $0$ とするともとの論理式は真、得られる文は偽である。
4 行目:$\psi=\exists z\,(y< z)$ に $z$ は自由に現れない($z$ の出現はすべて束縛されている)。$\psi[z/y]=\exists z\,(z< z)$ で、$(\mathbb N,<)$ でもとの文は真、$\forall z\,\exists z\,(z< z)$ は偽である。$z$ は $\psi$ の $y$ に代入可能でなく、捕獲が起きている。
5 行目:$\forall c\,(c=c)$ は、量化記号の直後が変数でないので論理式でない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する