개드립전학생

2010-12-26 [12:09]

반대 : 4

추천 : 36

1+1=2 증명입니다^^



PA1: 1은 자연수이다.

PA2: 모든 자연수 n은 그 다음 수 n'을 갖는다.

PA3: 1은 어떤 자연수의 그 다음 수도 아니다. 즉, 모든 자연수 n에 대해 1≠n'이다.

PA4: 두 자연수의 그 다음 수들이 같다면, 원래의 두 수는 같다. 즉, a'=b'이면 a=b이다.

PA5: 어떤 자연수들의 집합이 1을 포함하고, 그 집합의 모든 원소에 대해 그 다음 수를 포함하면, 그 집합은 자연수 전체의 집합이다.

공리가 "증명하지 않고 옳다고 인정하는 명제"인 것처럼 용어들 가운데도 "정의하지 않고 사용하는 용어"가 필요한데, 이것들을 "무정의 용어"라고 하며, 이 공리계에서는 "1", "그 다음 수"가 무정의 용어로 쓰인다.

우리가 알고 있는 것은 이 공리들과 몇 개의 무정의 용어들 뿐이므로, "1+1=2"를 증명하려면 무엇보다 먼저 "+"와 "2"가 정의되어야 한다.

일단 "2"를 정의하는 것은 간단하다. 2:=1', 즉 1의 그 다음 수로 정의하면 되니까. 여기서 기호 :=는 좌변이 우변과 같이 정의된다는 뜻으로 사용된다. 하는 김에 더 해 보면, 3:=2', 4:=3', 이런 식으로 모든 자연수에 이름을 붙일 수 있다.

다음으로 "+", 즉 "덧셈"을 정의하자. 덧셈을 정의하는 방법은 어렸을 때 손가락 셈하던 것을 흉내내면 된다.

예를 들어, "5+3=8"을 아이들이 계산하는 방법은 우선 손가락 다섯 개를 꼽고, 그 다음 손가락을 꼽는 과정을 세 번 반복하면 된다.

따라서, 두 자연수 a와 b에 대해 두 수의 덧셈 a+b는 우선 a를 놓고, 그 다음 수를 찾는 과정을 b번 반복한 것으로 정의한다. 이것을 기호로 나타내면,
a+b : a → a' → （a'）' → （（a'）'）' → ... → （...（（a'）'）'...）'
이 된다.

그런데 이런 식으로 "b번 반복한다"는 것은 페아노 공리계에 없는 용어이므로, 이 과정 자체를 공리계에 맞는 용어들로 번역하여야 한다.
그러기 위해서는, "그 다음 수를 찾는 과정을 b-1 번 반복한 결과"의 그 다음 수를 찾는 것으로 하여
a+b := （a+（b-1））'
라는 재귀적 표현을 이용하면 되는데, 여기서 문제는 "b-1"이라는 뺄셈이다. 덧셈도 정의되지 않았는데 뺄셈이라니!
따라서, 뺄셈 대신 c'=b인 c를 사용하면 되는데, PA3에 의해 c'=1인 c는 존재하지 않으므로 이 경우는 따로

a+1 := a'
으로 정의하고, b가 1이 아닌 경우는 PA2에 의해 c'=b인 c가 존재하고 PA4에 의해 이러한 c가 유일하므로,
a+b = a+c' := （a+c）'
으로 정의한다.
이 정의를 이용하여 우리는 덧셈을 자유롭게 할 수 있다. 앞서 들었던 예인 "5+3=8"의 경우, 3=2'이므로

5+3 = 5+2' = （5+2）'
이고, 2=1'이므로
5+2 = 5+1' = （5+1）'
이며, 정의에 의해 5+1=5'=6이므로 결국
5+3 = （（5'）'）' = （6'）' = 7' = 8
이 된다.

사실 우리가 원하는 "1+1=2"의 증명은 훨씬 쉽다. 정의에 의해 1+1 = 1'이고 2=1'이니까.

이제 이렇게 정의된 덧셈을 이용하여 교환법칙, 결합법칙도 증명할 수 있다. 증명은 그리 간단치 않은데, 교환법칙을 어떻게 증명하는지 살펴보자.

모든 자연수 a, b에 대하여 a+b = b+a가 성립하는 것을 보이려면 쓸만한 공리는 PA5밖에 없다. 따라서, 모든 a에 대하여 a+1 = 1+a가 성립함을 보인 다음, a+b = b+a가 성립하는 b에 대하여 a+b' = b'+a가 성립함을 보이면 된다. 이렇게 하면, a+b = b+a를 만족하는 b들을 모아 만든 집합에 1이 포함되고 그 집합의 원소 b에 대해 b' 또한 포함되므로 PA5에 의해 이 집합은 자연수 전체의 집합과 같아진다. 따라서, 모든 자연수 b에 대해 a+b = b+a가 된다. 한 마디로 "수학적 귀납법"이다.

첫 번째 단계인, 모든 a에 대하여 a+1 = 1+a가 성립함을 보이는 방법도 역시 PA5를 이용한다.
집합 S를 a+1 = 1+a가 성립하는 a들을 모두 모은 것이라고 하면 우선 1+1 = 1+1은 당연히 성립하므로 1∈S이다.
그 다음 a∈S일 때, 덧셈의 정의에 의해

a'+1 = （a+1）+1 = （1+a）+1 = （1+a）' = 1+a'

이 되어 a' 또한 S의 원소가 된다. 그러면 PA5에 의해 집합 S는 자연수 전체의 집합과 같아지므로, 결국 모든 자연수 a에 대하여 a+1 = 1+a가 성립함이 증명되었다.

이번에는 모든 자연수 a에 대하여 a+b = b+a가 되는 b들을 모두 모은 것을 집합 T라고 하자. 우선 a+1 = 1+a이므로 1은 T의 원소이다.

다음으로 a+b' = b'+a가 모든 자연수 a에 대하여 성립함을 보여야 한다. 고정된 자연수 b'에 대하여 a+b' = b'+a가 되는 a들을 모두 모은 것을 집합 Sb'이라고 하자. 1+b' = b'+1이므로 1∈Sb'이다. a∈Sb'일 때,


a'+b' = （a'+b）' （덧셈의 정의）
= （b+a'）' （b∈T이므로 a'+b = b+a'）
= （（b+a）'）' （덧셈의 정의）
= （（a+b）'）' （b∈T이므로 a+b = b+a）
= （a+b'）' （덧셈의 정의）
= （b'+a）' （a∈Sb'이므로 a+b' = b'+a））
= b'+a' （덧셈의 정의）
이므로 a'∈Sb'이 되고, 따라서 Sb'은 PA5에 의해 자연수 전체의 집합과 같다. 그러면 모든 자연수 a에 대하여 a+b' = b'+a가 성립하므로 b'∈T이고 다시 PA5에 의해 T는 자연수 전체의 집합이 된다. 이것은 모든 자연수 b가 모든 자연수 a에 대하여 a+b = b+a를 만족한다는 뜻이므로 결국 교환법칙이 증명되었다.