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

Successor function

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

Последующие операции также известны как зерация в контексте нулевого гипероперация: H0(а, б) = 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 как пустой набор {}, и преемник п, S(п), поскольку множество п ∪ {п}. В аксиома бесконечности тогда гарантирует существование набора, который содержит 0 и является закрыто относительно S. Наименьшее такое множество обозначается символом, а его члены называются натуральными числами.[1]

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

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

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

Рекомендации

  1. ^ Халмос, Глава 11
  2. ^ Рубцов, C.A .; Ромерио, Г.Ф. (2004). «Функция Акермана и новые арифметические операции» (PDF).
  • Пол Р. Халмос (1968). Наивная теория множеств. Ностранд.