定義可能集合

${\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}}}$ 内で（パラメータあり/なしで）定義可能であることである。

Summarize Timeline Top Qs Fact Check

${\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の研究に繋がる。