整数列

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

整数列は、n番目の項の式を与えることで明示的に指定することも、項間の関係を与えることで暗黙的に指定することもできます。たとえば、数列 0, 1, 1, 2, 3, 5, 8, 13, ... (フィボナッチ数列) は、0 と 1 から始めて、連続する 2 つの項を足し合わせて次の項を得ることで形成されます。これは暗黙的な記述です( OEISの数列A000045 )。数列 0, 3, 8, 15, ... は、次の式に従って形成されます。  ${\displaystyle n^{2}-1}$n番目の項については、明示的な定義を示します。

あるいは、整数列は、その列の要素が持ち、他の整数が持たない性質によって定義される場合もある。例えば、n番目の完全数を求める公式がなくても、与えられた整数が完全数であるかどうか（OEISのA000396列）を判定することができる。

整数列は、与えられた条件を満たすアルゴリズムが存在する場合に計算可能である。${\displaystyle n}$計算します${\displaystyle a_{n}}$すべての${\displaystyle n>0}$計算可能な整数列の集合は可算集合である。すべての整数列の集合は非可算集合（連続体の濃度に等しい）であり、したがってすべての整数列が計算可能であるとは限らない。

整数列の中には定義を持つものもあるが、整数列が宇宙において、あるいは絶対的な（モデルに依存しない）意味で定義可能であるとはどういうことかを体系的に定義する方法はない。

セットを仮定します${\displaystyle M}$はZFC 集合論の推移的モデルである。${\displaystyle M}$整数と整数列が内部にあることを意味します${\displaystyle M}$は実際には整数と整数のシーケンスです。整数のシーケンスは、${\displaystyle M}$何らかの公式が存在する場合${\displaystyle P(x)}$集合論の言葉で言えば、自由変数が 1 つでパラメータがない、これは次の場合に当てはまります。${\displaystyle M}$その整数列に対して、そして偽の場合${\displaystyle M}$他のすべての整数列について。${\displaystyle M}$計算可能でない定義可能な整数列も存在する。例えば、計算可能な集合のチューリングジャンプを符号化する数列などである。

いくつかの推移的モデルの場合${\displaystyle M}$ZFC の整数列は、${\displaystyle M}$は、${\displaystyle M}$; 他の場合、一部の整数列のみが該当します。 を体系的に定義する方法はありません${\displaystyle M}$それ自体は、${\displaystyle M}$そして、そのような集合は、場合によっては存在しないかもしれない。${\displaystyle M}$同様に、整数列を定義する式のセットからのマップは${\displaystyle M}$それらが定義する整数列は定義できません${\displaystyle M}$存在しない場合もある${\displaystyle M}$しかし、そのような定義可能性マップを持つモデルでは、モデル内のいくつかの整数列はモデルに対して定義できない。^{[ 1 ]}

もし${\displaystyle M}$すべての整数列を含み、次に定義可能な整数列の集合${\displaystyle M}$存在する${\displaystyle M}$そして、数えられるものであり、数えられるものである${\displaystyle M}$。

正の整数の列は、すべての正の整数が、その列に含まれる各値を最大で1回だけ使用して、それらの値の和として表せる場合、完全列と呼ばれる。

固有の名前を持つ整数列には、以下のようなものがあります。

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

• Hamkins, Joel David; Linetsky, David; Reitz, Jonas (2013)、「点ごとの定義可能な集合論モデル」、Journal of Symbolic Logic、78 (1): 139–156、arXiv : 1105.4597、doi : 10.2178/jsl.7801090、S2CID 43689192 。

• 整数列ジャーナル。記事はオンラインで無料で閲覧できます。