프레게 정리

Frege's theorem

금속론과 메타수학에서 프레게의 정리는 연산의 페아노 공리가 흄의 원리로부터 2차 논리로 유도될 수 있다는 메타이론입니다. 그것은 비공식적으로 Gottlob Frege에 의해 1884년 그룬들라겐 데어 아리스메틱(The Foundations of Arithmetik)[1]에서 처음으로 증명되었고 1893년 그룬데제 데어 아리스메틱 I(Grundgesetze der Arithmetik I)에서 더 공식적으로 증명되었습니다.[2] 이 정리는 1980년대 초 크리스핀 라이트에 의해 재발견되었으며 그 이후로 중요한 작업의 초점이 되었습니다. 그것은 신논리주의(적어도 스코틀랜드 학파의 다양성)로 알려진 수학 철학의 핵심입니다.

개요

1884년 《산술의 기초》(1884년)에서, 그리고 그 후 《산술의 기초》(1893년 1월 1일, 1903년 2월 1일)에서 프레게는 자신이 논리적이라고 주장한 공리로부터 모든 산술의 법칙을 도출하려고 시도했습니다(논리학 참조). 이러한 공리의 대부분은 그의 베그리프슈리프로부터 이어받은 것입니다. 진정으로 새로운 원칙은 그가 기본 법칙 V(현재는 무제한 이해의 공리 스키마로 알려져 있음)라고 부르는 것이었습니다. 함수 f(x)의 "값 범위"는 ∀x[f(x) = g(x)인 경우에만 함수 g(x)의 "값 범위"와 같습니다. 그러나 기본법 V는 논리적 명제가 되지 못했을 뿐만 아니라 러셀의 역설의 대상이 되었기 때문에 결과적인 체계가 일관성이 없음이 증명되었습니다.[4]

프레게의 그룬데제의 불일치는 프레게의 업적을 무색하게 했습니다: 에드워드 잘타에 따르면, 그룬데제는 "단일한 일관된 원리로부터 산술의 기본 명제에 대한 유효한 증명 (2차 논리에서)의 모든 필수 단계를 포함합니다."[4] 이 업적은 프레게의 정리로 알려지게 되었습니다.[4][5]

명제 논리학에서의 프레게 정리

( P → ( Q → R )) → (( P → Q ) → ( P → R ))
No Green tickY No ✓ No Green tickY ✗ ✓ ✗ Green tickY ✗ ✓ ✗
No Green tickY No ✓ Yes Green tickY ✗ ✓ ✗ Green tickY ✗ ✓ ✓
No Green tickY Yes ✗ No Green tickY ✗ ✓ ✓ Green tickY ✗ ✓ ✗
No Green tickY Yes ✓ Yes Green tickY ✗ ✓ ✓ Green tickY ✗ ✓ ✓
Yes Green tickY No ✓ No Green tickY ✓ ✗ ✗ Green tickY ✓ ✗ ✗
Yes Green tickY No ✓ Yes Green tickY ✓ ✗ ✗ Green tickY ✓ ✓ ✓
Yes Red XN Yes ✗ No Green tickY ✓ ✓ ✓ Red XN ✓ ✗ ✗
Yes Green tickY Yes ✓ Yes Green tickY ✓ ✓ ✓ Green tickY ✓ ✓ ✓
1 2 3 4 5 6 7 8 9 10 11 12 13

명제 논리학에서 프레게의 정리는 다음과 같은 항상성을 말합니다.

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

그 정리는 이미 상상할 수 있는 가장 약한 논리 중 하나인 건설적 함축적분학을 포함하고 있습니다. 브루어 밑에 있는 증거는-Heyting–Kolmogorov 은 ↦ ↦ ↦ ( (p) ∘ g ) ) f\mapsto p\mapsto (f(p)\circ g) (p)}를 읽습니다. 즉, "f가 Q가 R을 암시하는 이유를 나타내자. 그리고 g는 P가 Q를 암시하는 이유를 나타냅니다. 그리고 f가 주어지면 g가 주어지고 P에 대한 이유 p가 주어지면 Q는 g로 유지되고 Q는 R이 f로 유지됨을 의미한다는 것을 알 수 있습니다. 그래서 R은 보유하고 있습니다."

오른쪽에 있는 진리표는 의미론적 증거를 제공합니다. P, Q, R(열 1, 3, 5)에 대한 거짓(✗) 또는 참(✓)의 가능한 모든 할당에 대해 각 하위 공식은 재료 조건에 대한 규칙에 따라 평가되며, 그 결과는 주 연산자 아래에 표시됩니다. 열 6은 전체 공식이 모든 경우에 참인 것으로 평가됨을 보여줍니다. 즉, 항상성입니다. 실제로 선행(열 2)과 그에 따른 선행(열 10)은 동등합니다.

메모들

  1. ^ 고틀롭 프레게, 디 그룬들라겐 데어 아리스메틱, 브레슬라우: Verlag von Wilhelm Koebner, 1884, §63.
  2. ^ a b Gottlob Frege, Grundgesetze der Arithmetik I, Jena: Verlag Hermann Pohle, 1893, §§ 20, 47.
  3. ^ Richard Pettigrew, "기본 집합론", 2012년 1월 26일, 페이지 2.
  4. ^ a b c Zalta, Edward (2013), "Frege's Theorem and Foundations for Arithmetic", Stanford Encyclopedia of Philosophy.
  5. ^ Boolos, George (1998). Logic, Logic, and Logic. Edited by Richard C. Jeffrey, introduction by John P. Burgess. Cambridge, Mass: Harvard University Press. p. 154. ISBN 9780674537675. OCLC 37509971. Frege's startling discovery, of which he may or may not have been fully aware and which has been lost to view since the discovery of Russell's paradox, was that arithmetic can be derived in a purely logical system like that of his Begriffsschrift from this consistent principle and from it alone.

참고문헌