0

Prove that there is no function f : ℕ→ℕ such that f (f (n)) = n + 1. Here ℕ is the positive integers {1, 2, 3,...}.

I have messed around with the FE but can't seem to produce anything meaningful. I found the solution online which states but I'm having trouble following the part where it states that the former yields f 2 (N):

Let M = {2,3,...} = N\ {1}. Then f 2 (N) = M and therefore f(N) = N or M. The former yields f 2 (N) = N, which is not the case, so we must have the latter which yields f(M) = M. It follows that f 2 (M) = M and we have a contradiction, so there is no such f , as required.

Link is added below:

https://www.math.vt.edu/people/plinnell/Vtregional/E18/index.html

user690808
  • 157
  • 1
    Welcome to MSE. Please provide a link to the solution you found online as it could help us to better answer your question. Thanks. – John Omielan Jul 23 '19 at 04:19
  • https://www.math.vt.edu/people/plinnell/Vtregional/E18/index.html – user690808 Jul 23 '19 at 04:21
  • 1
    Thanks for providing a link. However, it only has your question stated as question #$3$. I don't see any solution for this question, or any other listed questions, on that page. – John Omielan Jul 23 '19 at 04:25
  • https://www.math.vt.edu/people/plinnell/Vtregional/solutions.pdf – user690808 Jul 23 '19 at 04:25
  • Solutions have been uploaded; I didn't attach it at first as the solutions are all the way at the bottom. – user690808 Jul 23 '19 at 04:26
  • Also could you explain how they can deduce that "Then f 2 (N) = M and therefore f(N) = N or M." – user690808 Jul 23 '19 at 04:43
  • I just worked on this one yesterday. I will post an alternate solution. – Display name Jul 23 '19 at 04:59
  • 1
    By the way, https://math.stackexchange.com/questions/1936098/is-there-are-function-f-on-the-positive-integers-so-that-ffn-n1 - though your question is not a duplicate of this, because you have a specific point of confusion. – Patrick Stevens Jul 23 '19 at 05:03
  • (())=+1 , ((()))=(+1)=()+1. Sorry to bother you, but how can we deduce that ()+1 is equal to all the rest of the statements? – user690808 Jul 23 '19 at 05:13

2 Answers2

1

Note that \begin{align*} 1 \mapsto k_1 &\mapsto 2\\ 2 \mapsto k_2 &\mapsto 3\\ 3 \mapsto k_3 &\mapsto 4\\ \vdots \mapsto \vdots &\mapsto\vdots\\ r \mapsto k_r &\mapsto r+1\\ \vdots \mapsto \vdots &\mapsto\vdots\\ \end{align*} As you can see from the composition mapping, $M=\{2,3,4,5, \ldots\}$ is definitely in the range of $f$. So $M \subseteq f(\Bbb{N})$.

Question: is $1 \in f(\Bbb{N})$?

Note that from the second part of the composition, it is clear that $1 \not\in f(\Bbb{N})$. Thus the range $f(\Bbb{N})=M$.

This means for all $i$, $k_i \in M$. Said differently $f(M)=M$. But then $f(f(M))=M$. If this was true then how will $2$ be in the range of $f$?

Anurag A
  • 41,067
0

Since $f(n+1)= (f \circ (f \circ f))(n)=((f \circ f) \circ f)(n)= f(n)+1,$ we have $f(n)=n+c$ where $c=f(1)-1 \in \mathbb{Z}.$ But then $c=1/2$ by substitution, a contradiction.

Display name
  • 5,144