Csdrhrt

Let $forall n in mathbb{N} : A_n$ be a non empty finite set and $ forall nin 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.

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