5.10: Definitions by Recursion are Representable
( \newcommand{\kernel}{\mathrm{null}\,}\)
If you look at the definition of a term (Definition 1.3.1), the definition of formula (Definition 1.3.3), the definition of uxt (Definition 1.8.1), and the definition of (Definition 1.8.2), you will notice that all of these definitions were definitions "by recursion". For example, in definition of a term, you see the phrase
…t is ft1t2…tn, where f is an n-ary function symbol of L and each of the ti are terms of L
so a term can have constituent parts that are themselves terms. In the last two sections we have used the device of construction sequences to show that the sets TERM, FORMULA, TERMSUB, and SUB are representable sets. In this section we outline a proof that all such sets of strings, defined "by recursion", give rise to sets of Gödel numbers that are representable. It will be clear from our exposition that a more general statement of our theorem could be proved, but what we present will be sufficient for our needs.
A string of symbols s form a first-order language L is called an expression if s is either a term of L or a formula of L.
Suppose that we have a set of LNT-expressions, which we will call Set, defined as follows: An expression s is an element of Set if and only if:
- s is an element of BaseCaseSet, or
- There is an expression t, a proper substring of s, such that (t,s) is an element of ConstructionSet.
If the sets of strings BaseCaseSet and ConstructionSet give rise to sets of Gödel numbers BASECASESET and CONSTRUCTIONSET that are defined by Δ-formulas, then the set
SET={⌜s⌝|s∈Set}
is representable, and has a Δ-definition Set.
Chaff: Try to keep the various typefaces straight:
- Set is a bunch of LNT-expressions - strings of symbols from LNT.
- SET is a set of natural numbers - the Gödel numbers of the strings in Set.
- Set is an LNT-formula such that N⊨Set(ˉa) if and only if there is an s∈Set such that ⌜s⌝=a.
We follow very closely the proof of the representability of the set TERM, which is in Section 5.8. As you worked through Exercise 6 in Section 5.8, you saw that you could prove the analogs of Lemmas 5.8.4 through 5.8.6 for formulas, so you have established the following lemma:
Suppose that s is an LNT-expression and u is a substring of s that is also an expression. Then
- If ⌜s⌝=a, then the number of symbols in s is less than or equal to a.
- The length of the shortest construction sequence of s is less then or equal to the number of symbols in s.
- ⌜u⌝<⌜s⌝.
Now we can write a Δ-definition of SETCONSTRUCTIONSEQUENCE and then use this lemma to show SET is representable:
SetConstructionSequence(c,a)=
CodeNumber(c)∧(∃l<c)[Length(c,l)∧IthElement(a,l,c)∧(∀i≤l)(∀e<c)(IthElement(e,i,c)→BaseCaseSet(e)∨(∃j<i)(∃ej<c)(IthElement(ej,j,c)∧ConstructionSet(ej,e)))].
We know, by assumption, that there are Δ-formulas BaseCaseSet and ConstructionSet that define the representable sets BASECASESET and CONSTRUCTIONSET. Thus, all of the quantifiers in the definition above are bounded, and SetConstructionSequence is a Δ-formula.
As before we can use Lemmas 5.8.5 and 5.8.7 to bound the size of the shortest construction sequence for a: By the same argument as in Section 5.8, there is a construction sequence coded by a number c such that c<(2aa)a2+a. So we define
Set(a)=
(∃c<(ˉ2aa)aˉ2+a)SetConstructionSequence(c,a)
and we have a Δ-definition of the set SET, finishing our proof.
This is a wonderful theorem, as it saves us lots of work. Merely by noting that their definitions fit the requirements of Theorem 5.10.2, the following sets all turn out to be representable and have Δ-definitions:
- FREE, where (x,f)∈FREE if and only if x is the Gödel number of a variable that is free in the formula with Gödel number f.
- SUBSTITUTABLE, where (t,x,f)∈SUBSTITUTABLE if and only if t is the Gödel number of a term that is substitutable for the variable with Gödel number x in the formula with Gödel number f.
Exercises
- Work through the details (including the needed modification of Theorem 5.10.2) and show that both FREE and SUBSTITUTABLE are representable.
- Suppose that the function f:Nk+1→N is defined as follows:
f(a∼,0)=g(a∼)f(a∼,b+1)=h(a∼,bf(a∼,b)),
where g and h are representable functions represented by Δ-formulas. Show that f is a representable function. [Suggestion: One approach is to define the formula fConstructionSequence(c,a∼,l), with the idea that the sequence coded by c will be (f(0),f(1),…,f(l)). Or, you might try to fit this situation into a theorem along the lines of Theorem 5.10.2.] - Use Exercise 2 to show that the following functions are representable:
(a) The factorial function n!
(b) The Fibonacci function F, where F(1)=F(2)=1, and for k≥3, F(k)=F(k−1)+F(k−2)
(c) The function a↑i, where a↑0=1 and a↑(j+1)=aa↑j (You should also compute a few values, along the lines of 2↑3, 2↑4, and 2↑5.)