Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations

Pure equational logic

Proofs in operator systems always rely on certain underlying rules about equality, such as the equivalence of u==v and v==u, and of u==v and u==v/. a -> b. And as Garrett Birkhoff showed in 1935, any equivalence between expressions that holds for all possible forms of operator must have a finite proof using just these rules. (This is the analog of Gödel's Completeness Theorem from page 1152 for pure predicate logic.) But as soon as one introduces actual axioms that constrain the operators this is no longer true—and in general it can be undecidable whether or not a particular equivalence holds.

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