1
$\begingroup$

Given a set $X$ of finite size and a function $f: X \to X$ such that there exists a positive $k \in \mathbb{Z}$ such that $|f^k(X)| = 1$, prove that $|f^n(X)| = 1$, where $n = |X|$.

I'm having some difficulty with this question. I understand that I must prove if $f^k$ has image size 1, then $f^n$ also has image size 1 where $n = |X|$, but I'm not completely sure how to start. I was thinking of using mathematical induction for $|X| \geq 1$, is this the right direction? Could anyone give me a general outline of where to go with this question?

2 Answers 2

1

Consider the sets $X,f[X],f^2[X],f^3[X],\dots,f^k[X]$. Show that if $f^i[X]=f^{i+1}[X]$ for some $i, then $f^k[X]=f^i[X]$; in words, show that if two successive sets in this sequence are equal, all the sets from that point on are equal. Conclude that if $k$ is the smallest integer such that $\left|f^k[X]\right|=1$, then

$n=\left|X\right|>\left|f[X]\right|>\left|f^2[X]\right|>\ldots>\left|f^k[X]\right|=1\;.\tag{1}$

$(1)$ implies that $k\le n$; can you see why?

HINT: What’s the smallest possible value of $\left|f^i[X]|-f^{i+1}[X]\right|$?

0

The assumption that $|f^k(X)|=1$, means that there is some $y\in X$ such that for all $x\in X$, we have $f^k(x)=y$. Let's take the least such $k$ for which this holds. Observe, then, that $f(y)=f\bigl(f^k(y)\bigr)=f^{k+1}(y)=f^k\bigl(f(y)\bigr)=y,$ so inductively, $f^m(x)=y$ for all $m\geq k$. Hence, $|f^m(X)|=1$ for all $m\geq k$.

Note further that if $f^j(X)\supseteq f^{j+1}(x)$ for all $j$, since if $z\in f(X)$, then for some $x\in X$ we have $z=f^{j+1}(x)=f^j\bigl(f(x)\bigr)$, so $z\in f^{j+1}(X)$. Also, if $f^{j+1}(X)=f^j(X)$, then $f^{j+2}(X)=f\bigl(f^{j+1}(X)\bigr)=f\bigl(f^j(X)\bigr)=f^{j+1}(X)=f^j(X)$. Inductively, if $f^{j+1}(X)=f^j(X)$, then $f^m(X)=f^j(X)$ for all $m>j$, so it follows that $j\geq k$. The contrapositive is that if $j, then $f^{j+1}(X)\neq f^j(X)$. Thus, $f^j(X)\supsetneq f^{j+1}(X)$ for $j. Since we're dealing with finite sets, then $f^j(X)=f^{j+1}(X)$ if and only if $|f^j(X)|=|f^{j+1}(X)|$. Hence, $n=|X|=|f^0(X)|>|f^1(X)|>...>|f^{k-1}(X)|>|f^k(X)|=1,$ so it follows that $k\leq n$ (in fact, that $k), and so $|f^n(X)|=1$.