整数シーケンス

数学において、整数列は整数の列（つまり、順序付けられたリスト）です。

整数列は、そのn番目の項に式を与えることによって明示的に指定することも、その項間の関係を与えることによって暗黙的に指定することもできます。たとえば、0、1、1、2、3、5、8、13、... という列 (フィボナッチ数列) は、0 と 1 から始めて、任意の 2 つの連続する項を追加して次の項を取得することによって形成されます。これは暗黙的な説明です ( OEISの列A000045 )。0、3、8、15、... という列は、 n番目の項について式n ²  − 1に従って形成されます。これは明示的な定義です。

あるいは、整数列は、列の要素が持ち、他の整数が持たない特性によって定義されることもあります。たとえば、n番目の完全数の式がなくても、与えられた整数が完全数( OEISの列A000396 ) であるかどうかを判断できます。

整数シーケンスが計算可能であるのは、 nが与えられたときに、すべてのn > 0 に対して n を計算するアルゴリズムが存在する場合です。計算可能な整数_{シーケンス}の集合は可算です。すべての整数シーケンスの集合は不可算(濃度は連続体の濃度に等しい) であるため、すべての整数シーケンスが計算可能であるとは限りません。

いくつかの整数列には定義がありますが、整数列が宇宙で定義可能であること、または絶対的な（モデルに依存しない）意味で定義可能であることが何を意味するのかを定義する体系的な方法はありません。

集合M がZFC 集合論の推移モデルであると仮定します。 M の推移性は、 M 内の整数と整数列が実際には整数と整数列であることを意味します。集合論の言語で、自由変数を 1 つ持ち、パラメータを持たない式 P ( x ) が存在し、その整数列についてはMで真であり、他のすべての整数列については M で偽である場合、整数列はMに対して定義可能な列です。このような各 M には、計算可能集合のチューリングジャンプをエンコードする列など、計算可能ではない定義可能な整数列が存在します。

ZFC の推移モデルMの中には、 M内のすべての整数シーケンスがMに対して定義可能なものもありますが、他のモデルでは、一部の整数シーケンスのみが定義可能です (Hamkins et al. 2013)。 M自体にMに対して定義可能なシーケンスの集合を定義する体系的な方法はなく、そのようなMの中にはその集合が存在しない場合もあります。同様に、 M内の整数シーケンスを定義する式の集合から、それらが定義する整数シーケンスへのマップはMでは定義できず、 Mにも存在しない場合があります。ただし、そのような定義可能性マップを持つモデルでは、モデル内の一部の整数シーケンスはモデルに対して定義できません (Hamkins et al. 2013)。

Mにすべての整数列が含まれている場合、 Mで定義可能な整数列の集合はMに存在し、可算かつMで可算になります。

正の整数のシーケンスは、各値を最大 1 回使用してシーケンス内の値の合計としてすべての正の整数を表現できる場合、 完全シーケンスと呼ばれます。

独自の名前を持つ整数シーケンスには次のものがあります。

• 定数再帰シーケンス
• 整数列のオンライン百科事典
  • OEIS シーケンスのリスト

• ハムキンス、ジョエル・デイビッド; リネツキー、デイビッド; ライツ、ジョナス (2013)、「集合論の点定義可能モデル」、Journal of Symbolic Logic、78 (1): 139–156、arXiv : 1105.4597、doi :10.2178/jsl.7801090、S2CID  43689192。

• Journal of Integer Sequences。記事はオンラインで無料でご覧いただけます。