定義可能集合

定義可能集合とは

数理論理学における定義可能集合（Definable set）は、特定の構造における要素を示すための重要な概念です。これらの集合は、ある構造の台集合上のn-項関係として定義されます。つまり、その要素が構造の一階言語で表現される式を満たすときに、「定義可能」であるとされます。

1. 定義

一階の言語を $\mathcal{L}$、その構造を $\mathcal{M}$ とします。ここで、 $\mathcal{M}$ は、台集合が $M$ である構造を指します。 $X$ は $M$ の固定された部分集合で、 $m$ は自然数です。集合 $A\subseteq M^{m}$ が定義可能であるとは、以下の条件を満たす式 $φ[x_{1}, ext{...},x_{m},y_{1}, ext{...},y_{n}]$ と、 $b_{1}, ext{...},b_{n} \in X$が存在することを意味しています。
要するに、すべての $a_{1}, ext{...},a_{m}\in M$ に対して、 $(a_{1}, ext{...},a_{m}) \in A$ であるとき、かつその時だけ、 $\mathcal{M} \models \varphi[a_{1},\text{...},a_{m},b_{1},\text{...},b_{n}]$ が成り立つとき、 $A$ は定義可能とされます。

この定義において、パラメータなしでの定義可能性は、 $X$ を空集合に置き換えることで理解されます。関数の定義には、このグラフが定義可能であることを求められます。また、単一の要素が定義可能であるためには、単元集合 $\{a\}$も同様に定義可能である必要があります。

2. 例

自然数の構造

自然数 $\mathcal{N} = (\mathbb{N}, <)$ の場合、すべての自然数はパラメータ無しで定義可能です。具体的には、数 $0$ は、式 $
eg \exists y(y < x)$ によって定義されます。一方で、任意の自然数 $n > 0$ は、次のような式で定義可能です。

\[ \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}))) \]

対照的に、整数の構造 $\mathcal{Z} = (\mathbb{Z}, <)$ では、パラメータ無しで特定の整数を定義することはできません。この構造では、任意の整数が平行移動で他の整数と対応できるため、特定の整数を定義することは不可能です。 $\mathcal{Z}$の要素のn-つ組は、無限に定義可能であり、特に $\{(a,b) \mid a-b=m\}$ のように定義されることができます。

実数の体

実数の体 $\mathcal{R} = (\mathbb{R}, 0, 1, +, \cdot)$ においては、平方根を伴う式を用いることで非負の実数集合を定義可能とすることができます。この場合は、 $\varphi = \exists y(y \cdot y \equiv x)$ で表される式が非負性を示します。従って、任意の実数 $a$ が非負であるかどうかは、実数構造において $\mathcal{R} \models \varphi[a]$ が成り立つかどうかで判別できます。さらに、加法逆元の定義と組み合わせることで、通常の順序を定義することができ、これが構造の拡大として知られています。

3. 定義可能集合の不変性

定義可能集合には、自己同型の下で保たれる性質があります。この性質により、与えられた構造の定義可能な部分集合を分類することが可能です。具体的には、自己同型が元の構造と一致している場合、元の集合が定義可能である限り、変換された集合も定義可能であるとされます。

4. 結論

定義可能集合は、数理論理学の基本的な要素であり、その性質はさまざまな構造の理解に役立ちます。特に自己同型の下での不変性は、これらの集合を評価する際の重要な視点を提供します。具体例を通じて、これらの概念を理解することができ、さらにその応用について考察が可能です。

もう一度検索