Введение

В математике целочисленная последовательность — это последовательность (то есть упорядоченный список) целых чисел. Целочисленная последовательность может быть задана явно, путем предоставления формулы для её n-го члена, или неявно, путем задания соотношения между её членами. Например, последовательность 0, 1, 1, 2, 3, 5, 8, 13 (последовательность Фибоначчи) формируется, начиная с 0 и 1, а затем путем сложения любых двух последовательных членов для получения следующего: неявное описание. Последовательность 0, 3, 8, 15 формируется в соответствии с формулой n² − 1 для n-го члена: явное определение. Кроме того, целочисленная последовательность может быть определена свойством, которым обладают члены последовательности, а другие целые числа не обладают. Например, мы можем определить, является ли данное целое число совершенным, даже не имея формулы для n-го совершенного числа.

Вычислимые и определяемые последовательности

Целая последовательность является вычислимой, если существует алгоритм, который, получив на вход n, вычисляет an для всех 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.

Полные последовательности

Последовательность положительных целых чисел называется полной, если любое положительное целое число может быть представлено в виде суммы элементов этой последовательности, используя каждый элемент не более одного раза.