定義可能集合

数理論理学において、定義可能集合（ていぎかのうしゅうごう、Definable set）とは、ある構造の台集合上のn-項関係であって、その要素がその構造の一階言語におけるある式を満たすものである。

定義

${\displaystyle {\mathcal {L}}}$ を一階の言語とする。${\displaystyle {\mathcal {M}}}$ を ${\displaystyle {\mathcal {L}}}$-構造で台が ${\displaystyle M}$ であるものとする。${\displaystyle X}$ は ${\displaystyle M}$ の固定された部分集合とし、${\displaystyle m}$ は自然数とする。このとき:

• 集合 ${\displaystyle A\subseteq M^{m}}$ が ${\displaystyle X}$ の元をパラメータとして ${\displaystyle {\mathcal {M}}}$ 内で定義可能であるとは、ある式 ${\displaystyle \varphi [x_{1},\ldots ,x_{m},y_{1},\ldots ,y_{n}]}$ とある ${\displaystyle b_{1},\ldots ,b_{n}\in X}$ があって、それらが全ての ${\displaystyle a_{1},\ldots ,a_{m}\in M}$ に対して、

${\displaystyle (a_{1},\ldots ,a_{m})\in A}$ であるときかつそのときに限り ${\displaystyle {\mathcal {M}}\models \varphi [a_{1},\ldots ,a_{m},b_{1},\ldots ,b_{n}].}$

が成立することを言う。

• 集合 ${\displaystyle A}$ が ${\displaystyle {\mathcal {M}}}$ 内でパラメータ無しで定義可能であるとは上記定義の X を空集合に置き換えたものである。(すなわち、定義式にパラメータが入っていない)
• 関数が ${\displaystyle {\mathcal {M}}}$ 内で（パラメータあり/なしで）定義可能であるとは、そのグラフが ${\displaystyle {\mathcal {M}}}$ 内で（パラメータあり/なしで）定義可能であることである。
• 要素 ${\displaystyle a}$ が ${\displaystyle {\mathcal {M}}}$ 内で（パラメータあり/なしで）定義可能であるとは、単元集合 ${\displaystyle \{a\}}$ が ${\displaystyle {\mathcal {M}}}$ 内で（パラメータあり/なしで）定義可能であることである。

例

順序関係だけを持った自然数構造

${\displaystyle {\mathcal {N}}=(\mathbb {N} ,<)}$ を自然数全体に通常の順序を入れた構造とする。このとき、全ての自然数は ${\displaystyle {\mathcal {N}}}$ 内でパラメータ無しで定義可能である。数 ${\displaystyle 0}$ は x より小さい要素が無いことを主張する式 ${\displaystyle \varphi (x)}$ :

${\displaystyle \varphi =\neg \exists y(y<x),}$

で定義可能である。そして各自然数 ${\displaystyle n>0}$ は x より小さい要素がちょうど ${\displaystyle n}$ 個存在することを主張する式 ${\displaystyle \varphi (x)}$ :

${\displaystyle \varphi =\exists x_{0}\cdots \exists x_{n-1}(x_{0}<x_{1}\land \cdots \land x_{n-1}<x\land \forall y(y<x\rightarrow (y\equiv x_{0}\lor \cdots \lor y\equiv x_{n-1})))}$

で定義可能である。

対照的に、通常の順序を入れた整数全体の構造 ${\displaystyle {\mathcal {Z}}=(\mathbb {Z} ,<)}$ においてはパラメータを用いずにはどの特定の整数も定義することができない。(後述の自己同型の節も参照)

算術操作を持った自然数構造

${\displaystyle {\mathcal {N}}=(\mathbb {N} ,+,\cdot ,<)}$ を通常の算術演算と順序が入った自然数の一階構造とする。この構造で定義可能な集合は算術的集合として知られ、算術的階層に属している。一階論理の代わりに二階論理を用いてこの構造を考えた時に定義可能になるような自然数集合は解析的階層に属する。これらの階層はこの構造における定義可能性と計算可能性理論との間の多くの関係を明らかにし、記述集合論においても興味深いものである。

実数体

${\displaystyle {\mathcal {R}}=(\mathbb {R} ,0,1,+,\cdot )}$ を実数の体の構造とする。通常の順序は構造には直接含まれないが、非負の実数集合を定義する式は存在している、というのも、平方根を持つ実数がちょうどそれだからである:

${\displaystyle \varphi =\exists y(y\cdot y\equiv x).}$

すなわち、任意の ${\displaystyle a\in \mathbb {R} }$ について、それが非負であるのは ${\displaystyle {\mathcal {R}}\models \varphi [a]}$ であるときちょうどその時限りである。${\displaystyle {\mathcal {R}}}$ の加法逆元を定義する式と組み合わせることで、${\displaystyle \varphi }$ を ${\displaystyle {\mathcal {R}}}$ 上の通常の順序を定義することに使うことができる: ${\displaystyle a,b\in \mathbb {R} }$ について、${\displaystyle a\leq b}$ とは ${\displaystyle b-a}$ が非負であることであると定義する。この拡大された構造 ${\displaystyle {\mathcal {R}}^{\leq }=(\mathbb {R} ,0,1,+,\cdot ,\leq )}$ は元の構造の定義による拡大と呼ばれる。これは集合が拡大された方の構造においてあるパラメータの集合から定義可能であるのは、元の構造において同じパラメータの集合から定義可能である場合にかつそのときに限る、という意味で元の構造と同じ表現力を持つ。

${\displaystyle {\mathcal {R}}^{\leq }}$ の理論は量化記号消去を持つ。したがって定義可能集合は多項式の等式と不等式の解のブール結合である; これらは半代数集合と呼ばれる。この実数直線の性質を一般化したものはo-minimalityの研究に繋がる。

自己同型のもとでの不変性

定義可能集合に関する重要な結果として、それらは自己同型のもとで保たれるというものがある。

${\displaystyle {\mathcal {M}}}$ を ${\displaystyle {\mathcal {L}}}$-構造で台が ${\displaystyle M}$ であるものとする。${\displaystyle X\subseteq M}$ とし、${\displaystyle A\subseteq M^{m}}$ は ${\displaystyle {\mathcal {M}}}$ で ${\displaystyle X}$ の元をパラメータとして定義可能であるとする。${\displaystyle \pi :M\to M}$ を ${\displaystyle {\mathcal {M}}}$ 上の自己同型で ${\displaystyle X}$ 上で恒等写像になっているものとする。このとき任意の ${\displaystyle a_{1},\ldots ,a_{m}\in M}$について、

${\displaystyle (a_{1},\ldots ,a_{m})\in A}$ であるときかつその時に限り ${\displaystyle (\pi (a_{1}),\ldots ,\pi (a_{m}))\in A.}$

となる。

この結果は、与えられた構造の定義可能な部分集合を分類するために使われることがある。例えば、前述の ${\displaystyle {\mathcal {Z}}=(\mathbb {Z} ,<)}$ の場合、${\displaystyle {\mathcal {Z}}}$ でパラメータを用いずに特定の整数を定義することは不可能である。実際、任意の2つの整数は平行移動とその逆によって互いに移るので ${\displaystyle {\mathcal {Z}}}$ でパラメータ無しで定義可能なものは空集合と ${\displaystyle \mathbb {Z} }$ それ自身のみである。対照的に、${\displaystyle {\mathcal {Z}}}$ の要素のn-つ組の集合で定義可能なものは無限に存在している: n = 2の場合、${\displaystyle m\in \mathbb {Z} }$ についての ${\displaystyle \{(a,b)\mid a-b=m\}}$ のブール結合などはその例である。特に、どの自己同型(平行移動)も二つの要素の"距離"を保存する。

他の結果

タルスキ-ヴォートテストは与えられた構造の初等部分構造を特徴づけるために用いられる。

参考文献

• Hinman, Peter. Fundamentals of Mathematical Logic, A K Peters, 2005.
• Marker, David. Model Theory: An Introduction, Springer, 2002.
• Rudin, Walter. Principles of Mathematical Analysis, 3rd. ed. McGraw-Hill, 1976.
• Slaman, Theodore A. and Woodin, W. Hugh. Mathematical Logic: The Berkeley Undergraduate Course. Spring 2006.