Перегляд вихідного коду сторінки Послідовність цілих чисел

[[Послідовність цілих чисел]]&nbsp;— у математиці&nbsp;— це [[Послідовність (математика)|впорядкований список]] [[Цілі числа|цілих чисел]].

''Послідовність цілих чисел'' можна задати в ''явному вигляді'' формулою ''n''-го члена, або ''неявно'', за допомогою відношення між її членами.

Наприклад, [[послідовність Фібоначчі]] (0, 1, 1, 2, 3, 5, 8, 13, …) можна задати так:

* неявно&nbsp;— [[Рекурентне співвідношення|рекурентним співвідношенням]]: <math>\mathcal F_0=0,~\mathcal F_1=1,~\mathcal F_{n+2}=\mathcal F_{n+1}+\mathcal F_n</math>;
* явно&nbsp;— [[Послідовність Фібоначчі#Формула Біне|формулою Біне]]: <math>\mathcal F_n=\frac{(1+\sqrt5)^n-(1-\sqrt5)^n}{2^n\sqrt5}</math>.

== Приклади ==
До цілочисельних послідовностей, які отримали власні назви, належать:
{{div col|colwidth=20em}}
* [[Надлишкові числа]]
* {{нп|Послідовність Баума — Світа||en|Baum–Sweet sequence}}
* [[Число Белла]]
* [[Біноміальний коефіцієнт]]
* [[Число Кармайкла]]
* [[Число Каталана]]
* [[Складене число]]
* [[Недостатні числа]]
* [[Числа Ейлера]]
* [[Парність (математика)|Парні та непарні числа]]
* [[Факторіал]]ьні числа
* [[Послідовність Фібоначчі]]
* {{нп|Слово Фібоначчі||en|Fibonacci word}}
* [[Фігурні числа]]
* {{нп|Послідовність Ґоломба||en|Golomb sequence}}
* [[Щасливе число]]
* {{нп|Високототієнтне число||en|Highly totient number}}
* [[Надскладене число]]
* {{нп|Гіпердосконале число|||Hyperperfect number}}
* {{нп|Послідовність жонглера||en|Juggler sequence}}
* {{нп|Послідовність Колакоскі||en|Kolakoski sequence}}
* [[Щасливе число]]
* [[Число Люка]]
* [[Число Моцкіна]]
* {{нп|Послідовність Падована||en|Padovan sequence}}
* [[Розбиття числа]]
* [[Досконале число]]
* [[Напівдосконале число]]
* [[Просте число]]
* [[Псевдопросте число]]
* {{нп|Регулярна послідовність складання паперу||en|Regular paperfolding sequence}}
* {{нп|Послідовність Рудіна&nbsp;— Шапіро||en|Rudin–Shapiro sequence}}
* [[Напівдосконале число]]
* [[Напівпросте число]]
* [[Високонадлишкове число]]
* [[Послідовність Морзе — Туе]]
* [[Число Уляма]]
* {{нп|Дивне число||en|Weird number}}
* {{нп|Число Волстенголма||en|Wolstenholme number}}
{{div col end}}

== Обчислювані та визна́чні послідовності ==
Цілочисельна послідовність є '''[[Теорія обчислюваності|обчислюваною]] послідовністю''', якщо існує алгоритм, який за заданим ''n'' обчислює ''a''<sub>''n''</sub> для всіх ''n''&gt;0. Набір обчислюваних цілих послідовностей є [[Зліченна множина|незліченним]]. Множина всіх цілих послідовностей є незліченною (з [[Потужність множини|потужністю]], що дорівнює потужності [[Континуум (теорія множин)|континууму]]), і тому не всі цілі послідовності є обчислюваними.

Хоча деякі цілочисельні послідовності мають визначення, не існує систематичного способу визначення того, що означає для цілочисельної послідовності бути визна́чною у Всесвіті або в будь-якому абсолютному (незалежному від моделі) сенсі.

Нехай множина ''M'' є {{Нп|Транзитивна модель|транзитивною моделлю|en|Transitive model}} з [[Теорія множин Цермело — Френкеля|теорії множин ZFC]]. Транзитивність ''M'' передбачає, що цілі числа і цілі послідовності всередині ''M'' є фактично цілими числами й послідовностями цілих чисел. Цілочисельна послідовність є '''{{Не перекладено|Визначна множина|визна́чною|en|Definable set}}''' '''послідовністю відносно ''M''''', якщо існує деяка формула ''P''(''x'') мовою теорії множин, з однією вільною змінною та без параметрів, яка є істинною в ''M'' для даної цілої послідовності та хибною в ''M'' для всіх інших цілих послідовностей. У кожній такій ''M'' існують визна́чні цілі послідовності, які не є обчислюваними, такі як послідовності, які кодують {{Нп|Стрибок Тюрінга|стрибки Тюрінга|en|Turing jump}} обчислюваних множин.

Для деяких транзитивних моделей ''M'' у ZFC кожна послідовність цілих чисел у ''M'' визна́чна відносно ''M''; для інших визна́чними є лише деякі цілі послідовності (Hamkins et al. 2013). Немає систематичного способу визначити в M самого набору послідовностей, визна́чних відносно ''M,'' і цього набору може навіть не існувати в деяких ''M''. Аналогічно, відображення з набору формул, які визначають цілочисельні послідовності в М у цілочисельні послідовності, які вони визначають, може не бути визна́чним в М і може не існувати в ''M''. Проте, в будь-якій моделі, що має таке відображення визна́чності, деякі цілочисельні послідовності в моделі не будуть визна́чними відносно моделі (Hamkins et al. 2013).

Якщо ''M'' містить всі цілочисельні послідовності, то множина цілочисельних послідовностей, визначених в ''M'', існуватиме в ''M'' і буде зліченною і зліченною в ''M''.

== Повні послідовності ==
Послідовність цілих чисел називається '''повною послідовністю''', якщо кожне натуральне число можна виразити як суму значень членів послідовності, використовуючи кожне значення не більше одного разу.

== Див. також ==
* [[Енциклопедія послідовностей цілих чисел]]
* {{нп|Список послідовностей OEIS||en|List of OEIS sequences|}}

== Література ==
* {{Citation|last=Hamkins|first=Joel David|last2=Linetsky|first2=David|last3=Reitz|first3=Jonas|title=Pointwise Definable Models of Set Theory|arxiv=1105.4597|journal=Journal of Symbolic Logic|volume=78|issue=1|pages=139–156|year=2013|doi=10.2178/jsl.7801090}}.

== Посилання ==
{{Commonscat|Integer sequences}}
* [http://www.cs.uwaterloo.ca/journals/JIS/ Journal of Integer Sequences] {{Webarchive|url=https://web.archive.org/web/20130523054156/http://www.cs.uwaterloo.ca/journals/JIS/ |date=23 травня 2013 }}. Статті доступні в Інтернеті.

{{Послідовності й ряди}}
{{Бібліоінформація}}
[[Категорія:Цілочисельні послідовності]]