Definition
The MU-puzzle is a toy formal system introduced in Gödel, Escher, Bach (Topic I). Its alphabet has three symbols: M, I, U. Its sole axiom is MI. Four rules of inference let you transform one string into another:
- Rule I: if a string ends in
I, append aU. - Rule II: from
MxformMxx(double the body). - Rule III: replace any
IIIwithU. - Rule IV: delete any
UU.
The puzzle: starting from MI, can you derive MU?
Why it matters
How it works
The trick is to find a property that every reachable string shares and that the target lacks. Count Is in any reachable string and look modulo 3:
- The axiom
MIhas oneI; 1 mod 3 = 1. - Rule I adds a
U— no change toI-count. - Rule II doubles the body, so doubles the
I-count. Modulo 3, doubling sends 1→2 and 2→1; neither becomes 0. - Rule III removes 3
Is — no change modulo 3. - Rule IV removes
UU— no change toI-count.
So I-count mod 3 is invariant in . The string MU has zero Is; 0 mod 3 = 0. Since 0 is unreachable from 1 by the rules, MU is unreachable.
Crucially, the proof never uses a MIU derivation. It runs in arithmetic, outside the MIU-system. This is the meta-level move the rest of GEB exploits.