述語

定義

命題とは、真か偽かが定まる文である。「7 は素数である」は真、「8 は素数である」は偽。

述語にはその性質がない。「$x$x は素数である」は真でも偽でもなく、$x$x に依存する。穴のあいた文であり、穴が埋まってはじめて真理値を返す。

自由変数と束縛変数

変数が自由なままである限り、文に真理値はない。それを閉じる操作は二つある。

量化された変数を束縛変数という。自由変数をもたない文は命題であり、真理値をただ一つもつ。

量化子の順序

種類の異なる二つの量化子は交換できない。整数上で、$S(x, y)$S(x,y) を「$y$y は $x$x より大きい」とすると：

$\forall x\, \exists y,\ S(x, y) \quad \text{は真}$∀x∃y, S(x,y)は真

$\exists y\, \forall x,\ S(x, y) \quad \text{は偽}$∃y∀x, S(x,y)は偽

前者は、どの整数に対してもより大きい整数が存在する、と述べる。$y$y は $x$x に依存してよい。後者は、すべてより大きい整数が存在する、と述べる。最大の整数であり、そんなものはない。

同じ記号を逆順に置いただけで、一方は真、他方は偽になる。極限の定義が交換不能なのも同じ仕組みによる。

量化された文の否定

否定は量化子を入れ替えながら通り抜ける。

$\neg\,\forall x,\ P(x) \iff \exists x,\ \neg P(x)$¬∀x, P(x)⟺∃x, ¬P(x)

$\neg\,\exists x,\ P(x) \iff \forall x,\ \neg P(x)$¬∃x, P(x)⟺∀x, ¬P(x)

「すべて素数である」の否定は「どれも素数でない」ではなく、「素数でないものが存在する」である。全称は反例ひとつで覆るが、存在を覆すには領域全体を調べ尽くさねばならない。

領域は文の一部である

述語は、宣言された領域のうえでしか判定できない。「$\exists x,\ x^2 = 2$∃x, x2=2」は $\mathbb{Q}$Q 上で偽、$\mathbb{R}$R 上で真である。式は変わっておらず、変わったのは全体集合のほうである。

領域を省くことは、文を未確定のまま放置することにあたる。意味が曖昧なのではなく、真理値をもたないのである。

まとめ

述語は、変数が固定されるか、宣言された領域のうえで量化されたとき、命題になる。