Целочисленная последовательность - Integer sequence

Начало Последовательность Фибоначчи на здании в Гетеборг

В математика, целочисленная последовательность это последовательность (т.е. упорядоченный список) целые числа.

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

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

Примеры

Целочисленные последовательности, имеющие собственное имя, включают:

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

Целочисленная последовательность - это вычислимый последовательность если существует алгоритм, который, учитывая п, вычисляет ап, для всех п > 0. Набор вычислимых целочисленных последовательностей равен счетный. Набор всех целочисленных последовательностей бесчисленный (с участием мощность равно что континуума ), поэтому не все целочисленные последовательности вычислимы.

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

Предположим, что множество M это переходная модель из Теория множеств ZFC. Транзитивность M означает, что целые числа и последовательности целых чисел внутри M на самом деле являются целыми числами и последовательностями целых чисел. Целочисленная последовательность - это определяемый последовательность относительно M если существует формула п(Икс) на языке теории множеств, с одной свободной переменной и без параметров, что верно в M для этой целочисленной последовательности и false в M для всех остальных целочисленных последовательностей. В каждом таком Mсуществуют определяемые целочисленные последовательности, которые невозможно вычислить, например последовательности, кодирующие Прыжки Тьюринга вычислимых множеств.

Для некоторых переходных моделей M ZFC, каждая последовательность целых чисел в M определимо относительно M; для других - только некоторые целочисленные последовательности (Hamkins et al. 2013). Нет систематического способа определения в M сам набор последовательностей, определяемых относительно M и этот набор может даже не существовать в некоторых таких M. Аналогично, карта из набора формул, определяющих целочисленные последовательности в M к целочисленным последовательностям, которые они определяют, не определяется в M и может не существовать в M. Однако в любой модели, которая имеет такую ​​карту определяемости, некоторые целочисленные последовательности в модели не будут определяться относительно модели (Hamkins et al. 2013).

Если M содержит все целочисленные последовательности, тогда набор целочисленных последовательностей, определяемых в M будет существовать в M и быть счетным и счетным в M.

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

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

Смотрите также

использованная литература

  • Хэмкинс, Джоэл Дэвид; Линецкий, Давид; Рейц, Йонас (2013), «Точечно определяемые модели теории множеств», Журнал символической логики, 78 (1): 139–156, arXiv:1105.4597, Дои:10.2178 / jsl.7801090.

внешние ссылки