述語

同義語：predicate命題関数propositional function真理集合

概要

前提知識: 論理と命題, 全称記号, 部分集合, 直積集合

「$x$ は偶数である」という文は、それだけでは真とも偽とも言えない。$x$ に $4$ を入れれば真の命題「$4$ は偶数である」になり、$7$ を入れれば偽の命題になる。「$x$ は $y$ を割り切る」も、$x$ と $y$ の両方に値を入れて初めて真偽が決まる。このように、変数を含み、変数に値を入れるごとに真偽が定まる文を述語という。数学の定義や定理は、ほとんどが述語に値を入れるか、述語を量化して作られている。「$f$ は連続である」は、述語「$\lvert x-a\rvert< \delta$ ならば $\lvert f(x)-f(a)\rvert< \varepsilon$」の変数 $\varepsilon,\delta,x,a$ を全称記号・存在記号で束縛した命題である。
述語には、それを満たす値の全体という集合（真理集合）が対応する。この対応で、述語の論理演算は集合演算に、量化は射影に、値の代入は逆像に移る。一方で、2 つの変数の間の関係、たとえば等号 $x=y$ は、無限集合の上では 1 変数の述語をいくつ組み合わせても表せない。また、述語はいつでも集合を定めるわけではなく、変数の動く範囲を集合として固定しておく必要がある。

定義

述語

$n$ を $0$ 以上の整数とし、$X_1,\dots,X_n$ を集合とする。変数 $x_1,\dots,x_n$ を含む文 $P(x_1,\dots,x_n)$ で、各 $(a_1,\dots,a_n)\in X_1\times\cdots\times X_n$ について、$x_i$ に $a_i$ を入れた文 $P(a_1,\dots,a_n)$ が真か偽のちょうど一方に定まる命題になるものを、$X_1\times\cdots\times X_n$ 上の $n$ 項述語（$n$-ary predicate）または 命題関数（propositional function）という。$X_1\times\cdots\times X_n$ を述語の 定義域（または変数の動く範囲）、$x_1,\dots,x_n$ をその 自由変数 という。
$1$ 項述語は元の性質を、$2$ 項以上の述語は元どうしの関係を表す。$0$ 項述語は自由変数をもたない文、すなわち論理と命題でいう命題である。

真理集合・外延的同値

$X:=X_1\times\cdots\times X_n$ 上の述語 $P$ に対し、
$$ T(P):=\{(a_1,\dots,a_n)\in X\mid P(a_1,\dots,a_n)\ \text{が真}\} $$
を $P$ の 真理集合（truth set）または外延（extension）という。$T(P)$ は $X$ の部分集合である。同じ定義域 $X$ 上の 2 つの述語 $P,Q$ について $T(P)=T(Q)$ であるとき、すなわち
$$ \forall(a_1,\dots,a_n)\in X\ \bigl(P(a_1,\dots,a_n)\leftrightarrow Q(a_1,\dots,a_n)\bigr) $$
が真であるとき、$P$ と $Q$ は $X$ 上で 外延的に同値 であるという。

述語 $P(x_1,\dots,x_n)$ から命題を作る方法は 2 つある。

値の代入：すべての変数に定義域の元を入れる。
量化：変数を $\forall$ や $\exists$ で束縛する（全称記号の記事の定義「全称記号・存在記号・一意存在記号」）。束縛された変数はもう自由変数ではなく、値を入れる対象ではなくなる。
一部の変数だけに値を入れたり、一部の変数だけを量化したりすると、残った変数についての述語が得られる。たとえば $\mathbb{Z}\times\mathbb{Z}$ 上の $2$ 項述語「$x=2y$」の $y$ を存在記号で束縛した「$\exists y\in\mathbb{Z}\ (x=2y)$」は、$\mathbb{Z}$ 上の $1$ 項述語「$x$ は偶数である」である。束縛変数と自由変数の区別と、束縛変数の名前を付け替えても意味が変わらないことは、全称記号の記事の節「束縛変数と自由変数」と、一階述語論理の記事の系「束縛変数の付け替え」にある。
述語は文であり、真理集合は集合である。この 2 つを区別しておくと、「意味の違う 2 つの述語が同じ真理集合をもつ」という状況が言い表せる。たとえば $\mathbb{R}$ 上の述語「$x^2+1=0$」と「$x\ne x$」は意味がまったく違うが、どちらも真理集合は空集合であり、$\mathbb{R}$ 上で外延的に同値である。一階述語論理では、述語を真理集合によってだけ区別し、意味の違いは扱わない（MBTZ25 第 30 章、pp. 258–260）。この記事でも、述語の性質を述べるときは真理集合だけを見る。
一階述語論理では、述語は記号（述語記号）として扱われ、その意味は構造によって与えられる（一階述語論理の記事の定義「構造」）。そこでは $n$ 項述語記号 $R$ の解釈は台集合の $n$ 乗の部分集合 $R^{\mathcal{M}}$ であり、これはこの記事の真理集合にあたる。この記事が扱うのは、記号の体系に入る前の、ふだんの数学で使う意味での述語である。

直感

述語は「空欄のある文」である。空欄に何を入れてよいかを決めているのが定義域で、空欄を埋めると真か偽かが決まる。真になるように埋める入れ方を全部集めたものが真理集合であり、述語を集合として見たものにあたる。$1$ 項述語は定義域の中の「部分」を、$2$ 項述語は定義域どうしの「対応のつき方」を切り出す。
同じ文でも、空欄に入れてよいものが変われば、真理集合も変わる。「$x^2=2$」は $\mathbb{Q}$ 上では真理集合が空集合だが、$\mathbb{R}$ 上では $\{\sqrt2,-\sqrt2\}$ である。述語を書くときは、変数の動く範囲を必ず決めておく。

例

数についての述語

$\mathbb{Z}$ 上の $1$ 項述語「$x$ は偶数である」の真理集合は $2\mathbb{Z}$ である。
正の整数全体を $\mathbb{Z}_{>0}$ と書く。$\mathbb{Z}_{>0}\times\mathbb{Z}_{>0}$ 上の $2$ 項述語「$x$ は $y$ を割り切る」の真理集合は、整除関係そのもの（$\{(a,b)\mid a\mid b\}$）である。
$\mathbb{R}\times\mathbb{R}$ 上の $2$ 項述語「$x^2+y^2=1$」の真理集合は単位円である。$y$ を存在記号で束縛した「$\exists y\in\mathbb{R}\ (x^2+y^2=1)$」は $\mathbb{R}$ 上の $1$ 項述語で、真理集合は区間 $[-1,1]$ である。
$\mathbb{R}$ 上の $1$ 項述語「$\forall y\in\mathbb{R}\ (xy=0)$」の真理集合は $\{0\}$、「$\exists y\in\mathbb{R}\ (xy=1)$」の真理集合は $\mathbb{R}\setminus\{0\}$ である。

定義域で変わる真理集合と外延的同値

述語「$x^2+1=0$」と「$x\ne x$」は、$\mathbb{R}$ 上ではどちらも真理集合が空集合で、外延的に同値である。ところが定義域を複素数全体 $\mathbb{C}$ に替えると、前者の真理集合は $\{i,-i\}$、後者は空集合のままであり、外延的に同値でない。外延的同値は定義域を決めて初めて意味をもつ関係である。
これに対し、論理式として同値な組み立て方をした述語、たとえば「$\lnot(x>0\land x< 1)$」と「$x\le0\lor x\ge1$」は、実数の大小が全順序であることだけを使って変形できるので、$\mathbb{R}$ のどの部分集合を定義域にしても外延的に同値である。命題変数だけからなる論理式についてのこの種の議論は、論理と命題の記事の定理「恒真な同値からの移送」にある。

項数を減らす量化と、量化の順序

$\mathbb{Z}\times\mathbb{Z}$ 上の $2$ 項述語 $P(x,y)$：「$x< y$」から、量化で次の命題が得られる。

$\forall x\ \exists y\ P(x,y)$：「どの整数にもそれより大きい整数がある」。真。
$\exists y\ \forall x\ P(x,y)$：「すべての整数より大きい整数がある」。偽（$x=y$ とすると $P(y,y)$ が偽）。
量化子の順序を入れ替えると真偽が変わる。この現象と、一般に $\exists y\,\forall x$ から $\forall x\,\exists y$ が従うことは、全称記号の記事の命題「順序を入れ替えた命題の含意」にある。

性質

真理集合の計算

述語に論理演算・量化・代入を施したときの真理集合は、もとの真理集合から集合の操作で計算できる。

真理集合の計算規則

$X,Y,Z$ を集合とする。

$X$ 上の述語 $P,Q$ について、
$$ T(\lnot P)=X\setminus T(P),\quad T(P\land Q)=T(P)\cap T(Q),\quad T(P\lor Q)=T(P)\cup T(Q),\quad T(P\to Q)=(X\setminus T(P))\cup T(Q). $$
$X\times Y$ 上の述語 $P(x,y)$ について、$\pi\colon X\times Y\to X$ を $\pi(a,b)=a$ で定めると、$X$ 上の述語 $\exists y\in Y\ P(x,y)$ と $\forall y\in Y\ P(x,y)$ の真理集合は
$$ T\bigl(\exists y\in Y\ P(x,y)\bigr)=\pi\bigl(T(P)\bigr),\qquad T\bigl(\forall y\in Y\ P(x,y)\bigr)=X\setminus\pi\bigl((X\times Y)\setminus T(P)\bigr) $$
である。
$X$ 上の述語 $P(x)$ と写像 $f\colon Z\to X$ について、$Z$ 上の述語 $P(f(z))$（$x$ に $f(z)$ を代入したもの）の真理集合は $f^{-1}\bigl(T(P)\bigr)$ である。

いずれも、両辺が同じ集合の部分集合であることは定義から分かるので、各元の所属が一致することを示す。
1：$a\in X$ をとる。$a\in T(\lnot P)$ であることは $\lnot P(a)$ が真であること、すなわち $P(a)$ が偽であることであり、$a\in X$ なのでこれは $a\in X\setminus T(P)$ と同じである。$a\in T(P\land Q)$ は「$P(a)$ と $Q(a)$ がともに真」、すなわち「$a\in T(P)$ かつ $a\in T(Q)$」である。$\lor$ も同様である。$P(a)\to Q(a)$ が真であるのは「$P(a)$ が偽、または $Q(a)$ が真」のときに限る（含意の記事の定義「含意」）ので、$a\in T(P\to Q)$ は「$a\notin T(P)$ または $a\in T(Q)$」、すなわち $a\in(X\setminus T(P))\cup T(Q)$ と同じである。命題変数の論理式全般についての同じ議論は、論理と命題の記事の補題「所属の言い換え」にある。
2：$a\in X$ をとる。
$$ a\in T\bigl(\exists y\in Y\ P(x,y)\bigr)\iff\exists b\in Y\ \bigl((a,b)\in T(P)\bigr)\iff a\in\pi\bigl(T(P)\bigr). $$
最後の同値は、$\pi(T(P))$ が「$T(P)$ のある元 $(a',b)$ について $a=a'$」となる $a$ の全体であることによる。全称については、全称記号の記事の命題「量化された命題の否定」により $\forall y\in Y\ P(a,y)$ は $\lnot\,\exists y\in Y\ \lnot P(a,y)$ と同値である。$\lnot P$ の真理集合は 1 により $(X\times Y)\setminus T(P)$ なので、いま示した存在の場合を $\lnot P$ に当てると、$\exists y\in Y\ \lnot P(a,y)$ が真であることは $a\in\pi\bigl((X\times Y)\setminus T(P)\bigr)$ と同値である。これを否定して、主張の式を得る。
3：$c\in Z$ をとる。$c\in T(P(f(z)))$ であることは $P(f(c))$ が真であること、すなわち $f(c)\in T(P)$ であることであり、これは逆像の定義により $c\in f^{-1}(T(P))$ と同じである。$\square$

この命題から、次のことが読み取れる。

代入は論理演算と交換する。$P(f(z))\land Q(f(z))$ の真理集合は $f^{-1}(T(P)\cap T(Q))=f^{-1}(T(P))\cap f^{-1}(T(Q))$ であり、逆像が共通部分・和集合・補集合を保つこと（逆像の記事の命題「逆像と集合の演算」）の言い換えである。
存在は射影（像）で、全称は「補集合をとって射影し、また補集合をとる」で書ける。全称を射影だけで書くことはできない。$X=Y=\{0,1\}$、$T(P)=\{(0,0),(0,1),(1,0)\}$ とすると $\pi(T(P))=X$ だが、$\forall y\ P(1,y)$ は $P(1,1)$ が偽なので偽であり、$T(\forall y\,P)=\{0\}$ である。
$Y=\emptyset$ の場合も式はそのまま正しい。$T(P)=\emptyset$ なので $T(\exists y\,P)=\emptyset$、$T(\forall y\,P)=X\setminus\emptyset=X$ である。空集合の上の全称が真になること（全称記号の記事の注意「空集合上の量化」）と合っている。
存在と全称が射影・引き戻しに対してそれぞれ左随伴・右随伴の関係にあることは、量化子の随伴の記事の定理「集合上の量化子の随伴」で扱われている。

1 項述語の組み合わせでは表せない関係

$1$ 項述語は性質、$2$ 項述語は関係を表すと述べた。関係は性質の組み合わせで書けることもある。$\mathbb{R}\times\mathbb{R}$ 上の「$x>0$ かつ $y>0$」は、$x$ だけの述語「$x>0$」と $y$ だけの述語「$y>0$」の連言である。では、どんな関係も性質の組み合わせで書けるのか。等号 $x=y$ について、答えは定義域が有限かどうかで決まる。
$X,Y$ を集合とする。$X\times Y$ 上の述語のうち、$x$ だけを含む述語（$X$ 上の $1$ 項述語を $x$ について読んだもの）と、$y$ だけを含む述語から、$\lnot,\land,\lor,\to$ を有限回用いて作られるものを、$1$ 項述語から組み立てた述語 と呼ぶことにする。また $A\subset X$、$B\subset Y$ に対し、$A\times B$ の形の $X\times Y$ の部分集合を 長方形 と呼ぶ。

1 項述語から組み立てた述語の真理集合

$X\times Y$ 上の $1$ 項述語から組み立てた述語の真理集合は、有限個の長方形の和集合である。

有限個の長方形の和集合で書ける $X\times Y$ の部分集合を、ここでは 長方形和 と呼ぶ。空集合は $0$ 個の長方形の和集合なので長方形和である。述語の組み立てに沿った帰納法で、真理集合が長方形和であることを示す。prop-pred-truth-calculus の 1 により、真理集合は $\lnot,\land,\lor,\to$ に対してそれぞれ補集合・共通部分・和集合・「補集合と和集合」に移るので、長方形和の族がこれらの操作で閉じていることを示せばよい。
$x$ だけを含む述語 $A(x)$ の真理集合は $T(A)\times Y$、$y$ だけを含む述語 $B(y)$ の真理集合は $X\times T(B)$ で、どちらも長方形である。
和集合。 長方形和どうしの和集合は、長方形を並べ直すだけで長方形和である。
共通部分。 $(A\times B)\cap(C\times D)=(A\cap C)\times(B\cap D)$ である。実際 $(a,b)$ が左辺に属することは「$a\in A$、$b\in B$、$a\in C$、$b\in D$」であり、これは右辺に属することと同じである。したがって
$$ \Bigl(\bigcup_{i=1}^{p}A_i\times B_i\Bigr)\cap\Bigl(\bigcup_{j=1}^{q}C_j\times D_j\Bigr)=\bigcup_{i=1}^{p}\bigcup_{j=1}^{q}(A_i\cap C_j)\times(B_i\cap D_j) $$
は長方形和である（共通部分は和集合の上に分配する）。
補集合。 長方形 $A\times B$ の補集合は
$$ (X\times Y)\setminus(A\times B)=\bigl((X\setminus A)\times Y\bigr)\cup\bigl(X\times(Y\setminus B)\bigr) $$
である。実際、$(a,b)\notin A\times B$ であることは「$a\notin A$ または $b\notin B$」と同じだからである。長方形和 $\bigcup_{i=1}^{p}R_i$ の補集合は、De Morgan の法則により $\bigcap_{i=1}^{p}\bigl((X\times Y)\setminus R_i\bigr)$ であり、各項は長方形和なので、共通部分の場合を $p-1$ 回使って長方形和である（$p=0$ のときは補集合は $X\times Y$ で、これは長方形である）。
含意。 $T(P\to Q)$ は $T(P)$ の補集合と $T(Q)$ の和集合なので、上の 2 つから長方形和である。$\square$

等号と有限性

$X$ を集合とする。$X\times X$ 上の述語「$x=y$」が、$1$ 項述語から組み立てたある述語と外延的に同値であるための必要十分条件は、$X$ が有限集合であることである。

「$x=y$」の真理集合は対角集合 $\Delta:=\{(a,a)\mid a\in X\}$ である。
有限なら書ける。 $X=\{a_1,\dots,a_m\}$（$a_i$ は相異なる）とする。各 $i$ について、$x$ だけを含む述語「$x=a_i$」と $y$ だけを含む述語「$y=a_i$」を考え、
$$ R(x,y):=(x=a_1\land y=a_1)\lor\cdots\lor(x=a_m\land y=a_m) $$
とおく。$(a,b)\in X\times X$ について $R(a,b)$ が真であることは、ある $i$ で $a=a_i=b$ となることであり、$X$ の元はどれもある $a_i$ に等しいので、これは $a=b$ と同じである。よって $T(R)=\Delta$ である。$m=0$（$X=\emptyset$）のときは $X\times X=\emptyset$ なので、たとえば「$x\ne x$」（$x$ だけを含む述語）の真理集合も $\emptyset=\Delta$ である。
書けるなら有限。 $\Delta$ が $1$ 項述語から組み立てた述語の真理集合であるとする。lem-pred-rectangles により、$\Delta=\bigcup_{i=1}^{p}A_i\times B_i$ と書ける。空でない長方形 $A_i\times B_i$ だけを残してよい。各 $i$ について、$a\in A_i$、$b\in B_i$ をとると $(a,b)\in A_i\times B_i\subset\Delta$ なので $a=b$ である。$A_i$ の元と $B_i$ の元がどの組でも等しいので、$A_i$ と $B_i$ はどちらも同じ 1 元からなる集合 $\{c_i\}$ である（$a,a'\in A_i$ と $b\in B_i$ をとると $a=b=a'$）。したがって $\Delta=\{(c_1,c_1),\dots,(c_p,c_p)\}$ は高々 $p$ 個の元からなる。$a\mapsto(a,a)$ は $X$ から $\Delta$ への全単射なので、$X$ も高々 $p$ 個の元からなる有限集合である。$\square$

たとえば $\mathbb{N}$ 上では、等号 $x=y$ はどんな性質の有限の組み合わせでも書けない。$2$ 項以上の述語が、$1$ 項述語の寄せ集めでは代わりのきかない新しい情報をもっていることを、この定理は示している。一階述語論理で $n$ 項の述語記号を最初から用意するのはこのためである。一方、有限集合の上では、どの $2$ 項述語も $1$ 項述語「$x=a$」「$y=b$」の組み合わせで書ける。真理集合 $S$ は有限個の点 $(a,b)$ からなり、各点が長方形 $\{a\}\times\{b\}$ だからである。

述語の個数

有限集合上の述語の個数

$X$ を $m$ 個の元からなる有限集合、$n$ を $0$ 以上の整数とする。$X^n$ 上の述語に真理集合を対応させると、外延的同値の類と $X^n$ の部分集合とが一対一に対応する。特に、$X^n$ 上の $n$ 項述語は、外延的同値を除いてちょうど $2^{m^n}$ 個ある。

外延的同値は「真理集合が等しい」ことなので、外延的同値の類に真理集合を対応させる写像は矛盾なく定まり、単射である。全射であることを示す。$S\subset X^n$ を任意にとり、$X^n$ 上の述語 $P_S$ を「$(x_1,\dots,x_n)\in S$」と定めると、$T(P_S)=S$ である。よって一対一に対応する。
$X^n$ は $m^n$ 個の元からなり、$m^n$ 個の元からなる集合の部分集合はちょうど $2^{m^n}$ 個ある（冪集合の記事の命題「有限集合の冪集合の濃度」）。したがって類の個数は $2^{m^n}$ である。$\square$

$n=0$ のとき $X^0$ は 1 点集合なので、類は $2^1=2$ 個で、真の命題と偽の命題に対応する。$m=2$、$n=2$ のときは $2^4=16$ 個で、2 元集合上の二項関係が 16 個あることに対応する（二項関係の記事の定理「性質ごとの関係の個数」も参照）。$X$ が無限集合のときは、$X$ 上の $1$ 項述語の類は $X$ の部分集合と一対一に対応し、冪集合の記事の定理「Cantorの定理」により、その個数（濃度）は $X$ の元の個数より真に大きい。

定義域を集合にしておく理由

def-pred-main では、変数の動く範囲を集合 $X_1,\dots,X_n$ として固定した。範囲を集合にしておけば、どんな述語 $P$ にも真理集合 $\{x\in X\mid P(x)\}$ が集合として存在する。これは ZFC公理系の記事の公理「ZFC の公理」の分出図式 (iii) の内容である（分出図式で使える述語は、集合論の言語の論理式で書けるものである）。
範囲を固定せずに「性質 $P$ をもつもの全体」を考えると、集合にならないことがある。変数 $x$ がすべての集合を動くとして、述語「$x\notin x$」を考える。この述語の真理集合にあたる集合 $R$、すなわち「すべての集合 $x$ について $x\in R\leftrightarrow x\notin x$」となる集合 $R$ があったとすると、$x$ に $R$ 自身を入れて $R\in R\leftrightarrow R\notin R$ となり、矛盾する。これが Russell の逆理である（Ham18 §1.10、pp. 32–33）。分出図式から見た同じ議論は、ZFC公理系の記事の定理「すべての集合からなる集合はない」にある。

注意

述語記号・定義可能性との関係

一階述語論理では、述語記号は構造ごとに台集合の $n$ 乗の部分集合として解釈され、論理式が定める関係を 定義可能な関係 という（一階述語論理の記事の定義「定義可能な関係」）。この記事の意味の述語はどんな部分集合 $S\subset X^n$ も「$(x_1,\dots,x_n)\in S$」として表すが、決まった言語の論理式で表せる関係は一般にはその一部に限られる（同じ記事の例「定義できない関係」）。「述語」の語は、文脈によって文（記号列）を指すことも、その真理集合（関係）を指すこともある。

文法の「述語」との違い

国語文法の「述語」は、文の中で「どうする・どんなだ・なんだ」にあたる部分（「犬が走る」の「走る」）を指す。論理学の述語は、主語にあたる項を空欄にした文全体（「$\square$ は走る」）であり、空欄が 2 つ以上あってもよい（「$\square$ は $\square$ を割り切る」）。英語の predicate も論理学ではこの意味で使う（MBTZ25 §23.3、p. 193）。

条件を外した反例

外す条件	反例	成り立たなくなること
自由変数にすべて値を入れるか量化する	「$x>0$」（$x$ は自由変数のまま）	真偽が定まり命題になる
定義域を固定する	「$x^2=2$」の真理集合は $\mathbb{Q}$ 上で $\emptyset$、$\mathbb{R}$ 上で $\{\pm\sqrt2\}$	述語の文だけから真理集合が決まる
定義域を固定する	「$x^2+1=0$」と「$x\ne x$」は $\mathbb{R}$ 上で外延的に同値、$\mathbb{C}$ 上で同値でない	外延的同値は定義域によらない
量化子の順序を保つ	$\mathbb{Z}$ 上の「$x< y$」で、$\forall x\,\exists y$ は真、$\exists y\,\forall x$ は偽	量化子を入れ替えても真偽が変わらない
全称は補集合を挟んで射影する（prop-pred-truth-calculus）	$T(P)=\{(0,0),(0,1),(1,0)\}\subset\{0,1\}^2$	$T(\forall y\,P)=\pi(T(P))$
定義域が有限（thm-pred-diagonal）	$\mathbb{N}$ 上の「$x=y$」	$2$ 項述語は $1$ 項述語の有限の組み合わせで書ける
定義域を集合にする	すべての集合を動く $x$ についての「$x\notin x$」	どの述語の真理集合も集合として存在する

反例の確かめ

1 行目：「$x>0$」は $x=1$ で真、$x=-1$ で偽であり、値を決めないと真偽が定まらない。2・3 行目は ex-pred-domain と「定義」の節で確かめた。$\sqrt2$ は有理数でない（無理数）ので $\mathbb{Q}$ 上の真理集合は空である。4 行目は ex-pred-order による。5 行目：$\pi(T(P))=\{0,1\}$ だが、$P(1,1)$ が偽なので $1\notin T(\forall y\,P)$ であり、$T(\forall y\,P)=\{0\}$ である（prop-pred-truth-calculus のあとの注意）。6 行目は thm-pred-diagonal の後半による。7 行目は「定義域を集合にしておく理由」の節で示した。