Функция-преемник
В математике функция -преемник или операция-преемник отправляет натуральное число следующему. Функция-преемник обозначается S , поэтому S ( n ) = n + 1. Например, S (1) = 2 и S (2) = 3. Функция-преемник является одним из основных компонентов, используемых для построения примитивно-рекурсивной функции. функция .
Последующие операции также известны как зерация в контексте нулевой гипероперации : H 0 ( a , b ) = 1 + b . В этом контексте расширением зерации является сложение , которое определяется как повторяющаяся последовательность.
Обзор [ править ]
Функция-преемник является частью формального языка, используемого для формулировки аксиом Пеано , которые формализуют структуру натуральных чисел. В этой формализации функция-преемник представляет собой примитивную операцию над натуральными числами, в терминах которой определяются стандартные натуральные числа и сложение. [1] Например, 1 определяется как S (0), а сложение натуральных чисел определяется рекурсивно следующим образом:
м + 0 = м , м + S ( п ) знак равно S ( м + п ).
Это можно использовать для вычисления сложения любых двух натуральных чисел. Например, 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]
Функция-преемник является основой нулевого уровня бесконечной Гжегорчика иерархии гиперопераций и т. д. Она была изучена в 1986 году в исследовании , , используемой для построения сложения , умножения , возведения в степень , тетрации включавшем обобщение шаблона для гиперопераций. [3]
Это также одна из примитивных функций, используемых при описании вычислимости с помощью рекурсивных функций .
См. также [ править ]
Ссылки [ править ]
- ^ Штеффен, Бернхард; Рютинг, Оливер; Хут, Майкл (2018). Математические основы продвинутой информатики. Том 1: Индуктивные подходы . Спрингер. п. 121. дои : 10.1007/978-3-319-68397-3 . ISBN 978-3-319-68397-3 .
- ^ Халмос, Глава 11.
- ^ Рубцов, Калифорния; Ромерио, Г.Ф. (2004). «Функция Аккермана и новые арифметические операции» (PDF) .
- Пол Р. Халмос (1968). Наивная теория множеств . Ностранд.
 | Эта математической логике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |