Abstract

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 aswith the condition; andis defined bywhereandare terms inL. We say “fis defined by a short limited iteration fromgandh” ifis defined bywhereτ,s, tare the same as above satisfying the condition.