How do I prove this function doesn't exist?

Question

Let $g: S\rightarrow S$ be a function such that $g$ has exactly two fixed points, and $g\circ g$ has exactly four fixed points. Prove that there is no function $f:S\rightarrow S$ such that $g=f\circ f$

I have literally no idea where to start, any hints or help?

Where $S$ is any set? – Hagen von Eitzen Dec 16 '14 at 09:10 — Hagen von Eitzen, Dec 16 '14 at 09:10
yeah, it doesn't specify, so I guess $S$ is any set – user93089 Dec 16 '14 at 09:11 — user93089, Dec 16 '14 at 09:11
It seems that $S$ has implicitely at least four elements. – Tom-Tom Dec 16 '14 at 09:12 — Tom-Tom, Dec 16 '14 at 09:12

score 1 · Answer 1 · answered Dec 16 '14 at 09:29

Assume $g=f\circ f$. If $x$ is a fixed point of $g$, then so is $f(x)$, for $g(f(x))=f(f(f(x)))=f(g(x))=f(x)$. Likewise, if $x$ is a fixed point of $g\circ g$, then so is $f(x)$ as well as $g(x)$. Now if $x_1,x_2$ are the fixed points of $g$ and $x_3,x_4$ the "extra" fixed points of $g\circ g$, we conclude that $f$ permutes $S':=\{x_1,x_2,x_3,x_4\}$. By the observations above, we have $f(x_1)\in\{x_1,x_2\}$, $f(x_2)\in\{x_1,x_2\}$, $f(x_3)\in\{x_3,x_4\}$, $f(x_4)\in\{x_3,x_4\}$. Consequently $f$ has order $1$ or $2$ (as permutation of $S'$). But then $g$ is the identity on $S'$, i.e. $x_{3}, x_4$ are also fixed points of $g$.

How do I prove this function doesn't exist?

1 Answers1