프레게의 정리

1. 개요

프레게의 정리는 프레게가 논리주의를 옹호하며 산술의 모든 법칙을 도출하려 시도한 과정에서 나타난 개념이다. 프레게는 《산술의 기초》와 《산술의 기본 법칙》에서 논리적인 공리로부터 산술의 법칙을 이끌어내려 했고, 이 과정에서 '기본 법칙 V'를 제시했으나, 이는 러셀의 역설로 인해 모순임이 증명되었다. 하지만 이 과정에서 프레게의 업적은 '프레게의 정리'로 불리며, 명제 논리에서 특정 항진명제를 가리키는 것으로 정의된다.

2. 프레게의 논리주의와 기본 법칙 V

《산술의 기초》(1884)와 《산술의 기본 법칙》(제1권, 1893년; 제2권, 1903년)에서 프레게는 자신이 논리적인 것으로 주장한 공리로부터 산술의 모든 법칙을 도출하려 시도했다(논리주의 참조). 이 공리들 대부분은 그의 《개념 표기법》에서 가져온 것이었다. 새로운 원리라고 할 수 있는 것은 그가 기본 법칙 V(현재는 무제한 이해의 공리 도식으로 알려짐)라고 부르는 것이었다. 이 법칙에 따르면, 함수 f(x)의 "값 범위"는 ∀x[f(x) = g(x)']인 경우에만 함수 g(x)의 "값 범위"와 같다.

그러나 기본 법칙 V는 논리 명제가 아니었고, 그 결과로 나온 체계는 러셀의 역설에 적용되어 모순임이 증명되었다. 에드워드 잘타에 따르면, 《기본 법칙》은 "단일한 일관된 원리로부터 산술의 기본적인 명제들을 (2차 논리에서) 유효하게 증명하는 데 필요한 모든 본질적인 단계를 포함하고 있다." 이러한 업적은 프레게의 정리로 알려지게 되었다.

2.1. 기본 법칙 V와 러셀의 역설

프레게는 《산술의 기초》(1884)와 《산술의 기본 법칙》(제1권, 1893년; 제2권, 1903년)에서 자신이 논리적인 것으로 주장한 공리로부터 산술의 모든 법칙을 도출하려 시도했다(논리주의 참조). 이 공리들의 대부분은 그의 《개념 표기법》에서 가져온 것이었다. 실제로 새로운 원리라고 할 수 있는 것은 그가 기본 법칙 V(현재는 무제한 이해의 공리 도식으로 알려짐)라고 부르는 것이었다. 함수 f(x)의 "값 범위"는 ∀x[f(x) = g(x)']인 경우에만 함수 g(x)의 "값 범위"와 같다. 그러나 기본 법칙 V는 논리 명제가 아닐 뿐만 아니라, 그 결과로 나온 체계는 러셀의 역설에 적용되어 모순임이 증명되었다.

프레게의 《기본 법칙》에서의 모순은 프레게의 업적을 가렸다.

2.2. 프레게의 정리와 그 의의

프레게는 《산술의 기초》(1884)와 《산술의 기본 법칙》(제1권, 1893년; 제2권, 1903년)에서 자신이 논리적인 것으로 주장한 공리로부터 산술의 모든 법칙을 도출하려 시도했다(논리주의 참조). 이 공리들 대부분은 그의 《개념 표기법》에서 가져온 것이었다. 새로운 원리라고 할 수 있는 것은 그가 기본 법칙 V(현재는 무제한 이해의 공리 도식으로 알려짐)라고 부르는 것이었다. 함수 f(x)의 "값 범위"는 ∀x[f(x) = g(x)']인 경우에만 함수 g(x)의 "값 범위"와 같다. 그러나 기본 법칙 V는 논리 명제가 아닐 뿐만 아니라, 그 결과로 나온 체계는 러셀의 역설에 적용되어 모순임이 증명되었다.

프레게의 《기본 법칙》에서의 모순은 프레게의 업적을 가렸다. 에드워드 잘타에 따르면, 《기본 법칙》은 "단일한 일관된 원리로부터 산술의 기본적인 명제들을 (2차 논리에서) 유효하게 증명하는 데 필요한 모든 본질적인 단계를 포함하고 있다." 이러한 업적은 프레게의 정리로 알려지게 되었다.

3. 명제 논리에서의 프레게의 정리

명제 논리에서 프레게의 정리는 다음 항진명제를 나타낸다.

: (P → (Q→R)) → ((P→Q) → (P→R))

이 정리는 가장 약한 논리 중 하나인 구성적 함축 미적분에서도 성립한다. 브라우어-헤이팅-콜모고로프 해석에 따른 증명은 $f\; \backslash mapsto\; g\backslash mapsto\; p\backslash mapsto\; (f(p)\backslash circ\; g)(p)$이다.

이를 풀어서 설명하면 다음과 같다. "f를 P가 Q를 거쳐 R을 함축한다는 명제로 정의하고, g를 P가 Q를 함축한다는 명제로 정의한다. f와 g, 그리고 P의 증명 p가 주어지면, g에 의해 Q가 성립하고 f에 의해 Q는 R을 함축함을 알 수 있다. 따라서 R이 성립한다."

3.1. 진리표를 통한 증명

명제 논리에서 프레게의 정리는 다음 항진명제를 가리킨다.

: (P → (Q→R)) → ((P→Q) → (P→R))

이 정리는 이미 가장 약한 논리 중 하나인 구성적 함축 미적분에서도 성립한다.

오른쪽의 진리표는 의미론적 증명을 제공한다. P, Q, R에 대해 가능한 모든 거짓 또는 참의 할당(열 1, 3, 5)에 대해, 각 하위 공식은 조건문에 대한 규칙에 따라 평가되며, 그 결과는 주요 연산자 아래에 표시된다. 열 6은 전체 공식이 모든 경우에 참으로 평가된다는 것을 보여주며, 즉 그것이 항진명제임을 의미한다. 실제로 그 전건(열 2)과 후건 (열 10)은 심지어 동치이다.