I need to prove that, for every non empty $A \subset \mathbb{N}$, there's a $f: \mathbb{N} \rightarrow \mathbb{N}$ with $f \circ f =f$ and $f(\mathbb{N})=A$

Unfortunately I have no idea where to start. I'm not even sure what exactly they want me to show, any kind of help would be great.

I tried to show it by using $f(x)=2x$ as an example. I see that it works, but how to show the general case?

  • $\begingroup$ Yes, A is empty as you guys pointed it out, thanks so far. $\endgroup$
    – sassequest
    May 22, 2014 at 9:05
  • 1
    $\begingroup$ $f(x) = 2x$ does not work because it does not fit the $f\circ f=f$ requirement: $f(f(x)) = 2(2x) = 4x \ne 2x = f(x)$. $\endgroup$
    – CiaPan
    May 22, 2014 at 9:44

3 Answers 3


This can only be solved under condition that $A$ is not empty. Let $a_0\in A$.

Define $f$ by $x\mapsto x$ if $x\in A$ and $x\mapsto a_{0}$ otherwise.


Consider the injection $j\colon A\to\mathbb{N}$; then there exists a function $g\colon\mathbb{N}\to A$ such that $g\circ j=1_A$ is the identity on $A$. Try $f=j\circ g$ and prove the claims.

Of course this is impossible if $A$ is the empty set. Note also that this doesn't require the set to be the natural numbers; you can start from any set $B$ and any non empty subset $A\subseteq B$.


I guess that by $N$ you mean the set of natural numbers and that $A$ is not empty.

There are two cases: $A$ is finite or infinite.

Case 1: $A = \{a_1 < \ldots < a_n\}$ is finite. Then define $f(x)$ s.t. $f(x) = a_1$ if $x \leq a_1$, $f(x) = a_2$ if $a_1 < x \leq a_2$, ..., $f(x) = a_n$ if $a_{n-1} < x$.

Case 2: $A = \{a_1 < a_2 < \ldots \}$ is infinite. Then define $f(x)$ to be the least $a_i$ s.t. $x \leq a_i$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .