В математике целочисленная последовательность — это последовательность (т. е. упорядоченный список) целых чисел .
Целочисленная последовательность может быть указана явно, путем указания формулы для ее n -го члена, или неявно, путем указания связи между ее членами. Например, последовательность 0, 1, 1, 2, 3, 5, 8, 13, ... (последовательность Фибоначчи ) формируется путем начала с 0 и 1, а затем добавления любых двух последовательных членов для получения следующего: неявное описание (последовательность A000045 в OEIS ). Последовательность 0, 3, 8, 15, ... формируется в соответствии с формулой n 2 − 1 для n -го члена: явное определение.
В качестве альтернативы, целочисленная последовательность может быть определена свойством, которым обладают члены последовательности и не обладают другие целые числа. Например, мы можем определить, является ли данное целое число совершенным числом (последовательность A000396 в OEIS ), даже если у нас нет формулы для n -го совершенного числа.
Целочисленная последовательность вычислима, если существует алгоритм, который при заданном n вычисляет a n для всех n > 0. Множество вычислимых целочисленных последовательностей счетно . Множество всех целочисленных последовательностей несчетно (с мощностью, равной мощности континуума ), и поэтому не все целочисленные последовательности вычислимы.
Хотя некоторые целочисленные последовательности имеют определения, не существует систематического способа определить, что означает для целочисленной последовательности быть определяемой во вселенной или в каком-либо абсолютном (независимом от модели) смысле.
Предположим, что множество M является транзитивной моделью теории множеств ZFC . Транзитивность M подразумевает, что целые числа и целочисленные последовательности внутри M на самом деле являются целыми числами и последовательностями целых чисел. Целочисленная последовательность является определимой последовательностью относительно M, если существует некоторая формула P ( x ) на языке теории множеств с одной свободной переменной и без параметров, которая истинна в M для этой целочисленной последовательности и ложна в M для всех других целочисленных последовательностей. В каждом таком M существуют определимые целочисленные последовательности, которые не являются вычислимыми, например, последовательности, которые кодируют скачки Тьюринга вычислимых множеств.
Для некоторых транзитивных моделей M из ZFC каждая последовательность целых чисел в M определима относительно M ; для других только некоторые целочисленные последовательности являются определимыми (Hamkins et al. 2013). Не существует систематического способа определить в самой M множество последовательностей, определимых относительно M , и это множество может даже не существовать в некоторых таких M . Аналогично, отображение из множества формул, которые определяют целочисленные последовательности в M , в целочисленные последовательности, которые они определяют, неопределимо в M и может не существовать в M . Однако в любой модели, которая обладает такой картой определимости, некоторые целочисленные последовательности в модели не будут определимы относительно модели (Hamkins et al. 2013).
Если M содержит все целочисленные последовательности, то множество целочисленных последовательностей, определяемых в M, будет существовать в M и будет счетным, причем счетным в M .
Последовательность положительных целых чисел называется полной последовательностью, если каждое положительное целое число можно выразить в виде суммы значений в последовательности, используя каждое значение не более одного раза.
Целочисленные последовательности, имеющие собственное имя, включают: