Prove that no function satisfies: $f(f(x))=x+3$, if $f: \mathbb Z_{>0}→ \mathbb Z_{>0}$?

Question

I feel like I need to work in modulo 3 and show that the cardinality of certain subsets has to be different but I don't know where to start, any help would be appreciated! I know the function has to be bijective but that is about it.

Answer 1

As pointed out in comments, applying $f$ on both sides we get $f(f(f(x)))=f(x+3)$, but also substituting $f(x)$ for $x$ in the original equation, we have $f(f(f(x)))=f(x)+3$. So $f(x+3)=f(x)+3$ and behavior of $f(x)$ is completely determined by its values on $x=1,2,3$, i.e we have the following:

Let $a \geq 1$, $k \geq 0$. Then $$f(a+3k)=f(a)+3k\tag{1}.$$

Now we can study some properties of $f(1)$, $f(2)$, $f(3)$, eventually we can see they lead to contradiction.

Let $i \in \{1,2,3\}$. Then $$f(i)\not\equiv i \pmod {3}\tag{2}.$$

Proof. Assume $f(i)\equiv i \pmod 3$. So $f(i)=i+3k$, and by $(1)$ we have $$i+3=f(f(i))=f(i+3k)=f(i)+3k=i+3k+3k,$$ hence $k=1/2$, a contradiction. So $f(i)\not\equiv i \pmod {3}$.

Note: As shown in YiFan's answer, the $(2)$ is already enough to show the function does not exist.

Let $i,j \in \{1,2,3\}$, $i\neq j$. Then $$f(i) \not\equiv f(j) \pmod 3.\tag{3}$$

Proof. Assume $f(i) \equiv f(j) \pmod 3$, WLOG assume $f(i)=f(j)+3k$ with $k \geq 0$. Then again by $(1)$ we have $$i+3=f(f(i))=f(f(j)+3k)=f(f(j))+3k=j+3+3k,$$ so $i \equiv j \pmod 3$ and by choice of $i,j$ this implies $i=j$, a contradiction. So $f(i) \neq f(j) \pmod 3$.

Finally, let $i \in \{1,2,3\}$. We have $f(i) \equiv j \pmod {3}$ for some $j\in \{1,2,3\}$, and $j\neq i$ by $(2)$. Now clearly $f(i) \geq j$ and so $f(i)=j+3k$ for $k \geq 0$ integer. So again by $(1)$ we have $$i+3=f(f(i))=f(j+3k)=f(j)+3k,$$ and so $f(j) \equiv i \pmod {3}$. Now, let $k$ be the remaining value $k \in \{1,2,3\}$, $k \neq i$, $k \neq j$. By $(3)$, the $f(k)$ cannot be congruent with $f(i)\equiv j$ nor with $f(j)\equiv i$. So only possibility left is $f(k)\equiv k \pmod 3$, but this contradicts $(2)$.

So no such $f(x)$ exists.

Answer 2

Suppose otherwise. $f$ must be injective, since $f(a)=f(b)$ implies $f(f(a))=f(f(b))$, which in turn implies $a=b$. We can therefore partition $\mathbb{N}$ into disjoint sets of the form $\{a,f(a),f(f(a)),\ldots\}$, by repeatedly taking the least element not in the partition and generating its orbit. However, since each one of these sets must have natural density $\frac{2}{3}$ (as it must contain precisely the integers of the form $a+3k$ and $f(a)+3k$, for $k\geq0$), there must be $\frac{3}{2}$ sets in this partition, an absurd. This proves no such function exists.

Answer 3

The following is a shorter version of what is essentially equivalent to Sil's answer. Note that $f(x+3)=f(f(f(x)))=f(x)+3$, which implies that $f(x)\equiv f(x+3)$ mod $3$. Now $f(f(x))\equiv x$ mod $3$, so the restriction of $f$ mod $3$ is an involution, but since $|\mathbb Z/3\mathbb Z|=3$ is odd this implies there is a fixed point $f(a)\equiv a$ mod $3$. But this is impossible: see Sil's answer for the proof.