호프스테더 MI공리를 통한 MU정리의 수리적 연역가능성
다음과 같은 두 가지 조건이 있다고 가정하자.
(a) MI is an axiom
(b) The axiom is a theorem by default. All the (and only all the) strings that can be derived using the following transformations on a theorem is also a theorem:
이때, 공리 MI에서 정리 MU를 연역하는 것은 수리적으로 가능한가? 이 문제는 더글라스 호프스테더의 저서 <괴델, 에셔, 바흐>에 나오는 유명한 MU퍼즐이다. 문제는 MI공리에서 MU를 수리적으로 도출가능한지 묻고 있다. 조건 (b)에 따르면 우리에게 주어진 규칙은 총 네 가지다.
(D1) XI→XIU
(D2) MX→MXX
(D3) XIIIY→XUY
(D4) XUUY→XY
그렇다면 위 규칙을 통해 MI 공리에서 MU 정리를 연역하는 것은 가능한가? U를 직접 생성하는 것은 규칙 (D1)과 (D3)를 통해서만 가능하며, 특정 정리에 U가 포함돼 있을 경우 우리는 규칙 (D2)를 사용해 U의 개수를 두 배로 증폭시킬 수 있다. 가령 MI 공리를 통해 MUI를 증명하고자 한다면:
P1.MI→MII (규칙 D2)
P2.MII→MIIII (규칙 D2)
P3.MIIII→MUI (규칙 D3)
Q1(P1,P2,P3).MI→MUI
라는 간단한 가정적 논법을 이용해 보일 수 있다. 그런데 규칙 (D1)은 I가 IU로 변환될 수 있다는 점만을 보인다. 즉, 규칙 (D1)만으로는 어떤 방식으로도 MI에서 MU를 도출할 수 없을 것이므로 우리는 대신 규칙 (D3)을 사용할 필요가 있다. 규칙 (D3)에 따르면 세 개의 I는 U로 치환된다. 따라서 우리는 MI→MU의 수리적 연역가능성 확보를 위해 I가 세 번 연속되는 정리를 찾아야한다. 이 말은 I가 3n번 연속되는 정리를 찾아야 한다는 의미이다. 가령:
MIIIIIIIII
라는 정리가 있다면 이는 규칙 (D3)에 따라 MUUU이므로 규칙 (D4)의 생략법칙에 의해 MU가 도출된다. 그러나 I를 증폭시키는 규칙은 (D3)밖에는 없다. 다시 말해 연속되는 I의 개수를 (n)으로 표현한다면 우리는 MI, MI(2), MI(4), MI(8), MI(16), MI(32), 등등 MI(2n)의 패턴으로 이어지는 시퀀스를 갖게 되며, 2의 제곱에는 결코 3의 배수가 있을 수 없기 때문에 MI공리로부터 MU를 증명하는 것은 논리적으로 불가능하다. 이를 수리적으로 증명하면 다음과 같다:
Let x, y, m, n, z be any positive integers. Suppose x=2ᵐ and y=3n. Then:
(∃x∈Z)(∀m∈ℤ)x=2ᵐ and (∃y∈ℤ,)(∀n∈ℤ,)y=3n
Let X be a set of all possible x value, X={2, 4, 8, 16, ...}
Let Y be a set of all possible y value, Y={3, 6, 9, 12, ...}
We know that 2¹≠3n. So 2ᵏ is not a multiple of 3 for some integer k. If 2ᵏ≠3n, then either 2ᵏ=3n+1 or 2ᵏ=3n+2.
So, even if xy=3n(2ᵐ) and xy∈Y, xy∉X─that is, (∀xy∉X)xy=3n(2ᵐ). Hence (~∃xy∣xy∈X) and Y∩X=∅
∴In both cases, if 2ᵏ≠3n, 2ᵏ⁺¹ is either 3n+1 or 3n+2. So 2ᵏ⁺¹≠3n. Therefore MI(2ᵐ)∩MI(3n)=∅ and (MI(2ᵐ)∌MI(3n))
그렇다면 MI공리를 통해 연역할 수 있는 정리에는 무엇이 있는가? 우리는 규칙 (D2)를 통한 I의 증폭이 2n의 꼴을 갖는다는 것을 알고 있다. 가령 MI(16)을 통해선 M(III)(III)(III)(III)(III)I, 즉 MI, MI(4), MI(7), MI(10), MI(13)과 MI(16)을 전부 만들어낼 수 있으며, MI(32)를 통해선 M(III)(III)(III)(III)(III)(III)(III)(III)(III)(III)II, 즉 MI(2), MI(5), MI(8), MI(11), MI(14), MI(17), MI(20), MI(23), MI(26), MI(29), MI(32)를 만들어낼 수 있다. 쉽게 예측할 수 있듯이 2n을 통해 도출할 수 있는 모든 값은 3으로 나눌 때 1혹은 2의 나머지를 갖는다. 그리고 바로 이 때문에 3으로 나눌 때 나머지가 1인 2n을 통해 연역할 수 있는 정리 MI(2n)에서의 I-반복가능횟수는 {1, 4, 7, 10, 13, 16, ...} 이며 나머지가 2인 2n을 통해 연역할 수 있는 MI(2n)에서의 I-반복가능횟수는 {2, 5, 8, 11, 14, 17, 20, ...}이다. 따라서 우리는 다음과 같은 결론을 내릴 수 있다.
(i) MI공리를 통해 연역할 수 있는 모든 정리는 기본식 MI(1+3(t-1)) 혹은 기본식 MI(2+3(t-1))을 사용해 도출가능하다.
(ii) MI공리를 통해 연역할 수 있는 그 어떠한 정리 MI(n)으로도 MI(3n)을 증명할 수 없다. 규칙 (D2)가 유효한 이상 MI(3n)이 아닌 모든 정리에는 연역해낼 수 없는 하나 이상의 명제가 존재한다.
(iii) 따라서 정리 MIII를 공리화해도 연역해낼 수 없는 명제는 존재하며, 모든 정리를 완벽히 연역해내기 위해선 MI공리와 MI(3n)공리가 필요하다.
(iv) 그러므로 문자열(string) MI와 MI(3n)을 공리화한다면 호프스테더의 형식체계에서 존재가능한 모든 종류의 정리를 증명할 수 있다.
가령 정리 MUIUIIUIU와 정리 MUIIIUIII를 증명하고자 한다면,
P1.MI→MII (규칙 D2)
P2.MII→MIIII (규칙 D2)
P3.MIIII→MIIIIIIII (규칙 D2)
P4.MIIIIIIII→MIIIIIIIIIIIIIIII (규칙 D2)
P5.M(III)I(III)II(III)I(III)→MUIUIIUIU (규칙 D3)
Q1(P1,P2,P3,P4,P5).MI→MUIUIIUIU
P1.MIII→MIIIIII (규칙 D2)
P2.MIIIIII→MIIIIIIIIIIII (규칙 D2)
P3.M(III)III(III)III→MUIIIUIII (규칙 D3)
Q1(P1,P2,P3).MIII→MUIIIUIII
와 같이 손쉽게 나타낼 수 있다. 이렇듯 MI공리로는 MI(3n) 공리를 통해 도출할 수 있는 정리를 증명할 수 없고 MI(3n)공리로는 MI공리를 통해 도출해낼 수 있는 정리를 증명할 수 없기 때문에, 호프스테더의 형식체계는 오직 양자가 함께 공리화될 때만(if and only if) 완전하다는 결론을 내려볼 수 있을 것이다.
