Hofstadter’s MIU system


The alphabet of the system contains three symbols M,I,U. The set of theoremMathworldPlanetmath is the set of string constructed by the rules and the axiom, is denoted by 𝒯 and can be built as follows:

  1. (axiom)

    M⁢I∈𝒯.

  2. (i)

    If x⁢I∈𝒯 then x⁢I⁢U∈𝒯.

  3. (ii)

    If M⁢x∈𝒯 then M⁢x⁢x∈𝒯.

  4. (iii)

    In any theorem, I⁢I⁢I can be replaced by U.

  5. (iv)

    In any theorem, U⁢U can be omitted.

example:

  • •

    Show that M⁢U⁢I⁢I∈𝒯
    M⁢I∈𝒯 by axiom ⟹M⁢I⁢I∈𝒯 by rule (ii) where x=I ⟹M⁢I⁢I⁢I⁢I∈𝒯 by rule (ii) where x=I⁢I ⟹M⁢I⁢I⁢I⁢I⁢I⁢I⁢I⁢I∈𝒯 by rule (ii) where x=I⁢I⁢I⁢I ⟹M⁢I⁢I⁢I⁢I⁢I⁢I⁢I⁢I⁢U∈𝒯 by rule (i) where x=M⁢I⁢I⁢I⁢I⁢I⁢I⁢I ⟹M⁢I⁢I⁢I⁢I⁢I⁢U⁢U∈𝒯 by rule (iii) ⟹M⁢I⁢I⁢I⁢I⁢I∈𝒯 by rule (iv) ⟹M⁢U⁢I⁢I∈𝒯 by rule (iii)

  • •

    Is M⁢U 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 premiseMathworldPlanetmath of all rule.
    inductionMathworldPlanetmath 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 formulaMathworldPlanetmathPlanetmath. 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≢0⁢mod⁡3 then 2⁢n≢0⁢mod⁡3). Therefore the statement is true for rule 2.
    Rule 3: Applying rule 3 replaces I⁢I⁢I by U. Since the initial amount of I’s was not a multiple of 3 by induction hypothesis. Removing I⁢I⁢I 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 U⁢U 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 2013-03-22 13:57:48
Last modified on 2013-03-22 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