Функция следования

Функция следования в математике — унарная функция (обычно обозначаемая ${\displaystyle S(n)}$), которая каждому натуральному числу ставит в соответствие следующее за ним число. Является основной функцией в аксиоматике Пеано, в которой определяет, каким образом можно переходить от одного натурального числа к другому.

Функция следования является частью формальной системы аксиоматики Пеано, с её помощью рекурсивно определяются операции сложения и умножения.^[1]

Для определения сложения используются следующие аксиомы:

1. ${\displaystyle x+0=x}$;
2. ${\displaystyle x_{1}+S(x_{2})=S(x_{1}+x_{2})}$.

Таким образом можно формализировать сложение двух любых натуральных чисел. К примеру, ${\displaystyle 5+2=5+S(1)=S(5+1)=S(5+S(0))=S(S(5+0))=S(S(5))=S(6)=7}$

Для умножения используются следующие аксиомы:

1. ${\displaystyle x\cdot 0=0}$;
2. ${\displaystyle x_{1}\cdot S(x_{2})=x_{1}\cdot x_{2}+x_{1}}$.

Например, ${\displaystyle 5\cdot 2=5\cdot S(1)=5\cdot 1+5=5+5=10}$

Существует несколько способов определения натуральных чисел через теорию множеств. К примеру, в конструкции фон Неймана числом 0 является пустое множество {}, а за числом ${\displaystyle n}$ следует множество ${\displaystyle S(n)=n\cup \{n\}}$

${\displaystyle 1=0\cup \{0\}=\{\}\cup \{0\}=\{0\}=\{\{\}\}}$;

${\displaystyle 2=1\cup \{1\}=\{0\}\cup \{1\}=\{0,1\}=\{\{\},\{\{\}\}\};}$

В свою очередь, аксиома бесконечности гарантирует существование бесконечного множества, содержащего пустое множество (число 0), замкнутого относительно операции ${\displaystyle n\cup \{n\}}$ (функции следования), что формирует множество натуральных чисел ${\displaystyle \mathbb {N} }$.^[2]

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

Функция содержится во множестве функций нулевого уровня ${\displaystyle {\mathcal {E}}^{0}}$ в бесконечной иерархии Гжегорчика, оценивающей скорости роста рекурсивных функций.^[3]

Также является гипероператором нулевого порядка ${\displaystyle A(0,m)=m+1}$.

• Инкремент
• Арифметика
• Рекурсия
• Рекурсивная функция

• Paul R. Halmos. Naive Set Theory. — Nostrand, 1968.