For function
f defined by (1), let
f -1(0)=0 and for
x>0,
f -1(x)=i ↔ f(i-1)<f(i)≤ x<f(2i).
If
2(i2)≤ x< 2((i+1)2)
then
f -1(x)=2i.
Similar definitions are used for functions
f defined by (2) and (3).
For functions
f defined by (1),(2), or (3), we will consider the
structure
S = < N, <, 0, 1,
+, {[/n] | n=1,2,…}, f, f -1
>
of signature
{<, 0, 1,
+, {[/n] | n=1,2,…}, f, f -1
}.
Lemma 11
Any first-order formula is equivalent to a quantifier-free formula
in
S.
Previous page
Next page