불가능의 증명

자와 컴퍼스로 각을 셋으로 나누는 법, 5차방정식의 근의 공식⁠(quadratic formula)⁠, 어떤 파일이든 줄여 주는 압축, 프로그램이 멈출지 알려 주는 프로그램, 모두가 공정하다고 여길 투표 규칙. 이것들이 없다는 것을 우리는 찾다가 지쳐서가 아니라 증명으로 압니다. 서로 멀리 떨어진 분야의 이 증명들은 거의 모두 세 가지 무기 가운데 하나를 씁니다.

이 글의 처럼 점선이 그어진 숫자는 좌우로 끌 수 있고(키보드 ←/→도 됩니다), 색이 칠해진 같은 말은 눌러서 바꿀 수 있습니다. 밑줄 친 말에 마우스를 올리면 그림에서 그 부분이 빛납니다. 그림 속 칸은 대부분 눌러서 바꿀 수 있고, 마우스를 올리면 설명이 뜹니다. 휴대폰에서는 마우스를 올리는 대신 누르면 됩니다.

1880년 초, 미국 동부의 신문들은 작은 나무 상자 하나를 두고 떠들썩했습니다. 가로세로 4칸의 상자에 1부터 15까지 적힌 조각 열다섯 개가 들어 있고, 한 칸이 비어 있습니다. 빈칸 옆의 조각을 밀어 옮기기만 하면서 조각들을 번호 순서대로 가지런히 놓는 것이 놀이입니다. 사람들은 특히 한 가지 배치에 매달렸습니다. 다른 조각은 모두 제자리인데 14와 15만 뒤바뀐 배치입니다. 거기서 가지런한 배치로 돌아가는 데 성공했다는 사람은 끝내 나오지 않았습니다.

그 무렵 볼티모어에서 나온 『미국 수학 저널』 1879년 12월호에 두 수학자의 짧은 글이 실렸습니다. 결론은 "그 배치는 풀 수 없다"였습니다. 여기서 한번 생각해 볼 만합니다. 조각 배치는 20조 가지가 넘습니다. 모두 시도해 볼 수는 없습니다. 천 명이 실패했다는 것도 증거가 되지 못합니다. 천한 번째 사람은 성공할지 모르니까요. '할 수 없다'는 것은 어떻게 증명할까요? 이미 해 본 시도뿐 아니라 아직 아무도 떠올리지 못한 시도까지 한꺼번에 막는 논증이 있어야 합니다.

이런 논증은 수학의 곳곳에 있습니다. 2,000년 묵은 작도 문제, 5차방정식, 압축과 통신의 한계, 계산할 수 없는 문제, 증명할 수 없는 문장, 투표의 역설. 겉으로는 서로 아무 상관이 없어 보이지만, 뜯어 보면 무기는 거의 셋뿐입니다. 규칙대로 움직여 닿을 수 있는 것들의 모임을 떠올려 봅시다. 목표가 그 모임 밖에 있다는 것을 보이는 방법은 이렇습니다.

• 불변량⁠(invariant)⁠: 모임의 모든 원소⁠(element)⁠가 공유하는 성질을 찾고, 목표에는 그 성질이 없음을 보입니다. 규칙대로 한 걸음 움직여도 변하지 않는 양을 찾으면 됩니다(1–5절).
• 세기: 모임의 크기가 목표를 다 담기에 모자람을 보입니다. 비둘기가 비둘기집보다 많으면 어딘가 두 마리가 들어갑니다(6절).
• 대각선: 모임의 원소 하나하나와 일부러 어긋나게 목표를 만들어, 그것이 모임에 들 수 없음을 보입니다(7절).

8절에서는 이 틀에 깔끔하게 들어맞지 않는 애로의 투표 정리를 보고, 9절에서는 불가능의 증명이 무엇을 남겼는지를 봅니다.

1 · 색칠 한 번잘린 체스판과 불변량

이 절의 물음은 이것입니다. 경우가 너무 많아 다 시도할 수 없을 때, '덮을 수 없다'를 어떻게 증명할까? 첫째 무기, 불변량을 가장 작은 예에서 봅니다.

가장 작은 예부터 봅시다. 1946년 미국의 철학자 맥스 블랙은 논리적 사고를 다룬 교과서 『비판적 사고』에 이런 문제를 실었습니다. 8×8 체스판에서 마주 보는 두 귀퉁이 칸을 떼어 내면 62칸이 남습니다. 두 칸짜리 도미노 31개로 남은 칸을 빈틈없이, 겹치지 않게 덮을 수 있을까요? 떼어 내지 않은 판을 도미노 32개로 덮는 방법만 해도 12,988,816가지이니, 하나하나 시도해서는 끝이 나지 않습니다.

답은 체스판의 색에 있습니다. 도미노는 어디에 놓든 이웃한 두 칸을 덮고, 이웃한 두 칸은 색이 다릅니다. 그러니 도미노를 몇 개 놓든 덮인 밝은 칸의 수 − 덮인 어두운 칸의 수는 언제나 0입니다. 도미노를 한 개 더 놓을 때마다 두 수가 똑같이 하나씩 늘기 때문입니다. 이렇게 규칙대로 한 걸음 움직여도 변하지 않는 양을 불변량이라 합니다. 마주 보는 두 귀퉁이는 색이 같아서, 남은 판에는 한 색이 32칸, 다른 색이 30칸입니다. 다 덮었다면 덮인 칸이 곧 남은 칸 전부이니 '밝은 칸 수 − 어두운 칸 수'가 32 − 30 = 2(또는 −2)여야 합니다. 그런데 도미노로 덮인 칸에서 이 값은 늘 0이니, 덮을 수 없습니다. 정리하면, 도미노가 무엇을 하든 지키는 성질(색의 균형)을 목표가 어기고 있으니, 아무리 많은 배치를 시도해도 소용없습니다.

아래 판에서 칸을 눌러 떼어 내 보세요(다시 누르면 되돌아옵니다). 그림은 도미노를 가장 많이 놓는 배치를 찾아 청록 막대로 그립니다. 마주 보는 귀퉁이 색이 다른 두 칸 색은 맞는데 막힌 판 모두 되돌리기 볼 것은 두 가지입니다. 밝은 칸과 어두운 칸의 수가 다를 때 짝 없는 칸이 남는지, 그리고 두 수가 같은데도 짝 없는 칸이 남는 판이 있는지.

남은 칸은 밝은 칸 개, 어두운 칸 개입니다.

색의 셈이 통과한다고 덮을 수 있는 것은 아닙니다. 흔히 불변량이 막지 않으면 가능하다고 생각하지만, 불변량이 주는 것은 필요조건⁠(necessary condition)⁠뿐입니다. 필요조건이란 '덮을 수 있으려면 반드시 성립해야 하는 조건'이고, 성립한다고 덮을 수 있다는 보장은 없습니다. '색은 맞는데 막힌 판'에서는 왼쪽 위 귀퉁이 칸의 두 이웃을 떼어 냈습니다(색의 수를 맞추려고 맨 아래 줄에서도 두 칸을 떼었습니다). 그 칸은 어느 쪽으로도 도미노를 놓을 수 없는데, 색의 수만 보면 아무 문제가 없습니다.

반대로 색이 다른 두 칸을 떼어 내면 어디서 떼어 내든 언제나 덮을 수 있다는 것이 미국의 수학자 랠프 고모리의 정리입니다. 고모리 자신은 발표하지 않았고, 1973년 로스 혼스버거의 책에 실려 알려졌습니다. 증명의 생각은 이렇습니다. 64칸을 한 번씩 모두 지나 제자리로 돌아오는 고리를 하나 그려 둡니다. 고리를 따라가면 칸의 색이 밝음, 어두움, 밝음, …으로 번갈아 나옵니다. 색이 다른 두 칸을 떼어 내면 고리가 두 토막으로 잘리는데, 번갈아 나오는 색 때문에 두 토막은 모두 짝수 개의 칸으로 이루어집니다. 그러니 토막마다 앞에서부터 두 칸씩 묶으면 됩니다.

그렇다면 색이 맞는데도 막힌 판은 무엇으로 막혔다고 증명할까요? 도미노 덮기는 밝은 칸마다 맞닿은 어두운 칸을 하나씩, 서로 겹치지 않게 짝지어 주는 일입니다. 도미노 하나가 밝은 칸 하나와 어두운 칸 하나를 짝짓기 때문입니다. 이런 짝짓기에는 1935년 영국의 수학자 필립 홀이 증명한 홀의 정리⁠(Hall's theorem)⁠가 답을 줍니다. 모두 짝지을 수 없다면 반드시 증거가 있습니다. 한 색의 칸 k개를 골랐는데 그 칸들이 맞닿은 다른 색 칸이 k개보다 적은 묶음이 그것입니다. 예를 들어 밝은 칸 3개가 맞닿은 어두운 칸이 모두 합쳐 2개뿐이라면, 세 칸에 서로 다른 짝을 줄 수 없으니 셋 가운데 하나는 짝 없이 남습니다. 그림의 노란 칸들이 그런 묶음이고, 분홍 칸들이 그 이웃 전부입니다.

색의 셈은 이 증거의 특별한 경우입니다. 귀퉁이 둘을 뗀 판에서 많은 쪽 색의 칸 32개를 모두 고르면, 그 이웃은 다른 색 칸 전부인 30개뿐이니 32 > 30입니다. 그림은 도미노를 한 개씩 더 놓을 수 있는 길을 찾아 끝까지 늘린 다음, 더 늘릴 수 없게 되면 그 길 찾기가 막힌 자리에서 이 증거를 읽어 냅니다. 이 방법은 「짝을 찾는 알고리즘」의 증가 경로⁠(augmenting path)⁠와 같습니다. 정리하면, '할 수 없다'에는 늘 확인할 수 있는 증거가 있고, 그 증거가 전체의 색 균형이든 일부 칸의 이웃 부족이든 모두 짝의 수가 모자란다는 셈입니다.

2 · 열다섯 조각순열⁠(permutation)⁠의 홀짝

이 절의 물음은 머리말의 물음입니다. 14와 15만 뒤바뀐 배치는 왜 풀 수 없을까? 체스판의 색처럼, 조각을 밀 때마다 지켜지는 무언가를 찾으면 됩니다.

다시 1880년으로 돌아갑시다. 퍼즐은 뉴욕주 캐너스토타의 우체국장 노이스 채프먼이 1874년 무렵 만든 것으로 알려져 있습니다. 1879년 말 보스턴에서 상품이 되어 나오자 몇 달 만에 미국과 유럽을 휩쓸었습니다. 뒤에 퍼즐 작가 샘 로이드는, 자기가 이 퍼즐을 발명했고 14–15 배치를 푸는 사람에게 1,000달러를 걸었다고 오랫동안 주장했습니다. 그러나 2006년 퍼즐 연구가 제리 슬로컴과 딕 손네펠트의 조사로, 발명 이야기는 근거가 없다는 것이 밝혀졌습니다.

『미국 수학 저널』은 존스홉킨스 대학에서 제임스 실베스터가 1878년에 창간한 학술지입니다. 해군사관학교의 윌리엄 존슨은 거기 실린 글에서 배치의 절반은 어떻게 밀어도 가지런해지지 않는다는 것을 보였고, 존스홉킨스의 윌리엄 스토리는 나머지 절반은 모두 풀린다는 것을 보였습니다.

존슨의 불변량을 만들어 봅시다. 판의 조각을 왼쪽 위에서부터 한 줄씩 읽어 한 줄의 수열로 놓습니다. 빈칸은 16이라고 칩니다. 그 수열에서 큰 수가 작은 수보다 앞에 오는 쌍의 수를 셉니다. 이런 쌍을 '뒤바뀐 쌍'이라 부릅니다. 예를 들어 짧은 수열 3, 1, 2에서는 (3, 1)과 (3, 2)가 뒤바뀐 쌍이니 2개이고, 1, 3, 2에서는 (3, 2) 하나입니다. 가지런한 배치에서는 0입니다.

핵심은 한 가지 사실입니다. 수열에서 아무 두 수를 맞바꾸면 뒤바뀐 쌍의 수는 반드시 홀수만큼 변합니다. 이웃한 두 수를 맞바꾸면 그 두 수의 쌍 하나만 뒤집히니 정확히 1만큼 변합니다. 3, 1, 2에서 이웃한 3과 1을 맞바꾸면 1, 3, 2가 되어 2개가 1개로 줄어듭니다. 다른 수들과의 앞뒤는 그대로이기 때문입니다. 떨어진 두 수를 맞바꾸는 일은 이웃끼리의 맞바꾸기를 홀수 번 한 것과 같습니다. 가운데에 k개가 끼어 있으면 앞의 수를 뒤로 보내는 데 k + 1번, 뒤의 수를 앞으로 가져오는 데 k번이 들어 모두 2k + 1번이기 때문입니다. 예를 들어 3, 1, 2에서 떨어진 3과 2를 맞바꾸면(가운데에 1이 하나, k = 1) 이웃 맞바꾸기 3번으로 2, 1, 3이 되고, 뒤바뀐 쌍은 (2, 1) 하나로 2개에서 1개로 줄어듭니다. 홀수 번의 ±1 변화를 더하면 늘 홀수입니다.

이제 퍼즐로 돌아갑니다. 조각을 한 번 밀면 빈칸(16)과 조각 하나가 맞바뀌니, 뒤바뀐 쌍의 홀짝이 바뀝니다. 동시에 빈칸이 한 칸 움직이니, 빈칸에서 오른쪽 아래 구석까지의 거리(가로와 세로 칸 수의 합)의 홀짝도 바뀝니다. 둘이 한꺼번에 바뀌니 뒤바뀐 쌍의 수 + 빈칸의 거리의 홀짝은 변하지 않습니다. 홀수에 홀수 변화를 두 번 주면 다시 홀수이듯, 홀짝이 두 번 바뀌면 제자리이기 때문입니다.

아래 판에서 직접 밀어 보세요. 조각을 밀 때마다 그림 아래의 값이 바뀌는데, 그 홀짝은 한 번도 바뀌지 않는 것을 확인할 수 있습니다.

섞기 14와 15를 빼서 바꿔 끼우기 밀어 온 길 되감기 처음으로

가지런한 배치의 값은 0 + 0, 짝수입니다. 14와 15만 바꾼 배치는 뒤바뀐 쌍이 하나이고 빈칸은 제자리이니 1 + 0, 홀수입니다. 밀기는 이 홀짝을 바꾸지 못하니, 수십억 번을 밀어도 두 배치는 서로 오갈 수 없습니다. 증명에 든 것은 셈 하나와 '한 걸음이 불변량을 지키면 몇 걸음을 가도 지킨다'는 수학적 귀납법⁠(mathematical induction)⁠뿐입니다. 스토리가 증명한 나머지 절반을 더하면, 16개의 자리에 놓을 수 있는 배치 16!(16 팩토리얼⁠(factorial)⁠, 곧 16 × 15 × ⋯ × 1) = 20,922,789,888,000가지 가운데 정확히 절반인 10,461,394,944,000가지가 가지런한 배치와 서로 오갈 수 있습니다.

이 홀짝은 순열의 가장 기본적인 성질입니다. 순열이란 늘어놓인 것들의 자리를 뒤섞는 방법 하나를 말합니다. 순열을 맞바꾸기 몇 번으로 쪼개는 방법은 많지만 그 횟수의 홀짝은 순열마다 하나로 정해져 있습니다. 맞바꾸기 짝수 번으로 되는 것을 짝수 순열⁠(even permutation)⁠, 홀수 번으로 되는 것을 홀수 순열이라 합니다. 두 순열을 이어서 하면 횟수가 더해지니 홀짝도 더해집니다(홀 + 홀 = 짝, 짝 + 홀 = 홀).

그래서 짝수 순열들은 자기들끼리 닫혀 있는 절반짜리 모임을 이룹니다. 짝수 순열 둘을 잇달아 하면 짝 + 짝 = 짝이니 다시 짝수 순열입니다. 이런 모임을 군 안의 부분군⁠(subgroup)⁠이라 합니다. 군이란 잇달아 하기와 되돌리기에 대해 닫혀 있는 동작들의 모임이고, 부분군은 그 안에서 다시 닫혀 있는 작은 모임입니다. 이 절반짜리 모임은 4절에서 5차방정식을 막는 자리에 다시 나옵니다.

150년 앞서 오일러도 같은 종류의 무기를 썼습니다. 쾨니히스베르크의 일곱 다리를 한 번씩만 건너는 산책을 하려면, 출발점과 도착점을 뺀 모든 땅에 붙은 다리 수가 짝수여야 합니다. 지나갈 때마다 들어가는 다리 하나와 나오는 다리 하나를 쓰기 때문입니다. 일곱 다리의 네 땅은 다리 수가 모두 홀수였습니다(오일러 경로⁠(Euler path)⁠, 「일곱 다리의 도시」).

3 · 2,000년의 숙제자와 컴퍼스로 오를 수 있는 탑

이 절의 물음은 이것입니다. 자와 컴퍼스로 그릴 수 있는 길이에는 어떤 공통된 성질이 있을까? 그 성질을 찾으면, 2,000년 동안 아무도 못 그린 길이들이 왜 그려지지 않는지가 한 번에 보입니다.

고대 그리스 사람들이 남긴 작도 문제 셋이 있습니다. 부피가 주어진 정육면체의 두 배인 정육면체의 변을 그리는 문제, 아무 각이나 셋으로 똑같이 나누는 문제, 주어진 원과 넓이⁠(area)⁠가 같은 정사각형을 그리는 문제입니다. 도구는 유클리드의 『원론』이 허락한 두 가지, 두 점을 잇는 눈금 없는 자와, 중심과 반지름으로 원을 그리는 컴퍼스뿐입니다. 첫 문제에는 델로스 사람들이 전염병을 멈추려고 신탁의 말대로 제단의 부피를 두 배로 키우려 했다는 이야기가 붙어 있지만, 수백 년 뒤의 기록에 나오는 전설입니다.

그리스 사람들이 이 문제들을 못 푼 것은 아닙니다. 기원전 4세기 메나이크모스는 포물선⁠(parabola)⁠과 쌍곡선⁠(hyperbola)⁠의 교점으로 두 배 정육면체의 변을 얻었고(원뿔곡선⁠(conic section)⁠), 아르키메데스의 것으로 전해지는 작도는 자에 눈금 두 개를 찍고 미끄러뜨려 어떤 각이든 셋으로 나눕니다. 그들은 도구가 중요하다는 것을 알았고, 자와 컴퍼스만으로는 되는지를 물었습니다. 그 질문이 2,000년을 버텼습니다. 1775년 파리 왕립 과학 아카데미는 이 세 문제와 영구 기관의 '풀이'를 더는 심사하지 않기로 결의했습니다. 제대로 된 불가능성 증명은 그때까지 하나도 없었습니다.

문제의 모양은 일찍부터 바뀌어 왔습니다. 기원전 5세기 키오스의 히포크라테스는 두 배 정육면체 문제가 길이 a와 2a 사이에 $a : x = x : y = y : 2a$가 되는 두 길이 x, y를 끼워 넣는 문제와 같다는 것을 보였습니다. a에서 x로, x에서 y로, y에서 2a로 갈 때마다 같은 배수⁠(multiple)⁠로 커지게 끼워 넣는 것입니다. 그 배수를 r이라 하면 $2a = a r^3$이니 $r^3 = 2$이고, $x = ar$이니 $x^3 = 2a^3$, 곧 x가 부피 두 배인 정육면체의 변입니다. 이렇게 끼워 넣는 두 길이를 비례중항⁠(mean proportional)⁠이라 하고, 메나이크모스의 원뿔곡선(원뿔을 평면으로 자른 단면에 생기는 포물선, 쌍곡선 같은 곡선)은 이 두 비례중항을 찾는 방법이었습니다.

도구를 따지는 태도에는 철학이 얹혀 있었습니다. 수백 년 뒤 플루타르코스가 전하는 이야기가 있습니다. 플라톤이 이 문제를 기계 장치로 푼 에우독소스, 아르키타스, 메나이크모스의 무리를 두고, 형체 없는 것을 다루는 기하학을 감각의 세계로 끌어내려 그 좋은 점을 망친다고 나무랐다는 것입니다. 4세기 알렉산드리아의 파포스는 문제를 직선과 원만으로 풀리는 '평면 문제', 원뿔곡선이 필요한 '입체 문제', 더 복잡한 곡선이 필요한 '선 문제'로 나누고, 평면 문제를 입체의 방법으로 푸는 것은 잘못이라고 적었습니다. 그렇다면 두 배 정육면체는 정말 평면 문제가 아닌가? 이 물음에 데카르트는 1637년 『기하학』에서 평면 문제가 아니라고 주장했지만, 덴마크의 수학사가 예스페르 뤼첸의 분석에 따르면 그의 논증은 증명이 되지 못했습니다. 1754년에는 몽튀클라가 이를 대수의 논증으로 바꾸어 적었고, 1775년에는 8절에서 만날 콩도르세도 비슷한 논증을 짧게 적었다고 전합니다. 그러나 오늘날의 기준으로 완결된 증명으로 꼽히는 것은 아래에 나올 1837년의 논문입니다.

파포스와 데카르트 사이의 긴 시간 동안 이 물음은 아랍어로 글을 쓴 수학자들의 손에서 이어졌습니다. 앞에서 본 아르키메데스의 눈금 자 삼등분부터 그리스어 원본이 남아 있지 않습니다. 9세기 바그다드에서 그리스 문헌을 아랍어로 옮기던 타비트 이븐 쿠라가 아르키메데스의 것이라며 소개한 『보조정리⁠(lemma)⁠의 책』으로만 전합니다(바그다드 지혜의 집). 1070년 무렵 사마르칸트에서 오마르 하이얌은 『대수 문제의 증명에 관한 논고』에서 3차방정식⁠(cubic equation)⁠을 모든 꼴로 나누고, 꼴마다 두 원뿔곡선이 만나는 점으로 양의 근을 그려 보였습니다. 두 배 정육면체를 원뿔곡선으로 푼 메나이크모스의 방법을 3차방정식 전체로 넓힌 셈입니다. 그는 이런 방정식의 풀이에는 원뿔곡선이 필요하고 자와 컴퍼스로는 풀 수 없다고 적었습니다. 증명은 없었고, 그 주장은 750여 년 뒤 아래의 1837년 논문에서야 증명됩니다. 하이얌은 계수에서 근을 바로 계산하는 셈법도 찾지 못했고 "우리 뒤에 오는 누군가가 찾을지도 모른다"고 적었습니다. 그 셈법은 4절에서 볼 16세기 이탈리아에서 나왔습니다.

돌파구는 문제를 기하⁠(geometry)⁠에서 대수로 옮긴 데서 왔습니다. 곧 '어떤 점을 그릴 수 있나'를 '어떤 수를 얻을 수 있나'로 바꾸는 것입니다. 길이 1인 선분을 하나 정해 두고, 그 선분을 좌표의 눈금으로 삼습니다. 그러면 그려 낸 점마다 좌표라는 수가 붙고, 그려 낸 선분마다 길이라는 수가 붙습니다.

그 첫걸음도 데카르트의 『기하학』(1637)에 있습니다. 데카르트는 길이 1인 선분을 하나 정해 두면 자와 컴퍼스로 두 길이의 합, 차, 곱, 몫과 한 길이의 제곱근을 그릴 수 있음을 보였습니다. 합과 차는 선분을 이어 붙이거나 잘라 내면 되고, 곱과 몫은 닮은 삼각형으로, 제곱근은 반원 안의 직각삼각형⁠(right triangle)⁠으로 그립니다. 그러니 1에서 출발해 사칙연산과 제곱근을 몇 번이고 거듭해 얻는 수는 모두 작도됩니다.

거꾸로, 작도로 얻는 수가 이것들뿐인지도 따져 볼 수 있습니다. 작도에서 새 점은 언제나 두 직선, 직선과 원, 두 원이 만나는 곳에 생깁니다. 좌표로 적으면 직선은 $y = 2x + 1$처럼 x와 y가 일차로만 나오는 식이고, 원은 중심 (a, b), 반지름 r일 때 $(x - a)^2 + (y - b)^2 = r^2$처럼 제곱이 들어간 식입니다. 두 직선의 교점은 일차방정식을 풀어 나오니 사칙연산만 씁니다. 원이 끼면 이차방정식이 됩니다. 두 원의 교점도 따로 따질 필요가 없습니다. 두 원의 식을 서로 빼면 제곱 항이 지워져 직선의 식이 되니, 두 원의 교점은 그 직선과 한 원의 교점과 같습니다.

작은 예를 봅시다. 원점이 중심인 반지름 1인 원 $x^2 + y^2 = 1$과 직선 $y = x$의 교점은, 둘째 식을 첫째 식에 넣어 $2x^2 = 1$, 곧 $x = \pm\sqrt{1/2}$입니다. 이미 얻은 수(1과 2)에서 사칙연산과 제곱근 하나로 새 수가 나왔습니다. 이차방정식의 근의 공식에는 제곱근이 하나 들어 있을 뿐이니, 어떤 교점을 구하든 새로 생기는 것은 기껏해야 제곱근 하나입니다.

두 방향을 합치면 이렇습니다. 작도할 수 있는 수는 1에서 출발해 사칙연산과 제곱근을 몇 번이고 거듭해 얻는 수, 정확히 그것뿐입니다(작도 가능한 수⁠, constructible number⁠). 이제 '그릴 수 있나'는 '사칙연산과 제곱근만으로 이 수에 닿을 수 있나'라는 대수의 물음이 되었습니다.

이제 불변량이 필요합니다. 사칙연산에 닫혀 있는 수들의 모임을 체라고 부릅니다. 닫혀 있다는 것은 모임 안의 두 수를 더하고 빼고 곱하고 (0이 아닌 수로) 나누어도 모임 안에 남는다는 뜻입니다. 유리수(분수로 적히는 수) 전체를 ℚ('큐'라고 읽습니다)로 적는데, 이것이 가장 작은 예입니다. 유리수끼리 사칙연산을 하면 다시 유리수입니다.

ℚ에 √2를 보태면 $a + b\sqrt2$(a, b는 유리수⁠(rational number)⁠) 꼴의 수들이 새 체를 이룹니다. 예를 들어 $(1 + \sqrt2)(3 - \sqrt2) = 3 - \sqrt2 + 3\sqrt2 - 2 = 1 + 2\sqrt2$로 곱해도 같은 꼴입니다(√2 × √2 = 2가 다시 유리수가 되기 때문입니다). 이 체의 수는 유리수 두 개(a와 b)로 적히니, 이 체의 ℚ에 대한 차수는 2라고 합니다. 차수는 '이 체의 수 하나를 적는 데 유리수가 몇 개 필요한가'입니다.

여기에 다시 √3을 보태 봅시다. 새 체의 수는 $p + q\sqrt3$ 꼴인데, 이번에는 p와 q가 유리수가 아니라 앞 체의 수 $a + b\sqrt2$, $c + d\sqrt2$입니다. 풀어 적으면

이니, 새 체의 수는 $a + b\sqrt2 + c\sqrt3 + d\sqrt6$ 꼴이고 유리수 네 개(a, b, c, d)가 필요합니다. 차수는 4 = 2 × 2입니다. 층이 하나 오를 때마다 '앞 층의 수 두 개'로 적히니 차수가 두 배가 됩니다.

일반적으로, 제곱근을 하나 더 보탤 때마다 차수는 그대로이거나(보탠 제곱근이 이미 들어 있던 수라면) 두 배가 됩니다. 층을 여러 번 오르면 차수는 층마다 곱해집니다. 그러니 작도할 수 있는 수는 모두 차수가 1, 2, 4, 8, … 인 체 안에 삽니다. 곧 2의 거듭제곱입니다. 이것이 작도의 불변량입니다.

한편 수 하나에도 차수가 있습니다. 그 수를 근으로 하는 유리수 계수 다항식⁠(polynomial)⁠ 가운데 가장 낮은 것의 차수입니다. √2는 $x^2 - 2 = 0$의 근이고 일차식의 근은 아니니(√2는 유리수가 아니니) 차수가 2입니다. 이 차수는 ℚ에 그 수 하나만 보태 만든 체의 차수와 같습니다. 예를 들어 ℚ에 $\sqrt[3]{2}$(세제곱하면 2가 되는 수)를 보태면 $a + b\sqrt[3]{2} + c\sqrt[3]{4}$ 꼴의 수가 생기고 유리수 세 개가 필요합니다. $(\sqrt[3]{2})^3 = 2$이라 세제곱부터는 다시 유리수로 줄어들기 때문입니다.

이제 두 사실을 맞붙입니다. 차수가 3인 수 α가 차수 8인 어떤 체 K 안에 있다고 해 봅시다. 그러면 ℚ에서 K까지 두 층으로 오를 수 있습니다. ℚ에 α만 보탠 체까지 한 층(차수 3), 거기서 K까지 또 한 층(차수를 m이라 합시다). 층마다 곱해지니 8 = 3 × m이어야 하는데, 8은 3으로 나누어떨어지지 않습니다. 곧 수 하나의 차수는 그 수가 든 체의 차수를 반드시 나눕니다. 2의 거듭제곱을 나누는 수는 2의 거듭제곱뿐이니, 차수가 3인 수는 작도될 수 없습니다.

두 배 정육면체의 변 $\sqrt[3]{2}$가 정말 차수 3인지 확인합시다. 이 수는 $x^3 - 2 = 0$의 근입니다. 차수가 3보다 낮으려면 이 식이 더 낮은 차수의 유리수 계수 식들의 곱으로 쪼개져야 합니다. 3을 더 작은 두 수의 합으로 나누는 길은 1 + 2뿐이니, 쪼개진다면 반드시 일차식 하나가 떨어져 나오고, 그 일차식에서 유리수 근이 하나 나와야 합니다.

그런데 유리수 근이 있다면 후보가 몇 개로 좁혀집니다. 근을 기약분수(더 약분할 수 없는 분수)로 적으면, 분자는 상수항 2를, 분모는 맨 앞의 계수 1을 나누어야 하기 때문입니다. 그러니 후보는 ±1, ±2 넷입니다. 넣어 보면 1³ − 2 = −1, 2³ − 2 = 6, (−1)³ − 2 = −3, (−2)³ − 2 = −10으로 모두 0이 아닙니다. 그러니 $\sqrt[3]{2}$의 차수는 3이고, 3은 어떤 2의 거듭제곱도 나누지 못합니다. 두 배 정육면체는 작도할 수 없습니다.

각의 삼등분도 같습니다. 반지름 1인 원에서 각 θ만큼 돌아간 점의 가로 좌표를 cos θ('코사인⁠(cosine)⁠ 세타')라 합니다. 원의 중심에서 20° 각을 그릴 수 있다면, 그 점에서 가로축에 수선⁠(perpendicular)⁠을 내려 길이 $\cos 20^\circ$를 얻습니다. 거꾸로 길이 $\cos 20^\circ$를 얻으면 그 자리에서 수선을 올려 원과 만나는 점으로 20° 각을 되찾습니다. 그러니 60°를 셋으로 나누는 일은 수 $\cos 20^\circ \approx 0.940$을 작도하는 일과 같습니다.

이 수가 만족하는 식은 삼배각 공식⁠(triple-angle formula)⁠ $\cos 3\theta = 4\cos^3\theta - 3\cos\theta$에서 나옵니다(θ = 0°를 넣으면 1 = 4 − 3으로 맞습니다). θ = 20°를 넣으면 cos 60° = 1/2이니 $x = \cos 20^\circ$는 $4x^3 - 3x = \tfrac12$, 양쪽에 2를 곱하면 $8x^3 - 6x - 1 = 0$의 근입니다. 유리수 근의 후보는 분자가 1의 약수⁠(divisor)⁠, 분모가 8의 약수인 ±1, ±1/2, ±1/4, ±1/8입니다. 예를 들어 x = 1/2을 넣으면 1 − 3 − 1 = −3이고, 여덟 후보 모두 0이 되지 않습니다. 그러니 이 식도 쪼개지지 않고 $\cos 20^\circ$의 차수는 3입니다.

아래 그림으로 여러 목표를 저울에 올려 봅시다. 목표를 골라 보세요: 그림의 왼쪽 사다리(작도로 오를 수 있는 높이)와 오른쪽 탑(목표가 요구하는 높이)을 비교하면 됩니다. 오른쪽 탑의 단 하나하나가 방정식 한 번이고, 모든 단이 초록(이차)이면 사다리의 가로대와 높이가 맞습니다. 빨간 단이 하나라도 있으면 맞지 않습니다.

이 수의 차수는 입니다.

정다각형⁠(regular polygon)⁠도 같은 저울에 올릴 수 있습니다. 1796년 3월, 괴팅겐 대학의 열여덟 살 학생 가우스는 정17각형⁠(regular heptadecagon)⁠을 자와 컴퍼스로 그릴 수 있다는 것을 발견했습니다. 유클리드 이후 처음으로 새 정다각형이 작도 목록에 오른 것입니다. 원의 중심을 원점에 두고 반지름을 1로 잡으면, 정17각형의 꼭짓점⁠(vertex)⁠은 원 둘레를 17등분하는 점들입니다. 이 점들을 복소수⁠(complex number)⁠로 보면 17제곱해서 1이 되는 수들이라서 1의 17제곱근이라 부릅니다.

가우스는 1을 뺀 나머지 16개 점을 8개씩 두 무리로 나누고, 각 무리를 다시 4개씩, 2개씩, 1개씩 나누었습니다. 나눌 때마다 '두 무리의 합'이 이차방정식 하나의 두 근이 됩니다. 17 − 1 = 16 = 2⁴이라 둘로 나누기를 네 번 하면 끝나고, 네 단계가 모두 이차방정식입니다. 그림에서 정17각형을 고르고 탑의 단에 마우스를 올려 보세요. 그림은 첫 꼭짓점의 가로 좌표 cos(2π/17)의 두 배인 수 2cos(2π/17)까지 세 단계를 보여 줍니다(2π/17은 360°를 17로 나눈 각입니다). 네 번째 단계는 이 가로 좌표에서 꼭짓점 자체를 얻는 이차방정식입니다.

1801년 『산술 연구』에서 가우스는 p가 소수⁠(prime number)⁠일 때 정p각형은 p − 1이 2의 거듭제곱일 때만 작도할 수 있다고 적었지만, '그때만'의 증명은 싣지 않았습니다. 정칠각형을 골라 보면 이유가 보입니다. 7 − 1 = 6에는 3이 들어 있어서 여섯 점을 어떻게 나누어도 한 번은 셋으로 나누어야 하고, 그 단계는 반드시 삼차방정식입니다. 정13각형도 12 = 2 × 2 × 3이라 같은 까닭으로 막힙니다.

여기서 두 가지를 조심해야 합니다. 첫째, 이 정리는 아무 각이나 셋으로 나누는 일반적인 방법이 없다는 뜻입니다. 90°처럼 셋으로 나눌 수 있는 각도 있습니다(30°는 작도됩니다). 흔히 '각의 삼등분은 불가능하다'를 '어떤 각도 삼등분할 수 없다'로 읽지만, 불가능한 것은 모든 각에 통하는 한 가지 방법입니다.

둘째, 차수가 2의 거듭제곱이라는 것은 작도의 필요조건일 뿐 일반적으로는 충분조건⁠(sufficient condition)⁠이 아닙니다. 차수가 4인데 작도할 수 없는 수도 있습니다. 예를 들어 $x^4 - 4x + 2 = 0$의 실근은 차수가 4이지만 작도할 수 없습니다. 차수라는 수 하나로는 이 둘을 가를 수 없고, 근들 사이의 대칭까지 보아야 가려집니다. 정다각형에서 충분조건이 되는 것은 1의 거듭제곱근⁠(roots of unity)⁠의 대칭이 특히 단순하기 때문이고, 그 대칭을 다루는 것이 다음 절의 이론입니다.

세 번째 문제, 원의 넓이는 가장 늦게 끝났습니다. 반지름 1인 원과 넓이가 같은 정사각형의 변은 $\sqrt\pi$이니, π를 작도할 수 있느냐는 문제입니다. 1761년 베를린의 요한 하인리히 람베르트가 π가 무리수⁠(irrational number)⁠임을 보였지만 그것으로는 모자랍니다. √2도 무리수이지만 작도됩니다. 필요한 것은 π가 0이 아닌 어떤 정수 계수 다항식의 근도 아니라는 것, 곧 π가 초월수⁠(transcendental number)⁠라는 것입니다(대수적 수와 초월수⁠(algebraic and transcendental numbers)⁠). √2처럼 정수 계수 다항식의 근이 되는 수를 대수적 수⁠(algebraic number)⁠, 그렇지 않은 수를 초월수라 합니다. 초월수는 차수가 유한하지 않습니다(그림은 '무한'으로 적습니다). 차수를 정해 줄 다항식이 하나도 없기 때문입니다. 작도할 수 있는 수는 모두 차수가 유한하니(2의 거듭제곱) 대수적 수입니다. 그러니 π가 초월수이면 √π도 작도될 수 없습니다(√π가 작도되면 그 제곱 π도 작도되기 때문입니다). 1873년 파리의 샤를 에르미트가 자연로그⁠(natural logarithm)⁠의 밑 e(약 2.718인 수)가 초월수임을 보였고, 1882년 프라이부르크의 페르디난트 린데만이 그 방법을 넓혀 π가 초월수임을 증명했습니다. 린데만은 이듬해 쾨니히스베르크로 옮겨 다비트 힐베르트의 박사 논문을 지도했습니다.

정리하면, 자와 컴퍼스로 얻는 수는 모두 차수가 2의 거듭제곱인 체 안에 삽니다. 두 배 정육면체의 $\sqrt[3]{2}$와 60°의 삼등분에 필요한 $\cos 20^\circ$는 차수가 3이고, 원의 넓이에 필요한 π는 차수가 아예 유한하지 않으니, 셋 모두 그 체에 들 수 없습니다.

가우스가 적지 않은 '그때만'의 증명과 두 배 정육면체, 각의 삼등분의 불가능성은 1837년 파리의 20대 초반 청년 피에르 방첼이 리우빌의 학술지에 낸 일곱 쪽짜리 논문에서 한꺼번에 나왔습니다. 2,000년 묵은 문제의 끝이었지만 반응은 거의 없었고, 그의 이름은 한 세기 가까이 잊혔습니다. 덴마크의 수학사가 예스페르 뤼첸은 2009년 논문에서, 무엇보다 당시 수학자들이 이런 불가능성의 결과에 큰 무게를 두지 않았다는 데서 그 까닭을 찾았습니다. 논문이 실린 곳은 당대의 이름난 학술지였으니, 묻힌 것은 자리 탓이 아니었습니다.

가우스가 이 발견을 얼마나 아꼈는지는 기록으로 남아 있습니다. 1796년 3월 30일, 그는 평생 쓴 짧은 수학 일기의 첫 줄에 정17각형 작도의 원리를 라틴어로 적었습니다. 이 일기는 그가 죽고 40여 년 뒤인 1897년에야 발견되어 1903년 클라인이 펴냈습니다. 가우스가 묘비에 정17각형을 새겨 달라고 했다는 이야기가 널리 전하지만 확인할 만한 기록은 없고, 오늘날 브라운슈바이크의 가우스 기념비 받침에 열일곱 꼭짓점의 별이 새겨져 있을 뿐입니다. p − 1이 2의 거듭제곱인 소수 p는 $2^{2^k} + 1$ 꼴이어야 하고, 이런 소수는 3, 5, 17, 257, 65537 다섯 개만 알려져 있습니다. 1640년 페르마가 이 꼴의 수는 모두 소수라고 짐작했다가 1732년 오일러에게 반박당한 이야기는 「소수를 세는 사람들」 8절에 있습니다. 작도의 문제가 소수의 문제로 바뀐 것입니다.

4 · 근의 공식이 없다근을 맞바꾸는 대칭

이 절의 물음은 이것입니다. 이차방정식에는 근의 공식이 있고, 3차와 4차에도 있습니다. 그런데 왜 5차에서 멈출까? 답은 근들을 서로 맞바꾸는 대칭에 있습니다.

이차방정식의 풀이법은 바빌로니아의 점토판에 이미 나옵니다. 오늘날의 말로 적으면 $ax^2 + bx + c = 0$의 근은 $\frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$입니다. 이것처럼 계수(a, b, c)에서 사칙연산과 거듭제곱근(제곱근, 세제곱근, …)만으로 근을 적는 식을 근의 공식이라 합니다. 3차와 4차방정식⁠(quartic equation)⁠의 근의 공식은 16세기 이탈리아에서 나와 1545년 카르다노의 책에 실렸습니다. 3차의 공식은 제곱근을 먼저 구하고 그것을 세제곱근 안에 넣는 모양입니다. 그다음 5차방정식에서 250년 동안 모든 시도가 막혔습니다.

1770년 베를린의 라그랑주는 방향을 바꾸어, 이미 아는 공식들이 왜 통하는지를 물었습니다. 그는 근들을 서로 맞바꾸는 순열에 주목했습니다. 예를 들어 근이 셋(r₁, r₂, r₃)일 때 r₁과 r₂의 자리를 바꾸는 것처럼 근의 자리를 뒤섞는 방법입니다. 근이 셋이면 3 × 2 × 1 = 6가지입니다. 라그랑주의 요령은, 근으로 만든 식 가운데 근을 뒤섞어도 값이 몇 가지로만 바뀌는 것을 찾아 그것부터 푸는 것입니다.

이차방정식으로 이 요령을 따라가 봅시다. $x^2 - 5x + 6 = 0$의 두 근을 r₁, r₂라 하면 $(x - r_1)(x - r_2) = x^2 - (r_1 + r_2)x + r_1 r_2$이니, 계수와 맞춰 보면 $r_1 + r_2 = 5$, $r_1 r_2 = 6$입니다. 합과 곱은 두 근을 맞바꿔도 그대로이니 계수만 보고 알 수 있습니다. 근의 차 $r_1 - r_2$는 맞바꾸면 부호가 바뀌니 값이 두 가지입니다. 그런데 그 제곱은 맞바꿔도 그대로이니, 역시 계수로 적힙니다.

(첫 등호는 양쪽을 풀어 보면 확인됩니다. 둘 다 $r_1^2 - 2r_1 r_2 + r_2^2$입니다.) 그러니 $r_1 - r_2 = \pm 1$이고, 합 5와 더해 반으로 나누면 근 3과 2가 나옵니다. 문자로 똑같이 하면 근의 공식이 그대로 나옵니다. 제곱근 기호는 바로 '맞바꾸면 부호가 바뀌는 양'을 되찾는 자리에 들어갑니다. 라그랑주는 3차와 4차에서도 이런 식을 찾아 공식이 통하는 까닭을 설명했지만, 5차에서는 같은 방법이 막힌다는 것을 보였습니다.

막힌다는 것이 불가능하다는 증명은 아닙니다. 모데나의 파올로 루피니가 1799년 첫 증명을 냈지만 빈틈이 있었고, 노르웨이의 아벨이 1824년 자기 돈으로 인쇄한 여섯 쪽 소책자와 1826년의 더 자세한 논문으로 증명을 완성했습니다. 5차 이상의 일반 방정식에는 근의 공식이 없다는 아벨–루피니 정리입니다. 그러나 어떤 방정식이 거듭제곱근으로 풀리고 어떤 방정식이 안 풀리는지를 가르는 기준은 스무 살에 죽은 에바리스트 갈루아가 찾았습니다.

갈루아의 생각은 3절의 탑과 같은 모양입니다. 방정식마다, 근들 사이의 유리수 계수 관계를 모두 지키면서 근을 맞바꾸는 순열들의 모임이 있습니다. 가장 작은 예로 $x^2 - 2 = 0$의 두 근 √2와 −√2를 봅시다. 두 근 사이의 유리수 계수 관계, 예를 들어 '합이 0', '곱이 −2'는 두 근을 맞바꿔도 그대로 성립합니다. 그래서 이 방정식에서는 '그대로 두기'와 '맞바꾸기' 두 순열이 허용됩니다. 이런 순열들의 모임은 군(잇달아 하기와 되돌리기에 닫혀 있는 동작들의 모임)을 이루고, 오늘날 그 방정식의 갈루아 군⁠(Galois group)⁠이라 부릅니다.

허용되지 않는 순열도 있습니다. $(x^2 - 2)(x^2 - 3) = 0$의 네 근 √2, −√2, √3, −√3에서 √2와 √3을 맞바꾸는 순열은 허용되지 않습니다. '제곱하면 2'라는 관계 $(\sqrt2)^2 = 2$가 맞바꾸면 $(\sqrt3)^2 = 2$라는 거짓이 되기 때문입니다. 갈루아 군은 근들 사이에 숨은 관계가 많을수록 작아지고, 관계가 적을수록 커집니다.

이제 탑과의 연결입니다. 아는 수의 체를 한 층 올리면, 그 층에서 새로 아는 수가 된 것은 더 이상 움직이면 안 됩니다. 그러니 허용되는 순열이 줄어듭니다. $x^2 - 2 = 0$에서 ℚ에 √2를 보태면, 이제 √2는 '아는 수'라서 두 근을 맞바꾸는 순열은 빠지고 '그대로 두기' 하나만 남습니다. 군이 2개에서 1개로 줄었습니다. 근이 모두 아는 수가 되어 군이 '그대로 두기' 하나로 줄어들면, 방정식이 풀린 것입니다.

갈루아가 알아낸 것은 거듭제곱근 하나를 보탤 때 군이 줄어드는 방식이 아주 특별하다는 것입니다(필요한 1의 거듭제곱근을 먼저 보태 둔다면). 그 한 층에서 떨어져 나가는 조각은 언제나 두 동작을 어느 순서로 하든 결과가 같은 군, 곧 가환군입니다. 제곱근이면 조각의 크기가 많아야 2, 세제곱근이면 많아야 3, 이런 식입니다. 세 점을 120°씩 돌리는 회전⁠(rotation)⁠들이 가환군의 예입니다. 120° 돌리고 240° 돌리든, 240° 돌리고 120° 돌리든 결과는 같습니다.

모든 군이 가환인 것은 아닙니다. A, B, C를 늘어놓고 '앞의 두 자리 맞바꾸기'와 '뒤의 두 자리 맞바꾸기'를 해 봅시다. 앞을 먼저 하면 ABC → BAC → BCA이고, 뒤를 먼저 하면 ABC → ACB → CAB입니다. 순서에 따라 결과가 다릅니다.

그러니 거듭제곱근으로 풀리는 방정식의 군은, 가환인 조각을 하나씩 떼어 내어 끝까지('그대로 두기' 하나만 남을 때까지) 줄일 수 있어야 합니다. 이런 군을 가해군⁠(solvable group)⁠이라 합니다. 떼어 내는 방식에는 조건이 하나 더 붙는데(정규부분군이라는 조건), 여기서는 그 세부를 생략합니다. 정리하면, 근의 공식이 있으려면 갈루아 군이 가해군이어야 합니다. 갈루아는 거꾸로 가해군이면 거듭제곱근으로 풀린다는 것도 보였습니다.

근이 셋, 넷, 다섯일 때 모든 순열의 군을 직접 줄여 봅시다. 개수만 적습니다.

• 근 3개(순열 6개): 6 → 3 → 1. 첫 조각은 2개짜리로 2절의 홀짝이고(짝수 순열만 남기기), 둘째 조각은 3개짜리 회전입니다. 둘 다 가환이니 가해군입니다. 3차의 공식이 제곱근 다음 세제곱근인 것과 맞아떨어집니다.
• 근 4개(순열 24개): 24 → 12 → 4 → 1. 조각의 크기가 2, 3, 4이고 모두 가환입니다. 끝에서 두 번째의 4개짜리 군은 '두 쌍을 동시에 맞바꾸기' 셋과 '그대로 두기'로 된 군입니다. 그래서 4차방정식에도 근의 공식이 있습니다.
• 근 5개(순열 120개): 120 → 60에서 첫 조각(홀짝)은 떼어 낼 수 있습니다. 그런데 남은 짝수 순열 60개의 군은 더 작은 조각으로 쪼갤 수 없고, 그 자체도 가환이 아닙니다. 더는 줄일 수 없으니 가해군이 아닙니다.

60개짜리 군이 쪼개지지 않는다는 증명은 짧지 않아 요지만 적습니다. 떼어 낼 수 있는 조각은 '닮은' 순열, 곧 글자의 이름표만 바꿔 붙인 순열을 모두 함께 품어야 합니다(이것이 앞에서 생략한 정규부분군의 조건입니다). 짝수 순열 60개는 닮은 것끼리 1, 15, 20, 12, 12개의 무리로 나뉩니다. 또 이런 모임의 크기는 늘 전체 크기 60의 약수여야 합니다. 그런데 '그대로 두기' 하나뿐인 1개짜리 무리를 포함해 이 무리들을 몇 개 모아 60의 약수 개가 되게 하는 방법은 1개와 60개 둘뿐입니다. 그러니 중간 크기의 조각은 떼어 낼 수 없습니다. 5 이상이면 늘 이렇게 막히고, 그래서 5차 이상의 일반 방정식에는 근의 공식이 없습니다.

구체적인 예로 $x^5 - 6x + 3 = 0$을 봅시다. 이 식은 실근이 셋, 허근(실수⁠(real number)⁠가 아닌 복소수 근)이 둘이고, 갈루아 군이 120개의 순열 전부임을 몇 줄로 보일 수 있습니다(아래 상자). 그러니 이 방정식의 근은 계수에서 사칙연산과 거듭제곱근으로 적을 수 없습니다.

흔한 오해 둘을 짚어 둡니다. 근이 없다는 뜻이 아닙니다. 다섯 근은 복소수로 분명히 있고, 뉴턴 방법⁠(Newton's method)⁠으로 원하는 자릿수까지 계산할 수 있습니다. 모든 5차방정식이 안 풀린다는 뜻도 아닙니다. $x^5 - 2 = 0$의 근 $\sqrt[5]{2}$는 거듭제곱근 그 자체입니다. 없는 것은 모든 5차방정식에 통하는 하나의 공식이고, 이 특정한 방정식의 근을 거듭제곱근으로 적는 식입니다.

불변량의 눈으로 보면 3절과 4절은 한 이야기입니다. 허용된 동작(제곱근 보태기, 거듭제곱근 보태기)은 어떤 성질(차수가 2의 거듭제곱, 군이 가해군)을 지키고, 목표($\sqrt[3]{2}$, 5차방정식의 근)에는 그 성질이 없습니다. 차이는 성질의 정교함입니다. 차수는 수 하나이고, 갈루아 군은 대칭 전체의 구조입니다. 그래서 3절의 $x^4 - 4x + 2 = 0$처럼 차수로는 가를 수 없던 것도 갈루아 군으로는 가려집니다. 수 하나가 작도되려면 차수만이 아니라 그 수가 만족하는 가장 낮은 식의 갈루아 군의 크기(순열의 개수)까지 2의 거듭제곱이어야 합니다. 이 식의 갈루아 군은 근 넷의 순열 24개 전부이고, 24는 2의 거듭제곱이 아니니 그 근은 작도되지 않습니다.

갈루아가 결투 전날 밤 친구에게 남긴 편지와 원고는 14년 뒤인 1846년 조제프 리우빌이 자기 학술지에 펴냈고, 군이라는 개념은 거기서 수학 전체로 퍼졌습니다. 불가능을 증명하려고 만든 도구가 대칭을 다루는 수학의 공용어가 되었습니다.

두 사람의 원고는 모두 파리 과학 아카데미에서 길을 잃었습니다. 아벨이 1826년 낸 큰 논문은 심사를 맡은 코시의 서류 속에 묻혔다가 아벨이 죽은 뒤 1841년에야 인쇄되었습니다(「틀린 증명이 만든 수학」 1절). 갈루아가 1829년 낸 원고는 코시가 심사를 맡았다가 흐지부지되었습니다(이듬해 갈루아가 거두어들인 것으로 보입니다). 1830년 아카데미 대상에 낸 원고는 심사를 맡은 푸리에가 그해 5월 죽으면서 사라졌고, 1831년의 세 번째 원고는 푸아송이 돌려보냈습니다. 그사이 그는 에콜 폴리테크니크 입학시험에 두 번 떨어졌고, 7월 혁명 뒤의 정치 소요 속에 에콜 노르말에서 쫓겨나 감옥에도 갇혔습니다. 1830년 아카데미 대상은 결국 죽은 아벨과 야코비에게 나뉘어 돌아갔습니다. 옳은 증명도 읽어 줄 사람과 자리를 만나지 못하면 묻혔습니다.

작도와 방정식의 불가능성. 아테네와 시라쿠사에서 자와 컴퍼스 밖의 풀이가 나오고, 그 풀이가 바그다드의 번역과 사마르칸트의 하이얌을 거쳐 이어지고, 2,000년 뒤 브라운슈바이크의 가우스, 모데나의 루피니, 크리스티아니아의 아벨, 파리의 갈루아와 방첼, 프라이부르크의 린데만이 차례로 '할 수 없다'를 증명하는 것을 보세요. 역사 줄(분홍)의 1775년 아카데미 결의는 방첼의 증명보다 60여 년, 린데만의 증명보다 100여 년 앞섰습니다.

5 · 단순한 세계에 비추기불변량의 정체, 그리고 증명할 수 없다는 증명

이 절의 물음은 이것입니다. 색, 홀짝, 차수, 군. 서로 달라 보이는 네 불변량에 공통된 모양이 있을까? 그리고 같은 모양으로 '증명할 수 없다'까지 증명할 수 있을까?

지금까지 본 불변량을 나란히 놓으면 공통된 모양이 드러납니다. 복잡한 세계의 대상 하나하나에 단순한 세계의 값 하나를 붙이되, 허용된 동작이 그 값을 바꾸지 않게(또는 정해진 방식으로만 바꾸게) 붙입니다. 체스판의 덮인 칸은 '밝은 칸 수 − 어두운 칸 수'라는 정수로, 퍼즐의 배치는 홀짝으로, 작도한 수는 차수로, 방정식은 군으로 비춥니다. 순열의 홀짝이 좋은 예입니다. 두 순열을 잇달아 하면 홀짝이 더해지니, 순열 전체의 복잡한 곱셈이 '짝·홀'의 덧셈으로 그대로 비칩니다. 이렇게 구조를 지키며 비추는 대응을 준동형⁠(homomorphism)⁠이라 합니다. 단순한 세계에서 두 값이 다르면 복잡한 세계에서도 둘은 오갈 수 없습니다.

가장 오래된 불가능성 증명도 이 모양입니다. 피타고라스 학파의 누군가가 √2가 두 정수의 비로 적히지 않음을 알아냈다고 전해집니다(누가 언제인지는 전설에 가깝습니다). $\sqrt2 = p/q$를 더 줄일 수 없는 분수라고 하면, 양쪽을 제곱하고 $q^2$을 곱해 $p^2 = 2q^2$입니다. 그러니 $p^2$은 짝수이고, 홀수의 제곱은 홀수이니 p는 짝수이고, p = 2r을 넣으면 $q^2 = 2r^2$이니 q도 짝수입니다. 줄일 수 없다던 분수가 2로 줄어드니 모순입니다(무리수). 정수를 '짝·홀'의 세계, 곧 2로 나눈 나머지⁠(remainder)⁠로 비춘 증명입니다.

같은 수법이 논리에서는 '증명할 수 없다'를 증명합니다. 유클리드의 다섯 번째 공준⁠(postulate)⁠, 곧 평행선 공준⁠(parallel postulate)⁠을 나머지 공준에서 증명하려는 시도는 2,000년 동안 이어졌습니다. 평행선 공준은 대략 '직선 밖의 한 점을 지나 그 직선과 만나지 않는 직선은 하나뿐'이라는 주장입니다. 1868년 이탈리아의 에우제니오 벨트라미는 원판 안에서 원판을 가로지르는 현(원 위의 두 점을 잇는 선분)을 '직선'으로 읽는 모형 등을 만들어, 그 안에서 평행선 공준을 뺀 유클리드의 공준들은 모두 참이 되고 평행선 공준만 거짓이 됨을 보였습니다(쌍곡기하⁠(hyperbolic geometry)⁠, 「평행선의 반란」). 여기서 불변량은 '이 모형에서 참'입니다. 올바른 추론 규칙은 참인 전제에서 참인 결론만 내니, 공준들에서 증명되는 것은 모두 이 모형에서 참입니다. 평행선 공준은 이 모형에서 거짓이니 증명될 수 없습니다(이 모형은 유클리드 기하 안에 지은 것이라, 유클리드 기하 자체에 모순이 없다는 가정 아래서입니다).

1963년 폴 코언이 연속체 가설⁠(continuum hypothesis)⁠을 집합론⁠(set theory)⁠의 공리⁠(axiom)⁠에서 증명할 수 없음을 보인 것도 같은 방법이었습니다. 무한에도 크기를 비교할 수 있고(6, 7절에서 봅니다) 실수 전체는 자연수⁠(natural number)⁠ 전체보다 큰 무한인데, 연속체 가설은 그 사이 크기의 무한은 없다는 주장입니다. 코언은 집합론의 공리는 모두 참이고 연속체 가설은 거짓인 모형을 지었습니다. 이것도 집합론 자체에 모순이 없다는 가정 아래서입니다. 반대로 1938년 괴델은 연속체 가설이 참인 모형을 지어, 그것을 반증할 수도 없음을 보였습니다.

불변량은 이렇게 강력하지만 두 가지 한계가 있습니다. 1절에서 보았듯 불변량이 막지 않는다고 가능한 것은 아니고, 가능하다는 쪽은 따로 보여야 합니다(고모리의 고리, 스토리의 절반). 그리고 불변량을 확인하기는 쉽지만 찾기는 어렵습니다. 체스판의 색은 한눈에 보이지만, 갈루아 군이 나오기까지는 카르다노의 책이 나온 뒤로 300년 가까이 걸렸습니다.

정리하면, 불변량은 복잡한 세계를 단순한 세계에 구조를 지키며 비추는 일이고, 두 대상이 단순한 세계에서 다른 값을 받으면 원래 세계에서도 서로 오갈 수 없습니다.

6 · 자리가 모자라다세기와 비둘기집

이 절의 물음은 이것입니다. 불변량을 찾지 못할 때도 '할 수 없다'를 증명할 수 있을까? 둘째 무기는 그냥 개수를 세는 것입니다.

둘째 무기는 세기입니다. 만들 수 있는 것이 필요한 것보다 적으면, 무엇을 어떻게 만들든 빠지는 것이 생깁니다. 비둘기 열 마리를 비둘기집 아홉 칸에 넣으면 어느 칸엔가 두 마리가 들어간다는 비둘기집 원리⁠(pigeonhole principle)⁠입니다. 너무 당연해서 무기처럼 보이지 않지만, 이 사이트의 여러 글에서 가장 날카로운 한계를 그었습니다.

• 압축: 길이 n인 비트열(0과 1을 늘어놓은 것)은 $2^n$개인데 그보다 짧은 비트열은 모두 합쳐 $2^n - 1$개뿐이니(길이 0, 1, …, n − 1인 것이 1 + 2 + ⋯ + 2ⁿ⁻¹개), 모든 파일을 줄여 주는 무손실 압축⁠(lossless compression)⁠은 없습니다. n = 3이면 길이 3인 비트열 8개를 길이 2 이하의 비트열 7개에 하나씩 따로 보낼 수 없습니다. 두 파일이 같은 압축 결과를 받으면 풀 때 어느 쪽인지 알 수 없습니다(「짧게 보내기」 8절).
• 정렬: 카드 n장의 순서는 $n!$가지이고, 예·아니오로 답하는 비교 k번으로 가를 수 있는 경우는 $2^k$가지뿐이니, 비교만으로 정렬하려면 가장 나쁜 경우 적어도 $\lceil \log_2 n! \rceil$번을 비교해야 합니다. $\log_2 n!$은 '2를 몇 번 곱해야 n!이 되는가'이고, ⌈ ⌉는 올림입니다. 10장이면 10! = 3,628,800이고, 이 수는 2²¹ = 2,097,152보다 크고 2²² = 4,194,304보다 작으니 22번입니다(비교 정렬의 하한⁠(comparison sorting lower bound)⁠, 「줄 세우기의 한계」).
• 통신: 섀넌의 1948년 정리의 '넘을 수 없다' 쪽도 셈입니다. 길이 n의 글 가운데 실제로 나올 법한 것은 대략 $2^{nH}$개이니(H는 기호 하나에 담긴 평균⁠(mean)⁠ 정보량, 곧 엔트로피입니다) 기호당 H비트보다 짧게 적을 수 없고(원천 부호화 정리⁠(source coding theorem)⁠), 잡음 섞인 통로의 출력에서 서로 헷갈리지 않게 가려낼 수 있는 메시지는 대략 $2^{nC}$개뿐이니 용량⁠(capacity)⁠ C보다 빨리 믿을 만하게 보낼 수 없습니다(통로 부호화 정리⁠(noisy-channel coding theorem)⁠, 「잡음 너머로」).

세기는 무한에서도 통합니다. 1874년 칸토어는 정수 계수 다항식의 근, 곧 대수적 수는 한 줄로 늘어놓아 셀 수 있지만 실수는 셀 수 없다는 것을 보였습니다(셀 수 있는 집합⁠(set)⁠). '셀 수 있다'는 1번, 2번, 3번, …처럼 자연수로 번호를 빠짐없이 붙일 수 있다는 뜻입니다. 셀 수 없는 것에서 셀 수 있는 것을 빼도 셀 수 없이 많이 남으니, 초월수는 있을 뿐 아니라 실수의 거의 전부가 초월수입니다(대수적 수는 수직선 위에서 길이로 재도 0입니다). 그런데 이 셈은 어느 수가 초월수인지는 말해 주지 않습니다. 칸토어의 논증을 한 단계씩 따라가면 초월수 하나를 계산해 낼 수는 있지만, 그것은 π나 e처럼 우리가 궁금해하던 수가 아닙니다. 3절의 린데만이 따로 필요했던 까닭입니다. 세기는 '대부분이 그렇다'를 쉽게 주지만 '이것이 그렇다'는 주지 않습니다.

이 간극이 가장 뚜렷하게 드러나는 곳이 계산의 어려움입니다. 1949년 섀넌은 스위칭 회로⁠(switching circuit)⁠를 세어 보았습니다. 먼저 만들어야 할 것, 곧 함수⁠(function)⁠를 셉니다. 입력이 n개이고 입력마다 0 또는 1이 들어오면 입력 조합은 $2^n$가지입니다. 함수는 조합마다 출력 0이나 1을 하나씩 정한 표(진리표⁠, truth table⁠)이니, 2를 $2^n$번 곱한 $2^{2^n}$개입니다. n = 2이면 입력 조합이 00, 01, 10, 11의 4가지이고 함수는 $2^4 = 16$개입니다. AND, OR도 이 16개 가운데 둘입니다.

다음은 만들 수 있는 것, 곧 회로를 셉니다. 두 입력을 받는 부품(AND, OR 같은 논리 소자) s개로 만드는 회로는, 부품마다 두 입력 함수 16가지 가운데 하나를 연산으로 고르고, 입력 n개와 앞선 부품들의 출력 가운데 둘을 입력으로 고릅니다. 입력을 고르는 방법은 많아야 $(n+s)^2$가지이니 부품 하나는 많아야 $16(n+s)^2$가지이고, 부품이 s개이니 이것을 s번 곱해 회로는 많아야 $(16(n+s)^2)^s$개입니다. 이 수가 함수의 수 $2^{2^n}$보다 작으면, 회로 하나가 함수 하나만 만드니 어떤 함수는 부품이 s개보다 많이 필요합니다. 비둘기집 원리 그대로입니다. 섀넌 자신은 계전기⁠(relay)⁠ 접점으로 된 회로를 셌고, 여기 적은 것은 오늘날 교과서에서 쓰는 같은 논증입니다. 입력 수 n = 에서 비교해 봅시다. 그림에서 파란 곡선(회로의 수)이 분홍 선(함수의 수)에 처음 닿는 노란 점을 보세요.

입력이 개인 함수는 개입니다. 부품이 개보다 적은 회로를 다 모아도 이 함수들을 모두 만들기에 모자랍니다. 반대로 1958년 소련의 올레크 루파노프는 어떤 함수든 대략 개($2^n/n$)의 부품이면 만들 수 있음을 보였습니다. 셈이 거의 정확한 답을 준 것입니다. 거의 모든 함수는 이만큼 어렵습니다. 그런데 "이 함수가 어렵다"고 이름을 댈 수 있는 함수에 대해 증명된 가장 좋은 하한은 부품 약 개, 곧 대략 $3.1n$개입니다. 2022년 리자투와 양톈치의 결과로, 정확히는 n이 커질 때의 점근적인 하한입니다. 1984년 노르베르트 블룸이 증명한 3n이 30년 넘게 최고 기록이었고, 2016년에야 조금 넘어섰습니다.

P 대 NP 문제의 한가운데에 이 간극이 있습니다. P는 빠르게 풀 수 있는 문제들, NP는 누가 답을 내밀면 그 답이 맞는지 빠르게 확인할 수 있는 문제들의 모임입니다. 여기서 '빠르게'는 걸리는 단계 수가 입력 크기 n의 다항식($n^2$, $n^3$처럼 n의 거듭제곱 정도)으로 묶인다는 뜻입니다. 스도쿠⁠(sudoku)⁠처럼 풀기는 어려워 보여도 채운 답을 확인하기는 쉬운 문제가 NP에 듭니다. P ≠ NP는 '확인은 쉬운데 빠르게 풀 수는 없는 문제가 정말 있다'는 추측입니다. 이것을 보이는 한 가지 길은 NP에 속하는 구체적인 문제 하나가 입력 크기의 어떤 다항식보다도 많은 부품을 요구함을 보이는 것입니다. 셈은 어려운 함수가 넘쳐난다고 말하지만 그중 하나를 집어 주지 않습니다. 1994년 알렉산드르 라즈보로프와 스티븐 루딕은 한 걸음 더 나아가, 회로 하한을 증명하는 데 흔히 쓰던 넓은 부류의 논법('자연스러운 증명')이 암호학에서 널리 믿는 가정 아래에서는 P와 NP를 가를 수 없다는 것을 보였습니다. 불가능성 증명에 대한 불가능성 증명입니다.

이 원리는 흔히 디리클레의 이름으로 불립니다. 1834년 그가 정수론⁠(number theory)⁠의 증명에 이 원리를 썼고 1842년에는 수를 분수로 가까이 어림하는 문제에도 쓴 뒤로, 독일어로 '서랍 원리⁠(drawer principle)⁠'라 불리게 되었기 때문입니다. 그러나 인쇄된 기록은 200년 앞섭니다. 1622년 로렌 공국 퐁타무송의 예수회 수사 장 뢰레숑은 책에서, 사람은 많고 머리카락 수는 한정되어 있으니 머리카락 수가 똑같은 두 사람이 반드시 있다고 적었습니다. 셈만으로 존재를 보이는 이 요령이 조합론⁠(combinatorics)⁠에서 자라난 이야기는 「세지 않고 세기」에 있습니다.

7 · 목록에서 빠지는 것대각선 논법⁠(diagonal argument)⁠

이 절의 물음은 이것입니다. 목록이 완전하지 않다는 것을, 목록을 하나하나 뒤지지 않고 어떻게 증명할까? 셋째 무기는 목록 자신을 재료로 목록에 없는 것을 만드는 것입니다.

셋째 무기는 1891년 칸토어의 대각선 논법에서 시작합니다. 0110…처럼 0과 1이 끝없이 이어지는 줄, 곧 0과 1로 된 무한 수열을 생각합시다. 이런 수열들에 1번, 2번, 3번, …으로 번호를 붙여 늘어놓은 목록이 있다고 합시다. 칸토어의 주장은 목록을 어떻게 만들든 빠지는 수열이 반드시 있다는 것입니다.

작은 예로 봅시다. 목록의 처음 세 수열이 0110…, 1001…, 1110…이라 합시다. 굵게 표시한 것처럼 첫째 수열의 첫째 자리, 둘째 수열의 둘째 자리, 셋째 수열의 셋째 자리를 읽으면 0, 0, 1입니다. 수열들을 위아래로 쌓은 표에서 비스듬히 내려가는 줄이라 이것을 대각선이라 부릅니다. 이 자리들을 모두 뒤집어(0은 1로, 1은 0으로) 1, 1, 0, …으로 시작하는 새 수열 d를 만듭니다. d는 첫째 수열과 첫째 자리에서, 둘째 수열과 둘째 자리에서, 셋째 수열과 셋째 자리에서 다릅니다.

목록이 끝없이 이어져도 똑같습니다. d의 k번째 자리는 k번째 수열의 k번째 자리를 뒤집은 것이니, d는 k번째 수열과 적어도 k번째 자리에서 다릅니다. 어떤 k에서도 그러니 d는 목록 어디에도 없고, 어떤 목록도 모든 수열을 담지 못합니다. 세기와 닮았지만 결정적인 차이가 있습니다. 세기는 모임의 크기를 비교하고, 대각선은 목록 자신을 재료로 목록에 없는 것을 직접 만듭니다.

이 한 가지 모양이 서로 다른 네 정리가 됩니다. 아래 표는 같은 대각선을 네 가지로 읽습니다. 표의 칸을 눌러 목록을 바꾸고(어떻게 바꿔도 분홍 줄이 목록의 모든 줄과 어긋나는지 보세요), k를 끌어(지금 k = ) "대각선을 뒤집은 줄이 k번째 줄이라면?"을 따져 보세요. 읽는 법을 바꾸면 줄의 이름과 칸의 기호가 바뀌고, 그림 아래의 설명도 그 읽기로 바뀝니다. 아래에서 네 읽기를 차례로 풀어 가니, 문단마다 그 읽기를 골라 함께 보면 좋습니다. 읽는 법:

넷의 차이는 뒤집은 줄이 목록 안에 있어야 하느냐에 있습니다. 칸토어의 두 읽기에서는 그 줄이 목록 밖에 있다는 것이 결론입니다. 목록이 불완전하니, 0과 1의 수열 전체는 자연수보다 많습니다. 번호 1, 2, 3, …을 아무리 나눠 주어도 번호를 받지 못하는 수열이 남기 때문입니다.

'부분집합⁠(subset)⁠' 읽기는 같은 표를 집합으로 봅니다. 자연수의 부분집합이란 자연수 몇 개(무한히 많아도 됩니다)를 골라 모은 것입니다. 줄 $S_k$의 j번째 칸이 ●이면 'j가 $S_k$에 들어 있다'로 읽습니다. 뒤집은 줄 D는 '자기 번호의 줄에 들어 있지 않은 번호'를 모은 집합입니다. 예를 들어 0이 $S_0$에 들어 있지 않으면 0을 D에 넣고, 들어 있으면 넣지 않습니다. 그러면 D는 어떤 $S_k$와도 원소 k에서 갈립니다. 그러니 자연수의 부분집합을 모두 모은 것, 곧 자연수의 멱집합⁠(power set)⁠은 자연수보다 큽니다.

1901년 러셀은 같은 모양을 '모든 집합의 목록'에 적용했습니다. 줄과 칸이 모두 집합이고, 줄 X와 칸 Y가 만나는 자리는 'Y가 X의 원소인가'입니다. 대각선을 뒤집으면 '자기 자신을 원소로 갖지 않는 집합들의 집합' R이 나옵니다. 그런데 모든 집합의 목록이니 R도 목록 안에 있어야 합니다. R의 대각선 칸을 보면, R이 자기 자신의 원소라면 R의 정의에 따라 원소가 아니고, 원소가 아니라면 정의에 따라 원소입니다. 어느 쪽도 될 수 없습니다. 산술을 논리 위에 세우려던 프레게의 체계는 '어떤 성질이 있는 것들의 모임'이면 무엇이든 집합으로 인정했기에 R도 인정해야 했고, 이 역설로 무너졌습니다(러셀의 역설⁠, Russell's paradox⁠).

튜링의 읽기에서 줄은 프로그램, 칸은 입력입니다. 프로그램은 모두 유한한 글이니, 짧은 것부터 사전 순으로 늘어놓으면 $P_0, P_1, P_2, \dots$로 번호를 매길 수 있습니다. 줄 k와 칸 j가 만나는 자리는 '프로그램 $P_k$에 수 j를 넣으면 언젠가 멈추는가, 영원히 도는가'입니다.

이제 모든 프로그램과 입력에 대해 멈출지 맞히는 판정기 H가 있다고 해 봅시다. 그러면 다음 프로그램 D도 짤 수 있습니다. D는 수 k를 받아 H에게 '$P_k$에 k를 넣으면 멈추는가?'를 묻고, H가 '멈춘다'고 하면 일부러 영원히 돌고, '돈다'고 하면 바로 멈춥니다. 대각선을 뒤집어 행동하는 것입니다. D도 프로그램이니 목록 어딘가, 예를 들어 m번째에 있습니다($D = P_m$).

D에 m 자신을 넣으면 어떻게 될까요? H가 '멈춘다'고 답하면 D는 영원히 돌고, '돈다'고 답하면 D는 멈춥니다. 어느 쪽이든 H의 답이 틀립니다. 그러니 그런 H는 없습니다(정지 문제⁠(halting problem)⁠, 「기계가 풀 수 없는 문제」). 칸토어의 읽기와 달리 여기서는 뒤집은 줄이 목록 안에 있어야 하는데 있을 수 없으니, 처음의 가정(H가 있다)이 거짓이 됩니다.

괴델의 읽기는 한 번 더 비틉니다. 여기서 체계란 공리(증명 없이 받아들이는 출발 문장)와 추론 규칙을 정해 둔 산수의 증명 체계입니다. 줄은 수 하나를 받는 문장들입니다. 'x는 짝수이다'처럼 x 자리에 수를 넣으면 참이나 거짓이 되는 문장이고, 이런 문장도 유한한 글이니 $\varphi_0, \varphi_1, \varphi_2, \dots$('파이 영, 파이 일, …')로 번호를 매길 수 있습니다. 줄 k와 칸 j가 만나는 자리는 "k번째 문장 $\varphi_k$('파이 k')의 x 자리에 수 j를 넣은 문장 $\varphi_k(j)$가 이 체계에서 증명되는가"입니다.

대각선을 뒤집은 문장 G(x)는 "$\varphi_x(x)$는 증명되지 않는다", 곧 'x번째 문장의 x 자리에 x 자신을 넣은 것은 증명되지 않는다'입니다. 괴델의 핵심 작업은 이런 문장이 산수의 언어로 실제로 적힌다는 것을 보인 것입니다. 문장과 증명에 번호를 매기면(괴델 수⁠(Gödel number)⁠ 매기기), '이 번호의 글은 저 번호의 문장의 증명이다'가 수와 수 사이의 관계가 되어 덧셈과 곱셈만으로 적힙니다. 그러니 G도 수 하나를 받는 산수의 문장이고, 목록 어딘가, 예를 들어 g번째에 있습니다($G = \varphi_g$).

이제 G의 x 자리에 g 자신을 넣은 문장 G(g)를 봅시다. 이 문장이 말하는 것은 "$\varphi_g(g)$는 증명되지 않는다"이고, $\varphi_g(g)$는 바로 G(g) 자신입니다. 곧 G(g)는 "나는 증명되지 않는다"는 문장입니다. 체계가 참인 것만 증명한다고 하고 두 경우를 따져 봅시다.

• G(g)가 증명된다면: 참인 것만 증명되니 G(g)는 참이고, 그러면 G(g)가 말하는 대로 G(g)는 증명되지 않습니다. 증명된다는 가정과 어긋나니 이 경우는 없습니다.
• 그러니 G(g)는 증명되지 않습니다. 그런데 이것이 바로 G(g)가 말하는 내용이니 G(g)는 참입니다.

모순 대신 참이지만 증명되지 않는 문장이 남습니다(불완전성 정리⁠, incompleteness theorem⁠). 칸토어나 튜링과 달리 G는 목록에 들어 있고, 그 대가로 체계가 불완전해집니다. 모순이 생기지 않는 까닭은 '증명되지 않는다'가 참과 거짓을 뒤집는 말이 아니기 때문입니다. 참이면서 증명되지 않을 수는 있습니다. 그림에서 괴델의 읽기를 고르고 칸 (k, k)를 눌러 ✓와 ·를 오가 보세요. ✓이면 체계가 거짓을 증명한 셈이 되고, ·이면 참이지만 증명되지 않는 문장이 됩니다.

흔히 이 정리를 '누구도 영원히 알 수 없는 참이 있다'로 읽지만, 정리가 말하는 것은 정해 둔 체계 하나에 대한 것입니다. G(g)를 공리로 보탠 더 큰 체계에서는 G(g)가 당연히 증명됩니다. 다만 그 새 체계에도 같은 방법으로 새 G가 생기니, 공리를 아무리 보태도 끝나지 않습니다.

정확한 가정도 짚어 둡니다. 공리 목록은 어떤 문장이 공리인지 기계적으로 확인할 수 있어야 하고, 체계는 덧셈과 곱셈을 다룰 만큼 강해야 합니다. 괴델의 실제 가정은 '참인 것만 증명한다'보다 약한 무모순성(어떤 문장과 그 부정을 함께 증명하지 않는다는 성질)의 한 형태였고, 1936년 로서가 그냥 무모순⁠(consistent)⁠이기만 하면 되도록 다듬었습니다.

1969년 윌리엄 로베어는 이 모든 논증을 정리 하나로 묶었습니다. 먼저 재료를 봅시다. 값이 둘뿐인 모임 Y = {0, 1}에서 Y로 가는 함수(0과 1을 받아 0이나 1을 내는 규칙)는 넷뿐입니다. 늘 0을 내는 것, 늘 1을 내는 것, 받은 값을 그대로 내는 것, 뒤집는 것(0 → 1, 1 → 0)입니다. 넣은 값과 나온 값이 같은 자리를 고정점⁠(fixed point)⁠이라 합니다. '늘 0'은 0이, '그대로'는 0과 1 모두가 고정점입니다. 뒤집기에는 고정점이 없습니다.

로베어의 정리는 이렇습니다. 모임 A의 원소 a마다 A에서 Y로 가는 함수 $f_a$가 하나씩 이름 붙어 있다고 합시다. 표로 보면 a번째 줄이 $f_a$이고, 줄 a와 칸 b가 만나는 자리의 값이 $f_a(b)$입니다. 그리고 A에서 Y로 가는 함수라면 무엇이든 이런 이름이 하나씩 있다고, 곧 목록이 완전하다고 합시다. 그러면 Y에서 Y로 가는 함수 g에는 모두 고정점이 있습니다.

증명은 세 줄입니다. 대각선을 읽고 거기에 g를 씌워 새 줄 d를 만듭니다. 곧 $d(b) = g(f_b(b))$입니다(칸토어의 d는 g가 뒤집기인 경우입니다). d도 A에서 Y로 가는 함수이니 목록에 이름이 있어 $d = f_m$입니다. 이제 자리 (m, m)을 보면

이니, $y = f_m(m)$을 g에 넣으면 그대로 y가 나옵니다. y가 g의 고정점입니다.

이 정리를 거꾸로 읽으면 칸토어가 나옵니다. 뒤집기에는 고정점이 없으니, 모든 함수에 이름을 주는 완전한 목록은 있을 수 없습니다. A가 자연수 전체, Y = {0, 1}이면 A에서 Y로 가는 함수가 곧 0과 1의 수열이니 칸토어의 정리 그대로입니다. 러셀의 집합과 튜링의 D도 모두 뒤집기로 만든 d입니다.

괴델의 경우는 방향이 반대입니다. 산수에서는 괴델 수 매기기 덕분에 '문장에 번호를 붙이고 번호로 문장을 부르는' 목록을 실제로 만들 수 있어서, 정리의 앞 조건이 문장들 사이에서 성립합니다. 그러니 문장에 씌우는 변환이면 무엇이든 고정점이 생깁니다(정확히는 체계 안에서 서로 같은 뜻임이 증명되는 고정점입니다). '증명되지 않는다'를 씌우는 변환의 고정점이 바로 "나는 증명되지 않는다"는 G(g)입니다(자기 참조⁠, self-reference⁠).

정리하면, 대각선 논법은 '목록의 k번째와 k번째 자리에서 어긋나게' 만든 것이 목록에 들 수 없다는 한 가지 생각이고, 그것이 칸토어, 러셀, 튜링, 괴델의 네 정리가 됩니다. 대각선은 무한에서의 세기라고도 볼 수 있습니다. 원소가 n개인 집합의 부분집합은 $2^n$개로 n보다 많고(n = 3이면 8개), 대각선 논법은 이 부등식을 무한집합까지 밀고 갑니다.

1930년 9월 괴델이 쾨니히스베르크의 학회에서 이 결과를 처음 알린 다음 날, 같은 도시에서 힐베르트는 "우리는 알아야 한다, 우리는 알게 될 것이다"로 끝나는 연설을 했습니다.

8 · 공정한 투표는 없다콩도르세의 순환과 애로의 정리

이 절의 물음은 이것입니다. 사람들의 순위를 모아 모두가 공정하다고 여길 사회의 순위 하나를 만드는 규칙이 있을까? 앞의 세 무기와 조금 다른 모양의 불가능이 나옵니다.

1785년 파리의 수학자이자 철학자 콩도르세 후작은 배심원과 의회의 다수결을 확률⁠(probability)⁠로 분석한 책에서 이상한 현상을 적었습니다. 세 사람이 후보 A, B, C에 순위를 매겼는데 첫째는 A > B > C, 둘째는 B > C > A, 셋째는 C > A > B라고 합시다. A > B > C는 A를 가장 좋아하고 C를 가장 싫어한다는 뜻입니다. 둘씩 다수결로 겨루면 A가 B를 2 대 1로, B가 C를 2 대 1로, C가 A를 2 대 1로 이깁니다. A와 B만 보면 첫째와 셋째가 A를 B보다 앞에 두었으니 2 대 1입니다. B와 C에서는 첫째와 둘째가 B를, C와 A에서는 둘째와 셋째가 C를 앞에 두었습니다. 개인은 모두 앞뒤가 맞는 순위를 적었는데, 다수결로 모으니 돌고 도는 순환이 됩니다. '가장 좋은 후보'라는 말이 뜻을 잃습니다. 누구를 뽑든 그 후보를 2 대 1로 이기는 후보가 있기 때문입니다. 콩도르세는 같은 아카데미의 장샤를 드 보르다가 1770년에 제안한 방식, 곧 순위마다 점수를 주어 더하는 방식도 비판했습니다.

아래 표에서 여섯 가지 순위마다 그 순위를 적어 낸 사람 수를 −와 +로 바꿔 보세요. 오른쪽 그림은 두 후보씩 다수결로 겨룬 결과이고, 아래에는 흔히 쓰는 규칙들의 결과가 나옵니다. '스포일러'는 이길 가망은 없지만 선거에 나와서 다른 두 후보의 승패를 바꾸는 후보를 부르는 말입니다. 두 번 누르라는 버튼은 한 번 누를 때마다 두 투표를 오갑니다. 두 투표에서 A와 B 사이의 순위가 달라진 사람이 있는지, 그런데도 결과의 A–B 순서가 바뀌는지 보세요. 콩도르세의 순환 스포일러 (두 번 누르기) 보르다 (두 번 누르기)

모두 명입니다. 1위 표만 세는 최다득표⁠(plurality voting)⁠로는 , 1위에 2점·2위에 1점을 주는 보르다 점수⁠(Borda count)⁠로는 , 1위 표가 많은 두 후보만 다시 겨루는 결선에서는 , 둘씩 겨뤄 모두 이기는 콩도르세 승자는 .

1951년 미국의 경제학자 케네스 애로는 이런 사례들이 우연이 아님을 증명했습니다. 애로는 사람들의 순위를 모아 사회의 순위 하나를 내놓는 규칙에 다음 조건을 걸었습니다. 유권자는 둘 이상이고 유한하며, 후보는 셋 이상입니다.

• 어떤 순위 조합이든 받는다: 사람들이 어떤 순위를 적어 내든 규칙이 답을 낸다.
• 사회의 순위도 순위다: 결과는 모든 후보를 앞뒤가 맞게(A > B이고 B > C이면 A > C) 줄 세운다.
• 만장일치: 모든 사람이 A를 B보다 좋아하면 사회도 A를 B보다 앞에 둔다.
• 무관한 후보로부터의 독립⁠(independence of irrelevant alternatives)⁠: 사회가 A와 B 가운데 누구를 앞에 두는지는, 사람들이 A와 B 사이의 순서를 어떻게 적었는지에만 달려 있다. C를 어디에 두었는지는 상관이 없다. 곧 A와 B 사이의 순서를 바꾼 사람이 아무도 없으면, C를 어디로 옮기든 사회의 A–B 순서도 그대로여야 한다.
• 독재자가 없다: 다른 모든 사람과 상관없이 늘 자기 순위가 사회의 순위가 되는 사람이 없다.

애로의 정리는 앞의 네 조건을 모두 지키는 규칙은 독재뿐이라는 것입니다(애로의 불가능성 정리⁠, Arrow's impossibility theorem⁠). 독재 규칙, 곧 미리 정해 둔 한 사람의 순위를 그대로 사회의 순위로 삼는 규칙은 앞의 네 조건을 실제로 모두 지킵니다. 그러니 정리는 '그것 말고는 없다'는 말이고, 다섯 조건을 모두 지키는 규칙은 하나도 없다는 말과 같습니다.

위의 규칙들은 저마다 하나씩 어깁니다. 둘씩 겨루는 다수결은 콩도르세의 순환처럼 A > B > C > A가 생길 수 있어 둘째 조건을 어깁니다. 최다득표와 보르다는 넷째 조건을 어깁니다. '스포일러' 버튼의 두 투표를 숫자로 따라가 봅시다. 처음에는 A > B > C가 4명, B > A > C가 3명, C > B > A가 2명입니다. 1위 표는 A 4, B 3, C 2이니 최다득표로는 A가 B를 앞섭니다. 다음에는 마지막 2명이 C를 1위에서 2위로 내려 B > C > A가 됩니다. 이제 1위 표는 A 4, B 5이니 B가 A를 앞섭니다. 그런데 A와 B 사이만 보면 두 투표 모두 4명이 A를, 5명이 B를 앞에 두었습니다. A–B 사이의 순서를 바꾼 사람이 없는데 사회의 A–B 순서가 뒤집혔습니다.

'보르다' 버튼도 같습니다. 처음에는 A > B > C가 3명, B > C > A가 2명입니다. 1위에 2점, 2위에 1점을 주면 A는 3 × 2 = 6점, B는 3 × 1 + 2 × 2 = 7점이니 B가 앞섭니다. 다음에는 뒤의 2명이 C만 맨 아래로 내려 B > A > C가 됩니다. 이제 A는 6 + 2 × 1 = 8점, B는 3 × 1 + 2 × 2 = 7점이니 A가 앞섭니다. 이번에도 A와 B 사이의 순서를 바꾼 사람은 없습니다(3명은 A를, 2명은 B를 앞에 둡니다). 선거에서 '표를 가르는 후보'가 결과를 바꾸는 현상이 바로 이것입니다.

정리하면, 흔히 쓰는 규칙은 모두 애로의 조건 가운데 하나를 어기고, 애로의 정리는 그것이 규칙을 잘못 고른 탓이 아니라 피할 수 없는 일이라고 말합니다.

왜 독재밖에 남지 않을까요? 2005년 경제학자 존 지나코플로스가 짧게 정리한 증명의 생각은 이렇습니다. 조건을 지키는 규칙이 있다고 하고, 모든 사람이 B를 꼴찌에 둔 상태에서 출발해 한 사람씩 차례로 B를 맨 위로 올립니다. 처음에는 만장일치 조건에 따라 사회도 B를 꼴찌에 두고, 끝에는 맨 위에 둡니다. 그 사이 어딘가에서 한 사람이 B를 올리는 순간 사회의 B가 꼴찌에서 맨 위로 한 번에 뛰어오릅니다(가운데에 머무를 수 없다는 것도 조건들에서 나옵니다).

이 '중추적인 사람'이 사실은 모든 두 후보 사이의 순서를 혼자 정한다는 것을 넷째 조건과 둘째 조건(앞뒤가 맞음)으로 보이면, 그가 독재자라는 결론에 이릅니다. 끊김 없이 변하는 양이 음수에서 양수로 가면 어딘가에서 0을 지난다는 중간값 정리⁠(intermediate value theorem)⁠의 이산판처럼 생긴 단계입니다. 개념 지도의 애로 정리 페이지에서 이 과정을 한 단계씩 넘겨 볼 수 있습니다.

이 정리는 세 가지 무기 가운데 어디에 들까요? 솔직히 말하면 깔끔하게 들지 않습니다. 그래도 넷째 조건 자체가 불변량 조건이라는 점은 눈여겨볼 만합니다. 'A와 B 사이의 순서가 같은 두 투표에서 사회의 A–B 판정은 같다'는 것은, C를 움직이는 모든 변화에 대해 판정이 불변이어야 한다는 요구입니다. 1–5절에서는 불변량이 목표를 막았다면, 여기서는 조건으로 요구한 불변성들이 서로 부딪혀 가능한 규칙을 독재 하나로 좁힙니다.

애로의 정리는 1972년 노벨 경제학상의 바탕 가운데 하나가 되었고, 비슷한 불가능성 정리들을 낳았습니다. 1973년 앨런 기바드와 1975년 마크 새터스웨이트는 따로따로 이런 정리를 증명했습니다. 당선자 하나를 정하는 규칙에서 당선될 수 있는 후보가 셋 이상이면, 독재가 아닌 어떤 규칙에서도 누군가는 거짓 순위를 적어 내는 편이 이득인 경우가 생긴다는 것입니다. 1982년 앨빈 로스는 안정적인 짝을 찾는 어떤 방법도 양쪽 모두에게 솔직함이 최선이도록 만들 수는 없음을 보였습니다(안정 매칭⁠(stable matching)⁠, 「짝을 찾는 알고리즘」). 반대로 후보가 둘뿐이면 불가능은 사라집니다. 1952년 케네스 메이는 모든 사람을 똑같이 대하고, 두 후보를 똑같이 대하며, 한 사람이 지지를 옮기면 결과가 그쪽으로만 움직이는 규칙은 다수결 하나뿐임을 보였습니다.

애로가 이 문제에 닿은 길도 전해집니다. 1940년대 말 RAND 연구소에서 논리학자 올라프 헬머가 "개인의 선호는 정의할 수 있다지만 나라의 선호란 무엇인가?"라고 물은 것이 계기였다고 애로는 회고했습니다. RAND는 미 공군의 지원을 받는 연구소로, 냉전의 전략을 폰 노이만의 게임 이론⁠(game theory)⁠으로 따지던 곳이었습니다. 게임 이론은 나라 하나를 한 사람처럼 선호가 있는 참가자로 놓는데, 헬머의 물음은 바로 그 가정을 겨냥한 것이었습니다(게임 이론의 출발은 「이기는 쪽이 존재한다」 5절에 있습니다).

콩도르세에게 투표의 수학은 책상 위의 문제가 아니었습니다. 그는 아카데미의 종신 서기였습니다. 3절에서 본 대로, 1775년 두 배 정육면체의 불가능성을 대수의 말로 적어 보았다고 전하는 사람도 그입니다. 혁명이 일어나자 그는 국민공회 의원으로 헌법안을 썼습니다. 그러나 권력을 잡은 자코뱅과 맞서다 쫓기는 몸이 되었고, 1794년 3월 체포되고 이틀 뒤 감옥에서 숨진 채 발견되었습니다. 그의 순환은 그 뒤 잊혔습니다. 1870년대 옥스퍼드의 수학 강사 찰스 도지슨, 곧 루이스 캐럴은 자기 칼리지의 선거 방식을 두고 소책자 세 편을 쓰면서 같은 순환을 따로 찾아 '순환적 다수'라 불렀습니다(그가 테니스 대회의 방식을 비판한 이야기는 「줄 세우기의 한계」에 있습니다). 이 흩어진 글들을 한데 모은 사람은 스코틀랜드의 경제학자 던컨 블랙입니다. 그는 1940년대 후반부터 위원회 투표를 연구하며 콩도르세와 보르다, 도지슨을 다시 읽었고, 1958년 『위원회와 선거의 이론』에 도지슨의 소책자를 다시 실었습니다.

퍼즐에서 논리와 투표까지. 캐너스토타의 퍼즐이 볼티모어의 증명이 되고, 할레의 대각선이 빈의 괴델과 케임브리지의 튜링으로 이어지며, 파리의 콩도르세가 160여 년 뒤 뉴욕의 애로에게 닿는 것을 보세요. 과학 줄의 섀넌은 같은 무렵 회로를 세어 대부분의 함수가 어렵다는 것을 보였습니다.

9 · 불가능이 주는 것규칙을 읽고, 지도의 가장자리를 긋기

이 절의 물음은 이것입니다. '할 수 없다'는 증명을 얻고 나면 무엇이 남을까? 막힌 길만 남는 것은 아닙니다.

불가능의 증명은 언제나 조건을 달고 옵니다. 그리고 조건 하나하나가 문입니다. 눈금 없는 자 대신 눈금 두 개를 찍은 자를 쓰면 각은 셋으로 나뉩니다. 종이접기도 됩니다. 1980년 일본의 아베 히사시는 종이를 접어 각을 삼등분하는 법을, 1986년 피터 메서는 두 배 정육면체의 변을 접는 법을 내놓았습니다. 자와 컴퍼스의 한 걸음이 이차방정식까지만 풀 수 있는 것과 달리, 한 번 접는 동작은 삼차방정식까지 풀 수 있기 때문입니다. 5차방정식의 근은 거듭제곱근 대신 수치 계산으로 구합니다. 카드끼리 비교하는 대신 자릿수를 보고 칸에 나눠 담는 기수 정렬⁠(radix sort)⁠은 $\log_2 n!$의 벽을 돌아갑니다(「줄 세우기의 한계」 7절). 모든 파일을 줄일 수는 없지만, 사람이 알아채지 못하는 것을 버리면 사진은 10분의 1로 줄어듭니다. 정지 문제는 풀 수 없지만, 가끔 '모르겠다'고 답해도 되는 분석기는 날마다 프로그램의 버그를 찾아냅니다. 불가능의 증명을 정확히 읽는다는 것은 어떤 조건을 늦추면 가능해지는지를 읽는 것입니다.

불가능을 증명하려고 만든 도구는 그 자체로 새 수학이 되었습니다. 갈루아의 군은 대칭의 언어가 되었습니다. 튜링이 정지 문제를 풀려고 정의한 기계는 컴퓨터의 설계도가 되었고, 섀넌이 넘을 수 없는 선을 그은 다음 50년 동안 공학자들은 그 선에 바짝 다가가는 부호를 만들었습니다. 한계가 정확히 어디인지 알아야 한계까지 가는 방법도 잴 수 있습니다. 병합 정렬⁠(merge sort)⁠이 최선에 가깝다는 것을 알 수 있는 것도 $\log_2 n!$의 하한이 있기 때문입니다.

그런데 수학자들이 불가능의 증명을 늘 반긴 것은 아닙니다. 방첼의 증명은 한 세기 동안 잊혔고, 아벨의 소책자는 인쇄비를 아끼려고 여섯 쪽에 눌러 담느라 읽어 내기 어려웠습니다. 갈루아가 1831년 아카데미에 낸 논문은 심사를 맡은 푸아송이 논증이 충분히 명료하지 않다며 돌려보냈습니다. 증명이 나온 뒤에도 원을 네모로 만들었다는 사람들은 사라지지 않았습니다. 1897년 미국 인디애나주 하원은 원의 넓이를 '해결'했다는 한 의사의 주장을 담은 법안을 만장일치로 통과시켰습니다. 마침 주 의회에 들른 퍼듀 대학의 수학 교수 클래런스 월도가 의원들을 설득한 뒤에야 상원이 처리를 미루었습니다. 할 수 없다는 증명은 시도를 멈추게 하는 말이 아니라, 헛된 시도에 쓸 시간을 옳은 질문으로 돌리게 하는 말입니다.

1775년 아카데미가 세 작도 문제와 함께 내친 영구 기관은 조금 다른 길을 걸었습니다. 스스로 영원히 움직이며 일을 해 주는 기계가 없다는 것도 그때는 증명된 사실이 아니었습니다. 그런데 물리학자들은 이 불가능을 증명하기보다 출발점으로 삼았습니다. 16세기 말에서 17세기 초에 걸쳐 네덜란드의 시몬 스테빈은 영구 기관은 없다는 원리 하나에서 출발해 정역학, 곧 멈춰 있는 물체에 걸리는 힘의 문제를 여럿 풀었습니다. 이 불가능이 더 깊은 법칙의 결과로 자리를 잡은 것은 에너지 보존 법칙이 널리 받아들여진 뒤였고, 그 계기는 1847년 헤르만 폰 헬름홀츠의 『힘의 보존에 대하여』였습니다. 다만 차이가 있습니다. 수학의 불가능은 공리에서 증명되고, 물리학의 불가능은 실험이 뒷받침하는 법칙에 기댑니다.

'할 수 없다'는 증명을 온전한 해답으로 대접한 것은 오래된 일이 아닙니다. 3절에서 보았듯 방첼의 시대에는 이런 결과에 큰 무게를 두지 않았습니다. 1900년 파리 국제수학자대회에서 힐베르트는 달랐습니다. 그는 평행선 공준의 증명, 원의 넓이, 5차방정식의 거듭제곱근 풀이 같은 오래된 문제들이 처음 뜻한 것과는 다른 의미에서 완전하고 엄밀한 해답을 얻었다고 말했습니다. 그리고 분명하게 적힌 수학 문제는 모두 실제 답이든 불가능의 증명이든 반드시 결말이 난다고 하면서 "수학에는 이그노라비무스가 없다"고 선언했습니다. 이그노라비무스는 '우리는 알지 못할 것이다'라는 라틴어입니다. 1872년 라이프치히의 학회에서 생리학자 에밀 뒤부아레몽이 물질의 본성과 의식 앞에서 과학은 모르고 앞으로도 모를 것이라고 하며 쓴 말입니다. 힐베르트에게 불가능의 증명은 앎의 한계가 아니라 앎의 한 모양이었습니다. 7절의 괴델 이후로 '결말'에는 셋째 모양이 더해졌습니다. 정해 둔 공리로는 증명도 반증도 할 수 없다는 결말입니다. 5절의 연속체 가설이 그 예입니다.

10 · 이어지는 길불가능의 증명이 닿는 곳

• 대칭: 1–5절의 불변량은 대칭과 불변량이라는 큰 생각⁠(big ideas)⁠의 한 얼굴입니다. 순열의 홀짝과 갈루아 군은 군에서, 정17각형의 비밀은 1의 거듭제곱근에서 이어집니다.
• 짝짓기: 색이 맞아도 막힌 판의 증거를 준 홀의 정리는 최대 흐름⁠(maximum flow)⁠과 최소 절단⁠(cut)⁠이 같다는 정리와 한 식구입니다. 이분 그래프⁠(bipartite graph)⁠의 짝짓기와 흐름에서 '할 수 있다'의 최댓값과 '막는 것'의 최솟값이 늘 같다는 쌍대성⁠(duality)⁠이 「짝을 찾는 알고리즘」의 뼈대입니다.
• 무한: 대각선 논법과 멱집합의 크기, 그리고 5절의 모형으로 증명된 연속체 가설의 독립성은 「무한에도 크기가 있다」에서 더 자세히 봅니다.
• 계산: 정지 문제에서 출발해 문제를 문제로 옮기면(환원) 불가능성이 퍼집니다. 1970년 유리 마티야세비치는 마틴 데이비스, 힐러리 퍼트넘, 줄리아 로빈슨의 앞선 작업을 완성해, 정수 계수 다항식 방정식에 정수해가 있는지 판정하는 알고리즘⁠(algorithm)⁠이 없다는 것을 이렇게 보여 힐베르트의 10번 문제를 풀었습니다. 문자열을 출력하는 가장 짧은 프로그램의 길이, 곧 콜모고로프 복잡도를 계산할 수 없다는 것도 같은 줄기입니다(「기계가 풀 수 없는 문제」).
• 세기의 반대편: 세기는 불가능만이 아니라 존재도 증명합니다. 1947년 에르되시는 색칠 방법을 세어, 작은 질서의 섬이 없는 색칠이 반드시 '있다'는 것을 하나도 보여 주지 않고 증명했습니다(확률적 방법⁠(probabilistic method)⁠, 「완전한 무질서는 없다」). 6절의 어려운 회로처럼, 있다는 것은 알지만 어느 것인지는 모르는 대상입니다.
• 증명하는 기계: 괴델의 정리는 증명 보조기⁠(proof assistant)⁠에도 적용됩니다. Lean이나 Coq 같은 증명 보조기도 제 논리의 무모순성⁠(consistency)⁠을 스스로 증명하지 못하며, 그래서 믿음의 바닥을 작은 검사 핵심부에 두고 그 부분을 사람이 읽을 수 있게 짧게 만듭니다(「증명은 프로그램이다」).
• 소수: 정17각형이 그려지는 까닭인 페르마 소수⁠(Fermat prime)⁠, 그리고 페르마의 짐작이 오일러의 641로 무너진 이야기는 「소수를 세는 사람들」 8절에 있습니다.
• 완벽한 비밀: 1949년 섀넌은 도청자가 아무것도 알 수 없는 암호를 만들려면 열쇠가 메시지만큼 길어야 한다는 것을 세기로 증명했습니다. 짧은 열쇠로 버티는 오늘날의 암호가 '불가능'이 아니라 '어렵다고 믿어지는 것'에 기대는 이유가 「나머지로 지키는 비밀」에 있습니다.
• 틀린 증명: 평행선 공준을 증명하려던 사케리가 모순이라 믿고 물리친 새 기하학처럼 증명이 넘어진 자리에서 새 개념이 나온 사례들과, 코시의 서류 속에 묻힌 아벨의 원고처럼 옳은 증명이 길을 잃은 사연은 「틀린 증명이 만든 수학」에 모여 있습니다.
• 통신과 정렬: 6절의 세기 논증들은 원천 부호화 정리, 통로 부호화 정리, 비교 정렬의 하한에서 수식으로 정리되어 있습니다. 모두 '가를 수 있는 경우의 수⁠(number of cases)⁠'와 '가려야 할 경우의 수'를 비교합니다.