等価な定式化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/23 10:02 UTC 版)
以下は、自然数の集合 S について同じ特性を表現したものである。 半決定可能性:集合 S は帰納的可算である。すなわち、S はある部分再帰関数の定義域である。 次のような部分再帰関数 f が存在する: f ( x ) = { 0 if x ∈ S undefined/does not halt if x ∉ S {\displaystyle f(x)=\left\{{\begin{matrix}0&{\mbox{if}}\ x\in S\\{\mbox{undefined/does not halt}}\ &{\mbox{if}}\ x\notin S\end{matrix}}\right.} 可算性:集合 S は、部分再帰関数の値域である。 集合 S は、全体再帰関数の値域であるか空である。S が無限の場合、その関数は単射でもよい。 集合 S は、原始再帰関数の値域であるか空である。S が無限であっても、単射とはならない。 ディオファントス方程式:次のような整数係数の多項式 p があり、変数 x, a, b, c, d, e, f, g, h, i の値域が自然数全体に及んでいる。 x ∈ S ⇔ ∃ a , b , c , d , e , f , g , h , i ( p ( x , a , b , c , d , e , f , g , h , i ) = 0 ) . {\displaystyle x\in S\Leftrightarrow \exists a,b,c,d,e,f,g,h,i\ (p(x,a,b,c,d,e,f,g,h,i)=0).} 整数群から整数群への多項式があり、集合 S はその値域の非負数だけを正確に含む。 最後のは最初の定義から単純に導かれるものではないが、ヒルベルトの第10問題を否定的に解決する過程でユーリ・マチャセビッチが発見した。ディオファントス集合は再帰理論に先行しているため、歴史的にはこれが帰納的可算集合の最初の定義であった（ただし、これらが同じものを表していると分かったのは帰納的可算集合が登場してから30年以上も後のことである）。上記の式における束縛変数の個数はこれまでのところ最小とされているもので、もっと少ない個数でディオファントス集合を表せる可能性はある。
※この「等価な定式化」の解説は、「帰納的可算集合」の解説の一部です。
「等価な定式化」を含む「帰納的可算集合」の記事については、「帰納的可算集合」の概要を参照ください。
- 等価な定式化のページへのリンク
