Choosing a sequence of elements of sets such that $f_n(a_{n+1})=a_n$. Let $\forall n \in \mathbb{N} : A_n$ be a non empty finite set and $ \forall n\in \mathbb{N} :  f_n : A_{n+1} \rightarrow A_n$. Prove you can choose a sequence of elements  $a_0 \in A_0, a_1 \in A_1, ...$ such that $\forall n \in \mathbb{N} : f_n(a_{n+1}) = a_n $. Is the assumption that $A_n$ is finite necessary?
Is this valid reasoning?
$f_n(a_{n+1})=a_n$
$a_{n+1} = f^{-1}_{n}(a_n)=f^{-1}_{n}(f^{-1}_{n-1}(a_{n-1}) =f^{-1}_{n}(f^{-1}_{n-1}(...f^{-1}_{0}(a_0)))$
$a_{n}=f^{-1}_{n-1}(f^{-1}_{n-2}(...f^{-1}_{0}(a_0)))$
$a_{n-1}=f^{-1}_{n-2}(f^{-1}_{n-3}(...f^{-1}_{0}(a_0)))$
...
$a_1=f^{-1}_{0}(a_0)$
$a_0$
$a_{0} \in A_{0}$ exists because every set is not empty . By $f_n : A_{n+1} \rightarrow A_n$ some element from $A_1$ that I choose to be $a_1$ is mapped to some element in $A_0$ that  I choose to be $a_0$. This reasoning continues all the way up. I don't know if the assumption that the sets are finite is important.
 A: Note that if all but finitely many $f_n$ are surjections, then the desired sequence $(a_n)$ with $a_n \in A_n$ obviously exists. This does not depend on the cardinality of the sets $A_n$.
If this is not the case, the situation gets complicated. But here are good news: If the sets $A_n$ are finite, we can always construct a sequence of nonempty subsets $A'_n \subset A_n$ such that $f_n(A'_{n+1}) = A'_n$. This provides a sequence $(a_n)$ as desired (with $a_n \in A'_n$).
For $m > n$ define $f^m_n = f_{n+1} \circ \dots \circ f_m : A_m  \to A_n$. For each $n$ the sets $f^m_n(A_m)$, $m > n$, form a decreasing sequence of nonempty subsets of $A_n$. If $A_n$ is finite, we can have only finitely many $m$ such that $f^{m+1}_n(A_{m+1}) \subsetneqq f^m_n(A_m)$. Hence there must exist an $\mu(n) > n$ such that $f^m_n(A_m) = f^{\mu(n)}_n(A_{\mu(n)})$ for all $m \ge \mu(n)$. Now define recursively
$$\phi(0) = 0, \phi(k+1) = \mu(\phi(k)) .$$
This is a strictly increasing sequence of integers. Next define
$$A'_{\phi(k)} = f^{\mu(\phi(k))}_{\phi(k)}(A_{\mu(\phi(k))}) \subset A_{\phi(k)} .$$
We have
$$f^{\phi(k+1)}_{\phi(k)}(A'_{\phi(k+1)}) = f^{\phi(k+1)}_{\phi(k)}(f^{\mu(\phi(k+1))}_{\phi(k+1)}(A_{\mu(\phi(k+1))})) = f^{\mu(\phi(k+1))}_{\phi(k)}(A_{\mu(\phi(k+1))})$$
$$= f^{\mu(\phi(k))}_{\phi(k)}(A_{\mu(\phi(k)}) = A'_{\phi(k)} .$$
For $\phi(k) \le n < \phi(k+1)$ define
$$A'_n = f^{\phi(k+1)}_n(A'_{\phi(k+1)}) .$$
Then by construction for all $n$
$$f_n(A'_{n+1}) = A'_n$$
and we are done.
If we drop the finiteness requirement, then in general we cannot find a sequence as required. Here is an example. Let $A_n = \{ k  \in \mathbb{N} \mid k \ge n \}$ and let $f_n : A_{n+1} \to A_n$ denote inclusion. Then for any $a_0 = k \in A_0$ we have $a_0
 \notin A_{k+1}$, hence $a_0 \notin f^{k+1}_0(A_{k+1})$. This shows that no $(a_n)$ exists.
Final remark: The set $\mathcal{S}$ of all sequences $(a_n)$ such that $a_n \in A_n$ and $f_n(a_{n+1}) = a_n$ for all $n$ is called the inverse limit of the system $\mathbf{A} = (A_n,f_n)$. One writes
$$\mathcal{S} = \varprojlim \mathbf{A} .$$
