集合Ｓがディオファントス的の意味を教えて下さい。

質問

定義
自然数Ｎ個の組の集合Ｓが”ディオファントス的である”とは、
整数係数の多項式Ｐ (x1, x2, ..., xn, y1, y2, ..., ym) があって、
集合Ｓは (x1, x2, ..., xn) を含む
＜＝＞
自然数の組 (y1, y2, ..., ym)
があり、P (x1, x2, ..., xn, y1, y2, ..., yn) ＝０となることである
と定義する。

とありますが、
理解出来ません。

わかる方、
よりわかりやすく教えて下さい。

回答No.1

stomachman · ベストアンサー

Ｐ (x1, x2, ..., xn, y1, y2, ..., ym) という表記のxとyの区別の意味が不明瞭です．この定義より前に，整数係数多項式P(...)の(...)内の部分の意味・約束事が決めてあるはずで，それを引用してくれなくちゃいけません．具体的には
(a) y1,...., ymはx1, ...., xnと同じく変数なのか（つまり，Pとは，整数係数多項式であって，変数がn+m個ある）
(b) y1,...., ymは係数や指数を表すパラメータなのか(つまり，Pとは，パラメータy1,...,ymを含む多項式であって，y1,...ymに具体的に自然数を代入すれば整数係数多項式になるような式）
どっちなのかがはっきりしない.

　ま，(a), (b)いずれであるにせよ，Sは

S={<x1,....,xn> | x1,...,xnは自然数，かつ，∃y1 .... ∃ym (y1,...ymは自然数，かつ，P(x1,....,xn,y1,...,ym)=0) }

という集合である．

　　言葉で言うと，
まず，多項式P(x1,...,xn,y1,...,ym)をひとつ決めた．このPに対して定義されるディオファントス的な集合Sとは，自然数n個(Nジャナイダロ）の組<x1,x2,...,xn>の集合であって，
(1)この多項式Pに使われているy1, y2, .... , ymに自然数をうまく割り当てて，その結果<x1, ..., xn>が方程式P=0の自然数解になるようにできるなら，<x1, ..., xn>はSの要素である．
(2) この多項式Pに使われているy1, y2, .... , ymに自然数をどう割り当てても<x1, ..., xn>が方程式P=0の自然数解にならないのならば，<x1, ..., xn>はSの要素ではない．
これらの条件を両方満たす集合である．

　具体例として，たとえばP(x,y) = x^2 - yに対するディオファントス的な集合Sはどうなるか．
どんな自然数xについても，yにx^2を割り当てれば（つまりy=x^2にすれば）P(x,y) =0が満たせる．だから，どんなxもSの要素である．つまりSはすべての自然数の集合である．

　また，たとえばP(x,y) = x^2 + y^2 - 25 に対するディオファントス的な集合Sはどうなるか．
方程式x^2 + y^2 = 25の自然数解は <x,y>=<0,5>, <5,0>, <3,4>, <4,3>の４通りしかない．
すると，x=0のときにはyに5を割り当てればP=0を満たせる．x=3のときにはyに4を割り当てればP=0を満たせる．x=5のときにはyに0を割り当てればP=0を満たせる．x=4のときにはyに3を割り当てればP=0を満たせる.　しかし，それ以外のxについては，yにどんな自然数を割り当ててもP=0を満たす事は出来ない．
なので，S={0,5,3,4}である．

　この話は，おそらく計算理論における枚挙可能性定理の文脈で出てきたものと思われるが，うーむ，この程度の記述が読みとれない人には，計算理論はごっつ難しいと思います．まずは基本的スキルとして「∀と∃の使い方」をしっかり練習する必要があると思う．がんばれー