다음수 함수

수학에서 다음수 함수() 또는 다음수 연산()은 자연수 n에 대해서 S(n) = n+1인 원시 재귀 함수 S이다.
예를 들어, S(1) = 2이고 S(2) = 3이다. 다음수 연산은 또한 0차 하이퍼 연산의 맥락으로 제레이션()으로 알려져 있다: H0(a, b) = 1 + b.

 개요 
다음수 함수는 자연수를 정의하는 페아노 공리계에서 사용된다. 이와 같이, 이 함수는 덧셈으로 정의되지 않지고 오히려 덧셈처럼 0보다 큰 모든 자연수들을 정의하는데 사용된다. 예를 들어, 1은 S(0)로 정의되고, 자연수의 덧셈은 다음과 같이 재귀적으로 정의된다:

{|
|-
| m + 0 || = m
|-
| m + S(n) || = S(m) + n
|}

그리고 예시로 5 + 2 = 5 + S(1) = S(5) + 1 = 6 + 1 = 6 + S(0) = S(6) + 0 = 7 + 0 = 7을 얻는다.

자연수가 집합론에 기반하여 구성되었을 때, 일반적인 접근은 숫자 0을 공집합 {}으로 정의하고, 다음수 S(x)를 x ∪ { x }로 정의한다. 무한 공리는 0을 포함하고 S에 대해 닫혀 있는 집합 ℕ이 있다는 것을 보장한다. ℕ의 원소는 자연수라고 부른다.Halmos, Chapter 11

다음수 함수는 (덧셈, 곱셈, 거듭제곱, 테트레이션, 등을 만들기 위한) 하이퍼 연산의 무한 계층의 0단계 기본이다.

이것은 또한 재귀 함수에 의한 계산 가능성의 특정화에 사용되는 원시 재귀함수 중 하나이다.

 같이 보기 
 따름 순서수
 다음 기수
 증감 연산자

 각주 

분류:수리논리학
분류:산술
분류:컴퓨터 과학 내 논리