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:

1. (axiom)

$MI\in\mathcal{T}$.

2. (i)

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

3. (ii)

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

4. (iii)

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

5. (iv)

In any theorem, $UU$ can be omitted.

example:

• Show that $MUII\in\mathcal{T}$
$MI\in\mathcal{T}$ by axiom $\implies MII\in\mathcal{T}$ by rule (ii) where $x=I$ $\implies MIIII\in\mathcal{T}$ by rule (ii) where $x=II$ $\implies MIIIIIIII\in\mathcal{T}$ by rule (ii) where $x=IIII$ $\implies MIIIIIIIIU\in\mathcal{T}$ by rule (i) where $x=MIIIIIII$ $\implies MIIIIIUU\in\mathcal{T}$ by rule (iii) $\implies MIIIII\in\mathcal{T}$ by rule (iv) $\implies MUII\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.

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\not\equiv 0\operatorname{mod}3$ then $2n\not\equiv 0\operatorname{mod}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 HofstadtersMIUSystem 2013-03-22 13:57:48 2013-03-22 13:57:48 Daume (40) Daume (40) 8 Daume (40) Definition msc 03B99 MIU system