Послідовність цілих чисел
Послідовність цілих чисел — у математиці — це впорядкований список цілих чисел.
Послідовність цілих чисел можна задати в явному вигляді формулою n-го члена, або неявно, за допомогою відношення між її членами.
Наприклад, послідовність Фібоначчі (0, 1, 1, 2, 3, 5, 8, 13, …) можна задати так:
- неявно — рекурентним співвідношенням: ;
- явно — формулою Біне: .
Приклади
До цілочисельних послідовностей, які отримали власні назви, належать:
- Надлишкові числа
- Послідовність Баума — Світа
- Число Белла
- Біноміальний коефіцієнт
- Число Кармайкла
- Число Каталана
- Складене число
- Недостатні числа
- Числа Ейлера
- Парні та непарні числа
- Факторіальні числа
- Послідовність Фібоначчі
- Слово Фібоначчі
- Фігурні числа
- Послідовність Ґоломба
- Щасливе число
- Високототієнтне число
- Надскладене число
- Гіпердосконале число
- Послідовність жонглера
- Послідовність Колакоскі
- Щасливе число
- Число Люка
- Число Моцкіна
- Послідовність Падована
- Розбиття числа
- Досконале число
- Напівдосконале число
- Просте число
- Псевдопросте число
- Регулярна послідовність складання паперу
- Послідовність Рудіна — Шапіро
- Напівдосконале число
- Напівпросте число
- Супердосконале число
- Послідовність Морзе — Туе
- Число Уляма
- Дивне число
- Число Волстенголма
Обчислювані та визна́чні послідовності
Цілочисельна послідовність є обчислюваною послідовністю, якщо існує алгоритм, який за заданим 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. Проте, в будь-якій моделі, що має таке відображення визна́чності, деякі цілочисельні послідовності в моделі не будуть визна́чними відносно моделі (Hamkins et al. 2013).
Якщо M містить всі цілочисельні послідовності, то множина цілочисельних послідовностей, визначених в M, існуватиме в M і буде зліченною і зліченною в M.
Повні послідовності
Послідовність цілих чисел називається повною послідовністю, якщо кожне натуральне число можна виразити як суму значень членів послідовності, використовуючи кожне значення не більше одного разу.
Див. також
- Енциклопедія послідовностей цілих чисел
- Список послідовностей OEIS
Література
- Hamkins, Joel David; Linetsky, David; Reitz, Jonas (2013). Pointwise Definable Models of Set Theory. Journal of Symbolic Logic 78 (1): 139–156. arXiv:1105.4597. doi:10.2178/jsl.7801090..