퍼스의 항진명제

수학기초론 Foundations of Mathematics
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px"	다루는 대상과 주요 토픽
수리논리학	논리 · 논증{ 귀납논증 · 연역논증 · 귀추 · 유추} · 공리 및 공준 · 증명{ 증명보조기 · 자동정리증명 · 귀류법 · 수학적 귀납법 · 반증 · 더블 카운팅 · PWW} · 논리함수 · 논리 연산 · 잘 정의됨 · 조건문( 조각적 정의) · 명제 논리( 명제 · 아이버슨 괄호 · 역 · 이 · 대우) · 양상논리 · 술어 논리( 존재성과 유일성) · 형식문법 · 유형 이론 · 모형 이론
집합론	집합( 원소 · 공집합 · 집합족 · 곱집합 · 멱집합) · 관계( 동치관계 · 순서 관계) · 순서쌍( 튜플) · 서수( 하세 다이어그램 · 큰 가산서수) · 수 체계 · ZFC( 선택공리) · 기수( 초한기수) · 절대적 무한 · 모임
범주론	범주 · 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성
계산가능성 이론	계산 · 오토마타 · 튜링 기계 · 바쁜 비버 · 정지 문제 · 재귀함수
정리
드모르간 법칙 · 대각선 논법 · 러셀의 역설 · 거짓말쟁이의 역설 · 뢰벤하임-스콜렘 정리 · 슈뢰더-베른슈타인 정리 · 집합-부분합 정리 · 퍼스의 항진명제 · 굿스타인 정리 · 완전성 정리 · 불완전성 정리( 괴델 부호화) · 힐베르트의 호텔 · 연속체 가설 · 퍼지 논리
기타
예비사항( 약어 및 기호) · 추상화 · 벤 다이어그램 · 수학철학
틀:논리학 · 틀:이산수학 · 틀:이론 컴퓨터 과학 · 철학 관련 정보 · 논리학 관련 정보 · 수학 관련 정보		}}}}}}}}}

1. 개요2. 증명

2.1. 전제는 없다(1번 라인)2.2. 조건문의 조건을 작성한다(2번 라인)2.3. 귀류법을 사용해보자(3-13번 라인)

2.3.1. 대우명제를 사용하자(4-7번 라인)2.3.2. p는 아무래도 좋게 되었다(8-11번 라인)2.3.3. 그러나 그러면 모순(12번 라인)

2.4. 그렇기에 p(13번 라인)2.5. 조건명제의 증명이 끝났다(14번 라인)

3. 진리표를 이용한 증명4. 관련 문서

1. 개요

퍼스(Peirce)의 항진명제는, 다음과 같은 항진인 명제이다.

[math(((p \rightarrow q) \rightarrow p) \rightarrow p)]

기호논리학의 선구자 중 한 명인 찰스 샌더스 퍼스의 이름을 따서 만들어졌다.[1]

2. 증명

이게 항진이라는 것을, 다음과 같이 증명할 수 있다.

2.1. 전제는 없다(1번 라인)

항진명제를 증명함에 있어서 중요한 것은, 이 명제가 어떤 경우에서라도 참으로 도출되어야 하는 것이다. 즉, 어떤 전제를 작성하거나 작성하지 않거나에 상관없이, 항진명제라고 하는 것에 대해서는 그 증명이 가능해야 한다는 것이다. 제시한 증명에서는 1번 라인[2]의 우측에 적힌 hyp[3]로 지정되어 있는 부분이 비어있다. 즉, 없다. 그런 상태에서 퍼스의 항진명제라 하는 조건명제를 증명하는 것이다.

2.2. 조건문의 조건을 작성한다(2번 라인)

퍼스의 항진명제를 구성하는 것은, 결론적으로 [math(\rightarrow)]로 연결되어 있는 부분이다. 이를 사이에 두고, 화살표의 왼쪽에는 [math((p \rightarrow q)\rightarrow p)]가, 오른쪽에는 [math(p)]가 나타나고 있다. 즉, 이를 증명하기 위해서 조건인 것을 2번에서 가정[4]을 노드 2에 세우고, 그 안에서 결론으로 [math(p)]를 얻으려는 과정을 시작한다.

2.3. 귀류법을 사용해보자(3-13번 라인)

3번 라인에서는 다시 [math(p)]가 거짓이라고 가정해 본다. 그리고 12번에서 결국 모순이 되는 것을 보임으로써, 결국 [math(p)]가 거짓이 아니어야 함을 13번 라인에서 제시한다. 그 과정에서 다음과 같은 시도들을 하게 된다.

2.3.1. 대우명제를 사용하자(4-7번 라인)

2번 라인의 조건명제에서 결론인 부분을 3번에서 부정하였다. 즉, 조건인 부분이 부정되어 나오는 것이 당연하므로, 7번에서는 2번 명제의 조건 부분이 부정되어 있다.

2.3.2. p는 아무래도 좋게 되었다(8-11번 라인)

8번 라인에서 [math(p)]가 참이라고 다시 가정해 본다. 그러면 조건인 [math(p)]가 어차피 거짓인 명제이므로, 이를 조건으로 갖는 조건명제는 어떤 것이든지 참이다. 즉, 11번 라인에서 [math(p \rightarrow q)]가 참이라고 해도 할 말 없다는 것.

2.3.3. 그러나 그러면 모순(12번 라인)

11번 라인에서 [math(p \rightarrow q)]가 참이라고 내놓긴 했지만, 이건 7번에서 이미 거짓이라고 나와 있는 부분이다. 즉, 모순일 수밖에 없으므로, 12번 라인에 모순이라고 표시해 둔다.

2.4. 그렇기에 p(13번 라인)

3번 라인의 가정에서부터 12번 라인의 모순이 도출되었으므로, 3번 라인의 가정은 거짓이어야 한다. 이는 [math(p)]의 거짓이 거짓이라고 하는 것이므로, 13번 라인에서는 [math(p)]를 참이라고 작성한다.

2.5. 조건명제의 증명이 끝났다(14번 라인)

2번 라인의 조건, [math((p \rightarrow q)\rightarrow p)]으로부터 13번 라인의 결론, [math(p)]로 도착하였다. 즉, 2번 라인의 조건은 13번 라인의 결론을 함의하고 있다. 이를 하나의 조건명제로 표현하여, 14번 라인에 다음과 같이 작성한다.

[math(((p \rightarrow q ) \rightarrow p ) \rightarrow p )]

이로써 증명이 완료된다.

3. 진리표를 이용한 증명

진리표를 이용하면 [math(p\rightarrow q)]는 [math(\neg p\vee q)]와 동등하다. 따라서 [math(((p \rightarrow q ) \rightarrow p ) \rightarrow p )]를 [math(\neg \left(\neg \left(\neg p\vee q\right)\vee p\right)\vee p)]로 변형하면 드 모르간의 법칙에 따라 [math(\left(\left(\neg p\vee q\right)\wedge \neg p\right)\vee p)]가 되고, 이는 다시 [math(\neg p\vee p)]가 되어 항진임을 알 수 있다.

4. 관련 문서

[1] 퍼스 사후 하버드 대학에서 출판한 그의 저작을 모은 퍼스의 전집(Collected Papers of Charles Sanders Peirce)의 Volume 3에 퍼스가 직접 증명한 내용이 실려있다. [2] 세로줄의 단계를 노드, 가로줄의 순서를 라인으로 부른다. [3] hypothesis의 준말. [4] 우측의 hyp 표시로부터 확인한다.