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 important properties of the graph: all the original nodes maintain their same in and out degrees and the new node $c$ has out degree of exactly one.
Is this correct or am I missing an important step?
By adding a vertex in the graph, you're changing the domain of the function. An analogous manipulation without the graph would be to take a function $f : X \to X$ and define a function $$ g : X \times \{0,1\} \to X \times \{0,1\} $$ with $g(x,0) = (x,1)$ and $g(x,1) = (f(x),0)$. Then the composition $g \circ g$ is a function very similar to $f$: we have $g(g(x,y)) = (f(x), y)$ for any $x \in X$ and $y \in \{0,1\}$.
In other words, $g\circ g$ acts the same as $f$ on $X \times\{0\}$ and on $X \times\{1\}$: on both copies of $X$ inside its domain. But it is not the same function as $f$.