Is it possible to iterate a function transfinite times?

Question

Let $f:A\rightarrow A$ be a function. We can simply define $f\circ f$, $f\circ f\circ f$, etc., for each given natural number inductively.

$f^{(0)}=id_A$

$\forall n\in\omega \qquad f^{(n+1)}=f\circ f^{(n)}$

How to define $f^{(\omega)}$ such that it be a function from $A$ to $A$? Is it possible to define $f^{(\alpha)}$ for arbitrary large ordinal number $\alpha$?

Answer 1

Yes, and no. Essentially, sometimes.

Consider the function $f(x)=-x$ for $x\in\Bbb R$. Then what would $f^{(\omega)}(x)$ be? It should be a limit of $f^{(n)}(x)$. But there is no limit.

Or consider the function $f(x)=x+1$ for $x\in\Bbb N$. Then $f^{(\omega)}(0)$ is what?

But consider the function $f(x)=x+1$ for $x\in\omega_1$, then $f^{(\omega)}(x)=x+\omega$ which is perfectly defined. But then $f^{(\omega_1)}$ causes the same issues as before.

---

You can sometimes talk about infinite iterations, but you need to have some mechanism to handle the limit steps. This usually requires topology, and convergence. And even then you may have to end up changing the domain a little bit.

So under additional assumptions (e.g. the function is surjective, and there is a way to assign values at limit points), yes. In general no.

Answer 2

One case, relatively simple and general, where you probably can do this sort of thing would seem to be given by Theorem 7.25 in Y. Moschovakis, Notes on Set Theory (2nd edition, Springer 2006).

I'll paraphrase the statement of the theorem a little, because on the one hand, it doesn't use your suggestive $f^{(\alpha)}$ notation, and on the other hand, it is couched in terms defined earlier in the book.

I have also extended the statement of the theorem, because as it stands, it only determines (in your notation) $f^{(\alpha)}(\bot)$ for one particular element $\bot$ of a particular kind of ordered set, whereas it seems clear that this special case can immediately be generalised by working in a subset of the ordered set.

(Caveat emptor! I may be talking rubbish, but if so, someone will surely correct me.)

Let $P$ be any partially ordered set which is chain-complete, i.e. every totally ordered subset $S \subseteq P$ has a least upper bound, $\sup S$.

Let $f: P \to P$ be any function which, while it might not necessarily preserve the order relation on $P$, is nevertheless "expansive" [I don't know if this is a standard term, but it is the one used in the book], meaning that it satisfies the condition $f(x) \geqslant x$ for all $x \in P$.

Let $U$ be any well-ordered set, for example an ordinal $\beta$, considered as the set of all ordinals $\alpha < \beta$.

Then there is a unique definition of an expansive mapping $f^{(\alpha)}: P \to P$, for all $\alpha \in U$, such that: $$ f^{(0)}(x) = x, \\ f^{(\alpha + 1)}(x) = f\big(f^{(\alpha)}(x)\big), \\ f^{(\lambda)}(x) = \sup_{\kappa < \lambda} f^{(\kappa)}(x) $$ where $x$ is any element of $P$, $\alpha$ is any element of $U$, and $\lambda$ is a any limit element of $U$, i.e. $\lambda \ne 0$, and for all $\kappa < \lambda$, there exists $\mu$ such that $\kappa < \mu < \lambda$.

Moreover, if $\alpha \leqslant \gamma$, then $f^{(\alpha)}(x) \leqslant f^{(\gamma)}(x)$ (generalisation of the "expansive" property).

Finally, note that if $V$ is any other well-ordered set, then either $U$ or $V$ is (uniquely) isomorphic to an initial segment (not necessarily proper, of course) of the other; and if for example (w.l.o.g.) $\Psi: V \to U$ is an order-preserving injection, then $f^{(\delta)} = f^{(\Psi(\delta))}$, for all $\delta \in V$, by the uniqueness clause of the theorem.

In particular (the most important case, presumably), if both $U$ and $V$ are ordinals, then one of them is greater than or equal to the other, and it doesn't matter whether you consider a smaller ordinal $\alpha$ as an element of $U$ or as an element of $V$: $f^{(\alpha)}$ is uniquely defined, for any ordinal $\alpha$.

I imagine one also has: $$ f^{(\alpha + \beta)}(x) = f^{(\beta)}\big(f^{(\alpha)}(x)\big), \\ f^{(\alpha\beta)}(x) = \big(f^{(\alpha)}\big)^{(\beta)}(x), $$ for all ordinals $\alpha$, $\beta$, all $x \in P$, and all expansive $f: P \to P$ (but I'm only guessing).

I also imagine this is pretty close to what started old Cantor off on the whole ordinal number thing!

(See e.g. P. E. B. Jourdain's introduction to his translation of Cantor, Contributions to the Founding of the Theory of Transfinite Numbers, Dover reprint, p.35f. - Cantor was interested in transfinite iterations of a "derived set" operation, defined on a class of subsets of the real line.)