[su_quote]The barber is the “one who shaves all those, and those only, who do not shave themselves.” The question is, does the barber shave himself?[/su_quote]

이발사의 역설은 누구나 한번 쯤은 들어본 유명한 역설입니다. 수학자 러셀이 누군가한테서 들었다고 자신에 책에 처음 적었다고 하네요. 워낙 유명해서 왠만한 사람들은 다 한번 씩 들어보았고 초등학교 수학관련 만화책에서도 왠만하면 나옵니다. 저는 메이플스토리 논리문제 만화책에서 처음 본 것 같네요.

한 마을의 이발사는 자신의 머리를 자르지 않는 모든 사람의 머리만 잘라줄 때, 이발사는 자기 자신의 머리를 자를 수 있을까, 라는 내용이 이발사의 역설입니다.

만약 이발사가 자신의 머리를 자른다고 생각해 봅시다. 그럼 이발사는 자신의 머리를 자르는 사람이기 때문에 자신의 머리를 잘라주면 안돼겠네요. 만약 자신의 머리를 자르지 않는다면 이발사는 자신의 머리를 자르지 않는 사람이니까, 자신의 머리를 잘라야 겠네요.

어느 선택을 해도 모순에 도달하는 ‘이 명제는 거짓이다’와 같은 역설처럼 보입니다.

오늘 계산이론 (Theory of Computation)이라는 수업을 들었는 데, 교수님이 이 역설을 대각선 논법으로 설명 해주신것이 인상 깊어서 이 글을 써봅니다. 대각선 논법은 실수가 비가산 집합임을 보여주는데도 사용하지만 이 글에서는 그정도 까지는 가지 않을 것 같네요. 그럼 대각선 논법을 간단히 설명해드리도록 하겠습니다.

O	X	O	O	O
X	O	X	X	O
X	O	X	X	O
O	X	O	O	X
O	O	X	X	X

다음과 같은 5X5 테이블을 있다고 할때 가로열을 각각

[latex]R_1 = \{1,3,4,5\} [/latex]

[latex]R_2 = \{2,5\} [/latex]

[latex]R_3 = \{2,5\} [/latex]

[latex]R_4 = \{1,3,4\} [/latex]

[latex]R_5 = \{1,2\} [/latex]

라고 봅시다. 즉 [latex] R_1 [/latex]는 첫번째 가로열에서 동그라미의 위치를 표현하는 집합입니다.

이제 이 테이블에서 대각선만 보면 순서대로 [latex] \{1,2,4\} [/latex] 가 됩니다 이것을 반전 시킨 것을 [latex] D = \{3,5\} [/latex] 라고 볼 때, 대각선 논법이란 것은 그 어느 가로열도 이것과 동일하지 않다는 것입니다. 즉 [latex] R_1, R_2, R_3, R_4, R_4 [/latex] 그 어느 것을 보아도 D와 동일하지 않다는 것을 확인 할 수 있습니다. 즉 이는

[latex] R_a \neq   D \forall a \in \{1,2,3,4,5\} [/latex]

로 볼 수 있고 이는 모든 가능한 [latex] N \times N [/latex]에 적용됩니다.

 

이제 다시 이발사 문제로 되돌아가 봅시다. 한번 이렇게 생각해 봅시다. [latex] R_a [/latex]란 a라는 사람이 머리를 잘라줄 수 있는 사람들의 집합으로 본다면, 1번 주민은 자기자신과, 3번, 4번, 5번 사람의 머리를 잘라줄 수 있겠네요.

어떤 마을 이라도 마을사람 수 x 마을 사람 수의 크기의 테이블을 만들 수 있고 이런 머리잘라주는 관계를 표현할 수 있습니다.

그렇다면 자기자신의 머리를 자를 수 없는 사람들의 집합은 D가 됩니다. D는 대각선의 반전이고 대각선에 동그라미가 표시된 사람들은 자기자신의 머리를 자를 수 있는 사람이기 때문입니다.

이발사가 머리를 잘라 줄 수 있는 사람은 [latex] R_{barber} [/latex]가 되겠고, 이발사가 마을 안에 있는 이상 이발사 역시 저 테이블 안에 들어있을 테니 대각선 논법에 의해 [latex] R_{barber} \neq D [/latex]가 될 수 밖에 없습니다.

즉 자기 자신의 머리를 자를 수 없는 사람만 잘라주는 이발사는 존재할 수 없는 것입니다.