Product Design, Manufacturing & Innovation Resources
» 괴델 수

괴델 수

1931
  • Kurt Gödel
고유한 자연수를 사용하는 수학 논리의 괴델 번호 매기기 기법.

(설명을 위한 생성된 이미지입니다)

괴델 번호 매기기는 형식 언어의 모든 기호, 공식, 증명에 고유한 자연수(괴델 번호)를 부여하는 기초적인 기법입니다. 이러한 구문의 산술화는 형식 체계에 대한 메타수학적 명제(예: "이 공식은 증명 가능하다")를 숫자에 대한 산술적 명제로 인코딩할 수 있게 하며, 이를 통해 체계 내에서 추론이 가능해집니다.

괴델 번호 매기기는 구문론(형식 언어의 기호 구조)과 수론(정수의 속성) 사이의 간극을 메우는 독창적인 메커니즘입니다. 이 과정을 통해 논리에 관한 명제를 숫자에 관한 명제로 변환할 수 있습니다. 이 방법은 형식 언어의 각 기본 기호에 고유한 정수를 할당하는 것으로 시작합니다(예: ¬ → 1, ∨ → 2, ∀ → 3, x → 4 등).

A formula, which is a sequence of these symbols, can then be assigned its own unique number. Gödel’s original method used prime factorization. For a sequence of symbols with numbers [latex]s_1, s_2, …, s_k[/latex], the formula’s Gödel number would be [latex]2^{s_1} \cdot 3^{s_2} \cdot 5^{s_3} \cdot \dots \cdot p_k^{s_k}[/latex], where [latex]p_k[/latex] is the k-th prime number. Due to the fundamental theorem of arithmetic (unique prime factorization), this mapping is injective; every formula gets a unique number, and from any such number, the original formula can be uniquely recovered.

마지막으로, 일련의 공식으로 이루어진 증명도 구성 공식들의 괴델 수를 취하고 소수 거듭제곱 인코딩을 다시 적용하는 동일한 방식으로 인코딩할 수 있습니다. 이러한 완전한 산술화는 "연속 공식 F는 공식 P의 유효한 증명이다"와 같은 복잡한 메타수학적 속성이 F와 P의 괴델 수를 포함하는 순수 산술적 술어로 변환됨을 의미합니다. 이를 통해 괴델은 자신의 증명 가능성을 참조하는 공식을 구성할 수 있었는데, 이는 그의 불완전성 증명의 핵심 단계였습니다.

UNESCO Nomenclature: 1201
순수 수학

유형

추상 시스템

분열

상당한

용법

개념적/이론적

전구체

  • 해석 기하학 (데카르트의 기하학과 대수학의 사상)
  • 라이프니츠의 '특징적 보편성' 개념
  • 산술의 기본 정리 (유일한 소인수분해)
  • 프레게와 러셀의 논리학에서의 언어 형식화
  • 칸토르의 집합 간 사상에 관한 연구

응용 프로그램

  • 계산 가능성 이론 (튜링 기계와 프로그램을 숫자로 표현하는 것)
  • 컴퓨터 과학 (코드는 데이터라는 원칙)
  • 정보 이론
  • 암호화
  • 형식 언어 이론
  • 정지 문제와 같은 결정 불가능성 증명

특허:

NA

잠재적 혁신 아이디어

현재 하루 4만 건이 넘는 봇 트래픽을 차단하기 위해 이 콘텐츠는 커뮤니티 회원만 이용할 수 있습니다.
> 로그인 < 또는 >등록 < 이 콘텐츠를 비롯한 모든 제한된 콘텐츠와 도구는 (100% 무료로) 이용할 수 있습니다.

관련 개념: 괴델 수, 산술화, 구문론, 메타수학, 인코딩, 형식 언어, 증명 이론, 계산 가능성, 자기 참조, 소인수분해.

역사적 맥락

괴델 수

1924
1925
1930
1931
1939
1940
1950
1922
1925
1928
1930
1936
1940
1943
1950

(날짜를 알 수 없거나 관련이 없는 경우, 예를 들어 "유체역학"의 경우, 주목할 만한 등장 시기를 대략적으로 추정하여 제공합니다.)

관련 발명, 혁신 및 기술 원칙

고화질 이미지 및 다운로드는 등록된 회원에게만 100% 무료로 제공됩니다.

> 로그인 <