# 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:

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.
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