134
$\begingroup$

I've been perusing the internet looking for interesting problems to solve. I found the following problem and have been going at it for the past 30 minutes with no success:

Find a function $f: \mathbb{R} \to \mathbb{R}$ satisfying $f(f(x)) = -x$ for all $x \in \mathbb{R}$.

I am also wondering, can we find $f$ so that is continuous?

I was thinking of letting $f$ be a periodic function, and adding half the period to x each time. I had no success with this, and am now thinking that such a function does not exist.

Source: http://www.halfaya.org/Casti/CalculusTheory2/challenge.pdf

|cite|improve this question
$\endgroup$
  • 22
    $\begingroup$ You have $f(f(f(f(x))))=f(f(-x))=x$ for all $x$. Therefore $f$ has to be a bijection (iterating it thrice gives its inverse). Consequently a periodic function is a non-starter. $\endgroup$ – Jyrki Lahtonen Feb 23 '13 at 23:00
  • 3
    $\begingroup$ This would be easy if complex numbers where permitted. $\endgroup$ – PyRulez Feb 23 '13 at 23:01
  • 4
    $\begingroup$ @JyrkiLahtonen Also, $f(x) = f^{-1}(-x)$. $\endgroup$ – Gamma Function Feb 23 '13 at 23:05
  • 3
    $\begingroup$ @PyRulez Yeah, f(z) = i * z. $\endgroup$ – Gamma Function Feb 23 '13 at 23:05
  • 7
    $\begingroup$ Given that Hurkyl already gave a proof of the non-existence of continuous functions satisfying that equality I find it a bit strange that you edited your question in this way. It has the undesired side-effect of making all the (heavily upvoted) answers appear out of place. $\endgroup$ – Jyrki Lahtonen Mar 23 '14 at 22:52
144
$\begingroup$

An important piece of information is:

Theorem: $f$ is not continuous.

Proof: Observe that $f$ is invertible, because

$$f(f(f(f(x)))) = f(f(-x)) = x$$

and so $f \circ f \circ f = f^{-1}$. Any continuous invertible function on $\mathbb{R}$ is either strictly increasing or strictly decreasing.

If $f$ is strictly increasing, then:

  • $1 < 2$
  • $f(1) < f(2)$
  • $f(f(1)) < f(f(2))$
  • $-1 < -2$

contradiction! Similarly, if $f$ is strictly decreasing, then:

  • $1 < 2$
  • $f(1) > f(2)$
  • $f(f(1)) < f(f(2))$
  • $-1 < -2$

contradiction! Therefore, we conclude $f$ is not continuous. $\square$

For the sake of completeness, the entire solution space for $f$ consists of functions defined as follows:

  • Partition the set of all positive real numbers into ordered pairs $(a,b)$
  • Define $f$ by, whenever $(a,b)$ is one of our chosen pairs,
    • $f(0) = 0$
    • $f(a) = b$
    • $f(b) = -a$
    • $f(-a) = -b$
    • $f(-b) = a$

To see that every solution is of this form, let $f$ be a solution. Then we must have $f(0) = 0$ because:

  • Let $f(0) = a$. Then $f(a) = f(f(0)) = 0$ but $-a = f(f(a)) = f(0) = a$, and so $f(0) = 0$

If $a \neq 0$, then let $f(a) = b$. We have:

  • $f(b) = f(f(a)) = -a$
  • $f(-a) = f(f(b)) = -b$
  • $f(-b) = f(f(-a)) = a$

From here it's easy to see the set $\{ (a,f(a)) \mid a>0, f(a)>0 \}$ partitions the positive real numbers and so is of the form I describe above.

One particular solution is

$$ f(x) = \begin{cases} 0 & x = 0 \\ x+1 & x > 0 \wedge \lceil x \rceil \text{ is odd} \\ 1-x & x > 0 \wedge \lceil x \rceil \text{ is even} \\ x-1 & x < 0 \wedge \lfloor x \rfloor \text{ is odd} \\ -1-x & x < 0 \wedge \lfloor x \rfloor \text{ is even} \end{cases}$$

e.g. $f(1/2) = 3/2$, $f(3/2) = -1/2$, $f(-1/2) = -3/2$, and $f(-3/2) = 1/2$.

(This works out to be Jyrki Lahtonen's example)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This proof provides wonderful intuition for the problem. I reckon that this would imply that $f$ is not an elementary function. $\endgroup$ – Gamma Function Feb 23 '13 at 23:26
  • $\begingroup$ Aren't all elementary functions nearly everywhere continuous? $\endgroup$ – Ben Millwood Feb 24 '13 at 1:32
  • $\begingroup$ @BenMillwood Yes, elementary functions have only finitely many discontinuities on their domain. It follows that f is not an elementary function, as an obvious corollary of the above is that f contains infinitely many points of discontinuity. $\endgroup$ – Gamma Function Feb 24 '13 at 3:08
  • 3
    $\begingroup$ Well done, Hurkyl! @Alexis, I think that we need a minimum of 3 points of discontinuity, and I don't see right away how to do even that. If we had a continuous bijection $g$ from $(0,1]$ to $(1,\infty)$, we could use that. The function $f$ would map (here $x\in(0,1]$) $$x\mapsto g(x)\mapsto -x\mapsto -g(x)\mapsto x,$$ and the discontinuities would be at $0,\pm1$. But I don't think there is such a function $g$ :-) $\endgroup$ – Jyrki Lahtonen Feb 24 '13 at 12:12
  • 4
    $\begingroup$ Yes, I was entirely wrong, I take it all back. I was heedlessly ignoring the boundary points. I now believe you really do need an infinite number of discontinuities, but it's not a trivial corollary. Please see the attempted proof sketch in my answer. $\endgroup$ – alexis Feb 24 '13 at 20:15
50
$\begingroup$

Here is a graph of one such function, piecewise continuous.

Graph of a function satisfying f(f(x))=-x

Here's another picture to clarify endpoint behavior.

Graph of a function satisfying f(f(x))=-x

|cite|improve this answer
$\endgroup$
  • 4
    $\begingroup$ Nice pictorial solution. It actually looks like a windmill of sorts, but when you look at it again, the function passes the vertical line test. $\endgroup$ – Joe Z. Feb 25 '13 at 5:08
  • 7
    $\begingroup$ @Joe and the horizontal line test too, as such a function needs to be one-to-one. $\endgroup$ – alex.jordan Feb 25 '13 at 5:26
  • 3
    $\begingroup$ As the OP points out in a comment to his question: $f(x) = f^{-1}(-x)$. Since inverting a function flips its graph over the line $y=x$, and since negating a function's argument flips its graph over the $y$-axis, the graph of $f^{-1}(-x)$ must be a rotation of the graph of $f(x)$ through $90$ degrees about the origin; because the graph of $f^{-1}(-x)$ must also coincide with the graph of $f(x)$ itself, we see that the graph itself must have four-fold rotational symmetry, as indeed yours does. $\endgroup$ – Blue Feb 25 '13 at 6:25
  • $\begingroup$ What software was used to draw this? $\endgroup$ – Aaron John Sabu May 15 '17 at 17:55
  • 1
    $\begingroup$ @AaronJohnSabu It has been a very long time, but I think probably GeoGebra, and then a screen shot capture. $\endgroup$ – alex.jordan May 15 '17 at 19:48
34
$\begingroup$

Hint: If all the real numbers in existence were $1,2,-1,-2$, then the function $f: 1\mapsto 2\mapsto -1\mapsto-2\mapsto 1$ would work.

Spoiler:

Similarly permute $t,1+t,-t,-1-t$ for all $t\in(2n,2n+1]$ and for all natural numbers $n$. Handle $x=0$ separately.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I don't know how to do this with an elementary function. $\endgroup$ – Jyrki Lahtonen Feb 23 '13 at 22:58
  • $\begingroup$ Me too. Also, how could zero be handled separately with an elementary function? $\endgroup$ – Gamma Function Feb 23 '13 at 23:08
  • $\begingroup$ We can map zero to itself, but basically all the non-zero numbers need to be permuted in a 4-cycle, and all those 4-cycles must be stable under negation. Therefore we need to "pair up" the positive numbers somehow. The spoiler contains one suggestion, there may be simpler ones. $\endgroup$ – Jyrki Lahtonen Feb 23 '13 at 23:15
26
$\begingroup$

Another way of phrasing @Haskell Curry's proof:

Assuming the axiom of choice, both $\Bbb{R}$ and $\Bbb{C}$ are $\Bbb{Q}$-vector spaces with bases of the same cardinality. Thus there is some $\Bbb{Q}$-linear isomorphism $\alpha:\Bbb{R} \to \Bbb{C}$.

Then we can let $f$ be $\alpha^{-1} \circ g \circ \alpha$, where $g(z)=iz$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ wait, if a is last, it could return a complex answer $\endgroup$ – PyRulez Feb 24 '13 at 13:50
  • $\begingroup$ @PyRulez: Functions compose from right to left. $\endgroup$ – Micah Feb 24 '13 at 14:25
  • $\begingroup$ slight problem This assumes that $\alpha^{-1}(-\alpha(x))=-x$. Explain how this can be assumed. $\endgroup$ – PyRulez Feb 24 '13 at 14:36
  • 3
    $\begingroup$ @Pyrulez: If $\alpha$ is $\Bbb{Q}$-linear, that means $\alpha(qx)=q\alpha(x)$ for any $q \in \Bbb{Q}$. $\endgroup$ – Micah Feb 24 '13 at 14:43
12
$\begingroup$

We can even find an $ f $ that is $ \mathbb{Q} $-linear, although we need the Axiom of Choice (AC).

  • As $ \mathbb{R} $ is a $ \mathbb{Q} $-vector space, use AC to obtain a basis $ \beta $ of $ \mathbb{R} $ over $ \mathbb{Q} $.

  • Next, form a partition $ \mathcal{P} $ of $ \beta $ into uncountably many two-element subsets.

  • Define a $ \mathbb{Q} $-linear function $ f: \mathbb{R} \to \mathbb{R} $ by defining it on $ \beta $ as follows and then extending the definition by linearity: $$ \forall \{ a,b \} \in \mathcal{P}: \quad f(a) = -b \quad \text{and} \quad f(b) = a. $$

  • We thus obtain \begin{align} \forall \{ a,b \} \in \mathcal{P}: \quad f(f(a)) &= f(-b) = - f(b) = -a \quad \text{and} \\ f(f(b)) &= f(a) = -b. \end{align}

  • Therefore, $ f(f(x)) = -x $ for all $ x \in \beta $. By linearity, $ f(f(x)) = -x $ for all $ x \in \mathbb{R} $.

Note: This argument shows that there exist uncountably many $ \mathbb{Q} $-linear $ f: \mathbb{R} \to \mathbb{R} $ satisfying $ f \circ f = - \text{id}_{\mathbb{R}} $ (due to the uncountably many ways of forming $ \mathcal{P} $). As any $ f $ satisfying $ f \circ f = - \text{id}_{\mathbb{R}} $ cannot be continuous, it follows that any such $ f $ that is $ \mathbb{Q} $-linear cannot be Lebesgue-measurable (see these notes).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Note you really haven't used linearity -- just that $f(-x) = -f(x)$ and $f(0) = 0$. The same idea works with any partition of the positive numbers into ordered two-element subsets. $\endgroup$ – Hurkyl Feb 23 '13 at 23:38
  • $\begingroup$ That doesn't make sense to me - does $f(3)=2$ if you decide $b=2$, or $f(3)=9$ if $b=9$? $\endgroup$ – nbubis Feb 23 '13 at 23:39
  • $\begingroup$ @Hurkyl: I don’t really need full linearity; it is merely a convenient device. :) $\endgroup$ – Haskell Curry Feb 23 '13 at 23:41
  • 2
    $\begingroup$ @nbubis: No. You can’t produce an explicit Hamel basis of $ \mathbb{R} $ over $ \mathbb{Q} $ because the Axiom of Choice is required for its existence. Hence, choosing random points won’t work. $\endgroup$ – Haskell Curry Feb 23 '13 at 23:44
  • 2
    $\begingroup$ @Hurkyl: I’ve made explicit my goal of showing the existence of a $ \mathbb{Q} $-linear $ f $. $\endgroup$ – Haskell Curry Feb 23 '13 at 23:49
8
$\begingroup$

In the comments to @Hurkyl's excellent answer (which really hits the original question out of the park) the question was raised whether the solution must have infinitely many points of discontinuity. Hurkyl's proof only shows that $f$ is discontinuous, and although the solution he presents has infinitely many discontinuities (nothing wrong with that), I don't see "an easy corollary" that any answer must have an infinite number of discontinuities.

Here's a sketch of a proof that an infinite number of discontinuities are indeed needed. If I'm doing this the hard way and there is indeed a two-thought proof, I'm really curious to hear it!

$f$ must have an infinite number of discontinuities

The idea: we must arrange open line intervals on 4-cycles and boundary points on 4-cycles. For the former there must be $0 \pmod 4$ intervals, but for the latter there must $2 \pmod 4$ intervals; so we can't finitely have both at the same time.

Proof sketch:

  1. From @Hurkyl's proof: $f$ is a bijection, $f(0) = 0$, and every nonzero point is on a 4-cycle, i.e., $f^n(x) = x$ iff $n = {0\pmod 4}$.

  2. Let $D$ be the set of non-zero discontinuities of $f$. If $D$ is finite, $D\cup \{0\}$ separates $\mathbb{R}$ into a set $X$ of $|D| + 2$ open intervals (proof by induction).

  3. $f$ is piecewise continuous on these intervals, and must map $X$ onto $X$ and $D$ onto $D$. Proof: take a partition of $\mathbb{R}$ into the maximal continuous subsets (points or intervals) that make $f$ continuous; consider it as a topological space under the induced topology (i.e., the usual topology on each component); $f$ is a topological isomorphism (continuous bijection) and must map boundary points to boundary points.

  4. Every interval in $X$ must be on a 4-cycle. (proof: every interval $L \in X$ has non-varying sign. If $f(L) = L$ or $f^2(L) = L$, then for $x \in L, f^2(x)$ has the same sign as $x$. Hence $L$ cannot be on a 1- or 2-cycle.) Therefore there must be $0 \pmod 4$ intervals.

  5. $f$ is a bijection on the points of $D$, which must also form 4-cycles. It follows that $|D| = 0 \pmod 4$. By step 2, we have $2 \mod 4$ intervals.

In short, there's no way to partition the real line so that both the intervals and the boundary points form 4-cycles, unless $D$ is infinite. We conclude that all solutions must have infinitely many points of discontinuity. (The constructive proof given by @Hurkyl shows that solutions do exist.)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I downvoted both incorrect answers (although I'm expecting them to be amended, in which case I'll remove the downvote) $\endgroup$ – Ben Millwood Feb 24 '13 at 13:11
  • $\begingroup$ oops, that was dumb, thanks for catching it! I think now I was wrong about the number of discontinuities... revision coming up. $\endgroup$ – alexis Feb 24 '13 at 15:02
  • $\begingroup$ @Hendrik you're right, I can see that was exactly Kaz's function.... unfortunately for both of us! (PS. It's continuous at $\pm1$) $\endgroup$ – alexis Feb 24 '13 at 15:06
  • $\begingroup$ @alexis The function can't be continuous at $\pm 1$ because it changes sign. The limit is 1 from below and -1 from above at both points. $\endgroup$ – Kaz Feb 24 '13 at 19:11
  • $\begingroup$ ah, rats. I was thinking of an earlier permutation. $\endgroup$ – alexis Feb 24 '13 at 19:26
0
$\begingroup$

See $f(f(x))=-x$, Windmills, and Beyond in Volume 83 No. 1 Feb. 2010 of Mathematics Magazine. The question of this thread is probed in detail.

Thanks, Chad

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Can you summarize the results from your source? $\endgroup$ – Null Feb 10 '16 at 18:47

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.