크레이그의 정리

수학적 논리학에서 크레이그의 정리는 1차 언어의 잘 구성된 공식의 모든 반복적으로 열거할 수 있는 집합은 (기본적으로) 재귀적으로 공리화할 수 있다고 말한다.이 결과는 비록 두 결과 모두 같은 논리학자 윌리엄 크레이그의 이름을 딴 것이지만 잘 알려진 크레이그 보간 정리와는 관련이 없다.

재귀 공리화

$A{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$… ${\displaystyle A_{1},A_{2},\dots }$을(를) 1차 공식의 반복적으로 열거할 수 있는 집합 T의 공리의 열거가 되도록$$ 한다.다음으로 구성된 다른 세트 T* 구성

${\displaystyle \underbrace {A_{i}\land \dots \land A_{i}} _{i}}$

각 양의 정수 i에 대해.따라서 T*와 T의 연역적 폐쇄는 동등하다. 그 증거는 T*가 재귀적 집합임을 보여줄 것이다.T*에 대한 의사결정 절차는 다음과 같은 비공식 추론에 따라 스스로를 빌려준다.T*의 각 멤버는 $A{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$} 또는$$ 폼 중 하나임

${\displaystyle \underbrace {B_{j}\land \dots \land B_{j}} _{j}.}$

각 공식은 길이가 유한하므로 A ${\displaystyle {1\mathrm{}}_{}}$ ${\$1}인지 또는$$해당 형태인지$$ 확인할 수 있다.상기 형태이고 j 결막으로 구성된 경우 (발생) 결막이 $A{\displaystyle {}_{}}$ j ${\$이면 T*이고$,$ 그렇지 않으면 T*에 없다.다시 T의 공리도를 열거한 다음 기호에 대한 기호를 체크하여$$ 결막이 실제로 ${\displaystyle {An}_{}}$ ${\$인지 확인할 수 있다.

원시 재귀 공리화

위의 증거는 각각의 반복적으로 열거된 공리 집합에 대해 동일한 연역적 폐쇄성을 갖는 재귀 공리 집합이 있음을 보여준다.공리 집합은 집합의 멤버십을 결정하는 원시 재귀함수가 있는 경우 원시 재귀함수다.수식 ${\displaystyle A_{}}$ i ${\$을(를) 다음으로$$ 대체하는 대신 원시 재귀적 축시화를 얻으려면

${\displaystyle \underbrace {A_{i}\land \dots \land A_{i}} _{i}}$

대신 으로 대체하다.

${\displaystyle \underset{}{\underset{}{A_{}}}}$ ${\displaystyle \underset{}{\underset{}{{}_{}}}}$ ${\displaystyle \underset{}{\underset{}{\cdots }}}$ ${\displaystyle \underset{}{\underset{}{\cdots }}}$ i ${\displaystyle \underset{}{\underset{}{i_{}}}}$ f${\displaystyle \underset{f}{\underset{}{{}_{}}}}$ f${\displaystyle \underset{}{}}$(${\displaystyle \underset{}{i}}$) ${\$

여기서 f(x)는 주어진 i에서 ${\displaystyle A_{}}$ i ${\$이(가) 원래의 재귀적으로 열거된 공리 집합에 있음을$$ 나타내는 계산 기록을 반환하는 함수다.원시 재귀함수는 형식(*)의 표현을 구문 분석하여 ${\displaystyle {Ai}_{}}$ ${\$디스플레이 $스타일 A_{i}}$와 j를 얻을 수 있다.그렇다면 클레네의 T 술어는 원시적 재귀성이기 때문에, 원시적 재귀함수가 j가 실제로 필요에 따라 계산이력임을 검증하는 것이 가능하다.

철학적 함의

If ${\displaystyle T}$ is a recursively axiomatizable theory and we divide its predicates into two disjoint sets ${\displaystyle V_{A}}$ and ${\displaystyle V_{B}}$, then those theorems of ${\displaystyle T}$ that are in the vocabulary ${\displaystyle V_{A}}$ are recursively enumerable, and따라서 크레이그의 정리를 바탕으로 공리화할 수 있다.칼 지 헴펠은 이를 근거로 모든 과학의 예측이 관찰용어의 어휘에 있기 때문에 과학의 이론적 어휘는 원칙적으로 제거할 수 있다고 주장했다.그 자신도 이 주장에 대해 두 가지 이의를 제기했다. 1) 과학의 새로운 공리는 사실상 다루기 어려운 것이고, 2) 과학은 귀납 추론과 이론적 용어들을 제거하면 관찰 문장 사이의 귀납적 관계가 바뀔 수 있다.힐러리 푸트남은 이 주장이 과학의 유일한 목적이 성공적인 예측이라는 잘못된 생각에 근거하고 있다고 주장한다.그는 우리에게 이론적 용어가 필요한 주된 이유는 이론적 실체(바이러스, 라디오 스타, 기초 입자 등)에 대해 이야기하고 싶기 때문이라고 제안한다.

참조

• 윌리엄 크레이그"시스템 내 악시오마티지빌리티에 관한 연구", 제18권, 제1호(1953) 페이지 30-32.
• 힐러리 푸트남."Craig's Organization", The Journal of 철학 저널, Vol. 62, No. 10 (1965), 페이지 251.260.