算術集合

数理論理学において、算術集合（または算術集合）とは、一階ペアノ算術の式で定義できる自然数の集合である。算術集合は算術階層によって分類される。

定義は、ゲーデル数を使用して集合の要素を表し、対応するゲーデル数の集合が算術的である場合に A のサブセットを算術的であると宣言することにより、任意の可算集合A (たとえば、 n組の整数の集合、有理数の集合、何らかの形式言語の式の集合など)に拡張できます。

関数のグラフが算術集合である 場合、その関数は算術的に定義可能と呼ばれます。${\displaystyle f:A\subseteq \mathbb {N} ^{k}\to \mathbb {N} }$ ${\displaystyle f}$

実数は、それより小さい有理数の集合が算術的である場合、算術的と呼ばれます。複素数は、その実部と虚部の両方が算術的である場合、算術的と呼ばれます。

正式な定義

自然数の集合Xが算術的または算術的に定義可能であるとは、ペアノ算術の言語において一階述語論理式 φ( n ) が存在し、各数nがXに含まれることと、算術の標準モデルにおいてφ( n ) が成立することとが同値であることを意味する。同様に、 k項関係が算術的であるとは、自然数のk組すべてに対して成立する論理式が存在することを意味する。 ${\displaystyle R(n_{1},\ldots,n_{k})}$ ${\displaystyle \psi (n_{1},\ldots ,n_{k})}$ ${\displaystyle R(n_{1},\ldots,n_{k})\iff \psi (n_{1},\ldots,n_{k})}$ ${\displaystyle (n_{1},\ldots,n_{k})}$

関数のグラフが算術的な ( k +1) 項関係 である場合、その関数は算術的であると呼ばれます。${\displaystyle f:\subseteq \mathbb {N} ^{k}\to \mathbb {N} }$

集合Aが、集合Bを集合パラメータとして 持つ算術式によって定義可能な場合、その集合Aは集合Bにおいて算術的であると言われます。

例

• すべての素数の集合は算術的です。
• すべての再帰的に列挙可能な集合は算術的です。
• すべての計算可能な関数は算術的に定義可能です。
• 停止問題をエンコードするセットは算術的です。
• チャイティン定数 Ωは算術実数です。
• タルスキの定義不可能定理は、第一階算術の真の公式の集合（のゲーデル数）が算術的に定義できないことを示しています。

プロパティ

• 算術集合の補集合は算術集合である。
• 算術集合のチューリングジャンプは算術集合です。
• 算術集合の集合は可算であるが、算術集合の列は算術的に定義できない。したがって、m がn番目の算術述語の要素である場合に限り真となる算術式 φ( n , m ) は存在しない。

実際、このような式はすべての有限チューリングジャンプの決定問題を記述するため、0 ^{(ω)に属しますが、これは}第 1 階算術階層に属していないため、第 1 階算術では形式化できません。

• 実算術数の集合は可算で、稠密であり、有理数の集合と順序同型である。

暗黙的な算術集合

それぞれの算術集合には、特定の数がその集合に含まれるかどうかを示す算術式があります。定義可能性の別の概念では、特定の数がその集合に含まれるかどうかではなく、集合自体が何らかの算術的性質を満たすかどうかを示す算術式が考えられます。

自然数の集合Yは、 Yをパラメータとして用いる算術式によって定義可能である場合、暗黙的に算術的であるか、暗黙的に算術的に定義可能である。つまり、ペアノ算術の言語において、自由数変数を持たず、新たな集合パラメータZと集合帰属関係を持つ式が存在し、 Yが唯一の集合Zであって、かつそれが成り立つような場合である。 ${\displaystyle \theta (Z)}$ ${\displaystyle \in}$ ${\displaystyle \theta (Z)}$

あらゆる算術集合は暗黙的に算術的である。Xがφ( n )によって算術的に定義されるならば、それは暗黙的に次の式によって定義される。

${\displaystyle \forall n[n\in Z\Leftrightarrow \phi (n)]}$ 。

しかし、暗黙的に算術的な集合のすべてが算術的であるとは限りません。特に、一階算術の真理集合は暗黙的に算術的ですが、算術的ではありません。

参照

• 算術階層
• 計算可能集合
• 計算可能な数

さらに読む

• ハートリー・ロジャース・ジュニア(1967).再帰関数の理論と実効計算可能性.マグロウヒル. OCLC  527706