1
$\begingroup$

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 \} $

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

2 Answers 2

6
$\begingroup$

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\})$.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Sam
    Apr 22, 2020 at 21:58
  • 2
    $\begingroup$ @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$. $\endgroup$
    – Sophie M
    Apr 23, 2020 at 4:04
3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 25, 2020 at 15:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .