Do half-iterate functions exist for any function?

2018-05-08 04:27:15

For a given a deterministic unary function,

$$ f(x) = y $$

A half-iterate function g(x) for f(x) is one which satisfies the following:

$$ g(g(x)) = f(x) $$

For any f(x), does there exist a corresponding g(x) that is a half-iterate for f(x)?

It seems as though this must be true though I am having difficulty proving it.

Given that any deterministic unary function can be transformed into a directed graph (where $ \overrightarrow {ab} $ denotes the edge pointing from a to b):

$$ \forall \ \overrightarrow {ab} \in G, \ \ make \ \ f(a) = b$$

And likewise that any graph whose nodes have out-degree of exactly one can be transformed into a unary function -

$$ \forall \ f(a) = b, \ add\ \overrightarrow {ab} \ to \ G $$

It seems obvious that one could create g(x) by replacing each edge $ \overrightarrow {ab} $ with two others and a third node: $ \overrightarrow {ac} $ and $ \overrightarrow {cb} $. Inserting these two in place of the original edge does not change the importa