우선 이것을 증명하기 위해서는 그 출발점이 되는 공리 체계가 필요하다. "Principia Mathematica"에서 사용한 공리는 자연수에 대한 공리 체계인 "페아노 공리계(Peano Axioms)"이다.
이것은 이탈리아 수학자 주제페 페아노(Giuseppe Peano)가 만든 것으로, 다음의 다섯 가지 공리로 이루어져 있다. 말하자면, 이 공리계는 "자연수란 무엇인가"에 대한 답이라고 할 수 있다.
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를 만족한다는 뜻이므로 결국 교환법칙이 증명되었다.
한편 덧셈과 비슷하게 곱셈은 다음과 같이 정의할 수 있는데,
a * 1 := a
a*b' := a*b + a
이 정의를 이용하면 곱셈에 대한 교환법칙, 결합법칙, 그리고 분배법칙까지 모두 증명할 수 있다.
