整数列
数学における整数列（せいすうれつ、英: integer sequence, sequence of integers）は、整数からなる数列（数の順番付けられた並び）を言う。
整数列を特定する方法は、その第 n-項を与える「陽」(explicit) な仕方や、それらの項の間の関係性を与える「陰」(implicit) な仕方などがある。例えばフィボナッチ数列 0, 1, 1, 2, 3, 5, 8, 13, … は「0, 1 から始まって、必ず連続する二つの項の和が次の項になっている」という陰伏的な記述ができる。陽な記述の仕方の例として、「第 n-項が n2 − 1 で与えられる」数列は 0, 3, 8, 15, … のように書ける。
もっと別な特定の仕方として、その数列に属する数は持っているけれどもそうではない整数は持っていないような性質を与えるという方法がある。例えば、与えられた整数が完全数であるかどうかは（n 番目の完全数を表す公式を知らなくとも）決定することができる。
例
[編集]整数列の中でも特別な名前のついているものをいくつか挙げる:
計算可能列と決定可能列
[編集]整数列が計算可能であるとは、任意の n > 0 に対して、n が与えられれば an を計算するアルゴリズムが存在するときに言う。計算可能整数列全体の成す集合は可算である。一方、整数列全体の成す集合は非可算（実はその濃度は連続体濃度 ב1）であるから、どの整数列でも計算可能というわけにはいかない。
整数列の中には定義を持つものはあるけれども、普遍的にあるいは絶対的な（つまりモデルに依存しない）意味で整数列が定義可能であるということの意味を定める系統的な方法は存在しない。
集合 M が ツェルメロ–フレンケル集合論 の推移モデル であると仮定する。M の推移性は M の内部での整数および整数列が実際に整数および整数列となることを含意する。整数列が M に関して (relative to M) 定義可能であるとは、考えている集合論の言葉で適当な（自由項が一つでパラメータのない）条件式 P(x)が存在して、考えている整数列に対しては M 内で真かつそうでない整数列に対しては M 内で偽となるようにできるときに言う。そのような M の何れにしても、決定可能だが計算可能でない数列というものが存在する（例えば、チューリングジャンプをエンコードする整数列など）。
ZFC の適当な推移モデル M に対して、M 内の任意の整数列が M に関して定義可能となるが、それ以外の場合には一部の整数列しかそのモデルに関して定義可能にならない[1]。M それ自身を M に関する定義可能列全体の成す集合と定める体系的な方法はなく、またそのような集合が適当な M の中にさえ存在しない可能性もある。同様に、M の中で整数列を定義する条件式全体の成す集合からそれら条件式の定義する数列全体の成す集合への写像は M の中で定義可能でなく、また M の中に存在しないかもしれない。しかしながら、そのような決定可能性写像を備えた任意のモデルにおいて、そのモデル内の整数列でそのモデルに関して決定可能でないものが存在する[1]。
M が全ての整数列を含むならば、M 内の決定可能整数列全体の成す集合は M 内に存在して可算かつ M 内で可算である。
完全数列
[編集]正の整数列が完全数列（完備数列）であるとは、任意の正整数がその数列の適当な項（有限部分列）の和（ただし一つの項は一度しか使ってはならない）として表されるときに言う。
関連項目
[編集]- オンライン整数列大辞典 (On-Line Encyclopedia of Integer Sequences)
参考文献
[編集]- Hamkins, Joel David; Linetsky, David; Reitz, Jonas (2013), “Pointwise Definable Models of Set Theory”, Journal of Symbolic Logic 78 (1): 139–156, arXiv:1105.4597, doi:10.2178/jsl.7801090.
外部リンク
[編集]
- Journal of Integer Sequences. Articles are freely available online.
- Weisstein, Eric W. "Integer Sequence". mathworld.wolfram.com (英語).
- Definition:Integer Sequence at ProofWiki
