The critical number of a variable in a function
Gaisi Takeuti · Journal of Symbolic Logic · 1994
LetL0be a language on ℕ consisting of 0, 1, +, ∸, ·, ⌊½a⌋, ∣a∣, #, ∧(a,b), ∨(a,b), ¬(a), ≤ (a,b), andμx≤ ∣s∣t(x). Hereμx≤ ∣s∣t(x) is the smallest numberx≤ ∣s∣ satisfyingt(x) > 0 and 0 if there exist no suchxand we stipulate that ifsandt(a) are terms inLo, thenμx≤ ∣s∣t(x) is also a term inLo. The defining axioms of functions ∧(a,b), ∨(a,b), ¬(a), ≤ (a,b) are as follows: LetLa language on ℕ with only predicate constant = andL0⊆L. Letf(b,a1,…,am) be a function for ℕm+1into ℕ. We say “fis weakly expressed by termst1(b,a1,…,am),…,tr(b,a1,…,am) inL” if for everyb,a1,…,am∈ ℕ,f(b,a1,…,am) is equal to one ofti(b,a1, …,am). The critical number ofbinfwith respect toLis the minimum numbernsuch that wheneverf(b,a1,…,an) is weakly expressed by termst1(b,a1, …,an),…, the number of occurrences ofbin someti(b,a1,…,an) is at leastn. As is defined in [1], a functionfis defined by a limited iteration fromgandhwith respect toLiff the following holds: Letτbe defined as with the condition ; and is defined by where and are terms inL. We say “fis defined by a short limited iteration fromgandh” if is defined by whereτ,s, tare the same as above satisfying the condition .