# How is it possible to define a recursive function call in set theory?

Let the function $$f : X \rightarrow X$$ and a variable $$x \in X$$

I would like to define a set, which contains the values, which can be constructed from consecutive calls of $$f$$ on $$x$$. I did it like this:

$$S = \{ x, f(x), f(f(x)), f(f(f(x))), \dots \}$$

How could this set be defined more elegantly? ( without the dots )

I would like to avoid using this upper index notation also, if possible: $$\{ f^0(x), f^1(x), f^2(x), \dots \}$$

• Do you mean, how to define this in the language of set theory, in the context of ZFC, or something less technical? Apr 22, 2020 at 21:39
• Yes, I mean that Apr 22, 2020 at 21:45
• The usual formalization of recursions such as this is via the set-theoretic recursion theorem. Apr 22, 2020 at 22:49

My interpretation of the question is that you are looking for a way to express this with a notation that doesn't involve the ellipsis? One way is to write $$S = \cap \{ T \, | \, x \in T \, \wedge \, \forall y \in T \, (f(y) \in T) \}$$ If you're planning to do this for several different $$x$$ and maybe several different $$f$$, then it might make sense to define an $$f$$-closure operation on sets, i.e. $$\mathrm{cl}_f (E) := \cap \{ T \, | \, E \subseteq T \, \wedge \, \forall y \in T \, (f(y) \in T) \}$$ You could then write $$S = \mathrm{cl}_f (\{ x\})$$.

• Not that it's wrong, but I don't quite like the fact that the definition of a set that's always countable may involve uncountably many uncountable sets.
– Sam
Apr 22, 2020 at 21:58
• @Sam I agree, both with you and with Andrés Caicedo -- the recursion theorem is the way to go. I wanted to give OP something that didn't immediately look like a trivial rewriting of the $\{ x, f(x), f^2(x), \dots \}$ notation. Of course, if $x = \emptyset$ and we define $f(y) = y \cup \{ y \}$, then $S$ is just $\mathbb{N}$ as von Neumann ordinals! So I'm only avoiding natural numbers in exponents by creating a special-purpose copy of the naturals along the $f$-orbit of $x$. Apr 23, 2020 at 4:04

That would be done with the recursion theorem (or at least that's one way to find that set, I don´t know if you're trying to find the exact property that defines it).

Let $$X$$ be a non-empty set, $$x_0\in X$$ and $$f\colon X\to X$$ a function. Then, we define a function:$$G\colon X\times\mathbb{N}\to X$$ such that $$G(x,n)=f(x)$$. According to the recursion theorem, there exists a unique function $$F\colon\mathbb{N}\to X$$ such that $$F(0)=x_0$$ and for all $$n\in\mathbb{N}$$, $$F(S(n))=G(F(n),n)=f(F(n))$$.

Let's find the first couple values of the function. $$F(0)=x_0$$, $$F(1)=F(S(0))=f(F(0))=f(x_0)$$, and $$F(2)=f(F(1))=f(f(x_0))$$ and so on. So the set you're looking for is, in fact, the image of this function, $$F[\mathbb{N}]$$. (I hope it is clear)

I'm not exactly sure if this is what you were looking for, but hopefully it helps :). Greetings.

• Since the question is about definability, it may be useful to add that the proof of the recursion theorem actually provides an explicit definition of $F$ in terms of the relevant parameters indicated above. Apr 25, 2020 at 15:35