2

What are the functions with $f \circ f \circ f=f$ defined from a set $E$ to itself?

I can prove that such a function is onto iff it is one to one. So suppose also that $f$ is bijective.

If $E=\mathbb{R}$ we have as solutions $f(x)=x$ and $f(x)=-x$ or functions defined piecewise with those functions.

Can we describe all solutions for $E=\mathbb{R}$? For $E=\mathbb{R}^n$ for $n>0$ integer?

mathcounterexamples.net
  • 70,018
  • 2
    Since $f$ is assumed to be bijective, we can compose both sides of your equality with $f^{-1}$ and so obtain $(f\circ f)(x)=x$. – Semiclassical Nov 28 '14 at 06:06

3 Answers3

2

Let's partition $\mathbb{R}$ into parts of size one or two, e.g. $$\mathbb{R}=\{1,-1\}\cup \{3,\pi\}\cup \{7\}\cup \cdots$$ On the parts of size two, $f$ will send one element to the other. On the parts of size one, $f$ will fix that element.

$f(x)=x$ corresponds to the partition where each part is of size $1$. $f(x)=-x$ corresponds to the partition where each nonzero element is in a part with its negative, and $0$ is in a part of size $1$.

Since $f=f^{-1}$, it is easy to see that any bijective $f$ induces such a partition.

vadim123
  • 82,796
1

There are many. For instance, just try any permutation of two integers, that "flips" them.

For $\mathbb{R}^2$ you have rotations, etc.

Off the top of my head I'm not sure the constraints you need for this to be interesting (continuous for one).

djechlin
  • 5,386
1

Without any further restrictions there is a huge array of solutions, particularly for infinite sets $E$. For instance, if you write $E$ is a disjoint union of doubletons $E=\bigcup D_i$, with $D_i=\{a_,b_i\}$, then defining $f:E\to E$ by $f(a_i)=b_i$ and $f(b_i)=a_i$, clearly solves $f\circ f \circ f=f$. This shows how random such functions can be as the decomposition of E into doubletons can be quite horrible.

In $R^n$, any reflection about a line solves the equation. Similarly, any rotation by $\pi$ radians about a point solves the equation. The identity function of course also solves the equation. The inversion $z\mapsto 1/z$ is also a solution.

All of these examples are actually ones where $f=f^-1$. Any such function will, of course, also solves your equation. So, if you include the condition that $f$ is bijective, then $f^{-1}$ exists, and then applying it to the equation yields $f\circ f = id$, in other words $f$ is an involution. In short, under the assumption of bijectivity, solutions to $f\circ f\circ f=f$ are the same as solutions to $f\circ f = id$.

Other solutions are obtained by writing $E$ as a disjoint union of doubletons and/or singletons, with $f$ defined similarly.

Ittay Weiss
  • 79,840
  • 7
  • 141
  • 236
  • You forgot the non-bijective functions. $f\equiv c$ for any constant $c$, for example. Or functions $f$ such that there is some disjoint union $E = \bigcup A_i$ such that $f(A_i) = a_i \in A_i \quad\forall i$ – AlexR Nov 18 '16 at 08:19
  • OP stated $f$ to be bijective. – Ittay Weiss Nov 18 '16 at 09:14
  • Maybe I misunderstood the OP, but to me it looked like that supposition was not part of the question but part of his thoughts on the problem. Evident of that is that a "function defined piecewise by [$x$ or $-x$]" will not be bijective in general. – AlexR Nov 18 '16 at 09:16
  • Ah, I see. Hopefully OP can clarify. – Ittay Weiss Nov 18 '16 at 09:19
  • In that case the actual condition is $f\circ f|_{f(E)} \equiv \mathrm{id}$, so it's slightly weaker, but not by much. You can then use your construction for $f(E)$ instead of $E$ and map $E\setminus f(E)$ arbitrarily into $f(E)$. – AlexR Nov 18 '16 at 09:22