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