Hofstadter’s MIU system
The alphabet of the system contains three symbols $M,I,U$. The set of theorem^{} is the set of string constructed by the rules and the axiom, is denoted by $\mathcal{T}$ and can be built as follows:

(axiom)
$MI\in \mathcal{T}$.

(i)
If $xI\in \mathcal{T}$ then $xIU\in \mathcal{T}$.

(ii)
If $Mx\in \mathcal{T}$ then $Mxx\in \mathcal{T}$.

(iii)
In any theorem, $III$ can be replaced by $U$.

(iv)
In any theorem, $UU$ can be omitted.
example:

•
Show that $MUII\in \mathcal{T}$
$MI\in \mathcal{T}$ by axiom $\u27f9MII\in \mathcal{T}$ by rule (ii) where $x=I$ $\u27f9MIIII\in \mathcal{T}$ by rule (ii) where $x=II$ $\u27f9MIIIIIIII\in \mathcal{T}$ by rule (ii) where $x=IIII$ $\u27f9MIIIIIIIIU\in \mathcal{T}$ by rule (i) where $x=MIIIIIII$ $\u27f9MIIIIIUU\in \mathcal{T}$ by rule (iii) $\u27f9MIIIII\in \mathcal{T}$ by rule (iv) $\u27f9MUII\in \mathcal{T}$ by rule (iii) 
•
Is $MU$ a theorem?
No. Why? Because the number of $I$’s of a theorem is never a multiple of 3. We will show this by structural induction.
base case: The statement is true for the base case. Since the axiom has one $I$ . Therefore not a multiple of 3.
induction hypothesis: Suppose true for premise^{} of all rule.
induction^{} step: By induction hypothesis we assume the premise of each rule to be true and show that the application of the rule keeps the staement true.
Rule 1: Applying rule 1 does not add any $I$’s to the formula^{}. Therefore the statement is true for rule 1 by induction hypothesis.
Rule 2: Applying rule 2 doubles the amount of $I$’s of the formula but since the initial amount of $I$’s was not a multiple of 3 by induction hypothesis. Doubling that amount does not make it a multiple of 3 (i.e. if $n\mathrm{\not\equiv}\mathrm{0}\mathit{}\mathrm{mod}\mathit{}\mathrm{3}$ then $\mathrm{2}\mathit{}n\mathrm{\not\equiv}\mathrm{0}\mathit{}\mathrm{mod}\mathit{}\mathrm{3}$). Therefore the statement is true for rule 2.
Rule 3: Applying rule 3 replaces $III$ by $U$. Since the initial amount of $I$’s was not a multiple of 3 by induction hypothesis. Removing $III$ will not make the number of $I$’s in the formula be a multiple of 3. Therefore the statement is true for rule 3.
Rule 4: Applying rule 4 removes $UU$ and does not change the amount of $I$’s. Since the initial amount of $I$’s was not a multiple of 3 by induction hypothesis. Therefore the statement is true for rule 4.
Therefore all theorems do not have a multiple of 3 $I$’s.
[HD]
References
 HD Hofstader, R. Douglas: Gödel, Escher, Bach: an Eternal Golden Braid. Basic Books, Inc., New York, 1979.
Title  Hofstadter’s MIU system 

Canonical name  HofstadtersMIUSystem 
Date of creation  20130322 13:57:48 
Last modified on  20130322 13:57:48 
Owner  Daume (40) 
Last modified by  Daume (40) 
Numerical id  8 
Author  Daume (40) 
Entry type  Definition 
Classification  msc 03B99 
Synonym  MIU system 