2

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.

Andrés E. Caicedo
  • 79,201
Student
  • 83
  • 4
  • I don't see any reasoning in the chain of equalities you wrote. It is not clear how these rows of equations are connected. What do you mean by "every set is not empty"? If $a_0$ exists you are done, right? After all, $a_0$ is defined as the first term of the infinite sequence with the required property. Since your proof does not end there, that means that when you say that "$a_0$ exists" you mean something else. – Andrés E. Caicedo Nov 20 '18 at 21:44
  • I think you need to work out some specific examples to see what the actual difficulties are. The obvious proof uses the finiteness and nonemptyness of all the $A_n$ in an essential manner. The fact that you are not using this should indicate that you are not yet clear on what is going on. – Andrés E. Caicedo Nov 20 '18 at 21:47

1 Answers1

1

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

Paul Frost
  • 76,394
  • 12
  • 43
  • 125