We will consider the structures < N, <,  0,  1,  +, {[/n] | n=1,2,…}, f > where f is a weakly monotone function. A weakly monotone function f is called strong divided iff it has the following properties:

• any sm-formula with m quantifiers is equivalent to a disjunction of sm-formulas with less than m quantifiers and sm-formulas (∃ [u₁])…(∃ [u_m]) Θ([u], x), where Θ( [u], x) is a conjunction of a formula ρ (x₁,…, x_k, [u₁],…,[u_m]), which says that x₁,…, x_k, [u₁],…, [u_m] have given remainders for given positive natural numbers, and sm-formulas of the forms t₂( x)+ m₂f([u₁]) < t₁(x)+m₁f(u₁),    (5) n₂t( x)<mf([u₁])< n₁t(x)& Ψ([u],x), (6) t₂(x)+ m₂[u₁]< t₁(x) +m₁[u₁],           (7) and n₂t(x)<m[u₁]< n₁t(x)& Ψ([u],x),       (8) where m, m₁, m₂, n₁, and n₂ are natural numbers, and Ψ([u],x) is a quantifier-free sm-formula
• for any natural numbers m, and n<m, there is a natural number g(n,m) such that, for any natural numbers a and i, if s⁽ⁱ⁾(f)=f ^-1(na), then s^(i+g(n,m))(f)> f ^-1(ma)
• there is a natural number j such that either forms (7) and (8) never appear or s⁽ⁱ⁺¹⁾(f)≥ 2s⁽ⁱ⁾(f) for any natural i≥ j
• there is a natural number k such that for any natural number i, f ^k(s⁽ⁱ⁾(f))≥ s⁽ⁱ⁺¹⁾(f)

Previous page
Next page