Do all computable functions on ordinals satisfy this certain modular property?

87 Views Asked by At

Consider the following property of a non decreasing function $f$ whose domain and codomain are each the set of ordinals less than the Church-Kleene ordinal, and whose set of fixed points is unbound.

There exists a fixed point $\alpha$ of $f$ such that, for $\beta>\alpha$ any fixed point of $f$, and $\beta^\prime$ the first fixed point of $f$ after $\beta$, the following holds for $\gamma$ any ordinal in $[\beta,\beta^\prime)$.

1) $f$ is computable in $[0,\beta)$.

2) If $\gamma=\beta+\delta$, then $f(\gamma)=\beta+f(\delta)$.

Is it known if there is any function satisfying the first condition but not the second? If so, can anyone provide an example?

EDIT

I have been asked to clarify the following. Let $f$ be computable in an interval $I$ if there is a computable ordering of the naturals isomorphic to the ordering of $I$, and there is a computable function on the naturals which mirrors $f$ relative to this ordering.

1

There are 1 best solutions below

4
On BEST ANSWER

The answer is no. Consider the following function (where "$\lfloor\cdot\rfloor$" denotes the floor function):

  • $f(n)=\lfloor{n\over 7}\rfloor$ if $n$ is finite,

  • $f(\alpha)=\alpha$ if $\alpha$ is a limit,

  • $f(\lambda+n)=\lambda+\lfloor{n\over 10000}\rfloor$ if $\lambda$ is a limit and $n$ is finite.

This $f$ is nondecreasing and onto $\omega_1^{CK}$, has a club of fixed points, and satisfies (1) (by standard mucking about with ordinal notations). However, it does not satisfy (2).