定義可能集合のソースを表示

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

== 定義 ==
<math>\mathcal{L}</math> を一階の言語とする。<math>\mathcal{M}</math> を <math>\mathcal{L}</math>-構造で台が <math>M</math> であるものとする。<math>X</math> は <math>M</math> の固定された部分集合とし、<math>m</math> は[[自然数]]とする。このとき:
* 集合 <math>A\subseteq M^m</math> が ''<math>X</math> の元をパラメータとして <math>\mathcal{M}</math> 内で定義可能''であるとは、ある式 <math>\varphi[x_1,\ldots,x_m,y_1,\ldots,y_n]</math> とある <math>b_1,\ldots,b_n\in X</math> があって、それらが全ての <math>a_1,\ldots,a_m\in M</math> に対して、
:<math>(a_1,\ldots,a_m)\in A</math> であるときかつそのときに限り <math>\mathcal{M}\models\varphi[a_1,\ldots,a_m,b_1,\ldots,b_n].</math>
:が成立することを言う。

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

== 例 ==
=== 順序関係だけを持った自然数構造 ===
<math>\mathcal{N}=(\mathbb{N},<)</math> を自然数全体に通常の順序を入れた構造とする。このとき、全ての自然数は <math>\mathcal{N}</math> 内でパラメータ無しで定義可能である。数 <math>0</math> は ''x'' より小さい要素が無いことを主張する式 <math>\varphi(x)</math> :
:<math>\varphi=\neg\exists y(y<x),</math>
で定義可能である。そして各自然数 <math>n>0</math> は ''x'' より小さい要素がちょうど <math>n</math> 個存在することを主張する式 <math>\varphi(x)</math> :
:<math>\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})))</math>
で定義可能である。

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

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

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

:<math>\varphi = \exists y(y \cdot y \equiv x).</math>

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

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

== 自己同型のもとでの不変性 ==
定義可能集合に関する重要な結果として、それらは[[自己同型]]のもとで保たれるというものがある。
:<math>\mathcal{M}</math> を <math>\mathcal{L}</math>-構造で台が <math>M</math> であるものとする。<math>X\subseteq M</math> とし、<math>A\subseteq M^m</math> は <math>\mathcal{M}</math> で <math>X</math> の元をパラメータとして定義可能であるとする。<math>\pi:M\to M</math> を <math>\mathcal{M}</math> 上の自己同型で <math>X</math> 上で恒等写像になっているものとする。このとき任意の <math>a_1,\ldots,a_m\in M</math>について、
::<math>(a_1,\ldots,a_m)\in A</math> であるときかつその時に限り <math>(\pi(a_1),\ldots,\pi(a_m))\in A.</math>
:となる。

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

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

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

{{Authority control}}
{{DEFAULTSORT:ていきかのうしゆうこう}}
[[Category:モデル理論]]
[[Category:論理学]]
[[Category:数理論理学]]
[[Category:数学に関する記事]]