최근 편집
최근 토론
게시판 메인
도구
투표
무작위 문서
스킨 설정
파일 올리기
기타 도구
216.73.216.143
IP
사용자 도구
사용자 설정
로그인
회원 가입
최근 편집
최근 토론
돌아가기
삭제
이동
파일 올리기
괴델의 불완전성 정리
(편집) (1)
(편집 필터 규칙)
122,940
== 진술 == 우선 괴델의 불완전성 정리를 서술하는 데 필요한 용어들을 몇 개 소개하자. 어떤 이론이 '''일관되었다'''는 것은 그 이론 내에서 [math(\phi)]와 [math(\lnot\phi)]가 동시에 증명되지 않는다는 것을 말한다. 그리고 어떤 이론이 '''완전하다'''는 것은 그 이론 내의 모든 명제가 참 혹은 거짓이라는 것, 즉 [math(T\vdash \phi)]이거나 [math(T\vdash\lnot\phi)]인 것을 말한다. 그리고 어떤 이론이 '''효율적으로 생성 가능하다'''는 것은 그 이론의 공리들의 집합이 재귀 열거 집합이란 것, 즉 주어진 이론 내에서 서술되는 명제들을 모두 나열했을 때 그 명제가 공리인지 아닌지 체크해서 그 명제가 공리이면 이를 출력해내는 프로그램이 존재한다는 것을 말한다. (이 때 그 프로그램이 끝날 필요는 없다.) 괴델의 불완전성 정리는 두 가지가 있는데, 이 둘을 각각 쓰자면 다음과 같다. * '''괴델의 제1 불완전성 정리''' 일관되고 완전하며 산술을 포함하는 형식 체계는 효율적으로 생성 가능하지 않다. * '''괴델의 제2 불완전성 정리''' : [math(T)]가 산술을 포함하고 효율적으로 생성 가능하면, [math(T)]가 일관되었단 사실을 [math(T)] 내에서 증명할 수 없다. 괴델의 제2 불완전성 정리는 몇몇 명제가 그 이론 내에서 결정 불가능임을 보일 때 이용된다. 위 두 정리에서 제시된 세 가지 조건 중에서 하나라도 만족하지 않으면 괴델의 정리는 유도되지 않는다. 페아노 공리 체계와 체르메로-프랜켈 공리 체계는 괴델의 정리에서 요구하는 세가지 조건을 만족한다.
(임시 저장)
(임시 저장 불러오기)
기본값
모나코 에디터
normal
namumark
namumark_beta
macromark
markdown
custom
raw
(↪️)
(💎)
(🛠️)
(추가)
== 진술 == 우선 괴델의 불완전성 정리를 서술하는 데 필요한 용어들을 몇 개 소개하자. 어떤 이론이 '''일관되었다'''는 것은 그 이론 내에서 [math(\phi)]와 [math(\lnot\phi)]가 동시에 증명되지 않는다는 것을 말한다. 그리고 어떤 이론이 '''완전하다'''는 것은 그 이론 내의 모든 명제가 참 혹은 거짓이라는 것, 즉 [math(T\vdash \phi)]이거나 [math(T\vdash\lnot\phi)]인 것을 말한다. 그리고 어떤 이론이 '''효율적으로 생성 가능하다'''는 것은 그 이론의 공리들의 집합이 재귀 열거 집합이란 것, 즉 주어진 이론 내에서 서술되는 명제들을 모두 나열했을 때 그 명제가 공리인지 아닌지 체크해서 그 명제가 공리이면 이를 출력해내는 프로그램이 존재한다는 것을 말한다. (이 때 그 프로그램이 끝날 필요는 없다.) 괴델의 불완전성 정리는 두 가지가 있는데, 이 둘을 각각 쓰자면 다음과 같다. * '''괴델의 제1 불완전성 정리''' 일관되고 완전하며 산술을 포함하는 형식 체계는 효율적으로 생성 가능하지 않다. * '''괴델의 제2 불완전성 정리''' : [math(T)]가 산술을 포함하고 효율적으로 생성 가능하면, [math(T)]가 일관되었단 사실을 [math(T)] 내에서 증명할 수 없다. 괴델의 제2 불완전성 정리는 몇몇 명제가 그 이론 내에서 결정 불가능임을 보일 때 이용된다. 위 두 정리에서 제시된 세 가지 조건 중에서 하나라도 만족하지 않으면 괴델의 정리는 유도되지 않는다. 페아노 공리 체계와 체르메로-프랜켈 공리 체계는 괴델의 정리에서 요구하는 세가지 조건을 만족한다.
비로그인 상태입니다. 편집한 내용을 저장하면 지금 접속한 IP가 기록됩니다.
편집을 전송하면 당신은 이 문서의 기여자로서 본인이 작성한 내용이
CC BY 4.0
에 따라 배포되고, 기여한 문서의 하이퍼링크나 URL로 저작자 표시가 충분하다는 것에 동의하는 것입니다.
전송
미리보기
