Notes

Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations


[Universality of] set theory

Any integer n can be encoded as a set using for example Nest[Union[#, {#}] &, {}, n]. And from this a statement s in Peano arithmetic (with each variable explicitly quantified) can be translated to a statement in set theory by using

Replace[s, {ForAll[a_, b_] -> ForAll[a, Implies[a \[Element] \[DoubleStruckCapitalN], b]], Exists[a_, b_] -> Exists[a, a \[Element] \[DoubleStruckCapitalN] \[And] b]}, {0, ∞}]

and then adding the statements below to provide definitions (\[DoubleStruckCapitalN] is the set of non-negative integers, < x, y, z> is an ordered triple, and ↕a determines whether each triple in a set a is of the form < x, y, f[x, y] > specifying a single-valued function).

This means that set theory can be used to prove any statement that can be proved in Peano arithmetic. But it can also prove other statements—such as Goodstein's result (see note below), and the consistency of arithmetic (see page 1168). An important reason for this is that set theory allows not just ordinary induction over sequences of integers but also transfinite induction over arbitrary ordered sets (see below).


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