게임의 결정성(Determinacy of games)

두 사람 I과 II가 번갈아 왼쪽(0) 또는 오른쪽(1)을 네 번 고릅니다. I, II, I, II 순서입니다. 네 번이 끝나면 0과 1로 된 길이 4의 수열이 하나 나오고, 수열마다 누가 이기는지 미리 정해 둔 표가 있습니다. 이런 게임에서는 언제나 둘 중 한 사람에게 이기는 전략, 곧 상대가 어떻게 두든 이기게 해 주는 수 고르기 규칙이 있습니다. 아래 그림에서 직접 확인해 보세요. 잎(맨 아랫줄)마다 이기는 사람이 적혀 있고, 위의 노드들은 끝에서부터 거꾸로 따져 채웁니다. 자기 차례인 노드에서 자기가 이기는 자식이 하나라도 있으면 그 노드는 자기 것입니다.

잎을 무작위로

어떻게 잎을 바꾸어도 뿌리는 파랑 아니면 분홍으로 칠해집니다. 한쪽에 이기는 전략이 있는 게임을 결정된 게임이라 부르고, 비김 없이 반드시 끝나는 게임은 모두 결정된다는 것이 1912년 에른스트 체르멜로가 체스를 두고 보인 정리의 오늘날 형태입니다. 논리로 적으면, I이 이긴다는 것은 "∃x₁ ∀x₂ ∃x₃ ∀x₄: 수열이 I의 승리 집합⁠(set)⁠ A에 든다"는 문장이고, 이 문장의 부정은 드모르간 법칙⁠(De Morgan's laws)⁠으로 "∀x₁ ∃x₂ ∀x₃ ∃x₄: 수열이 A에 들지 않는다", 곧 II가 이긴다는 문장입니다. 양화사⁠(quantifier)⁠가 유한하면 이 바꿔 적기는 늘 옳습니다. 그러니 유한한 게임의 결정성은 고전 논리의 드모르간 법칙과 배중률⁠(law of excluded middle)⁠이 게임의 말로 나타난 것입니다.

끝나지 않는 게임. 이제 두 사람이 자연수⁠(natural number)⁠를 번갈아 하나씩 부르기를 영원히 계속한다고 합시다. 결과는 자연수의 무한 수열이고, 미리 정한 수열들의 집합 A에 들면 I이, 아니면 II가 이깁니다. 끝이 없으니 거꾸로 따지기를 시작할 곳이 없습니다. 위의 문장은 양화사가 끝없이 이어지는 문장이 되고, 그 부정을 드모르간 법칙으로 바꿔 적어도 되는지가 더는 자명하지 않습니다. 1953년 데이비드 게일과 프랭크 스튜어트는 이 물음에 두 가지로 답했습니다.

첫째, I의 승리가 언제나 유한한 단계에서 확정되는 게임(A가 '열린' 집합인 게임)은 결정됩니다. 증명의 뼈대는 이렇습니다. I에게 이기는 전략이 없다고 합시다. 그런 국면을 'I이 아직 못 이기는 국면'이라 부르면, 이런 국면에서 I이 무엇을 두든 II는 다시 'I이 아직 못 이기는 국면'으로 가는 수를 찾을 수 있습니다. 만약 모든 응수가 I에게 이기는 전략을 준다면 처음 국면에서 이미 I에게 이기는 전략이 있었을 테니까요. II가 이 규칙을 따르면 I의 승리는 어느 유한한 단계에서도 확정되지 않고, 승리가 유한한 단계에서만 확정되는 게임이니 I은 끝내 이기지 못합니다. 그러니 이것이 II의 이기는 전략입니다.

둘째, 선택공리를 쓰면 결정되지 않는 게임이 있습니다. 전략은 국면마다 수를 정하는 규칙이니 모두 실수⁠(real number)⁠만큼 있습니다. 선택공리로 I의 전략과 II의 전략을 모두 한 줄로 세운 뒤, 차례로 하나씩 무력화합니다. I의 전략 하나를 만나면 그 전략을 따르는 판 가운데 아직 쓰지 않은 것 하나를 'II의 승리'로 정하고, II의 전략 하나를 만나면 그 전략을 따르는 판 하나를 'I의 승리'로 정합니다. 전략마다 그것을 따르는 판이 실수만큼 있고, 한 줄로 세울 때 각 전략 앞에 실수보다 적은 개수의 전략만 오도록 세웠으니, 앞에서 정해 둔 판들과 겹치지 않는 판을 늘 찾을 수 있습니다. 이렇게 만든 A에서는 어떤 전략도 이기지 못합니다. 대각선 논법⁠(diagonal argument)⁠의 비켜 가기가 전략 전체를 상대로 벌어진 것입니다.

바나흐–마주르 게임과 결정성 공리⁠(axiom of determinacy)⁠. 이보다 앞서 1935년 르부프의 스테판 바나흐와 스타니스와프 마주르는 두 사람이 번갈아 점점 작은 구간을 고르는 게임을 다루었습니다. 공통 부분이 집합 E와 만나면 I이 이깁니다. E가 셀 수 있는 집합이면 II는 E의 원소⁠(element)⁠를 하나씩 차례로 비켜 가서 이기는데, 이것이 1874년 칸토어가 실수가 셀 수 없음을 보인 논증 그대로입니다. 바나흐는 II가 이기는 것이 E가 '성긴' 집합, 곧 어디에서도 조밀⁠(dense)⁠하지 않은 집합을 셀 수 있을 만큼 모은 합집합⁠(union)⁠일 때, 그리고 그때만이라는 것을 보였습니다. 1962년 얀 미치엘스키와 후고 슈타인하우스는 거꾸로 "자연수를 번갈아 부르는 무한 게임은 승리 집합이 무엇이든 모두 결정된다"를 공리로 삼자고 제안했습니다. 이 결정성 공리는 선택공리와 함께 쓸 수 없지만, 실수의 모든 부분집합⁠(subset)⁠이 르베그 측도⁠(Lebesgue measure)⁠를 가진다는 것 같은 결과를 줍니다. 선택공리가 만들어 내는 괴상한 집합이 없는 세계입니다.

어디까지 결정되는가. 오늘날의 집합론은 선택공리를 지키면서, '적어 낼 수 있는' A에 대해 결정성을 묻습니다. 1975년 도널드 마틴은 A가 보렐 집합⁠(Borel set)⁠이면 게임이 결정된다는 것을 표준 공리(ZFC)만으로 증명했습니다. 이 정리는 문장 자체는 실수에 관한 것인데도, 증명에 멱집합⁠(power set)⁠을 셀 수 없이 여러 번 거듭 쌓은 거대한 집합들이 꼭 필요하다는 것이 1971년 하비 프리드먼의 결과로 알려져 있습니다. 한 층 위의 사영 집합⁠(projective set)⁠에 대해서는 ZFC만으로 결정성을 증명할 수 없고, 1980년대 말 마틴과 존 스틸이 우딘 기수⁠(cardinal number)⁠라는 아주 큰 무한이 무한히 많다고 가정하면 모든 사영 집합의 게임이 결정된다는 것을 증명했습니다. 사영 결정성은 사영 집합이 모두 측도⁠(measure)⁠를 가진다는 것 같은 결과들을 한꺼번에 주기⁠(period)⁠ 때문에, 많은 집합론자가 ZFC에 더할 자연스러운 공리의 후보로 봅니다.

결정성은 컴퓨터 과학에서도 쓰입니다. 1969년 리처드 뷔히와 로런스 랜드웨버는, 유한한 상태 그래프 위에서 끝없이 이어지는 게임이라도 승리 조건이 유한 오토마톤⁠(finite automaton)⁠으로 적히는 것이면 결정되고, 이기는 전략도 유한 오토마톤으로 계산해 낼 수 있음을 보였습니다. 환경이 어떻게 행동하든 명세를 지키는 제어기를 자동으로 만드는 일(합성)이 바로 이 게임을 푸는 일입니다.

이어지는 곳. 유한한 게임을 끝에서부터 푸는 방법은 게임 트리⁠(game tree)⁠ 탐색에, 공정한 유한 게임이 모두 님 더미 하나와 같다는 정리는 님과 스프라그–그런디 정리에 있습니다. 결정성이 드모르간 법칙의 무한판이라는 점은 불 대수⁠(Boolean algebra)⁠와, 배중률을 게임과 대화로 다시 읽는 직관주의 논리⁠(intuitionistic logic)⁠로 이어집니다. 결정되지 않는 게임을 만드는 비켜 가기는 대각선 논법과 자기 참조⁠(self-reference)⁠와 대각선의 한 예이고, 어떤 공리를 받아들일지의 논쟁은 수학 기초론 논쟁⁠(debate on the foundations of mathematics)⁠과 연속체 가설⁠(continuum hypothesis)⁠의 독립성으로 이어집니다. 체스, ε–δ, 님, 최소최대 정리⁠(minimax theorem)⁠와 함께 이 이야기를 따라가려면 「이기는 쪽이 존재한다」를 보세요.