# Notation of an iterated function on 2 sets

Let $X$ and $C$ be two sets, I have defined an iterated function on them $f: X \times C \rightarrow X$. What interests me is the iterations of $f$ on an initial value $x \in X$, and a sequence $(c_n)_{n \in \mathbb{N}} \in C$, for instance $f(f(f(x, c_0), c_1),c_2)$.

I am wondering if there is some conventional way to express these iterations, for example by adding superscript on $f$. What I need to write are:

1) iterations from $c_0$ to $c_{n_0}$ where $n_0 \in \mathbb{N}$ $$f(\ldots f(f(f(x, c_0), c_1), c_2) \ldots, c_{n_0})$$

2) iterations from $c_k$ to $c_{k+m}$: $$f(\ldots f(f(\ldots, c_k), c_{k+1}) \ldots, c_{k+m})$$

Could anyone help?

-
There's something off about your notation. $X\to C\to X$ means two two functions, but it looks like, since you write $f(x,c_0)$, that you really mean $f:X\times C\to X$. Alternatively, you could have meant: $f:X\to X^C$. Perhaps you meant $C\to X$ to mean the collection of functions from $C$ to $X$, but then you need to be specific with parentheses that you mean $f:X\to(C\to X)$. – Thomas Andrews Feb 19 '13 at 16:43
I agree w/ Thomas that there's an interpretation issue. However, $f:X \times C \to X$ is more likely what you intend, ie, $C$ is the parameter space. This interpretation is typical in dynamics. But $f:X \to X^C$ is inconsistent with argument list $f(x,c_i)$ – alancalvitti Feb 19 '13 at 17:12
It is definitely $f: X \times C \rightarrow X$, i have amended the OP... – SoftTimur Feb 19 '13 at 19:00

I doubt that there is any such formula. Let $g_i(x)=f(x,c_i)$. Then you really just want $h_{0}(x)=x$ and $h_{n+1}(x)=g_{n+1}(h_n(x))$.

But also note that if there is a sequence of $g_i:X\to X$ we can let $C=\mathbb N$ and define $f(x,i)=g_i(x)$ and $c_i=i$. So given any sequence $g_i$, we can get this recursive sequence.

So any sequence that looks like:

$$x,g_1(x),g_2(g_1(x)),\dots$$

will be of this form.

I don't think there is a a general notation for this sort of induction. Certainly, none that also includes $C$ and $c_i$ in the formulation, since they are essentially arbitrary.

-

I don't know about conventional in mathematics, but in the symbolic math system Mathematica, your operation is called Fold (see the comments below your Q regarding proper functional notation however).

Fold[f, Subscript[x, 0], {Subscript[c, 1], Subscript[c, 2], Subscript[
c, 3], Subscript[c, 4]}]


Gives:

f[f[f[f[Subscript[x, 0], Subscript[c, 1]], Subscript[c, 2]], Subscript[c, 3]], Subscript[c, 4]]

This remains unevaluated since $f$ is undefined. Suppose you define:

f[x_, c_] := c + Sqrt[x]


(Note f takes two arguments, the 2nd interpreted as parameter, and returns a real number hence the functional signature is $f:X \times C \to X$).

Then evaluating this gives:

The related function FoldList returns all the iterates, not just the last one.

I don't see a way to obtain an output sequence on $C$. It is an exogenous input to the dynamic, it is not determined by the dynamic.

You could in principle add a second equation $g: X \to C$ or even $h: X \times C \to C$ to determine $c_i$ at each iteration ($g$ just depends on the state, whereas $h$ depends on both the state and parameter values); either way this second equation would be separate from $f$.

-
The sequence on $C$ is input, not an output. It is indeed a Fold... – SoftTimur Feb 19 '13 at 19:01
@SoftTimur, if you're satisfied w/ my answer, do you mind upvoting and accepting it? – alancalvitti Feb 20 '13 at 18:24