Послідовність цілих чисел

Послідовність цілих чисел — у математиці — це впорядкований список цілих чисел.

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

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

  • неявно — рекурентним співвідношенням: ;
  • явно — формулою Біне: .

ПрикладиРедагувати

До цілочисельних послідовностей, які отримали власні назви, належать:

Обчислювані та визна́чні послідовностіРедагувати

Цілочисельна послідовність є обчислюваною послідовністю, якщо існує алгоритм, який за заданим n обчислює an для всіх n>0. Набір обчислюваних цілих послідовностей є незліченним. Множина всіх цілих послідовностей є незліченною (з потужністю, що дорівнює потужності континууму), і тому не всі цілі послідовності є обчислюваними.

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

Нехай множина M є транзитивною моделлю[en] з теорії множин ZFC. Транзитивність M передбачає, що цілі числа і цілі послідовності всередині M є фактично цілими числами й послідовностями цілих чисел. Цілочисельна послідовність є визна́чною[en] послідовністю відносно M, якщо існує деяка формула P(x) мовою теорії множин, з однією вільною змінною та без параметрів, яка є істинною в M для даної цілої послідовності та хибною в M для всіх інших цілих послідовностей. У кожній такій M існують визна́чні цілі послідовності, які не є обчислюваними, такі як послідовності, які кодують стрибки Тюрінга[en] обчислюваних множин.

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

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

Повні послідовностіРедагувати

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

Див. такожРедагувати

ЛітератураРедагувати

  • 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. .

ПосиланняРедагувати