계산 가능한 서수

수학, 특히 계산성과 집합 이론에서 순서형 $\alpha$ $\alpha$ 이(가) $\alpha$ $\alpha$ 을(를) 가진 자연수의 하위 집합의 계산 가능한 순서가 있으면 계산이 가능하거나 재귀적이라고 한다 $\alpha$ $\alpha$

$\omega$ $\omega$ 이(가) 계산 가능한지 $\omega$ 쉽게 확인할 수 있다.계산 가능한 서수의 후속은 계산 가능하며, 계산 가능한 모든 서수의 집합은 아래쪽으로 닫힌다.

계산 가능한 모든 서수들의 우월성을 최초의 비구구구적 서수인 Church-Kleene 서수(Church-Kleene sordinal)라고 하며, $\omega _{1}^{CK}$ 1 $\omega _{1}^{CK}$ ${\$ 로 표시한다 $\omega _{1}^{CK}$ 교회-Kleene 서수는 한계 서수이다.서수는 $\omega _{1}^{CK}$ $\omega _{1}^{CK}$ $\omega _{1}^{CK}$ $\omega _{1}^{CK}$ ${\$ 보다 작을 경우에만 계산할 수 있다 $\omega _{1}^{CK}$ 계산 가능한 관계가 셀 수 없이 많으므로 계산 가능한 서수 또한 셀 수 없이 많다.따라서 $\omega _{1}^{CK}$ $\omega _{1}^{CK}$ $\omega _{1}^{CK}$ K ${\$ 을(를) 셀 수 있다 $\omega _{1}^{CK}$ .

계산 가능한 서수들은 정확히 Kleene의 ${\mathcal {O}}$ ${\$ 에 서수 표기법이 있는 서수들이다 ${\mathcal {O}}$

참고 항목

참조

하틀리 로저스 주니어재귀함수와 유효계산성 이론, 1967.1987년, MIT 출판사, ISBN0-262-68052-1(페이퍼백), ISBN0-07-053522-1
제럴드 색스 상위 재귀 이론.수학 논리학의 관점들, Springer-Verlag, 1990.ISBN 0-387-19305-7

이 세트 이론 관련 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.

Search

계산 가능한 서수

네임스페이스

더

참고 항목

참조