Notes

Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations


Implicational calculus

With k=2 the operator can be either 2 or 11 (Implies), with k=3 {2694, 9337, 15980}, and with k=4 any of 16 possibilities. (Operators exist for any k.) No single axiom, at least with up to 7 operators and 4 variables, reproduces all equivalences. With modus ponens as the rule of inference, the shortest single-axiom system that works is known to be {((a ∘ b) ∘ c) ∘ ((c ∘ a) ∘ (d ∘ a))}. Using the method of page 1151 this can be converted to the equational form

{((a ∘ b) ∘ c) ∘ ((c ∘ a) ∘ (d ∘ a)) == d ∘ d, (a ∘ a) ∘ b == b, (a ∘ b) ∘ b == (b ∘ a) ∘ a}

from which the validity of the axiom system in the main text can be established.


From Stephen Wolfram: A New Kind of Science [citation]