A simple formal system (MIU-system) borrowed from D. Hofstadter's Gödel, Escher, Bach has a three letter (M, I, U) alphabet. A sentence in the MIU-stem is a finite string formed by the three letters of the alphabet: IMU, IIMMUU, UIMUUIIIIIIIII, etc. There is one axiom (MI) and four rules of deduction. An application of a rule produces a theorem which is inserted at the top of the list in the main area of the applet. Originally there is only one item: the axiom MI.

Rule 1

(Here and below, x and later y, stands for any sentence of the system and plays the role of a metavariable, a place holder. For this reason, axioms like that are often called axiom schema. Significantly, x is not a symbol of the MIU-system nor it is included into its alphabet.)

Rule 2

(Although x stands for an arbitrary MIU-sentence, the sentence x stands for is the same in all three occurrences of x.)

Rule 3

(As before, x and now also y stand for an arbitrary MIU-sentence, which are the same in all occurrences of x and, respectively, y.)

Rule 4

The MIU-system is presented by the author as a puzzle: is the sentence MU a theorem?

The applet below affords you an opportunity to deduce theorems in the MIU-system. To apply one of the for deduction rules to the topmost statement on the right just press one of the buttons on the left. An ambiguity may arise in applying Rules 3 or 4. For example, the string MIIII may be reduced by Rule 3 to either MUI or MIU. On such occasions, the string is displayed at the bottom of the applet where you should select the occurrence of the triple "III" (to apply Rule 3) or the double "UU" (to apply Rule 4) by clicking on the first letter of the pattern. If there is no ambiguity the rule applies automatically.

(The applet has a built-in limitation: you can't prove theorems that are longer than 10000 characters.)

Discussion

Reference

1. D. Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid, Basic Books, 1999

Copyright © 1996-2009 Alexander Bogomolny

The answer to the puzzle is that MU is not a theorem in the MIU-system.

To see that let's observe that any theorem in the MIU starts with M, with rest of the string consisting entirely from U's and I's. This is true of the axiom MI. Furthermore, if any of the rules 1-4 applies to a string of U's and I's preceded by M, the result is a string with the same property.

Next, let's establish the following theorem about MIU-system from which the impossibility for MU to be a theorem will follow immediately.

Theorem

The number of I's in a theorem of the MIU-system is never divisible by 3.

Proof

Let's N(x) denote the number of I in string x. N(MI) = 1. The rules 1 and 4 do not affect the number of I's in a string. Rule 2 doubles that number so that, if Rule 2 converts a string x into a string y then 2N(x) = N(y), obviously. But, if N(y) = 2N(x) is divisible by 3, then so is N(x), for 2 and 3 are primes. It follows that if N(x) is not divisible by 3, N(y) is also is not divisible by 3.

Lastly, if y is produced by applying rule 3 to x, then N(y) = N(x) - 3, so, again either both N(x) and N(y) are divisible by 3 or both are not. This proves the (meta)theorem.

Since N(MU) = 0 and is divisible by 3, hence MU is not a theorem in the MIU-system.

• Infinitesimals. Non-standard Analysis
• Formal Languages
• Theories and Proofs
  • Formal Systems - an Example
• Models and Metamathematics
• Hyperintegers and Hyperreal Numbers
• Structure of Hyperreal Numbers
• Transfer Principle
• Is .999... = 1?

Back to What Is Infinity?

Copyright © 1996-2009 Alexander Bogomolny