Three kinds of sub-structures on a set with an injective function? Suppose we have an injective function $f: S \to S$ for non-empty $S$. Intuitively, it seems to me that the set $S$ can be partitioned into "sub-structures" using $f$ as a kind of successor function, each of these sub-structures being one of only three kinds: (1) a finite closed loop, (2) an infinite set with a starting point, e.g. like $\mathbb{N}$, and (3) an infinite set with no starting point, e.g. like $\mathbb{Z}$. Is this correct? Are there other possibilities?
 A: Let $X$ be a set and $f \colon X \to X$ injective. For every $x \in X$ let $(x) = \{f^n(x) \mid n \in \mathbb{N}\}$ be the orbit of $x$ under $f$.

We define an equivalence relation $\sim$ on $X$ via $x \sim y \iff (x) \cap (y) \neq \emptyset$. Notice that $x \sim y$ if and only if $f^n(x) = f^m(y)$ for some $n,m \in \mathbb{N}$, which by the injecitivity of $f$ is equivalent to $x = f^k(y)$ or $y = f^k(x)$ for some $k \in \mathbb{N}$.
It is clear that $\sim$ is reflexive and symmetric. To see that it is transitive let $x, y, z \in X$ with $x \sim y$ and $y \sim z$. Then $f^k(x) = f^l(y)$ and $f^m(y) = f^n(z)$ for some $k,l,m,n \in \mathbb{N}$. Therefore
$$
 f^{m+k}(x)
 = f^m(f^k(x))
 = f^m(f^l(y))
 = f^{m+l}(y)
 = f^l(f^m(y))
 = f^l(f^n(z))
 = f^{l+n}(z),
$$
showing that $x \sim z$.
The "substructures" you are referring to are the equivalence classes of $\sim$; we denote the equivalence class of $x \in X$ by $[x]$. Notice that $(x) \subseteq [x]$, and that this inclusion may be proper! (Take for example $X = \mathbb{N}$ and $f \colon \mathbb{N} \to \mathbb{N}$, $n \mapsto n+1$. Then $(1) = \{n \in \mathbb{N} \mid n \geq 1\}$ but $1 = f(0)$ and thus $1 \sim 0$ and therefore $[1] = [0] = \mathbb{N}$).
The equivalence classes come in the three forms you described:

The cyclic ones
If $x \in X$ with $[x]$ being finite, then the elements
$$
 x, f(x), f^2(x), f^3(x), \dotsc, f^n(x), \dotsc
$$
are not pairwise different, so $f^n(x) = f^m(x)$ for some $n,m \in \mathbb{N}$, from which it follows from the injectivity of $f$ that $x = f^k(x)$ for some $k \in \mathbb{N}_{\geq 1}$; picking $k \in \mathbb{N}_{\geq 1}$ minimal with $x = f^k(x)$, we get that $[x] = \{x, f(x), \dotsc, f^k(x)\}$ with the element $f^l(x)$, $0 \leq l \leq k$ being pairwise different. These are the equivalence classes of the first kind, i.e. the cyclic ones.
An interesting special case of finite equivalence classes are those consisting of a single element; these correspond precisely to the fixed-points of $f$.
The infinite ones
There are two kinds of infinite equivalence classes: Let $E \subseteq X$ be an infinite equivalence class.
The ones looking like $\mathbb{N}$
Suppose that there exists some $x \in E$ with $x \notin f(X)$. Then $(x) \subseteq [x]$. On the other hand for every $y \in E = [x]$ we have $x = f^k(y)$ or $y = f^k(x)$ for some $k \in \mathbb{N}$. Because $x \notin f(X)$ we have the second case, so $y = f^k(x)$ for some $k \in \mathbb{N}$ and thus $y \in (x)$. So we already have $E = [x] = (x) = \{x, f(x), f^2(x), \dotsc\}$.
Because $[x] = E$ is infinite we know that the elements $f^k(x)$ with $k \in \mathbb{N}$ must be pairwise different, so the equivalence class $E$ does indeed look like $\mathbb{N}$, in the sense that the map $\mathbb{N} \to E$, $n \mapsto f^n(x)$ is a bijection.
Also notice that the choosen starting point $x$ is unique in $E$, in the sense that for no other $y \in E$ the map $\mathbb{N} \to E$, $n \mapsto f^n(y)$ is bijective; this follows because $x \notin f(X)$, so this mapping would not be surjective.
The ones looking like $\mathbb{Z}$
If $x \in f(X)$ for every $x \in X$ then by the injectivity of $f$ there exists for every $x \in X$ an unique $y \in X$ with $f(y) = x$; notice that in particular $y \sim x$, so $y \in [x] = E$. It follows that the restriction $f|_E \colon E \to E$ is not only injective (which follows from $f$ being injective), but also surjective, and therefore bijective.
We fix some arbitrary $x \in E$. We already know that $(x) \subseteq [x]$, i.e. $f^n(x) \sim x$ for every $n \geq 0$. On the other hand we have for every $n \leq 0$ that $f^{-n}((f|_E)^n(x)) = x$ and thus also $f^n(x) \sim x$. So we have $f|_E^n(x) \sim x$ for every $n \in \mathbb{Z}$.
If on the other hand $y \in E = [x]$ then $y = f^k(x)$ or $x = f^k(y)$ for some $k \in \mathbb{N}$, and thus $y = f|_E^k(x)$ or $y = (f|_E)^{-k}(x)$ for some $k \in \mathbb{N}$. So we already have $[x] = E = \{f^n(x) \mid n \in \mathbb{Z}\}$.
Because $E$ is infinite we find that the elements $f|_E^n(x)$ with $n \in \mathbb{Z}$ are pairwise different, so the map $g_x \colon \mathbb{Z} \to E$, $n \mapsto f|_E^n(x)$ is a bijection. In this sense this equivalence class does indeed look like $\mathbb{Z}$.
Also notice that in this case we can choose any point $y \in E$ as a base point, in the sense that the map $g_y \colon \mathbb{Z} \to E$, $n \mapsto f|_E^n(y)$ would also be a bijection. This follows because $y = f|_E^k(x)$ for some $k \in \mathbb{Z}$, and as both $g_x$ and the shift $h_k \colon \mathbb{Z} \to \mathbb{Z}$, $n \mapsto n+k$ are bijections the same goes for $g_y = g_x \circ h_k$.

With this we have distinguished between all three kinds of equivalence classes; as every equivalence class is finite or infinite, and every infinite equivalence class contains an element of $f(X)$ or does not contains an element of $f(X)$, we find that there are no other types than the above three. 
