1

Suppose that we have an arbitrary function $f$ that map a set X into itself and let this set consist of $2^5$ points. Is that true that some point there has a periodic orbit?

Intuitively it is clear because we only have $2^5$ points and if we start at some point $x$ and iterate this $2^5+1$ times, at least one result will be repeated and we can just take this point. But Im not sure that this is proper proof.

zxczxc
  • 25
  • If you interest in this field, you can study Boolean Monomial Dynamical Systems, Boolean network or finite dynamical system – user479859 Nov 03 '19 at 19:44

1 Answers1

2

What you have is a full proof. I would personally just expand a bit on the details, as your proof is a bit brief. For instance,

Take a point $x_0\in X$, and consider the sequence $x_n=f(x_{n-1})$ for $n\geq1$. By the pigeonhole principle, there must be at least one $n\leq2^5$ such that $x_n$ is equal to some earlier term in the sequence. Let $k$ be the smallest such index. Let $j<k$ be such that $x_j=x_k$. Then $x_j$ has orbit of period $k-j$.

Arthur
  • 199,419