다음수 함수
1. 개요
다음수 함수는 페아노 공리계에서 자연수를 정의하는 데 사용되는 함수이다. 덧셈보다 기본적인 연산으로 취급되며, 0을 포함하는 자연수를 정의하는 데 사용된다. 1은 S(0)으로 정의되며, 덧셈은 재귀적으로 정의된다. 집합론적 정의에서는 0을 공집합으로, 다음수 S(x)를 x ∪ {x}로 정의한다. 다음수 함수는 하이퍼 연산의 0단계 기본 함수이며, 덧셈, 곱셈, 거듭제곱 등을 만드는 데 사용되며, 재귀 함수에 의한 계산 가능성 특정화에 사용되는 원시 재귀 함수 중 하나이다.
| 이름 | 다음수 함수 |
|---|---|
| 다른 이름 | 사상 함수 증분 함수 |
| 영어 이름 | Successor function |
| 정의 | 어떤 자연수 n에 대해 n+1을 반환하는 연산 |
|---|---|
| 표기법 | S(n) = n + 1 (∀n) |
| 예시 | H₀(a, b) := 1 + b |
|---|
| 관련 개념 | 페아노 공리계 |
|---|
-
컴퓨터 과학 내 논리 -
자동화된 추론
자동화된 추론은 컴퓨터 프로그램을 사용하여 논리적 추론을 수행하는 인공지능 분야로, 수리 논리학의 발전과 초기 연구를 통해 자동 정리 증명 분야의 기틀을 마련했으며, AI 겨울을 겪었지만 소프트웨어 검증 등 다양한 분야에 활용되며 Coq, HOL Light 등의 증명 보조기가 개발되어 난제들의 형식적 증명에 기여했다. -
컴퓨터 과학 내 논리 -
혼 절
혼 절은 하나의 긍정 리터럴만을 포함하는 분리절이며, 논리 프로그래밍, 자동 정리 증명, 데이터베이스 이론 등 여러 분야에 응용된다. -
산술 -
페아노 공리계
페아노 공리계는 자연수를 엄밀하게 정의하기 위해 주세페 페아노가 제시한 공리계로, 자연수 집합이 만족해야 할 5가지 성질(0의 존재, 따름수의 존재, 따름수의 0이 아님, 따름수 함수의 단사성, 수학적 귀납법)을 규정하며 현대 수학의 기초를 이룬다. -
산술 -
연산 (수학)
수학에서 연산은 집합의 원소들을 입력받아 새로운 원소를 생성하는 과정으로, 입력값의 수에 따라 n항 연산으로 정의되며, 항수에 따라 영항, 단항, 이항 연산 등으로 분류되고 내부 연산과 외부 연산으로 구분된다. -
수리논리학 -
NAND 게이트
NAND 게이트는 모든 입력이 1일 때 0을 출력하고 그 외에는 1을 출력하는 논리 게이트로서, 다양한 기호로 표현되며, AND 연산의 결과를 부정하는 연산을 수행하고, 여러 방식으로 구현될 수 있으며, 기능적으로 완전하여 디지털 회로 설계에 필수적이다. -
수리논리학 -
셈
셈은 대상의 개수를 파악하는 기본적인 행위로, 수학에서는 집합의 원소 개수를 파악하는 과정으로 정의되며, 셈의 방식에 따라 결과가 달라질 수 있고, 셈을 배우는 과정은 아동의 교육 및 발달에 중요한 역할을 한다.
2. 페아노 공리계에서의 정의
다음수 함수는 자연수를 정의하는 페아노 공리계에서 기본적인 연산으로 사용된다. 페아노 공리계에서는 덧셈보다 다음수 함수가 먼저 정의되며, 이를 이용해 0을 제외한 모든 자연수를 구성한다. 예를 들어, 1은 다음수 함수 S를 0에 적용한 S(0)으로 정의된다.
집합론을 기반으로 자연수를 구성하는 방식도 있다. 존 폰 노이만은 숫자 0을 공집합 {}으로 정의하고, 임의의 자연수 n의 다음수 S(n)을 집합 n ∪ {n}으로 정의하는 방법을 제안했다. 무한 공리는 0을 포함하며 다음수 연산 S에 대해 닫혀있는 집합 N(자연수의 집합)의 존재를 보장하며, 이 집합 N의 원소들을 자연수라고 부른다.
2.1. 덧셈과의 관계
다음수 함수는 자연수를 정의하는 페아노 공리계에서 사용된다. 이 공리계에서는 덧셈이 먼저 정의되는 것이 아니라, 다음수 함수를 통해 0보다 큰 모든 자연수와 덧셈 연산 자체가 정의된다. 예를 들어, 숫자 1은 다음수 함수를 0에 적용한 S(0)으로 정의된다.
자연수의 덧셈은 다음과 같이 재귀적으로 정의된다:
| 식 | 정의 |
|---|---|
| m + 0 | m |
| m + S(n) | S(m + n) |
이 정의를 이용하면 임의의 두 자연수의 덧셈을 계산할 수 있다. 예를 들어, 5 + 2는 다음과 같이 계산된다:
5 + 2 = 5 + S(1) = S(5 + 1) = S(5 + S(0)) = S(S(5 + 0)) = S(S(5)) = S(6) = 7
또한 다음수 함수는 하이퍼 연산의 무한 계층(덧셈, 곱셈, 거듭제곱, 테트레이션 등)을 구축하는 가장 기본적인 연산(0단계)으로 간주된다. 더 나아가, 다음수 함수는 계산 가능성을 계산 가능한 함수로 특징지을 때 사용되는 기본적인 원시 재귀 함수 중 하나이다.
3. 집합론적 구성
자연수를 집합론에 기반하여 구성하는 여러 방법이 제안되었다. 그중 존 폰 노이만이 제시한 방식이 널리 알려져 있는데, 이는 수학기초론에서 중요한 접근법 중 하나이다. 이 방식은 자연수를 순차적인 집합으로 정의하며, 무한 공리는 이러한 방식으로 정의된 자연수 전체의 집합이 존재함을 보장하는 데 사용된다.
3.1. 무한 공리
자연수를 집합론에 기반하여 구성할 때, 일반적인 접근 방식은 숫자 0을 공집합 {}으로 정의하고, 다음수 S(x)를 x ∪ { x }로 정의하는 것이다. 무한 공리는 0을 포함하고 다음수 함수 S에 대해 닫혀 있는 집합 ℕ의 존재를 보장한다. 이 집합 ℕ의 원소들을 자연수라고 부른다.