Lawvere's fixed-point theorem — one diagonal to rule them all
칸토어의 대각선, 러셀의 역설, 튜링의 정지 문제, 괴델의 불완전성. 전혀 다른 분야의 이 네 사건은 사실 똑같은 한 수법입니다. 1969년 로비어(Lawvere)는 그것을 단 하나의 범주론적 정리로 묶었습니다 — "부동점이 없으면, 전사도 없다."
겉보기엔 남남입니다. 칸토어는 "실수가 자연수보다 많다"고, 러셀은 "모든 집합의 집합은 모순"이라고, 튜링은 "정지 문제는 풀 수 없다"고, 괴델은 "참이지만 증명 불가능한 명제가 있다"고 말했죠. 그런데 네 증명을 나란히 놓으면 똑같은 골격이 드러납니다 — 자기 자신을 입력으로 먹인 뒤(대각선), 답을 뒤집는다.
윌리엄 로비어는 이 공통 골격을 범주론의 언어로 한 문장에 담았습니다. 핵심은 두 단어, 전사(surjective)와 부동점(fixed point)입니다. 먼저 가장 친숙한 칸토어부터 손으로 만져 봅시다.
집합 \(A\)의 부분집합 전체(멱집합 \(\mathcal{P}(A)\))는 \(A\)보다 진짜로 큽니다. 즉 \(A\)에서 \(\mathcal{P}(A)\)로 가는 전사함수는 없습니다. 증명은 대각선입니다. 어떤 함수 \(f:A\to\mathcal{P}(A)\)가 있다 치고, "자기 자신을 품지 않는 원소들"의 집합
$$ D=\{\,a\in A \;:\; a\notin f(a)\,\} $$을 봅시다. 만약 \(D=f(d)\)인 \(d\)가 있다면, "\(d\in D\)인가?"를 묻는 순간 \(d\in f(d)\iff d\notin f(d)\)라는 모순이 터집니다. 그러니 \(D\)는 어떤 \(f(a)\)와도 같지 않습니다 — \(f\)는 전사가 아니죠. 아래 표를 직접 건드려 보세요. 무엇을 채워 넣든 대각선을 뒤집은 행은 늘 표를 빠져나갑니다.
이제 그 수법을 추상화합니다. "함수를 값처럼 다룰 수 있는" 범주(데카르트 닫힌 범주, 예컨대 집합의 범주)에서:
증명은 정말로 한 줄입니다. 자기사상 \(t\)가 주어지면, 대각선에 \(t\)를 씌운 함수
$$ g(a) = t\big(f(a)(a)\big) $$를 만듭니다. \(f\)가 전사라 했으니 \(g=f(a_0)\)인 \(a_0\)이 있죠. 그 점에서 양변을 평가하면
$$ f(a_0)(a_0) = g(a_0) = t\big(f(a_0)(a_0)\big). $$즉 \(y_0=f(a_0)(a_0)\)은 \(t\)의 부동점입니다. 끝. 이 한 줄에 대각선("\(a\)에 \(a\)를 먹인다")과 자기지시가 모두 들어 있습니다.
칸토어로 되돌아가 봅시다. \(Y=\{0,1\}\)에서 뒤집기(\(0\leftrightarrow1\))는 부동점이 없습니다. 그러니 \(A\to\{0,1\}^{A}=\mathcal{P}(A)\)인 전사는 없다 — 바로 칸토어의 정리죠.
"자기 자신을 원소로 갖지 않는 모든 집합의 집합"을 생각하면 모순이 생깁니다(러셀). 이건 칸토어 대각선의 날것 그대로입니다 — 위의 \(D=\{a:a\notin f(a)\}\)에서 \(f\)를 "집합을 자기 자신으로 보내는 항등"으로 두면, \(D\)는 곧 "자신을 안 품는 집합들의 모임"이 되고 \(D\in D\iff D\notin D\)가 터지죠. 부동점 없는 "뒤집기"(소속의 부정)가, "모든 집합을 한 집합에 담기"를 금지한 겁니다. 그래서 순진한 내포공리는 폐기되고, 집합론은 공리적 토대(ZFC)로 다시 세워졌습니다.
이번 무대는 계산 가능한 함수들의 범주입니다. (정지 문제 자체를 게임·프로그램으로 더 깊이 파고든 이야기는 게임, 컴퓨터가 되다 편에 있습니다.) 프로그램은 유한한 문자열이라 나열할 수 있고, 보편 기계(universal machine)는 "프로그램과 입력을 받아 실행"하는 평가 사상을 줍니다 — 전사 \(f\)의 역할이죠. 여기서 \(Y=\{\text{멈춤},\text{무한루프}\}\)에 뒤집기(멈춤\(\leftrightarrow\)루프)는 부동점이 없습니다.
만약 "이 프로그램이 멈추는가?"를 계산으로 판정할 수 있다면, 그 판정에 뒤집기를 붙여 대각선 프로그램을 만들 수 있습니다 — "내가 멈춘다고 하면 무한루프, 안 멈춘다고 하면 즉시 멈춤." 자기 자신에 먹이면 로비어의 \(y_0\)이 부동점이 되어야 하는데, 뒤집기엔 부동점이 없죠. 모순. 따라서 정지 문제는 판정 불가능합니다.
충분히 힘센 형식 체계는 자기 자신을 이야기할 수 있습니다. 괴델 수 매기기로 명제·증명을 수(數)로 코드화하면, "문장에 관한 술어"들을 체계 안에서 표현할 수 있게 되죠 — 이것이 전사 \(f\)에 해당합니다. 진리값의 부정(참\(\leftrightarrow\)거짓)은 부동점이 없습니다(어떤 문장도 자기 부정과 동치일 순 없으니까).
대각선 보조정리는 자기 자신을 가리키는 문장 \(G\) — "나는 증명될 수 없다" — 를 만들어 냅니다(로비어의 \(y_0\)). 만약 체계 안의 "증명 가능성"이 곧 "참"이라면, \(G\)는 부정의 부동점이 되어야 하는데 그건 불가능. 결론은 둘 중 하나 — 체계가 모순이거나, 아니면 참이지만 증명할 수 없는 문장이 존재합니다. 후자가 괴델의 제1 불완전성 정리죠.
지금까지는 "부동점이 없어서 전사가 불가능"한 나쁜 소식이었습니다. 그런데 정리를 정방향으로 읽으면 좋은 소식이 됩니다 — 전사가 존재하면, 모든 자기사상이 부동점을 가진다.
타입 없는 람다 대수가 바로 그런 세계입니다. 항(term)들이 충분히 풍부해 "자기 적용"(\(a\)에 \(a\)를 먹이기)이 자유롭죠. 그러면 로비어의 \(y_0=f(a_0)(a_0)\)이 글자 그대로 Y 결합자가 됩니다 — 임의의 함수 \(t\)에 대해 \(t\)의 부동점 \(Y\,t = t\,(Y\,t)\)를 뽑아내는 그 유명한 장치. 역설을 일으키던 자기지시가, 여기서는 재귀(recursion)라는 축복으로 돌변합니다. 같은 대각선, 반대 부호.
"부동점이 없으면 전사도 없다." 이 짧은 문장 하나가 19세기의 무한론에서 20세기의 논리·계산 이론, 그리고 프로그래밍의 재귀까지를 한 줄로 꿴다는 사실은 — 추상화가 단지 어려워지기 위한 것이 아니라, 흩어진 진실들을 한 자리에 모으는 망원경임을 보여 줍니다. 다른 곳에서 또 대각선 냄새가 난다면, 십중팔구 로비어가 먼저 와 있을 겁니다.