This proves that a number of useful relations and functions are in first order arithmetic, providing a bootstrapping of parts of mathematical practice into any system including the relations (since the relations are exactly the recursive ones, this includes Turing machines).
First, we want to build a tupling relation which will allow a finite sets of numbers to be encoded by a single number. To do this we first show that is . This is true since , a formula with only bounded quantifiers.
Next note that x is prime is since . Also .
These two can be used to define (the graph of) a primality function, -th prime. Let .
This rather awkward looking formula is worth examining, since it illustrates a principle which will be used repeatedly. is intended to be a function of the form and so on. If it includes but not then we know that must be the -th prime. The definition is so complicated because we cannot just say, as we’d like to, is the smallest prime greater than (since we don’t allow recursive definitions). Instead we embed the series of values this recursion would take into a single number () and guarantee that the recursive relationship holds for at least terms; then we just check if the -th value is .
Finally, we can define our tupling relation. Technically, since a given relation must have a fixed arity, we define for each a function . Then define to be the -th element of when is interpreted as a tuple, so . Note that the tupling relation, even taken collectively, is not total. For instance is not a tuple (although it is sometimes convenient to view it as a tuple with “empty spaces”: ). In situations like this, and also when attempting to extract entries beyond the length, (for instance, ). On the other hand there is a -ary tupling relation, .
Thanks to our definition of , we have . This is clearly . (Note that we don’t use the as above, since we don’t have that, but since we have a different tupling function for each this isn’t a problem.)
For the reverse, .
Also, define a length function by and a membership relation by .
Armed with this, we can show that all primitive recursive functions are . To see this, note that , the zero function, is trivially recursive, as are and .
Finally, suppose we have functions and in . Then define the primitive recursion by first defining:
and then .
is also closed under minimization: if is a relation then is a function giving the least satisfying . To see this, note that .
Finally, using primitive recursion it is possible to concatenate sequences. First, to concatenate a single number, if then . Then we can define the concatenation of with by defining and , and by primitive recursion, there is a function whose value is the first elements of appended to . Then .
We can also define , which concatenates only elements of not appearing in . This just requires defining the graph of to be
|Date of creation||2013-03-22 12:58:25|
|Last modified on||2013-03-22 12:58:25|
|Last modified by||Henry (455)|