Функция следования в математике — унарная функция (обычно обозначаемая ), которая каждому натуральному числу ставит в соответствие следующее за ним число. Является основной функцией в аксиоматике Пеано, в которой определяет, каким образом можно переходить от одного натурального числа к другому.
Аксиомы Пеано Функция следования является частью формальной системы аксиоматики Пеано, с её помощью рекурсивно определяются операции сложения и умножения.
Для определения сложения используются следующие аксиомы: ; . Таким образом можно формализировать сложение двух любых натуральных чисел. К примеру,
Для умножения используются следующие аксиомы: ; . Например,
Другие свойства Существует несколько способов определения . К примеру, в конструкции фон Неймана числом 0 является пустое множество {}, а за числом следует множество
В свою очередь, аксиома бесконечности гарантирует существование бесконечного множества, содержащего пустое множество (число 0), замкнутого относительно операции (функции следования), что формирует множество натуральных чисел .Halmos, Chapter 11
Функция следования также является базовой примитивно рекурсивной функцией и используется в определении вычислимости рекурсивных функций.
Функция содержится во множестве функций нулевого уровня в бесконечной , оценивающей скорости роста рекурсивных функций.
Также является гипероператором нулевого порядка .
См. также Инкремент Арифметика Рекурсия Рекурсивная функция
Примечания
Литература
Категория:Математика Категория:Арифметика Категория:Теория чисел