Math Challenge - April 2020

  • Challenge
  • Thread starter fresh_42
  • Start date
  • Featured
  • #101
julian
Gold Member
584
105
Or decreasing



There don't have to be only finitely many intersections.


Why can't there be mixed concavity on each interval? The points where ##f(x)## changes concavity won't be the same points where ##f(x)=x## in general.


I don't see how you are using concavity for this.

@archaic has an almost complete solution.
Increasing because of claim 3 above.

Convex up implies ##r \equiv f(f(f(r))) > r## for ##p< r < q## from attached figure. Seems the only way to not have a contradiction is if ##f(x) = x##.
 

Attachments

Last edited:
  • #102
556
161
9. Let ##f:[0,1]\to[0,1]## be a continuous function such that ##f(f(f(x)))=x## for all ##x\in[0,1]##. Show that ##f## must be the identity function ##f(x)=x##. (IR)
Saying ##f(f(f(x)))=x## is like saying ##f(u\in[0,1])=x##. As such, ##f:[0,1]\to[0,1]## is bijective, and ##f(f(x))=f^{-1}(x)##. Repeating this step twice more, we get that:$$f^{-1}(f^{-1}(f^{-1}(x)))=x\Leftrightarrow f(f(f(x)))=f^{-1}(f^{-1}(f^{-1}(x)))$$
Since ##f## is a continuous bijection on ##[0,1]##, then it is either strictly decreasing or strictly increasing, the same for its inverse (which has the same direction of variation as ##f##).

Suppose that ##f## is not the identity function, then there exists ##a\in[0,1]## such that ##f(a)\neq f^{-1}(a)##. Let ##f(a)=b## and ##f^{-1}(a)=c##, then:$$f(f(f(a)))=f^{-1}(f^{-1}(f^{-1}(a)))\Leftrightarrow f(f(b))=f^{-1}(f^{-1}(c))$$
Since ##f(x)## and its inverse are bijections, then ##f(b)=d\neq f(a)=b## and ##f^{-1}(c)=e\neq f^{-1}(a)=c##.
We get:$$f(f(b))=f^{-1}(f^{-1}(c))\Leftrightarrow f(d)=f^{-1}(e)$$
Let us go back to our original equation and chose ##x=a##.
$$f(f(f(a)))=f(f(b))=f(d)=f^{-1}(e)\neq a=f^{-1}(c)$$
That ##f^{-1}(e)\neq a## is because the inverse of ##f## is a continuous bijection and ##a=f^{-1}(c)##.
Therefore, ##f(x)## must be the identity function.
 
Last edited:
  • #103
Infrared
Science Advisor
Gold Member
735
355
Increasing because of claim 3 above.

Convex up implies ##r \equiv f(f(f(r))) > r## for ##p< r < q## from attached figure. Seems the only way to not have a contradiction is if ##f(x) = x##.
What is "claim 3"?

I'm still not sure how you're using convexity. Just ##f## being increasing is enough to say that ##x<f(x)## implies ##f(x)<f(f(x))## etc.
 
  • #104
Infrared
Science Advisor
Gold Member
735
355
@archaic I didn't read your new argument carefully, but it doesn't look like it uses the continuity of ##f##, and so it cannot be right. A discontinuous counterexample is: Let ##f(x)=x## except when ##x=0,1/2,1##, for which we set ##f(0)=1/2, f(1/2)=1,## and ##f(1)=0##. Let me know if you still want me to read through it.

You had everything you needed in your old argument, just needed to clean some things up.
 
  • Informative
Likes archaic
  • #105
julian
Gold Member
584
105
What is "claim 3"?

I'm still not sure how you're using convexity. Just ##f## being increasing is enough to say that ##x<f(x)## implies ##f(x)<f(f(x))## etc.
@Lament's post #86, claim 3.

I think a combination of convex up in ##[p,q]## + no local maximum anywhere in the interior of ##[0,1]## is enough to say ##x<f(x)## implies ##f(x)<f(f(x))## etc.
 
  • #106
Infrared
Science Advisor
Gold Member
735
355
Okay, but it still has nothing to do with concavity- only monotonicity. If ##f## is strictly increasing, and ##x<f(x)## for some ##x##, then ##f(x)<f(f(x))## and ##f(f(x))<f(f(f(x)))=x##, which gives a contradiction. Similarly for the other cases.
 
  • #107
556
161
@archaic I didn't read your new argument carefully, but it doesn't look like it uses the continuity of ##f##, and so it cannot be right. A discontinuous counterexample is: Let ##f(x)=x## except when ##x=0,1/2,1##, for which we set ##f(0)=1/2, f(1/2)=1,## and ##f(1)=0##. Let me know if you still want me to read through it.

You had everything you needed in your old argument, just needed to clean some things up.
I added that it is a continuous bijection. This way you can't chose values as you did; you either chose them to be strictly increasing or strictly decreasing.
 
  • #108
Infrared
Science Advisor
Gold Member
735
355
Okay, you state that ##f## is strictly monotonic, but where do you use this fact in your proof? It still doesn't seem like your argument relies on it.
 
  • #109
556
161
Okay, you state that ##f## is strictly monotonic, but where do you use this fact in your proof? It still doesn't seem like your argument relies on it.
It maintains the order of the values so that you cannot chose discontinuities like you did.
 
  • #110
Infrared
Science Advisor
Gold Member
735
355
I understand that, but where in your argument do you use the fact that ##f## is monotonic?
 
  • Like
Likes archaic
  • #111
7
1
You have the right idea here, but the wording is a little off. Your argument that having a maxmum or a minimum contradicts the injectivity of ##f## is good, but concavity doesn't have much to do with it. Being "concave down" does not mean that a maximum is achieved on the interior (e.g. the square root function is concave down, but still strictly increasing on its domain). The last detail that you should check for this argument to be airtight is that a continuous function defined on an interval is either monotonic or has (interior) local extrema.
Yes, I think there is no reason to use concavity here. Here, I modified the Claim 2 according to your suggestion.

Claim 2: Since ##f(x)## is continuous bijection in the domain ##[0,1]##, so ##f(x)## is either strictly increasing or strictly decreasing within the interval.
Proof: WLOG, let us consider a small neighbourhood ##[a,b]## around a local extrema ##f(c)## such that ##a \lt c \lt b## (We ensure that each such interval contains only one such extrema). Obviously, ##f'(c)=0##. But, then by mean value theorem, ##\exists x_1, x_2## such that ##a \lt x_1 \lt c## and ##c \lt x_2 \lt b##, i.e. ##x_2 \gt x_1## but ##f(x_2)=f(x_1)##. This is a contradiction, since ##f(x)## is injective. So, a local extrema cannot lie in the interval (a,b). Hence, the local extrema must be at the end-points of the interval,i.e. either ##f(b) \gt f(a)## (strictly monotonically increasing) or ##f(b) \lt f(a)## (strictly monotonically decreasing). The monotonicity is strict because otherwise for some interval ##f(x)## is constant which contradicts the injectiveness of ##f(x)##. This result can be extended other adjacent intervals repeatedly.

It is evident that if ##f(x)## is monotonically increasing(or decreasing) in ##[a,b]##, then in the next interval ##[b,d]## (say), it cannot become monotonically decreasing(or increasing) because that would imply ##f'(x)## changed signs while we moved from one interval to the next. But that implies that ##f'(b)=0##. But our choice of intervals was such that each interval contains only such peak or valley, so a extrema cannot occur at ##x=b## or else we can again squeeze ##f(b)## within some interval and apply the same reasoning as above to conclude ##f'(b) \ne 0##.

So, ##f(x)## is either strictly monotonically increasing or strictly monotonically decreasing.

Why are the only three possible cases that f(x)=x,f(x)>xf(x)=x,f(x)>x, and f(x)<xf(x)<x (for all xx)? Why can't it be mixed?
Yes, of course, it can be mixed. My argument can be restated by just dividing the entire intervals into sub-intervals where either ##f(x)>x## or ##f(x)<x##, and applying the same argument over the various sub intervals over the entire interval.

I think that solves all the problems. Do I need to post the complete solution again?
 
  • #112
13,218
10,121
Do I need to post the complete solution again?
This would be very kind of you. It is meanwhile almost impossible to figure out in which post which argument contributes to a possible solution. It is generally best to quote the question and provide a consistent answer. Especially as there are quite a few members involved. E.g. someone used claim 3 of your attempt to argue about his, whereas claim 2 had a flaw. and it is impossible to figure out whether this affected claim 3 etc.
It's a mess.
 
  • Like
Likes Adesh
  • #113
735
191
This would be very kind of you. It is meanwhile almost impossible to figure out in which post which argument contributes to a possible solution. It is generally best to quote the question and provide a consistent answer. Especially as there are quite a few members involved. E.g. someone used claim 3 of your attempt to argue about his, whereas claim 2 had a flaw. and it is impossible to figure out whether this affected claim 3 etc.
It's a mess.
Just a general query, do you people have to search every time who has has answered your question? Because whenever we post a solution we don’t ping (we don’t put @ before anybody’s name) you, QQ or IR. I think it’s a very hard job to come here and search for who has solved your question.
 
  • #114
735
191
Question 9:

Regarding the monotonicity of ##f##, we are given that $$f \left (
f \left (
f(x) \right ) \right) =x $$ for all ## x \in [0,1]##. Now, either ##f## is an identity function or ##f## undo the effect of ##f \left ( f(x) \right)##, the latter condition implies that ##f \left ( f(x) \right) ## is inverse of ##f##. Hence, ##f## is inevrtible.

Any function which is invertible (in an interval) is also monotonic in that interval.
 
  • #115
7
1
9. Let ##f:[0,1]\to [0,1]## be a continuous function such that ##f(f(f(x)))=x## for all ##x\in [0,1]##. Show that ##f## must be the identity function ##f(x)=x.## (IR)
The question confines itself to ##f:[0,1]\to [0,1]## such that ##f(f(f(x)))=x## for all ##x\in [0,1] \Rightarrow f(x)=x##.

However, it can be proved for the general case,i.e. when ##f :\mathfrak {R}\rightarrow \mathfrak {R} ## such that ##f(f(f(x)))=x## for all ##x\in \mathfrak {R}##, ##f(x)=x.##

I prove the general case below :

Claim 1: ##f(x)## is a bijective mapping.
Proof: To prove ##f## is one-one, assume $$f(x)=f(y)$$
$$\Rightarrow f(f(x))=f(f(y))$$
$$\Rightarrow f(f(f(x)))=f(f(f(y)))$$
$$\Rightarrow x=y$$
So, ##f(x)## is injective.

Now, to prove ##f## is onto, ##\forall y \in \mathfrak {R},## ##\exists x \in \mathfrak {R}## such that ##y=f(x)##.
Evidently, if ##y\in \mathfrak {R} \text { then } y=f(f(f(y))) \Rightarrow x=f(f(y))\in \mathfrak {R}##
Thus, we can find ##s## such that $$y=f(x)$$
So, ##f(x)## is surjective.

Thus, ##f(x)## is a continuous bijection as the mapping ##f :\mathfrak {R}\rightarrow \mathfrak {R} ## is continuous.

Claim 2: Since ##f(x)## is continuous bijection in the domain ##[0,1]##, so ##f(x)## is either strictly increasing or strictly decreasing within the interval.

Proof: WLOG, let us consider a small neighbourhood ##[a,b]## around a local extrema ##f(c)## such that ##a \lt c \lt b## (We ensure that each such interval contains only one such extrema). Obviously, ##f'(c)=0##. But, then by mean value theorem, ##\exists x_1, x_2## such that ##a \lt x_1 \lt c## and ##c \lt x_2 \lt b##, i.e. ##x_2 \gt x_1## but ##f(x_2)=f(x_1)##. This is a contradiction, since ##f(x)## is injective. So, a local extrema cannot lie in the interval (a,b). Hence, the local extrema must be at the end-points of the interval,i.e. either ##f(b) \gt f(a)## (strictly monotonically increasing) or ##f(b) \lt f(a)## (strictly monotonically decreasing). The monotonicity is strict because otherwise for some interval ##f(x)## is constant which contradicts the injectiveness of ##f(x)##. This result can be extended other adjacent intervals repeatedly.

It is evident that if ##f(x)## is monotonically increasing(or decreasing) in ##[a,b]##, then in the next interval ##[b,d]## (say), it cannot become monotonically decreasing(or increasing) because that would imply ##f'(x)## changed signs while we moved from one interval to the next. But that implies that ##f'(b)=0##. But our choice of intervals was such that each interval contains only such peak or valley, so a extrema cannot occur at ##x=b## or else we can again squeeze ##f(b)## within some interval and apply the same reasoning as above to conclude ##f'(b) \ne 0##.


Claim 3: ##f(x)## is strictly increasing.
Proof: Assume on the contrary that f(x) is strictly decreasing, then for
$$y>x \Rightarrow f(y)<f(x)$$
$$\Rightarrow f(f(y))>f(f(x))$$
$$\Rightarrow f(f(f(y)))<f(f(f(x)))⇒y<x$$
a contradiction.
So, ##f(x)## is strictly increasing.

Claim 4: ##f(x)## satisfies the identity relation, i.e., ##f(x)=x##
Proof: Suppose ##f(x)≠x##, then either ##f(x)>x## or ##f(x)<x## for a certain interval.
As such, the entire interval can be subdivided on the basis of ##f(x)>x## or ##f(x)<x##, and for each such interval, we prove that it leads to a contradiction.

Therefore, if in a certain interval,
\begin{equation}f(x)>x\end{equation}
\begin{equation}\Rightarrow f(f(x))>f(x)\end{equation}
\begin{equation}\Rightarrow f(f(f(x)))>f(f(x))\end{equation}
\begin{equation}\Rightarrow x>f(f(x))\end{equation}
From (1), (2) and (4)
$$x>f(f(x))>f(x)>x$$
which is impossible.

Similarly, in another interval if
\begin{equation}f(x)<x\end{equation}
\begin{equation}\Rightarrow f(f(x))<f(x)\end{equation}
\begin{equation}\Rightarrow f(f(f(x)))<f(f(x))\end{equation}
\begin{equation}\Rightarrow x<f(f(x))\end{equation}
From (5), (6) and (8)
$$x<f(f(x))<f(x)<x$$
which is impossible.
Hence,
$$f(x)=x$$ Q.E.D.
 
  • #116
13,218
10,121
Just a general query, do you people have to search every time who has has answered your question?
If a new post is entered, the alert box says there is. And then we know who posted which question, and at least you guys normally quote the number of the question. The harder part is to edited the "solved by" part, because I link to the solution. Unless someone comes up with a full solution, this will be impossible for revolution no. 9. I need the id number of the post, and I only get it by pressing "reply". But that fills my edit box and if I'm waiting too long, it will be stored automatically, which is annoying for future posts. Unfortunately, the "give credit to" messages from my colleagues don't provide that url or id either. I normally look for a like that might indicate which post is meant to be the solution. So the edit might take some time, especially as I have to wait until the browser interpreted the MathJax code, for otherwise I risk that it will be destroyed.
 
  • Sad
Likes Adesh
  • #117
7
1
5. For coprime natural numbers ##n,m## show that
$$
m^{\varphi(n)}+n^{\varphi(m)} \equiv 1 \operatorname{mod} nm
$$
Edited after comments from @fresh_42

Fermat-Euler Theorem states that for every pair of co-prime integers ##a## and ##m##, it holds
$$a^{\varphi(m)} \equiv 1 (\operatorname{mod} m)$$ where ##{\varphi(m)}## is the Euler totient function.

Thus, since ##n,m## are co-prime, $$m^{\varphi(n)}+n^{\varphi(m)} \equiv 1+0 \equiv 1(\operatorname{mod} n)$$
& $$m^{\varphi(n)}+n^{\varphi(m)} \equiv 1+0 \equiv 1 (\operatorname{mod} m)$$
This suggests $$n|(m^{\varphi(n)}+n^{\varphi(m)}-1)$$ and $$m|(m^{\varphi(n)}+n^{\varphi(m)}-1)$$
Hence, (since if ##a|c## and ##b|c## then ##lcm(a,b)|c##. Now, ##gcd(a,b)=1 \Rightarrow lcm(a,b)=ab##. Hence, ##ab|c## ) $$mn|(m^{\varphi(n)}+n^{\varphi(m)}-1)$$
or equivalently, $$m^{\varphi(n)}+n^{\varphi(m)} \equiv 1 \operatorname{mod} nm$$.
 
Last edited:
  • #118
13,218
10,121
Fermat-Euler Theorem states that for every pair of co-prime integers ##a## and ##m##, it holds
$$a^{\varphi(m)} \equiv 1 (\operatorname{mod} m)$$ where ##{\varphi(m)}## is the Euler totient function.

Thus, since ##n,m## are co-prime, $$m^{\varphi(n)}+n^{\varphi(m)} \equiv 1 (\operatorname{mod} n)$$
Easier to read: ##m^{\varphi(n)}+n^{\varphi(m)} \equiv 1 + 0 \equiv 1 (\operatorname{mod} n)##
& $$m^{\varphi(n)}+n^{\varphi(m)} \equiv 1 (\operatorname{mod} m)$$
This suggests $$n|(m^{\varphi(n)}+n^{\varphi(m)}-1)$$ and $$m|(m^{\varphi(n)}+n^{\varphi(m)}-1)$$
Hence, (since if ##a|c## and ##b|c## such that ##gcd(a,b)=1##, then ##ab|c## ) $$
Here we use ##a|c## and ##b|c \Longrightarrow lcm(a,b)|c ## and ##lcm=ab## for ##gcd(a,b)=1##.
mn|(m^{\varphi(n)}+n^{\varphi(m)}-1)$$
or equivalently, $$m^{\varphi(n)}+n^{\varphi(m)} \equiv 1 \operatorname{mod} nm$$.
 
  • #119
Infrared
Science Advisor
Gold Member
735
355
The question confines itself to ##f:[0,1]\to [0,1]## such that ##f(f(f(x)))=x## for all ##x\in [0,1] \Rightarrow f(x)=x##.

However, it can be proved for the general case,i.e. when ##f :\mathfrak {R}\rightarrow \mathfrak {R} ## such that ##f(f(f(x)))=x## for all ##x\in \mathfrak {R}##, ##f(x)=x.##

I prove the general case below :

Thus, ##f(x)## is a continuous bijection as the mapping ##f :\mathfrak {R}\rightarrow \mathfrak {R} ## is continuous.

Claim 2: Since ##f(x)## is continuous bijection in the domain ##[0,1]##, so ##f(x)## is either strictly increasing or strictly decreasing within the interval.

Proof: WLOG, let us consider a small neighbourhood ##[a,b]## around a local extrema ##f(c)## such that ##a \lt c \lt b## (We ensure that each such interval contains only one such extrema). Obviously, ##f'(c)=0##. But, then by mean value theorem, ##\exists x_1, x_2## such that ##a \lt x_1 \lt c## and ##c \lt x_2 \lt b##, i.e. ##x_2 \gt x_1## but ##f(x_2)=f(x_1)## This is a contradiction, since ##f(x)## is injective.
It is not given that ##f## is differentiable. The function ##f(x)=|x|## is minimized ##0##, but is not differentiable there. Even for differentiable functions, I think your MVT argument is flawed- I can't tell how you're applying MVT, but it looks like you're claiming that any function whose derivative has a zero cannot be injective. The function ##f(x)=x^3## is a counterexample to that. It is also not clear how you can make each interval contain only one such extremum, since in general functions can change monotonicity infinitely often in a finite interval, like ##f(x)=x\sin(1/x), f(0)=0## near ##x=0##. Your original argument using the IVT was sound, aside from the concavity language.


Claim 4: ##f(x)## satisfies the identity relation, i.e., ##f(x)=x##
Proof: Suppose ##f(x)≠x##, then either ##f(x)>x## or ##f(x)<x## for a certain interval.
As such, the entire interval can be subdivided on the basis of ##f(x)>x## or ##f(x)<x##, and for each such interval, we prove that it leads to a contradiction.
...
As before, dividing into intervals adds some confusion. Here the problem is less severe because the set where ##x\neq f(x)## is open, so it must contain an interval if it's nonempty, but it's still easier to avoid it: suppose for contradiction that ##f(x)\neq x## for some ##x##. Then either ##x<f(x)## or ##x>f(x)##, and apply your argument to the point ##x##, not to an entire interval.


Any function which is invertible (in an interval) is also monotonic in that interval.
Any continuous invertible function, yes. This is the content of @Lament's claim 2.
 
  • #120
735
191
Just a general query, do you people have to search every time who has has answered your question? Because whenever we post a solution we don’t ping (we don’t put @ before anybody’s name) you, QQ or IR. I think it’s a very hard job to come here and search for who has solved your question.
Any continuous invertible function, yes. This is the content of @Lament's claim 2.
I can give an informal proof of why an invertible function would be monotonic.
PROOF: Function is invertible implies it is injective, that is it passes horizontal line test for all horizontal lines. That is our function passes every horizontal line just once and this is possible only if it keeps on increasing/decreasing, if it were to change it’s nature, that is from increasing to decreasing (or decreasing to increasing) it would surely intersect at least one horizontal line at least twice and hence will not be injective

Was my proof of “##f## is invertible” right?
 
  • #121
Infrared
Science Advisor
Gold Member
735
355
I can give an informal proof of why an invertible function would be monotonic.
PROOF: Function is invertible implies it is injective, that is it passes horizontal line test for all horizontal lines. That is our function passes every horizontal line just once and this is possible only if it keeps on increasing/decreasing, if it were to change it’s nature, that is from increasing to decreasing (or decreasing to increasing) it would surely intersect at least one horizontal line at least twice and hence will not be injective
The claim "an invertible function would be monotonic" is false. A counterexample is ##f:[0,1]\to [0,1]## defined by ##f(x)=x## for ##x\in (0,1)## and ##f(0)=1, f(1)=0##. Continuity is necessary. You don't mention continuity anywhere in your explanation, so I don't think it can be right.

Was my proof of “##f## is invertible” right?
A bit wordy. I think it's fine to just say "##f## is invertible because ##f\circ f## is an inverse function to ##f##."
 
  • #122
7
1
It is not given that ##f## is differentiable. The function ##f(x)=|x|## is minimized ##0##, but is not differentiable there.
True, I overlooked that. I took a stationary point for defining the extrema.
Even for differentiable functions, I think your MVT argument is flawed- I can't tell how you're applying MVT, but it looks like you're claiming that any function whose derivative has a zero cannot be injective. The function ##f(x)=x^3## is a counterexample to that.
It is supposed to be IVT (typographical error on my part). What I meant to do was to take an interval around the extrema, if it exists. And then prove that since any horizontal line in between the range of the interval will intersect the curve at two points at least, by injectiveness of ##f## this is impossible and the regional extrema must only occur at the end-points of the interval making the function either strictly monotonically increasing or decreasing.
I wouldn't consider ##f(x)=x^3## at ##x=0## because it is not an extremum even though it is a stationary point.
It is also not clear how you can make each interval contain only one such extremum, since in general functions can change monotonicity infinitely often in a finite interval, like ##f(x)=x\sin(1/x), f(0)=0## near ##x=0##.
Well, is we take an extremum then in a small neighbourhood of it, it will only contain that extrema. Yes, it can be done away with. Even if we consider any arbitrary interval and it contains an extremum, then again with IVT we can prove that no local extrema are present within the interval. I thought of having an interval with only one such extremum because then we can eventually conclude it to be monotonically increasing within each such interval.
Also from your argument ##f(x)=x\sin(1/x), f(0)=0## near ##x=0##. I didn't think about badly behaving functions.

As before, dividing into intervals adds some confusion. Here the problem is less severe because the set where ##x\neq f(x)## is open, so it must contain an interval if it's non-empty, but it's still easier to avoid it: suppose for contradiction that ##f(x)\neq x## for some ##x##. Then either ##x<f(x)## or ##x>f(x)##, and apply your argument to the point ##x##, not to an entire interval.
I understand considering point by point the proof is easier but I do not understand why the interval argument raises confusion. Because if ##f(x)\neq x## for some x, then in a small neighbourhood around the point the same must hold true (it is strictly monotonic after all).

Am I still missing something?
 
  • #123
735
191
Question 9
We are given that ##f## is a continuous function and satisfies $$ f (f ( f(x) ) ) =x$$ for all ##x \in [0,1]##. Since, ##f## undo the effect of ##f \circ f## therefore ##f \circ f## is inverse of ##f##. Hence, ##f## is an invertible function.
Any continuous invertible function is always monotonic (an informal proof is given in post #120).

Let’s assume that ##f(x) \neq x## for some sub-interval, that is ##f## is not an identity function. Now, in that sub-interval ##f## is either greater or smaller than ##x## and also monotonically continuous (increasing/ decreasing).

Let’s assume ##f## is greater than ##x## in that sub-interval and is monotonically increasing in that sub-interval, $$ x \lt f(x) \\ f(x) \lt f (f(x)) \implies x \lt f ( f(x)) ~~~~~(1)\\ f(f(x)) \lt f ( f( f (x) ) ) \implies f(f(x)) \lt x$$ the last inequality above contradicts with inequality (1). Hence, our assumption was wrong.

We can show similar contradictions for other cases: ##f## is monotonically decreasing, ##f## is less than ##x## and more.

Let’s do it for ##f## being less than ##x## (in a some sub-interval) and monotonically decreasing. $$ f(x) \lt x \\
f ( f(x)) \gt f(x) \\
f( f ( f (x) ) ) \lt f ( f (x) ) \\
x \lt f (f (x) ) \\
f(x) \gt f ( f ( f (x) ) ) \implies f(x) \gt x $$
The last inequality above contradicts with our assumption that ##f(x)## is less than ##x## in the considered sub-interval.

These contradictions are occurring because our assumption of ##f## being not an identity function was false.

Hence, ##f## must be an identity function .
 
  • #124
Infrared
Science Advisor
Gold Member
735
355
I wouldn't consider ##f(x)=x^3## at ##x=0## because it is not an extremum even though it is a stationary point.
Yes, this is my point. To me, it looked like your argument was roughly:

"##f## has a local extremum" ##\implies## "##f'(c)=0## for some ##c##" ##\implies## "##f## is not injective"

But ##f(x)=x^3## is a counterexample to the second implication. If this was not the shape of your argument, could you clarify how you were trying to use the fact that ##f'(c)=0##?

Well, is we take an extremum then in a small neighbourhood of it, it will only contain that extrema. Yes, it can be done away with. Even if we consider any arbitrary interval and it contains an extremum, then again with IVT we can prove that no local extrema are present within the interval. I thought of having an interval with only one such extremum because then we can eventually conclude it to be monotonically increasing within each such interval.
Also from your argument ##f(x)=x\sin(1/x), f(0)=0## near ##x=0##. I didn't think about badly behaving functions.
I think my function ##f(x)=x\sin(1/x)## has local extrema in every small interval ##(0,\varepsilon)##, so you can't always make these intervals. But anyway, there is no need to try to make these intervals.

I understand considering point by point the proof is easier but I do not understand why the interval argument raises confusion. Because if ##f(x)\neq x## for some x, then in a small neighbourhood around the point the same must hold true (it is strictly monotonic after all).

Am I still missing something?
It is okay, but the reasoning shouldn't involve monotonicity- only continuity. The function ##x\mapsto f(x)-x## is continuous, so if it is negative (or positive) at a point, it is negative (or positive) in a neighborhood of the point. In general, it's better to avoid making diversions like this that aren't necessary for the proof.
 
  • #125
556
161
9. Let ##f:[0,1]\to [0,1]## be a continuous function such that ##f(f(f(x)))=x## for all ##x\in [0,1]##. Show that ##f## must be the identity function ##f(x)=x.## (IR)
Saying ##f(f(f(x)))=x## is like saying ##f(u\in[0,1])=x##. As such, ##f:[0,1]\to[0,1]## is bijective.
Since ##f## is a continuous bijection on ##[0,1]##, then it is either strictly decreasing or strictly increasing, the same for its inverse (which has the same direction of variation as ##f##).

Proving ##\forall x\in [0,1],\,f(f(f(x)))=x\implies f(x)=x## is the same as proving ##f(x)\neq x\implies\exists x\in [0,1]\,|\,f(f(f(x)))\neq x##.

Suppose that ##f(x)\neq x##, i.e, there exists a real number in ##[0,1]## such that its image by ##f## is different than itself. In the following, by ##a## I mean this real.
All inequalities will be strict because ##f## is a continuous bijection.
Suppose that ##f(x)## is strictly increasing, and let there be ##a\in[0,1]## such that ##f(a)=b\neq a##, then:
If ##b<a##, then ##f(b)=c<f(a)=b##, and thus ##f(c)<f(a)=b##. It follows that ##f(f(f(a)))<b<a##.​
If ##b>a##, then ##f(b)=c>f(a)=b##, and thus ##f(c)>f(a)=b##. It follows that ##f(f(f(a)))>b>a##.​
I have proved that if ##f(x)## is strictly increasing, then ##\exists x\in [0,1]\,|\,f(f(f(x)))\neq x##.

Suppose that ##f(x)## is strictly decreasing, and let there be ##a\in[0,1]## such that ##f(a)=b\neq a##, then:
If ##b<a##, then ##f(b)=c>f(a)=b##.​
If ##b<c<a##, then ##f(b)=c>f(c)>f(a)=b##. It follows that ##f(f(f(a)))>f(a)##​
If ##a<c##, then ##f(a)=b>f(c)##. It follows that ##f(f(f(a)))<f(a)##​
If ##b>a##, then ##f(b)=c<f(a)=b##.​
If ##b>c>a##, then ##f(b)=c<f(c)<f(a)=b##. It follows that ##f(f(f(a)))<f(a)##​
If ##a>c##, then ##f(a)=b<f(c)##. It follows that ##f(f(f(a)))>f(a)##​
I have proved that if ##f(x)## is strictly decreasing, then ##\exists x\in [0,1]\,|\,f(f(f(x)))\neq x##.

I have proved that ##f(x)\neq x\implies\exists x\in [0,1]\,|\,f(f(f(x)))\neq x##!
 
Last edited:

Related Threads on Math Challenge - April 2020

Replies
77
Views
5K
Replies
107
Views
8K
Replies
156
Views
4K
Replies
64
Views
7K
Replies
137
Views
4K
  • Last Post
3
Replies
61
Views
3K
Replies
83
Views
13K
Replies
51
Views
4K
Replies
18
Views
2K
  • Last Post
Replies
2
Views
3K
Top