定義可能集合
概要
定義可能集合（definable set）とは、構造 $\mathcal M$ の台集合の直積 $M^n$ の部分集合で、$\mathcal M$ の元をパラメータとして書き込んだ一階の論理式を満たす元の組の全体として表されるものである。パラメータを集合 $A$ から取る定義可能集合の族は、補集合・共通部分・射影・直積・座標の並べ替え・$A$ の点でのファイバーで閉じており、基本の関係を含みこれらの操作で閉じた最小の族として特徴づけられる。$A$ の各点を固定する自己同型は $A$ 上定義可能な集合を保つ。これを使うと、$(\mathbb R,<)$ で有限集合 $B$ 上定義可能な部分集合は $B$ の点と $B$ で区切った開区間の和に限られ、$\mathbb Q$ はどのパラメータを使っても定義できない。
構造 $\mathcal M$ の 定義可能集合（definable set）とは、$\mathcal M$ の台集合の直積 $M^n$ の部分集合で、一階の論理式によって切り出されるもののことである。論理式には $\mathcal M$ の元をパラメータとして書き込んでよい。たとえば実数の順序体で、区間 $(0,1)$ は論理式 $0< x\land x< 1$ で、関係 $x\le y$ は論理式 $\exists z\,(y=x+z\cdot z)$ で定義される。どの集合が定義可能かは構造の言語によって変わり、定義可能集合の全体を調べることは、その構造がどれだけ複雑かを測ることにあたる。「$\mathcal M$ の理論のモデルの中で、ある論理式を満たす元はどのように振る舞うか」は モデル理論 の基本的な問いの一つである。
この記事では、パラメータの集合を指定した定義可能集合を定め、定義可能集合の族が論理の操作に対応する集合の操作（補集合・共通部分・射影・直積・座標の並べ替え・ファイバー）で閉じていること、さらにそれが基本の集合を含みこれらの操作で閉じた最小の族として特徴づけられることを証明する。次に、パラメータを固定する自己同型が定義可能集合を保つことを示し、これを使って順序 $(\mathbb R,<)$ の定義可能集合を完全に決定する。特に $\mathbb Q$ はどのパラメータを使っても $(\mathbb R,<)$ で定義できない。最後に、代数閉体・実閉体・整数環での例と、自己同型による判定の限界を述べる。
定義
言語 $L$ と $L$ 構造 $\mathcal M$（台集合 $M$）を固定する（構造(モデル)、一階述語論理 の定義「構造」）。論理式 $\varphi$ の自由変数が相異なる変数 $x_1,\dots,x_n,y_1,\dots,y_k$ の中にあることを $\varphi(\bar x,\bar y)$ と書く（$\bar x=(x_1,\dots,x_n)$、$\bar y=(y_1,\dots,y_k)$）。$\bar a\in M^n$、$\bar b\in M^k$ について、$x_i$ に $a_i$、$y_j$ に $b_j$ を割り当てたとき $\varphi$ が $\mathcal M$ で成り立つことを $\mathcal M\models\varphi(\bar a,\bar b)$ と書く（一階述語論理 の定義「充足関係」。ほかの変数への割り当てによらないことは同記事の補題「一致補題」）。
$A\subset M$、$n\ge0$ とする。$X\subset M^n$ が $A$ 上定義可能（$A$-definable）であるとは、論理式 $\varphi(\bar x,\bar y)$（$\bar x$ は $n$ 個、$\bar y$ は $k\ge0$ 個の変数）と $\bar b\in A^k$ で
$$X=\varphi(\mathcal M,\bar b):=\{\bar a\in M^n\mid \mathcal M\models\varphi(\bar a,\bar b)\}$$
となるものがあることをいう。$\bar b$ を パラメータ という。$\emptyset$ 上定義可能な集合を パラメータなしで定義可能 な集合といい、$M$ 上定義可能な集合を単に 定義可能集合 という。$A$ 上定義可能な $M^n$ の部分集合の全体を $\mathrm{Def}_n(A)$ と書く。
$X\subset M^n$ から $M^m$ への写像 $g$ が $A$ 上定義可能であるとは、そのグラフ $\{(\bar a,g(\bar a))\mid\bar a\in X\}\subset M^{n+m}$ が $A$ 上定義可能であることをいう。
パラメータ付きの定義可能性は PS86 p. 565 や Edm00 p. 3 の定義と同じである。パラメータなしで定義可能な集合は、一階述語論理 の定義「定義可能な関係」の $\varphi^{\mathcal M}$ と同じものである。$A\subset B\subset M$ なら $\mathrm{Def}_n(A)\subset\mathrm{Def}_n(B)$ である。言語が可算なら論理式は可算個（論理式 の定理「可算言語の論理式は可算個」）なので、$A$ が可算なら $\mathrm{Def}_n(A)$ も可算である。
- どの構造でも、$a\in A$ について $\{a\}=\varphi(\mathcal M,a)$（$\varphi(x,y)$ は $x=y$）は $A$ 上定義可能である。
- $(\mathbb R,<)$ で、$a< b$ について開区間 $(a,b)$ は $a< x\land x< b$ により $\{a,b\}$ 上定義可能である。
- 体の言語の構造 $(\mathbb R,+,\cdot,0,1)$ で、順序 $\{(x,y)\mid x\le y\}$ は $\exists z\,(y=x+z\cdot z)$ によりパラメータなしで定義可能である（一階述語論理 の例「定義可能な関係」）。有理数 $1/2$ からなる 1 点集合も、$x\cdot(1+1)=1$ によりパラメータなしで定義可能である。
- 環の言語の構造 $(\mathbb Z,+,\cdot,0,1)$ で、自然数の全体 $\{x\mid x\ge0\}$ は
$$\exists a\,\exists b\,\exists c\,\exists d\;(x=a\cdot a+b\cdot b+c\cdot c+d\cdot d)$$
によりパラメータなしで定義可能である。$0$ 以上の整数はどれも 4 つの平方数の和であり（Lagrangeの四平方定理）、平方数の和は $0$ 以上だからである。したがって順序 $x\le y$ も $\exists z\,(y=x+z\wedge z\ge0)$ の形の論理式で定義できる。一方、加法だけの $(\mathbb Z,+)$ では順序はパラメータなしでは定義できない（一階述語論理 の例「定義できない関係」）。言語を増やすと、定義可能集合は増えうる。
定義可能集合の族の性質
$X\subset M^{n+1}$ の 射影 を $\mathrm{pr}(X):=\{\bar a\in M^n\mid\text{ある }c\in M\text{ で }(\bar a,c)\in X\}$、$X\subset M^{n+m}$ と $\bar c\in M^m$ についての ファイバー を $X_{\bar c}:=\{\bar a\in M^n\mid(\bar a,\bar c)\in X\}$ と書く。
$A\subset M$ とする。
- $\mathrm{Def}_n(A)$ は $\emptyset$ と $M^n$ を含み、補集合・有限個の共通部分・有限個の和集合で閉じている。
- $X\in\mathrm{Def}_{n+1}(A)$ ならば $\mathrm{pr}(X)\in\mathrm{Def}_n(A)$ である。
- $X\in\mathrm{Def}_n(A)$、$Y\in\mathrm{Def}_m(A)$ ならば $X\times Y\in\mathrm{Def}_{n+m}(A)$ である。$\{1,\dots,n\}$ の置換 $s$ について、座標を並べ替えた $\{(a_{s(1)},\dots,a_{s(n)})\mid\bar a\in X\}$ も $\mathrm{Def}_n(A)$ に属する。
- $X\in\mathrm{Def}_{n+m}(A)$、$\bar c\in A^m$ ならば $X_{\bar c}\in\mathrm{Def}_n(A)$ である。
- 対角線 $\{(a,a)\mid a\in M\}$、各関係記号 $R$ の解釈 $R^{\mathcal M}$、各関数記号 $f$ の解釈のグラフ $\{(\bar a,f^{\mathcal M}(\bar a))\}$、各定数記号 $c$ の解釈の 1 点集合 $\{c^{\mathcal M}\}$ はパラメータなしで定義可能であり、$a\in A$ について $\{a\}\in\mathrm{Def}_1(A)$ である。
$X=\varphi(\mathcal M,\bar b)$、$Y=\psi(\mathcal M,\bar b')$（$\bar b\in A^k$、$\bar b'\in A^{k'}$）とする。束縛変数を付け替えて、論理式どうしの変数が衝突しないようにしておく（一階述語論理 の系「束縛変数の付け替え」）。以下では充足関係の定義をそのまま使う。
1：$\emptyset$ と $M^n$ はそれぞれ $\lnot(x_1=x_1)$ と $x_1=x_1$ で定義される（$n=0$ のときは $M^0$ を 1 点集合とし、文 $\lnot\exists z\,(z=z)$ と $\exists z\,(z=z)$ を使う）。$M^n\setminus X$ は $\lnot\varphi(\bar x,\bar b)$ で定義される。$X\cap Y$ は、$\varphi(\bar x,\bar y)$ と $\psi(\bar x,\bar y')$ の変数 $\bar y,\bar y'$ を別にとって $(\varphi\land\psi)(\bar x,\bar y\bar y')$ にパラメータ $\bar b\bar b'$ を入れたもので定義される。和集合は補集合と共通部分で書ける。
2：$X=\varphi(\mathcal M,\bar b)$、$\varphi(x_1,\dots,x_{n+1},\bar y)$ とすると、$\mathrm{pr}(X)$ は $\exists x_{n+1}\,\varphi$ にパラメータ $\bar b$ を入れたもので定義される。
3：$\psi$ の自由変数 $x_1,\dots,x_m$ を $\varphi$ に現れない変数 $z_1,\dots,z_m$ に置き換えた $\psi'(\bar z,\bar y')$ をとると、$X\times Y$ は $\varphi(\bar x,\bar y)\land\psi'(\bar z,\bar y')$ にパラメータ $\bar b\bar b'$ を入れたもので定義される。座標の並べ替えは、自由変数 $x_1,\dots,x_n$ を $x_{s^{-1}(1)},\dots,x_{s^{-1}(n)}$ に同時に置き換える（衝突を避けるため、いったん新しい変数を経由する）ことで得られる。
4：$X=\varphi(\mathcal M,\bar b)$、$\varphi(x_1,\dots,x_{n+m},\bar y)$ とする。$\varphi$ を $(x_1,\dots,x_n)$ の論理式とみて、$(x_{n+1},\dots,x_{n+m},\bar y)$ をパラメータの変数とみなすと、$X_{\bar c}=\varphi(\mathcal M,\bar c\bar b)$ であり、$\bar c\bar b\in A^{m+k}$ である。
5：対角線は $x_1=x_2$、$R^{\mathcal M}$ は $R(x_1,\dots,x_r)$、$f$ のグラフは $f(x_1,\dots,x_r)=x_{r+1}$、$\{c^{\mathcal M}\}$ は $x_1=c$ で定義される。$\{a\}$ は ex-defset-first の 1 である。$\square$
逆に、これらの操作だけで定義可能集合はすべて作れる。そのために、論理式を使わずに族の性質だけを述べる。
$A\subset M$ とする。各 $n\ge0$ について $\mathcal E_n$ を $M^n$ の部分集合の族とし、族の列 $\mathcal E=(\mathcal E_n)_{n\ge0}$ が次の (E1)〜(E4) を満たすとき、$\mathcal E$ は $A$ 上の定義可能性の公理 を満たすという。
- (E1) 各 $\mathcal E_n$ は $M^n$ を含み、補集合と有限個の共通部分で閉じている。
- (E2) $X\in\mathcal E_{n+1}$ ならば $\mathrm{pr}(X)\in\mathcal E_n$。
- (E3) $X\in\mathcal E_n$ ならば $X\times M\in\mathcal E_{n+1}$ であり、座標を並べ替えたものも $\mathcal E_n$ に属する。
- (E4) $\mathcal E$ は thm-defset-closure の 5 に挙げた集合をすべて含む（$\{a\}$ は $a\in A$ について）。
$A\subset M$ について、$(\mathrm{Def}_n(A))_{n\ge0}$ は $A$ 上の定義可能性の公理を満たす。さらに、$A$ 上の定義可能性の公理を満たす任意の族の列 $\mathcal E$ について、すべての $n$ で $\mathrm{Def}_n(A)\subset\mathcal E_n$ である。すなわち $(\mathrm{Def}_n(A))_n$ は、この公理を満たす最小の族の列である。
前半は thm-defset-closure の 1・2・3・5 から従う（$X\times M$ は $M\in\mathrm{Def}_1(A)$ との直積である）。
後半を示す。$\mathcal E$ が $A$ 上の定義可能性の公理を満たすとする。まず (E1)〜(E4) から、(a) 直積で閉じていること、(b) $A$ の点でのファイバーで閉じていること、(c) 任意の座標を消す射影で閉じていることが従う。
(a)〜(c) の確かめを開く
(a) $X\in\mathcal E_n$、$Y\in\mathcal E_m$ ならば $X\times Y\in\mathcal E_{n+m}$。実際、(E3) を $m$ 回使って $X\times M^m\in\mathcal E_{n+m}$、同様に $Y\times M^n$ の座標を並べ替えて $M^n\times Y\in\mathcal E_{n+m}$ であり、両者の共通部分が $X\times Y$ である。
(b) $X\in\mathcal E_{n+m}$、$\bar c\in A^m$ ならば $X_{\bar c}\in\mathcal E_n$。実際、(E4) と (a) から $\{\bar c\}=\{c_1\}\times\cdots\times\{c_m\}\in\mathcal E_m$、$M^n\times\{\bar c\}\in\mathcal E_{n+m}$ であり、$X\cap(M^n\times\{\bar c\})$ に (E2) を $m$ 回使うと $X_{\bar c}$ になる。
(c) 座標の並べ替えと (E2) を組み合わせると、任意の座標を消す射影で閉じている。
論理式 $\varphi$ と、$\varphi$ の自由変数をすべて含む相異なる変数の列 $\bar x=(x_1,\dots,x_N)$ について、
$$\varphi[\bar x]:=\{\bar a\in M^N\mid x_i\text{ に }a_i\text{ を割り当てると }\mathcal M\text{ で }\varphi\text{ が成り立つ}\}$$
とおく。すべての $\varphi$ と $\bar x$ について $\varphi[\bar x]\in\mathcal E_N$ であることを、$\varphi$ の組み立てに沿った帰納法で示す。これが言えれば、$X=\varphi(\mathcal M,\bar b)$（$\varphi(\bar x,\bar y)$、$\bar b\in A^k$）について $X=(\varphi[\bar x\bar y])_{\bar b}$ なので、(b) により $X\in\mathcal E_n$ である。
原子論理式。 項 $t$ の変数が $\bar x$ の中にあるとき、$t$ のグラフ $\Gamma_t:=\{(\bar a,d)\in M^{N+1}\mid t^{\mathcal M}[\bar a]=d\}$ が $\mathcal E_{N+1}$ に属することを $t$ の組み立てに沿って示し、原子論理式の定める集合をグラフの共通部分の射影として表す。
項のグラフと原子論理式の確かめを開く
$t$ が変数 $x_i$ なら、$\Gamma_t=\{(\bar a,d)\mid a_i=d\}$ は対角線と $M^{N-1}$ の直積の座標を並べ替えたものである。$t$ が定数記号 $c$ なら $\Gamma_t=M^N\times\{c^{\mathcal M}\}$ である。$t=f(s_1,\dots,s_r)$ なら、$M^{N+1+r}$ の点を $(\bar a,d,\bar e)$ と書くとき、$\Gamma_t$ は $\bigcap_{j=1}^r\{(\bar a,d,\bar e)\mid(\bar a,e_j)\in\Gamma_{s_j}\}\ \cap\ \{(\bar a,d,\bar e)\mid f^{\mathcal M}(\bar e)=d\}$ から $\bar e$ の座標を消す射影であり、各集合は帰納法の仮定・(E4)・(a)・座標の並べ替えにより $\mathcal E_{N+1+r}$ に属する。すると $(t_1=t_2)[\bar x]$ は $\Gamma_{t_1}\cap\Gamma_{t_2}$ の最後の座標を消す射影であり、$R(t_1,\dots,t_r)[\bar x]$ は $\{(\bar a,\bar e)\mid(\bar a,e_j)\in\Gamma_{t_j}\ (1\le j\le r),\ \bar e\in R^{\mathcal M}\}$ から $\bar e$ を消す射影である。
結合子。 $(\lnot\psi)[\bar x]=M^N\setminus\psi[\bar x]$、$(\psi\land\chi)[\bar x]=\psi[\bar x]\cap\chi[\bar x]$ であり、ほかの結合子はこの 2 つで書ける。
量化記号。 $\varphi=\exists y\,\psi$ とする。$y$ が $\bar x$ に現れなければ、帰納法の仮定から $\psi[\bar xy]\in\mathcal E_{N+1}$ であり、$\varphi[\bar x]=\mathrm{pr}(\psi[\bar xy])$ である。$y=x_i$ なら、$x_i$ は $\varphi$ の自由変数でない。$\bar x$ から $x_i$ を除いた列を $\bar x'$ とすると、$\varphi[\bar x']=\mathrm{pr}(\psi[\bar x'x_i])\in\mathcal E_{N-1}$ であり、一致補題により $\varphi[\bar x]$ は $\varphi[\bar x']\times M$ の座標を並べ替えたものである。$\forall y\,\psi$ は $\lnot\exists y\,\lnot\psi$ と同じ集合を定める。$\square$
この特徴づけは、定義可能性が論理式の書き方の細部によらないことを示している。集合論で構成可能集合の階層を作るときには、論理式を集合論の中で形式化する代わりに、この形の「基本の関係を含み、補集合・共通部分・射影で閉じた最小の族」を定義として採る（Kun80 Ch. V, Definition 1.1（p. 153）、Lemma 1.2・1.3（pp. 153–154））。論理の操作と集合の操作の対応（$\land$ と共通部分、$\lnot$ と補集合、$\exists$ と射影）は Edm00 pp. 2–3 にも述べられている。
自己同型による判定
$A\subset M$、$X\in\mathrm{Def}_n(A)$ とし、$h$ を $\mathcal M$ の自己同型で $A$ の各点を固定するもの（すべての $a\in A$ で $h(a)=a$）とする。このとき $h(X)=X$ である。ここで $h(X):=\{(h(a_1),\dots,h(a_n))\mid\bar a\in X\}$ とする。
$X=\varphi(\mathcal M,\bar b)$、$\bar b\in A^k$ とする。一階述語論理 の定理「同型補題」により、$\mathcal M\models\varphi(\bar a,\bar b)$ と $\mathcal M\models\varphi(h(\bar a),h(\bar b))$ は同値であり、$h(\bar b)=\bar b$ なので、$\bar a\in X$ と $h(\bar a)\in X$ は同値である。よって $h(X)\subset X$ である。$h^{-1}$ も $A$ の各点を固定する自己同型なので $h^{-1}(X)\subset X$、すなわち $X\subset h(X)$ である。$\square$
パラメータなしの場合は 一階述語論理 の系「定義可能な関係は自己同型で保たれる」である。この命題は、ある集合が定義可能で ない ことを示すのに使える。集合を動かす自己同型で、使うパラメータを固定するものを見つければよい。
$(\mathbb R,<)$ を順序の言語の構造とし、$B=\{b_1,\dots,b_k\}$（$b_1< \cdots< b_k$、$k\ge0$）とする。$b_0:=-\infty$、$b_{k+1}:=+\infty$ とおき、$\mathbb R$ を $2k+1$ 個の集合
$$\{b_1\},\dots,\{b_k\},\qquad J_i:=(b_i,b_{i+1})\quad(0\le i\le k)$$
に分ける。$\mathbb R$ の部分集合が $B$ 上定義可能であることは、それがこれらの集合のいくつか（$0$ 個も許す）の和集合であることと同値である。特に、$B$ 上定義可能な $\mathbb R$ の部分集合はちょうど $2^{2k+1}$ 個あり、$\mathbb Q$ は $(\mathbb R,<)$ でどのパラメータを使っても定義できない。
各 $\{b_j\}$ と各 $J_i$ は $B$ 上定義可能である（$J_i$ は $b_i< x\land x< b_{i+1}$ で定義され、端が $\pm\infty$ のときはその側の不等式を省く。$k=0$ なら $J_0=\mathbb R$ は $x=x$ で定義される）。thm-defset-closure の 1 により、それらの和集合も $B$ 上定義可能である。
逆に $X\subset\mathbb R$ が $B$ 上定義可能であるとする。各 $J_i$ について、$X\cap J_i$ が $\emptyset$ か $J_i$ であることを示せばよい。$q,r\in J_i$ を任意にとり、$q\in X$ なら $r\in X$ であることを示す。$J_i$ の外では恒等写像で、$J_i$ を $J_i$ の上に狭義単調増加に写し、$h(q)=r$ を満たす全単射 $h\colon\mathbb R\to\mathbb R$ を次のように作る。
- $J_i=(u,v)$ が有界なら、$[u,q]$ を $[u,r]$ に、$[q,v]$ を $[r,v]$ に、それぞれ 1 次関数で写す。
- $J_i=(u,+\infty)$（$u$ は実数）なら、$(u,q]$ を $(u,r]$ に 1 次関数で写し、$x\ge q$ では $h(x):=x+(r-q)$ とする。$J_i=(-\infty,v)$ も左右を逆にして同様に作る。
- $J_i=\mathbb R$（$k=0$）なら $h(x):=x+(r-q)$ とする。
どの場合も $h$ は狭義単調増加な全単射なので $(\mathbb R,<)$ の自己同型であり、$B$ の各点を固定する。prop-defset-automorphism により $h(X)=X$ なので、$q\in X$ なら $r=h(q)\in X$ である。
$2k+1$ 個の集合は互いに交わらず空でないので、その部分集合族と和集合は 1 対 1 に対応し、$B$ 上定義可能な部分集合は $2^{2k+1}$ 個である。任意の定義可能集合は有限個のパラメータで定義されるので、ある有限集合 $B$ の上で定義可能である。$\mathbb Q$ はどの $J_i$ についても $J_i$ と交わり、かつ $J_i$ を含まない（区間は有理数と無理数をともに含む）ので、上の形の和集合でない。$\square$
$\mathbb Z$ や $\mathbb N$ も同じ理由で $(\mathbb R,<)$ で定義できない。この定理の 1 変数の部分は、$(\mathbb R,<)$ が o-極小構造 であることの直接の証明にもなっている（同記事の命題「稠密な順序は o-極小」、量化記号消去 の系「DLO の完全性と定義可能集合」は量化記号消去による証明である）。ここでの証明は、パラメータで区切った各区間の中で点を自由に動かす自己同型を使うので、どの和集合が実際に現れるかまで決まる。
代数的な構造での例
体や環の構造では、定義可能集合は多項式で表される集合と深く結びつく。次の 2 つは、量化記号消去を通して得られる結果であり、この記事では証明しない。
- 代数閉体。 代数閉体 $K$ を体の言語の構造と見ると、$K$ の元をパラメータとして定義される $K$ の部分集合は、有限集合か有限集合の補集合である（量化記号消去 の系「代数閉体の理論の帰結」の 3）。$K^n$ の定義可能集合も、量化記号消去 の定理「代数閉体の量化記号消去」により量化記号のない論理式で定義でき、したがって多項式の零点集合を補集合・共通部分・和集合で有限回組み合わせた集合（構成可能集合）である。特に $\mathbb R$ は $(\mathbb C,+,\cdot,0,1)$ で定義可能でない。$\mathbb R$ は無限集合で、補集合も無限集合だからである。
- 実閉体。 $(\mathbb R,+,\cdot,<)$ の定義可能集合は半代数的集合であり（Tarski–Seidenbergの定理）、$\mathbb R$ の定義可能な部分集合は有限個の点と開区間の和である（o-極小構造 の命題「実閉体は o-極小」）。順序は $(\mathbb R,+,\cdot,0,1)$ でパラメータなしで定義可能なので（ex-defset-first の 3）、$<$ を含む論理式は $<$ を含まない論理式に書き直せ、$(\mathbb R,+,\cdot,0,1)$ でも定義可能集合は同じである。特に $\mathbb Z$ と $\mathbb Q$ は $(\mathbb R,+,\cdot,0,1)$ で定義可能でない（どちらも開区間を含まない無限集合なので、有限個の点と開区間の和でない）。
これと対照的に、$(\mathbb Z,+,\cdot,0,1)$ では $\mathbb N$ が定義可能だった（ex-defset-first の 4）。整数環は、実数体よりはるかに多くの集合を定義できる構造である。
prop-defset-automorphism の逆は成り立たない。$(\mathbb R,+,\cdot,0,1)$ の自己同型 $h$ は恒等写像だけである。実際、$h$ は $0,1$ と体の演算を保つので有理数を固定し、パラメータなしで定義可能な順序を保つ（prop-defset-automorphism）。$h(x)\ne x$ となる $x$ があれば、たとえば $h(x)< x$ のとき、有理数 $q$ を $h(x)< q< x$ ととると、$q< x$ から $q=h(q)< h(x)$ となって矛盾する（$h(x)>x$ のときも同様）。したがって $\mathbb R$ のどの部分集合もすべての自己同型で保たれるが、$\mathbb Z$ は上で見たとおり定義可能でない。自己同型で保たれることは定義可能であるための必要条件だが、十分条件ではない。
反例：条件を外すと成り立たない
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 自己同型がパラメータの各点を固定する（prop-defset-automorphism） | $(\mathbb R,<)$、$A=\{0\}$、$h(x)=x+1$ | $h(X)=X$（$X=\{0\}$ は $A$ 上定義可能だが $h(X)=\{1\}$） |
| ファイバーをとる点がパラメータの集合に入る（thm-defset-closure の 4） | $(\mathbb R,<)$、$A=\emptyset$、$X=\{(x,y)\mid x< y\}$ のファイバー $X_0$ | ファイバーが $A$ 上定義可能（$X_0=(-\infty,0)$） |
| 順序が稠密で端点をもたない（thm-defset-real-order） | $(\mathbb Z,<)$、$B=\{0\}$、集合 $\{1\}$ | 定義可能集合が $\{b_j\}$ と区間 $J_i$ の和集合になること |
| 体が代数閉（量化記号消去 の系「代数閉体の理論の帰結」の 3） | 実数体 $(\mathbb R,+,\cdot,0,1)$ と $[0,\infty)$ | 定義可能な部分集合が有限集合か有限集合の補集合 |
1 行目：$x\mapsto x+1$ は狭義単調増加な全単射なので $(\mathbb R,<)$ の自己同型だが、$0$ を固定しない。$\{0\}$ は $x=y$ にパラメータ $0$ を入れて定義される。
2 行目：$X$ は $x< y$ で定義されるので $\emptyset$ 上定義可能である。$X_0=(-\infty,0)$ は $\{0\}$ 上定義可能だが、thm-defset-real-order で $k=0$ とすると、$\emptyset$ 上定義可能な $\mathbb R$ の部分集合は $\emptyset$ と $\mathbb R$ だけなので、$X_0$ は $\emptyset$ 上定義可能でない。
3 行目：$\{1\}$ は論理式 $0< x\land\lnot\exists z\,(0< z\land z< x)$（$0$ の直後の元）にパラメータ $0$ を入れて定義される。$J_1=(0,+\infty)$ の中では $\{1\}$ は空でも $J_1$ 全体でもない。$(\mathbb Z,<)$ では、$0$ を固定する自己同型は恒等写像だけなので（各元は $0$ から直後の元を何回たどるかで決まる）、証明で使った「区間の中で点を動かす自己同型」がない。
4 行目：$[0,\infty)$ は $\exists z\,(x=z\cdot z)$ で定義され、無限集合で補集合 $(-\infty,0)$ も無限集合である。実数体は $x^2+1$ が根をもたないので代数閉でない。
補足
- 型との関係。 $A$ 上の元の組 $\bar a,\bar a'\in M^n$ が $A$ 上の同じ型をもつとは、$A$ 上定義可能なすべての集合 $X\subset M^n$ について「$\bar a\in X\iff\bar a'\in X$」が成り立つことである。prop-defset-automorphism により、$A$ の各点を固定する自己同型で移り合う組は同じ型をもつ。
- 集合論での定義可能性。 集合 $A$ を $\in$ だけの言語の構造 $(A,\in)$ と見て、$A$ の元をパラメータとして定義される $A$ の部分集合の全体を $\mathcal D(A)$ と書く。Gödel の構成可能集合の階層は $L(0)=\emptyset$、$L(\alpha+1)=\mathcal D(L(\alpha))$、極限順序数では和集合で定義される（Kun80 Ch. VI, Definition 1.1（p. 165）と同章 §1 の冒頭）。ここで使う「定義可能」は、この記事の定義の特別な場合である。
- o-極小構造。 1 変数の定義可能集合が有限個の点と区間の和である順序構造では、高い次元の定義可能集合を胞体に分解して調べられる（o-極小構造、胞体分解定理(o-極小)）。
関連項目
- 前提: 一階述語論理, 構造(モデル), 論理式
- 定義可能集合を調べる道具: 量化記号消去, 初等同値, Tarski–Seidenbergの定理
- 定義可能集合が単純な構造: o-極小構造, 半代数的集合, 胞体分解定理(o-極小)
- 例の出どころ: Lagrangeの四平方定理, 代数閉体, 実閉体
- 分野: モデル理論
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
