TITLE: Show that exists a function $\phi :\mathbb{N}\rightarrow \mathbb{N}$ strictly increasing such that $f\circ \phi(x)$ is a constant function.
QUESTION [0 upvotes]: Let $A$ be a nonempty set and $f:\mathbb{N} \rightarrow A$ a function with a finite image. Show that there exists a strictly increasing function $\phi :\mathbb{N}\rightarrow \mathbb{N}$ such that $f\circ \phi(x)$ is a constant function.
My try: 
We need to find a $\phi$ strictly increasing function that changes the domain of $f$ such that $f\circ \phi(x)$ is a constat function. The only function I can think of is $\phi(x) = f^{-1}(c)$ with $c \in A$. But this isn't strictly increasing. Any suggestions?

REPLY [7 votes]: Since $f(\mathbb{N})$ is finite, there must be an $a\in A$, such that $f^{-1}(\{a\})$ is an infinite subset of $\mathbb{N}$. From here, we can define $\phi(n)$ to be the $n$th smallest element in   $f^{-1}(\{a\})$.
{"set_name": "stack_exchange", "score": 0, "question_id": 3542945}