Idempotence of iterating a function

110 Views Asked by At

In the context of fixed points and fixed point combinators (for lambda calculus) I have repeatedly encountered the handwavingly motivated claim that applying a function to an infinite iteration of itself will not make a difference to the result of the iteration. Or formally:

$$\lim_{n \to \infty} f^n(x) = f(\lim_{n \to \infty} f^n(x))$$

for some $x$ in the domain of $f$.

I mean, I don't think $\forall n \in \mathbb{N}. n + \infty = \infty$ is a convincing argument nor a valid looking proof here.

The context in which this theorem appeared was that if $\textit{iterate}(f, x)$ is a function that iterates $f$ on $x$ then $\textit{iterate}(f,x)$ is a fixed point of $~f$, as

$$\text{iterate}(f,x) = \lim_{n \to \infty} f^n(x) \overset{\text{by above theorem}}{=} f(\lim_{n \to \infty} f^n(x)) = f(\text{iterate}(f,x))$$ $$\iff f(\text{iterate}(f,x)) = \text{iterate}(f,x)$$

But what is a valid proof for said theorem in the first place and does it have a name?

1

There are 1 best solutions below

2
On

EDIT: I didn't read the OP question carefully and incorrectly assumed it was in the setting of topological dynamics. In terms of lambda-calculus, the operator $\lim_{n \to \infty} f(x)$ seems to refer to the Y-combinator, the operator

$Y=\lambda g . (\lambda x. g(xx)).(\lambda x. g(xx))$.

Applied to a function $f$ yields

$Yf = (\lambda x. f(xx)).(\lambda x. f(xx)) = f((\lambda x. f(xx)).(\lambda x. f(xx))) = f(Yf)$. So, the Y-combinator gives the fixed point of $f$.