PDF version of this article

The hierarchy of mathematical truth

The Arithmetical and Analytical Hierarchies classify sets of integers based on the number of alternating quantifiers over the integers (arithmetical) and reals (analytical) in the statement that defines the set. For statements in the Arithmetical Hierarchy it is straight forward to enumerate all the finite events that determine if the statement is true or false. For a low level in the analytical hierarchy ($\Pi^1_1$) we can also do this. (A statement is $\Pi^1_1$ if it has a single pair of alternating quantifiers on the reals that begins with $\forall$.)

Let $T_i$ be some Gödel numbering of TMs (Turing Machines) such that each TM accepts an integer input and after that may output an integer value. If a nonzero integer value is output it is interpreted as the Gödel number of a TM that has the same property of accepting an integer input and perhaps having a subsequent integer output. We define a path $p$ as an arbitrary sequence of integers. $E(n,p,T_i)$ is the value output from $T_i$ when evaluated on the first $n$ elements of $p$. $E$ may be undefined because $T_i$ may terminate before we get to level $n$ or because there is no output at that level.

Let $P$ be the set of all infinite sequences of integers and $\omega$ be the set of all integers. We say that $T_i$ is well founded iff the following holds.

$$\forall p \exists m \: (p \in P) \wedge (m \in \omega) \wedge E(m,p,T_i) = 0$$

This says that every path $p$ terminates in some finite number $m$ of steps.

The set of all well founded TMs is $\Pi_1^1$ complete[2, p 396]. This means from this set we can recursively compute any $\Pi_1^1$ set of integers.

We are able to enumerate all the events that determine if a TM is well founded. Those events are the $E(m,p.T_i)$ where $p$ ranges over all integer sequences of length $m$ and $m$ ranges over all integers. Even though the set of well founded Turing Machines requires quantification over the reals to define it is an objective property of integers under Creative Objectivism.

PDF version of this article