Целочисленная последовательность
В математике целочисленная последовательность - это последовательность (т. Е. упорядоченный список) целых чисел.
Целочисленная последовательность может быть задана явно, давая формулу для ее n-го члена, или неявно, давая связь между ее членами. Например, последовательность 0, 1, 1, 2, 3, 5, 8, 13, ... ( последовательность Фибоначчи) формируется, начиная с 0 и 1, а затем добавляя любые два последовательных члена, чтобы получить следующий: неявное описание. Последовательность 0, 3, 8, 15, ... образуется по формуле n 2 − 1 для n-го члена: явное определение.
В качестве альтернативы целочисленная последовательность может быть определена свойством, которым обладают члены последовательности, а другие целые числа не обладают. Например, мы можем определить, является ли данное целое число совершенным числом, даже если у нас нет формулы для n-го совершенного числа.
Примеры[править]
Целочисленные последовательности, имеющие собственное имя, включают:
Изобилие чисел * Baum–Sweet sequence * Числа колокола Биномиальные коэффициенты Числа Кармайкла * Каталонские числа * Составные числа * Дефицитные числа * Числа Эйлера Четные и нечетные числа * Факториальные числа * Числа Фибоначчи * Слово Фибоначчи * Фигурные числа * Последовательность Голомба Счастливые числа * Очень сложные числа * Высокоточные числа * Домашние простые числа * Гиперперфектные числа Последовательность жонглеров * Последовательность Колакоски * Счастливые числа * Числа Лукаса * Числа Моцкина Натуральные числа * Падованские числа * Номера разделов * Совершенные числа * Простые числа * Псевдопростые числа Последовательность Рекамана * Обычная последовательность складывания бумаги Последовательность Рудина–Шапиро * Полуперфектные числа Полупростые числа * Суперперфектные числа * Thue–Morse sequence * Числа Улама * Странные числа * Число Вольстенхольма
Вычислимые и определяемые последовательности[править]
Целочисленная последовательность является вычислимой последовательностью, если существует алгоритм, который при заданном n вычисляет 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.
Полные последовательности[править]
Последовательность положительных целых чисел называется полной последовательностью, если каждое положительное целое число может быть выражено как сумма значений в последовательности, используя каждое значение не более одного раза.