定義可能な集合

数理論理学において、定義可能な集合とは、構造の領域上のn項関係であり、その要素は、その構造の1階述語論理における何らかの式を満たす。集合は、パラメータの有無にかかわらず定義できる。パラメータとは、関係を定義する式の中で参照できる領域の要素のことである。

させて$\displaystyle {\mathcal {L}}}$第一階言語であること、$\displaystyle {\mathcal {M}}}$1$\displaystyle {\mathcal {L}}}$ドメインを持つ構造${\displaystyle M}$、${\displaystyle X}$固定されたサブセット${\displaystyle M}$、 そして${\displaystyle m}$自然数。すると：

• セット${\displaystyle A\subseteq M^{m}}$定義可能$\displaystyle {\mathcal {M}}}$パラメータ付き${\displaystyle X}$式が存在する場合に限り${\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}}}$パラメータなしで定義可能$\displaystyle {\mathcal {M}}}$パラメータが空集合から選ばれる場合（つまり、定義式にパラメータが含まれていない場合）。
• 関数は定義可能です$\displaystyle {\mathcal {M}}}$（パラメータ付き）そのグラフが（それらのパラメータ付きで）定義可能であれば$\displaystyle {\mathcal {M}}}$。
• 要素${\displaystyle a}$定義可能$\displaystyle {\mathcal {M}}}$（パラメータ付き）シングルトンセットの場合${\displaystyle \{a\}}$定義可能$\displaystyle {\mathcal {M}}}$（これらのパラメータを用いて）

定義可能な集合に関する重要な結果の一つは、それらの集合は、そのパラメータ集合を固定する自己同型写像​​の下で保存されるということである。

させて$\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}}}$これはパラメータの空集合を保存する自己同型であり、したがって、パラメータなしでこの構造で特定の整数を定義することは不可能です。${\displaystyle {\mathcal {Z}}}$実際、任意の2つの整数は平行移動とその逆によって互いに渡されるため、定義可能な整数の集合は${\displaystyle {\mathcal {Z}}}$パラメータなしの場合は空集合で、${\displaystyle \mathbb {Z} }$それ自体。対照的に、要素のペア（または任意の固定n > 1 に対するnタプル）の定義可能な集合は無限に存在する。${\displaystyle {\mathcal {Z}}}$（ n = 2の場合）集合のブール結合${\displaystyle \{(a,b)\mid ab=m\}}$のために${\displaystyle m\in \mathbb {Z} }$特に、任意の自己同型写像​​（平行移動）は、2つの要素間の「距離」を保存します。

タルスキー・ヴォート検定は、特定の構造の基本部分構造を特徴づけるために用いられる。

• ヒンマン、ピーター。『数理論理学の基礎』 AKピーターズ、2005年。
• マーカー、デイビッド。『モデル理論入門』、シュプリンガー、2002年。
• ルディン、ウォルター。『数学解析の原理』第3版。マグロウヒル、1976年。
• スラマン、セオドア A.およびウッディン、W. ヒュー。「数理論理学：バークレー大学学部課程」。2006 年春。