재귀적 정의

코흐 눈송이를 만드는 4단계입니다.다른 많은 프랙탈과 마찬가지로, 단계들은 재귀적 정의를 통해 얻어진다.

수학과 컴퓨터 과학에서, 재귀적 정의 또는 귀납적 정의는 집합의 다른 요소들의 관점에서 집합의 요소를 정의하기 위해 사용됩니다(Accel 1977:740ff).재귀적으로 정의할 수 있는 객체의 예로는 요인수, 자연수, 피보나치 수, 칸토어 삼원 집합 등이 있습니다.

함수의 재귀적 정의는 일부 입력에 대한 함수의 값을 다른(보통 더 작은) 입력에 대한 동일한 함수의 값으로 정의합니다.예를 들어, 요인 함수 n!은 규칙에 의해 정의됩니다.

0! = 1.

(n+1)!= (n + 1)·n!

이 정의는 자연수 n마다 유효합니다.재귀가 최종적으로 베이스 케이스0에 도달하기 때문입니다.이 정의는 또한 n = 0에서 시작하여 n = 1, n = 2, n = 3 등으로 계속 진행하는 함수 n!의 값을 계산하는 절차를 제공하는 것으로 생각할 수 있다.

재귀정리에 따르면 이러한 정의는 실제로 고유한 함수를 정의한다.그 증거는 수학적 ^[1]귀납법을 사용한다.

집합의 귀납적 정의는 집합의 요소를 집합의 다른 요소 관점에서 설명합니다.예를 들어, 자연수의 집합 N의 정의는 다음과 같습니다.

1은 N에 있습니다.
요소 n이 N이면 n + 1이 N에 있습니다.
N은 (1)과 (2)를 만족하는 모든 집합의 교집합이다.

(1)과 (2)를 만족하는 집합이 많이 있습니다. 예를 들어, 집합 {1, 1.649, 2, 2.649, 3, 3.649, ...}은 정의를 만족합니다.단, 조건 (3)은 관계없는 부재가 있는 집합을 제거함으로써 자연수 집합을 지정한다.이 정의에서는 N이 더 큰 집합(실수 집합 등)에 포함되는 것을 전제로 하고 있습니다(연산 +가 정의되어 있습니다).

재귀적으로 정의된 함수 및 집합의 특성은 재귀적 정의를 따르는 유도 원리에 의해 종종 입증될 수 있습니다.예를 들어, 여기에 제시된 자연수의 정의는 자연수에 대한 수학적 귀납 원리를 직접적으로 암시한다. 즉, 자연수 0(또는 1)의 속성이 유지되고 n이 유지될 때마다 n+1의 속성이 유지되면 모든 자연수의 속성이 유지된다(Aczel 1977:742).

재귀 정의의 형식

대부분의 재귀적 정의에는 베이스 케이스(베이스)와 귀납절의 두 가지 기초가 있습니다.

순환적 정의와 재귀적 정의의 차이점은 재귀적 정의는 항상 기본 케이스, 정의 자체에서 정의되지 않고 정의를 충족하는 케이스, 그리고 귀납적 절의 다른 모든 인스턴스는 어떤 의미에서는 "더 작아야 한다"(즉, 그러한 기본 케이스에 더 가깝다)는 것이다.rminate the recursion) : "더 단순한 ^[2]대소문자만 포함"이라고도 하는 규칙입니다.

반대로 순환 정의에는 기본 대소문자가 없을 수 있으며 함수의 다른 값이 아니라 그 값 자체의 관점에서 함수의 값을 정의할 수도 있습니다.그러한 상황은 무한 퇴보로 이어질 것이다.

그 재귀적 정의는 유효하다.재귀적 정의는 고유한 함수를 식별한다는 것을 의미한다.재귀정리로 알려진 집합론의 정리이며, 그 증거는 간단하지 ^[3]않다.여기서 함수의 영역이 자연수일 때 정의가 유효하기 위한 충분한 조건은 f $(0)$ 의 값(즉, 기준 대소문자)이 $주어지는$ $것$ 이고, n > $0$ 일 $경우$ n, $f (0), f$ (1 $)\dots, f(n$ - 1) (즉, 유도절)의 $관점$ 에서 f $($ n)를 결정하기 위한 알고리즘이 주어지는 것이다.

보다 일반적으로, 도메인이 잘 정렬된 집합일 때마다 함수의 재귀 정의를 초한 재귀 원리를 사용하여 수행할 수 있습니다.유효한 재귀적 정의를 구성하는 공식 기준은 일반적인 경우에 더 복잡합니다.일반적인 증거와 기준의 개요는 James Munkres의 토폴로지에서 찾을 수 있습니다.단,^[4] 일반 재귀 정의의 특정 케이스(도메인은 올바른 순서 집합 대신 양의 정수로 제한됨)는 다음과 같습니다.

재귀적 정의의 원리

A를 세트로 하고 a를 A의 $요소$ 로 $하자 0$ . $θ$ 가 양의 정수 중 비어 있지 않은 부분을 A의 $요소$ 인 $A$ 에 매핑하는 각 $함수$ f에 할당하는 함수라면, 다음과 $h:\mathbb {Z} _{+}\to A$ 고유한 $h:\mathbb {Z} _{+}\to A$ h $h:\mathbb {Z} _{+}\to A$ Z $h:\mathbb {Z} _{+}\to A$ + $h:\mathbb {Z} _{+}\to A$ $h:\mathbb {Z} _{+}\to A$ {\ $displaystyle$ h $:\mathbb {Z} _{+}\to$ A $}$ 가 $h:\mathbb {Z} _{+}\to A$ 존재한다.

h(1)=a_{0

\displaystyle h(i)=\rho(h _{1,2,\ldots,i-1\}){\text{ for }}i > 1.}

재귀 정의의 예

기본 함수

덧셈은 카운트를 기준으로 재귀적으로 정의됩니다.

0+a=a,

(\displaystyle (1+n)+a=1+(n+a))}

곱셈은 다음과 같이 재귀적으로 정의됩니다.

0a=0,

(\displaystyle (1+n)a=a+na)

지수화는 다음과 같이 재귀적으로 정의됩니다.

a^{0}=1,

(\displaystyle a^{1+n}=aa^{n}).}

이항 계수는 다음과 같이 재귀적으로 정의할 수 있습니다.

{binom {a} {0}}=1,

({displaystyle {1+a}{1+n}}=param frac {(1+a){\binom {a}{n}}{1+n}}).}

소수

소수들의 집합은 다음을 만족시키는 양의 정수의 고유한 집합으로 정의될 수 있다.

1은 소수가 아닙니다.
다른 양의 정수는 자신보다 작은 소수로 나누어지지 않는 경우에만 소수입니다.

정수 1의 primality는 기본 케이스입니다.이 정의에 의해 큰 정수 X의 primality를 체크하려면 1과 X 사이의 모든 정수의 primality를 알아야 합니다.이것은 이 정의에 의해 잘 정의됩니다.그 마지막 점은 X에 대한 귀납에 의해 증명될 수 있는데, 이 경우 두 번째 절이 "if and only if"라고 말하는 것이 필수적입니다. 예를 들어 "if"라고만 말했다면 숫자 4의 primity는 명확하지 않을 것이고, 두 번째 절의 추가 적용은 불가능할 것입니다.

음수가 아닌 짝수

짝수는 다음과 같이 정의될 수 있습니다.

0은 음이 아닌 even의 집합 E(기준 절)에 있습니다.
집합 E의 임의의 요소 x에 대해 x + 2는 E(유도절)에 있습니다.
기본절과 귀납절(초절)에서 얻지 않는 한 E에는 아무것도 없다.

잘 형성된 공식

재귀적 정의는 주로 논리나 컴퓨터 프로그래밍에서 발견됩니다.예를 들어, 올바른 형식의 공식(wff)은 다음과 같이 정의할 수 있습니다.

p와 같이 "코너는 변호사"라는 뜻의 제안의 상징이다.
Np와 같은 wff 뒤에 오는 부정 기호는 "코너가 변호사라는 것은 사실이 아니다"를 의미합니다.
4개의 바이너리 접속 중 하나(C, A, K 또는E)에 이어2개의 wffs가 계속됩니다.기호 K는 "둘 다 사실"을 의미하기 때문에 Kpq는 "코너는 변호사이고 메리는 음악을 좋아한다"를 의미할 수 있다.

이러한 재귀적 정의의 가치는 특정 기호 문자열이 "잘 형성"되었는지 여부를 결정하는 데 사용될 수 있다는 것입니다.

Kpq는 K 뒤에 원자 wffs p와 q가 이어지기 때문에 잘 형성됩니다.
NKpq는 N 다음에 Kpq가 이어지기 때문에 잘 형성되어 있습니다.
KNpNq는 K 다음에 Np와 Nq가 이어집니다.Np는 wff 등입니다.

「」를 참조해 주세요.

메모들

^ Henkin, Leon (1960). "On Mathematical Induction". The American Mathematical Monthly. 67 (4): 323–338. doi:10.2307/2308975. ISSN 0002-9890. JSTOR 2308975.
^ "All About Recursion". www.cis.upenn.edu. Retrieved 2019-10-24.
^ 재귀정리의 증명은 리언 헨킨의 수학적 귀납에 대하여(1960년)를 참조한다.
^ Munkres, James (1975). Topology, a first course (1st ed.). New Jersey: Prentice-Hall. p. 68, exercises 10 and 12. ISBN 0-13-925495-1.

레퍼런스

Halmos, Paul (1960). Naive set theory. van Nostrand. OCLC 802530334.
Aczel, Peter (1977). "An Introduction to Inductive Definitions". In Barwise, J. (ed.). Handbook of Mathematical Logic. Studies in Logic and the Foundations of Mathematics. Vol. 90. North-Holland. pp. 739–782. doi:10.1016/S0049-237X(08)71120-0. ISBN 0-444-86388-5.
Hein, James L. (2010). Discrete Structures, Logic, and Computability. Jones & Bartlett. ISBN 978-0-7637-7206-2. OCLC 636352297.

[1] Henkin, Leon (1960). "On Mathematical Induction". The American Mathematical Monthly. 67 (4): 323–338. doi:10.2307/2308975. ISSN 0002-9890. JSTOR 2308975.

[2] "All About Recursion". www.cis.upenn.edu. Retrieved 2019-10-24.

[3] 재귀정리의 증명은 리언 헨킨의 수학적 귀납에 대하여(1960년)를 참조한다.

[Munkres-4] Munkres, James (1975). Topology, a first course (1st ed.). New Jersey: Prentice-Hall. p. 68, exercises 10 and 12. ISBN 0-13-925495-1.

[1]

[2]

[3]

[4]

Search

재귀적 정의

네임스페이스

더

목차