Целочисленная последовательность
Целочисленная последовательность — это последовательность (т.е., упорядоченный список) целых чисел.
Целочисленная последовательность может быть задана явно путём задания формулы для её n-го члена, либо неявно путём задания связи между членами. Например, последовательность 0, 1, 1, 2, 3, 5, 8, 13, ... (последовательность Фибоначчи) формируется, начиная с 0 и 1, путём сложения двух последовательных членов для получения следующего (неявное задание) (последовательность A000045 в OEIS). Последовательность 0, 3, 8, 15, ... формируется по формуле n2 − 1 для n-го члена (явное задание).
Или же последовательность целых чисел может быть задана свойством, которым обладают члены этой последовательности, но не обладают другие целые числа. Например, мы можем определить, является ли данное целое число совершенным (последовательность A000396 в OEIS), даже если у нас нет формулы для n-го совершенного числа.
Вычислимые и определимые последовательности
Целочисленная последовательность вычислима, если существует алгоритм, который по заданному n вычисляет an для всех n > 0. Число вычислимых целочисленных последовательностей счётно. Множество всех целочисленных последовательностей несчётно (мощность равна мощности континуума), так что не все целочисленные последовательности вычислимы.
Хотя некоторые целочисленные последовательности имеют определения, не существует систематического способа определить, что означает «определимая целочисленная последовательность» во Вселенной или в каком-либо абсолютном (не зависящем от модели) смысле.
Предположим, что множество M является транзитивной моделью теории множеств ZFC[1]. Целочисленная последовательность является определимой относительно M, если существует некоторая формула P(x) на языке теории множеств с одной свободной переменной и без параметров, которая истинна в M для данной целочисленной последовательности и ложна в M для всех других целочисленных последовательностей. В каждой такой модели M существуют определимые целочисленные последовательности, которые не являются вычислимыми.
Полная последовательность
Последовательность положительных целых чисел называется полной последовательностью, если любое положительное целое число может быть выражено как сумма значений из последовательности, используя каждое значение максимум один раз.
Примеры
Последовательности, имеющие собственные имена:
- Последовательность Баума — Свита
- Числа Белла
- Биномиальные коэффициенты
- Высокототиентные числа
- Гиперсовершенные числа
- Последовательность Голомба
- Домашние простые
- Последовательность жонглёра
- Избыточные числа
- Числа Кармайкла
- Числа Каталана
- Последовательность Колакоски
- Числа Люка
- Последовательность Морса — Туэ
- Числа Моцкина
- Натуральне числа
- Недостаточные числа
- Последовательность Падована
- Полусовершенные числа
- Полупростые числа
- Практичные числа
- Простые числа
- Простые числа Вольстенхольма
- Псевдопростые числа
- Последовательность регулярного складывания бумаги
- Последовательность Рекамана
- Последовательность Рудина — Шапиро
- Числа разбиения
- Сверхсоставные числа
- Совершенные числа
- Составные числа
- Странные числа
- Суперсовершенные числа
- Счастливые числа
- Счастливые числа
- Треугольные числа
- Числа Улама
- Факториалы
- Фигурные числа
- Чётные и нечётные числа
- Слова Фибоначчи
- Числа Фибоначчи
- Эйлеровы числа
См. также
Примечания
- ↑ ДРАГАЛИН, ЛЮБЕЦКИЙ, ФУКСОН, 1971, с. 1264.
Литература
- Joel David Hamkins, David Linetsky, Jonas Reitz. Pointwise Definable Models of Set Theory // Journal of Symbolic Logic. — 2013. — Т. 78, вып. 1. — С. 139–156. — doi:10.2178/jsl.7801090. — arXiv:1105.4597.
- А. Г. ДРАГАЛИН, В. А. ЛЮБЕЦКИЙ, В. И. ФУКСОН. ОПРЕДЕЛИМЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ СЧЕТНЫХ ОРДИНАЛОВ // Доклады Академии наук СССР. — 1971. — Т. 196, № 6.
Цитата: «Модель ZF мы назовем стандартной, если -отношение в модели является естественным отношением принадлежности между элементами модели, и транзитивной, если все элементы элементов модели сами являются элементами модели»
Ссылки
- Journal of Integer Sequences. Articles are freely available online.