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 $𝒯$ and can be built as follows:

1. $MI\in 𝒯$.

2. If $xI\in 𝒯$ then $xIU\in 𝒯$.

3. If $Mx\in 𝒯$ then $Mxx\in 𝒯$.

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

5. In any theorem, $UU$ can be omitted.

example:

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