Does this certain modular property hold for functions on recursive ordinals?

51 Views Asked by At

Let $f$ be a function with the following properties.

1) The domain and codomain of $f$ are the recursive ordinals.

2) $f$ is nondecreasing.

3) The set of fixed points of $f$ is unbound.

4) $f$ is computable in the sense that, for any fixed point $\lambda$ of $f$, there is a recursive ordering of the naturals with order type $\lambda$, such that there is a computable function on the naturals mirroring $f$.

Is it true that $f$ has the following property as well?

There exists some fixed point $\alpha$ of $f$ satisfying the following.

1) All multiples of $\alpha$ are fixed points of $f$.

2) Let $\beta$ and $\gamma$ be nonzero multiples of $\alpha$, and let $\delta<\alpha$. Then there exists an $\epsilon<\alpha$ such that $f(\beta+\delta)=\beta+\epsilon$ and $f(\gamma+\delta)=\gamma+\epsilon$.

Essentially, a computable function begins repeating itself after some $\alpha$, possibly with its mapping of ordinals less than $\alpha$ not matching the mapping of other $\alpha$ sized intervals.

If not, can anyone provide a counterexample?

EDIT: I need to add the condition that $f$ be explicitly definable, say in terms of $ZFC$ (but any other reasonable theory would do as well).

1

There are 1 best solutions below

1
On BEST ANSWER

The answer is still no.

Since $\omega_1^{CK}$ is countable, we can find a sequence $\{\alpha_i: i<\omega\}$ of computable ordinals such that

  • (1) $\alpha_{i+1}>\alpha_i+\alpha_i$,

  • (2) $\sup\{\alpha_i: i\in\omega\}=\omega_1^{CK}$.

Now let $$f: \omega_1^{CK}\rightarrow\omega_1^{CK}: \theta\mapsto\max\{\alpha_i: \alpha_i\le\theta\}.$$ It's not hard to show that $f$ is computable (only finitely many $\alpha$s appear in any proper initial segment of $\omega_1^{CK}$), nondecreasing (immediate), and with unboundedly many fixed points (condition (2)); however, the fixed points of $f$ are exactly the $\alpha_i$s, and by condition (1) multiples of fixed points are not in general fixed points.