stringtranslate.com

Функция преемника

В математике функция -последователь или операция-последователь отправляет натуральное число к следующему. Функция-последователь обозначается как S , поэтому S ( n ) = n  + 1. Например, S (1) = 2 и S (2) = 3. Функция-последователь является одним из основных компонентов, используемых для построения примитивной рекурсивной функции .

Операции-последователи также известны как зерация в контексте нулевой гипероперации : H 0 ( a , b ) = 1 +  b . В этом контексте расширением зерации является сложение , которое определяется как повторяющаяся последовательность.

Обзор

Функция-последователь является частью формального языка, используемого для формулировки аксиом Пеано , которые формализуют структуру натуральных чисел. В этой формализации функция-последователь является примитивной операцией над натуральными числами, в терминах которой определяются стандартные натуральные числа и сложение. [1] Например, 1 определяется как S (0), а сложение над натуральными числами определяется рекурсивно:

Это можно использовать для вычисления сложения любых двух натуральных чисел. Например, 5 + 2 = 5 + S (1) = S (5 + 1) = S (5 + S (0)) = S ( S (5 + 0)) = S ( S (5)) = S (6) = 7.

Было предложено несколько конструкций натуральных чисел в рамках теории множеств. Например, Джон фон Нейман конструирует число 0 как пустое множество {}, а преемника n , S ( n ), как множество n  ∪ { n }. Аксиома бесконечности тогда гарантирует существование множества, содержащего 0 и замкнутого относительно S . Наименьшее такое множество обозначается N , а его члены называются натуральными числами. [2]

Функция-преемник является основанием уровня 0 бесконечной иерархии гиперопераций Гжегорчика , используемой для построения сложения , умножения , возведения в степень , тетрации и т. д. Она была изучена в 1986 году в исследовании , включающем обобщение шаблона для гиперопераций. [3]

Это также одна из примитивных функций, используемых при характеристике вычислимости с помощью рекурсивных функций .

Смотрите также

Ссылки

  1. ^ Штеффен, Бернхард; Рютинг, Оливер; Хут, Михаэль (2018). Математические основы продвинутой информатики — Том 1: Индуктивные подходы. Springer. стр. 121. doi :10.1007/978-3-319-68397-3. ISBN 978-3-319-68397-3.
  2. ^ Халмос, Глава 11
  3. ^ Рубцов, CA; Ромерио, GF (2004). «Функция Аккермана и новые арифметические операции» (PDF) .