이발사의 역설
마을의 이발사를 찾아가 보세요
어느 마을에 단 한 명의 이발사가 있습니다. 이 이발사는 "스스로 수염을 깎지 않는 마을 사람들의 수염만 깎아 준다"는 엄격한 규칙을 세웠습니다.
그렇다면 이 이발사는 자기 자신의 수염을 깎아야 할까요, 깎지 말아야 할까요? 깎아도 규칙 위반이고 안 깎아도 규칙 위반인 이 깊은 딜레마의 탈출구는 어디일까요?
이야기
Bassano Ltd
Public domain · 위키미디어 공용
어느 마을에 이발사가 한 명 있습니다. 그는 스스로 머리를 깎지 않는 사람만 깎아 줍니다. 그리고 그런 사람은 모두 깎아 줍니다.
그러면 이발사 자신의 머리는 누가 깎을까요?
그가 스스로 깎는다면, 그는 「스스로 깎는 사람」이니 이발사는 그를 깎으면 안 됩니다. 모순입니다.
그가 스스로 안 깎는다면, 그는 「스스로 안 깎는 사람」이니 이발사가 반드시 깎아야 합니다. 그런데 이발사가 곧 그입니다. 또 모순입니다.
이 이야기는 버트런드 러셀이 1901년에 발견한 더 심각한 문제를 쉽게 옮긴 것입니다.
「자기 자신을 원소로 갖지 않는 집합들의 집합」을 생각해 보세요. 그것은 자기를 원소로 가질까요? 어느 쪽이든 모순입니다.
이것이 러셀의 역설입니다. 당시 수학의 바탕을 세우고 있던 집합론이 스스로 무너진 순간이었습니다.
이 역설이 위험한 까닭은 말장난이 아니라 수학의 밑돌을 건드리기 때문입니다. 이발사를 「자기 자신을 원소로 갖지 않는 집합들의 집합」으로 바꾸면 그대로 러셀의 역설이 됩니다.
1902년 러셀이 이것을 편지로 알렸을 때, 프레게는 평생을 바친 책의 인쇄를 앞두고 있었습니다. 그는 부록에 이렇게 적었습니다. 「작업이 끝난 순간 토대가 무너지는 것보다 더 나쁜 일은 없다.」
「자기를 가리키는 것」이 위험합니다. 프로그램이 자기를 부르거나, 데이터가 자기를 참조하면 무한 반복에 빠집니다.
스프레드시트의 순환 참조 경고, 웹페이지의 무한 리다이렉트, 데이터베이스의 순환 외래키가 모두 이 역설의 후손입니다.
계단 넷 — 같은 사실을 네 깊이로
말장난처럼 따져 본다
규칙을 차근차근 따져 봅니다. 이발사가 스스로 수염을 깎으면 '스스로 깎지 않는 사람만 깎는다'는 규칙을 어기게 됩니다.
반대로 스스로 수염을 안 깎으면 '스스로 깎지 않는 사람이니 이발사가 깎아 주어야 한다'가 되어 자기가 깎아야 합니다. 깎아도 안 되고 안 깎아도 안 되는 기막힌 모순에 갇혀 버립니다.
이발사는 누가 깎나요
어느 쪽도 안 됩니다 — 그런 이발사는 있을 수 없습니다.
⭐ 사람이 몇이든 상관없습니다 — 이발사 한 사람에서 막힙니다.
모순이 생기는 자리 찾기
이 역설은 버트런드 러셀이 1901년에 발표한 러셀의 역설(Russell's Paradox)을 알기 쉽게 비유한 것입니다.
"자신을 원소로 포함하지 않는 모든 집합들의 집합 "을 생각합니다. 이라 가정하면 정의에 의해 이 되고, 반대로 이라 가정하면 이 되어 논리적 파탄에 이릅니다.
집합으로 옮겨 보세요
「모든 것을 모은 집합」은 있을 수 없습니다.
집합의 역설
이 역설의 근본 원인은 자유로운 자기 참조(Self-reference)와 칸토어의 '소박한 집합론(Naive Set Theory)'이 조건제시법으로 아무 집합이나 다 만들 수 있다고 허용한 데 있습니다.
집합론의 기초가 무너지자 수학자들은 아무 조건이나 집합이 되는 것이 아니라 엄격한 공리계로 집합 형성을 제한하는 체르멜로-프렝켈 공리계(ZFC)를 구축하여 역설을 추방했습니다.
어떻게 고쳤을까요
「모든 집합의 집합」을 애초에 못 만들게 한 것입니다.
공리적 집합론
러셀의 역설은 20세기 초 수학기초론의 수학 기초의 위기(Foundational Crisis of Mathematics)를 촉발했습니다.
이 자기 참조 모순 구조는 1931년 쿠르트 괴델의 불완전성 정리(Incompleteness Theorems)와 1936년 앨런 튜링의 정지 문제(Halting Problem) 불가능성 증명으로 이어지며 현대 수리논리학과 컴퓨터 과학의 한계를 규정하는 핵심 열쇠가 되었습니다.
자기를 가리키는 것들
자기 자신을 가리키는 것이 그 뿌리입니다.
풀어 보기
이발사의 역설과 러셀의 집합. 집합 에 대하여 다음 물음에 답하시오.
(1) 이라고 가정할 때 발생하는 모순을 쓰시오.
(2) 이라고 가정할 때 발생하는 모순을 쓰시오.
(3) 이 역설을 해결하기 위해 현대 수학이 도입한 표준 공리계의 명칭을 쓰시오.
(1) 의 정의에 의해 이 되어 모순, (3) ZFC 공리계입니다.
답과 풀이 보기
(1) 이라 하면, 은 의 원소이므로 그 조건을 만족해야 합니다.
곧 — 가정과 정반대입니다.
(2) 이라 하면, 은 자기 자신을 원소로 갖지 않는 것이므로 의 조건에 딱 맞습니다.
그러므로 — 이번에도 정반대입니다.
⛔ 참이라 해도 거짓이 되고 거짓이라 해도 참이 됩니다. 빠져나갈 길이 없습니다.
(3) ZFC 공리계(체르멜로–프렝켈 집합론 + 선택공리)입니다.
⭐ 해결의 요점은 「아무 조건이나 모아 집합을 만들 수는 없다」로 규칙을 바꾼 것입니다. 이미 있는 집합에서 골라내는 것만 허락합니다 (분리 공리).
그러면 는 애초에 집합이 아니게 되어 역설이 생기지 않습니다.
1901 년 러셀이 이것을 발견하고 프레게에게 편지를 보냈습니다. 프레게는 30 년 공들인 책의 2 권이 인쇄되던 중이었습니다.
그는 책 끝에 이렇게 적었습니다 — 「저술을 마친 뒤 그 토대가 무너지는 것보다 학자에게 더 달갑지 않은 일은 없다.」
역설 하나가 수학의 바닥을 다시 깔게 만들었습니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
이 역설이 수학의 바닥을 다시 놓게 했습니다.
- 공리적 집합론 — 아무 모임이나 집합으로 인정하지 않도록 규칙을 세웠습니다
- 괴델의 정리 — 이 흐름의 끝에서 나온 결과입니다
- 프로그래밍 — 자기를 참조하는 구조는 지금도 조심해서 다룹니다
이어지는 장
자신의 수염을 깎지 않는 마을 사람의 수염만 깎아주는 이발사의 딜레마는, '이 문장은 거짓이다'라는 자기참조 문장이 품고 있는 고대의 논리적 수수께끼와 같은 뿌리에서 자라났습니다 — 제126장 에서 자기언급의 함정을 더 깊이 파고들어 보세요.
영감을 받은 곳
버트런드 러셀(Bertrand Russell)이 1901년에 발견하고 1903년 저서 『수학의 원리』(The Principles of Mathematics)에서 칸토어와 프레게의 소박한 집합론의 모순을 짚어낸 자기참조 역설입니다.