수학에서, 다음수 함수(영어: successor function)또는 다음수 연산(영어: successor operation)은 자연수 n에 대해서 S(n) = n+1인 원시 재귀 함수 S이다. 예를 들어, S(1) = 2이고 S(2) = 3이다. 다음수 연산은 또한 0차 하이퍼 연산의 맥락으로 제레이션(영어: zeration)으로 알려져 있다: 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에 대해 닫혀 있는 집합 ℕ이 있다는 것을 보장한다. ℕ의 원소는 자연수라고 부른다.[1]

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

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

같이 보기편집

참고 문헌편집

  1. Halmos, Chapter 11
  • Paul R. Halmos (1968). 《Naive Set Theory》. Nostrand.