Mixing
Prove f has a fixed point if it is increasing but not necessarily continuous
$begingroup$
Suppose $f : [0, 1] rightarrow [0, 1]$ is increasing (but not necessarily continuous).
Show that there is a number $x in [0, 1]$ with $f(x) = x$.
(Hint: You can’t apply the IVT directly because the function need not be
continuous. Draw a picture and try to copy the proof of the Intermediate
Value Theorem.)
I don't understand how copying the IVT and connecting it to my graph would help me prove this since the IVT has nothing to do with increasing functions(or am I wrong about this?)
real-analysis functional-analysis analysis
edited Jan 28 at 6:08
Mark
2,09232450
asked Jan 27 at 15:42
The Poor JewThe Poor Jew
566
$endgroup$
|
show 1 more comment
$begingroup$
Suppose $f : [0, 1] rightarrow [0, 1]$ is increasing (but not necessarily continuous).
Show that there is a number $x in [0, 1]$ with $f(x) = x$.
(Hint: You can’t apply the IVT directly because the function need not be
continuous. Draw a picture and try to copy the proof of the Intermediate
Value Theorem.)
I don't understand how copying the IVT and connecting it to my graph would help me prove this since the IVT has nothing to do with increasing functions(or am I wrong about this?)
real-analysis functional-analysis analysis
edited Jan 28 at 6:08
Mark
2,09232450
asked Jan 27 at 15:42
The Poor JewThe Poor Jew
566
$endgroup$
$begingroup$
What have you tried so far?
$endgroup$
– Matteo
Jan 27 at 15:44
$begingroup$
I tried copying the IVT but could not connect it with an increasing function
$endgroup$
– The Poor Jew
Jan 27 at 15:46
1
$begingroup$
I think you can apply squeeze theorem after doing binary search
$endgroup$
– Mark
Jan 27 at 15:47
$begingroup$
For the function to be increasing, $[0,1]$ being it's range, isn't it necessary to have $f(0) = 0$? Forgive me if I'm mistaken.
$endgroup$
– Matteo
Jan 27 at 15:54
$begingroup$
@Matteo The function need not be surjective. It could be the constant function equal to $1$, for all we know.
$endgroup$
– Clement C.
Jan 27 at 16:10
|
show 1 more comment
$begingroup$
Suppose $f : [0, 1] rightarrow [0, 1]$ is increasing (but not necessarily continuous).
Show that there is a number $x in [0, 1]$ with $f(x) = x$.
(Hint: You can’t apply the IVT directly because the function need not be
continuous. Draw a picture and try to copy the proof of the Intermediate
Value Theorem.)
I don't understand how copying the IVT and connecting it to my graph would help me prove this since the IVT has nothing to do with increasing functions(or am I wrong about this?)
real-analysis functional-analysis analysis
edited Jan 28 at 6:08
Mark
2,09232450
asked Jan 27 at 15:42
The Poor JewThe Poor Jew
566
$endgroup$
Suppose $f : [0, 1] rightarrow [0, 1]$ is increasing (but not necessarily continuous).
Show that there is a number $x in [0, 1]$ with $f(x) = x$.
(Hint: You can’t apply the IVT directly because the function need not be
continuous. Draw a picture and try to copy the proof of the Intermediate
Value Theorem.)
I don't understand how copying the IVT and connecting it to my graph would help me prove this since the IVT has nothing to do with increasing functions(or am I wrong about this?)
real-analysis functional-analysis analysis
real-analysis functional-analysis analysis
edited Jan 28 at 6:08
Mark
2,09232450
asked Jan 27 at 15:42
The Poor JewThe Poor Jew
566
edited Jan 28 at 6:08
Mark
2,09232450
asked Jan 27 at 15:42
The Poor JewThe Poor Jew
566
edited Jan 28 at 6:08
Mark
2,09232450
edited Jan 28 at 6:08
Mark
2,09232450
edited Jan 28 at 6:08
Mark
2,09232450
2,09232450
asked Jan 27 at 15:42
The Poor JewThe Poor Jew
566
asked Jan 27 at 15:42
The Poor JewThe Poor Jew
566
asked Jan 27 at 15:42
The Poor JewThe Poor Jew
566
566
$begingroup$
What have you tried so far?
$endgroup$
– Matteo
Jan 27 at 15:44
$begingroup$
I tried copying the IVT but could not connect it with an increasing function
$endgroup$
– The Poor Jew
Jan 27 at 15:46
1
$begingroup$
I think you can apply squeeze theorem after doing binary search
$endgroup$
– Mark
Jan 27 at 15:47
$begingroup$
For the function to be increasing, $[0,1]$ being it's range, isn't it necessary to have $f(0) = 0$? Forgive me if I'm mistaken.
$endgroup$
– Matteo
Jan 27 at 15:54
$begingroup$
@Matteo The function need not be surjective. It could be the constant function equal to $1$, for all we know.
$endgroup$
– Clement C.
Jan 27 at 16:10
|
show 1 more comment
$begingroup$
What have you tried so far?
$endgroup$
– Matteo
Jan 27 at 15:44
$begingroup$
I tried copying the IVT but could not connect it with an increasing function
$endgroup$
– The Poor Jew
Jan 27 at 15:46
1
$begingroup$
I think you can apply squeeze theorem after doing binary search
$endgroup$
– Mark
Jan 27 at 15:47
$begingroup$
For the function to be increasing, $[0,1]$ being it's range, isn't it necessary to have $f(0) = 0$? Forgive me if I'm mistaken.
$endgroup$
– Matteo
Jan 27 at 15:54
$begingroup$
@Matteo The function need not be surjective. It could be the constant function equal to $1$, for all we know.
$endgroup$
– Clement C.
Jan 27 at 16:10
$begingroup$
What have you tried so far?
$endgroup$
– Matteo
Jan 27 at 15:44
$begingroup$
What have you tried so far?
$endgroup$
– Matteo
Jan 27 at 15:44
$begingroup$
I tried copying the IVT but could not connect it with an increasing function
$endgroup$
– The Poor Jew
Jan 27 at 15:46
$begingroup$
I tried copying the IVT but could not connect it with an increasing function
$endgroup$
– The Poor Jew
Jan 27 at 15:46
1
1
$begingroup$
I think you can apply squeeze theorem after doing binary search
$endgroup$
– Mark
Jan 27 at 15:47
$begingroup$
I think you can apply squeeze theorem after doing binary search
$endgroup$
– Mark
Jan 27 at 15:47
$begingroup$
For the function to be increasing, $[0,1]$ being it's range, isn't it necessary to have $f(0) = 0$? Forgive me if I'm mistaken.
$endgroup$
– Matteo
Jan 27 at 15:54
$begingroup$
For the function to be increasing, $[0,1]$ being it's range, isn't it necessary to have $f(0) = 0$? Forgive me if I'm mistaken.
$endgroup$
– Matteo
Jan 27 at 15:54
$begingroup$
@Matteo The function need not be surjective. It could be the constant function equal to $1$, for all we know.
$endgroup$
– Clement C.
Jan 27 at 16:10
$begingroup$
@Matteo The function need not be surjective. It could be the constant function equal to $1$, for all we know.
$endgroup$
– Clement C.
Jan 27 at 16:10
|
show 1 more comment
3 Answers
3
active
oldest
votes
$begingroup$
Hint
What about $$c=inf{xin [0,1]mid f(x)leq x}$$ if it exist ?
answered Jan 27 at 15:45
SurbSurb
38.4k94478
$endgroup$
1
$begingroup$
This approach is elucidated here en.wikipedia.org/wiki/Knaster–Tarski_theorem and is actually pretty interesting in that it doesn't require the use of any real analysis.
$endgroup$
– Mark
Jan 28 at 6:05
add a comment |
$begingroup$
Similar to Mark's solution. It makes use of Completeness principle.
If $f(0) = 0$, then $x = 0$; if $f(1) = 1$, then $x = 1$; otherwise let $a_0=f(0)$, $b_0=f(1)$, and, for $n=1,2,dots$ repeat the following.
(1) Let $Delta_n =frac{a_{n-1}+b_{n-1}}{2}$,
(2) If $fleft(Delta_nright) = Delta_n$, then $x = Delta_n$ and we are done.
(3) If $fleft(Delta_nright) < Delta_n$, set $a_n = a_{n-1}$, $b_n = Delta_n$.
(4) If $fleft(Delta_nright) > Delta_n$, set $a_n = Delta_n$, $b_n = b_{n-1}$.
This leads to the construction of a monotonically increasing sequence $left(a_nright)_{nin mathbb Z^+}$ and a monotonically decreasing sequence $left(b_nright)_{nin mathbb Z^+}$, such that
$$0=a_0 leq a_1 leq cdots leq a_n cdots leq b_n cdots leq b_1 leq b_0=1,$$
with
begin{equation}
f(b_n)<b_n,tag{1}label{eq:down}
end{equation}
and
begin{equation}
f(a_n)>a_n.tag{2}label{eq:up}
end{equation}
Furthermore we have
begin{equation}b_n - a_n leq frac{1}{2^n}.tag{3}label{eq:diff}end{equation}
So, by boundedness and monotonicity the two sequences converge (here Completeness comes into play), and by eqref{eq:diff}, they converge to the same number $alpha in [0,1]$.
Suppose now $f(alpha) > alpha$. Then, for sufficiently large $n$,
$$alpha leq b_n < f(alpha),$$
which, together with eqref{eq:down} gives
$$f(b_n) < b_n < f(alpha),$$
contradicting monotonicity of $f$. Similarly, if $f(alpha) < alpha$, then, for sufficiently large $n$,
$$f(alpha) < a_n leq alpha,$$
so that, using eqref{eq:up},
the inequality
$$ f(a_n) > a_n > f(alpha)$$
leads again to a contradiction. Thus, it must be $f(alpha) = alpha$.
Note
Completeness is necessary for the statement to hold true. As a counterexample consider the function $f: [0,1]cap Bbb Q rightarrow [0,1]cap Bbb Q$
$$f(x) = -frac{1}{x-3}.$$
This function is continuous and strictly increasing in its domain, but there is no point in the domain in which $f(x) = x$.
answered Jan 28 at 15:30
MatteoMatteo
1,242313
$endgroup$
add a comment |
$begingroup$
Start by defining the sequences $l_n, u_n$, where the variable names stand for "lower" and "upper". And let $x_n equiv (l_n + u_n)/2$.
$l_0 equiv 0, u_0 equiv 1$
Now inductively define $l_k, u_k$:
If $f(x_{k-1}) lt x_{k-1}$, define $u_k equiv x_{k-1}, l_k equiv l_{k-1}$ (shift the upper bound down).
If $f(x_{k-1}) > x_{k-1}$, define $u_k equiv u_{k-1}, l_k equiv x_{k-1}$ (shift the lower bound up)
(And if $f(x_{k-1}) = x_{k-1}$ we are done, so we can ignore this case).
This part is kind of like the intermediate value theorem, where we keep narrowing the search for our target.
The set $f([l_k, u_k])$ is in the square $[l_k, u_k]times[l_k, u_k]$. (Using induction and $f$ is increasing. It's kind of clear if you draw a picture.)
For any $k$, the square $[l_k, u_k]times[l_k, u_k]$ intersects the diagonal line ${ (x, x )}$ since it contains $(l_k, l_k)$, so if the sequence of nested squares converges, it converges to a point on the diagonal.
But it does converge, since $[l_k, u_k]$ converges to some singleton set ${ c }$.
Putting it all together, $forall k, f(c) in f([l_k, u_k]) subset [l_k, u_k]times[l_k, u_k]$.
$ f([c]) in cap_k [l_k, u_k]times[l_k, u_k]$.
$ f([c]) in { (c, c) }$.
$ f(c) = c $.
answered Jan 27 at 17:12
MarkMark
2,09232450
$endgroup$
$begingroup$
I read your comment on @Surb answer. Of course some "real analysis" must be necessary. For if the domain is not complete (an interval), then the statement isn't true anymore. I added a counterexample in my answer. Do you agree?
$endgroup$
– Matteo
Jan 28 at 19:12
$begingroup$
@Matteo yes the only requirement is that the set in question is a complete lattice. After after that, the tarski fixed point theorem applies a purely logical argument.
$endgroup$
– Mark
Jan 29 at 3:30
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3089721%2fprove-f-has-a-fixed-point-if-it-is-increasing-but-not-necessarily-continuous%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Hint
What about $$c=inf{xin [0,1]mid f(x)leq x}$$ if it exist ?
answered Jan 27 at 15:45
SurbSurb
38.4k94478
$endgroup$
1
$begingroup$
This approach is elucidated here en.wikipedia.org/wiki/Knaster–Tarski_theorem and is actually pretty interesting in that it doesn't require the use of any real analysis.
$endgroup$
– Mark
Jan 28 at 6:05
add a comment |
$begingroup$
Hint
What about $$c=inf{xin [0,1]mid f(x)leq x}$$ if it exist ?
answered Jan 27 at 15:45
SurbSurb
38.4k94478
$endgroup$
1
$begingroup$
This approach is elucidated here en.wikipedia.org/wiki/Knaster–Tarski_theorem and is actually pretty interesting in that it doesn't require the use of any real analysis.
$endgroup$
– Mark
Jan 28 at 6:05
add a comment |
$begingroup$
Hint
What about $$c=inf{xin [0,1]mid f(x)leq x}$$ if it exist ?
answered Jan 27 at 15:45
SurbSurb
38.4k94478
$endgroup$
Hint
What about $$c=inf{xin [0,1]mid f(x)leq x}$$ if it exist ?
answered Jan 27 at 15:45
SurbSurb
38.4k94478
answered Jan 27 at 15:45
SurbSurb
38.4k94478
answered Jan 27 at 15:45
SurbSurb
38.4k94478
answered Jan 27 at 15:45
SurbSurb
38.4k94478
38.4k94478
1
$begingroup$
This approach is elucidated here en.wikipedia.org/wiki/Knaster–Tarski_theorem and is actually pretty interesting in that it doesn't require the use of any real analysis.
$endgroup$
– Mark
Jan 28 at 6:05
add a comment |
1
$begingroup$
This approach is elucidated here en.wikipedia.org/wiki/Knaster–Tarski_theorem and is actually pretty interesting in that it doesn't require the use of any real analysis.
$endgroup$
– Mark
Jan 28 at 6:05
1
1
$begingroup$
This approach is elucidated here en.wikipedia.org/wiki/Knaster–Tarski_theorem and is actually pretty interesting in that it doesn't require the use of any real analysis.
$endgroup$
– Mark
Jan 28 at 6:05
$begingroup$
This approach is elucidated here en.wikipedia.org/wiki/Knaster–Tarski_theorem and is actually pretty interesting in that it doesn't require the use of any real analysis.
$endgroup$
– Mark
Jan 28 at 6:05
add a comment |
$begingroup$
Similar to Mark's solution. It makes use of Completeness principle.
If $f(0) = 0$, then $x = 0$; if $f(1) = 1$, then $x = 1$; otherwise let $a_0=f(0)$, $b_0=f(1)$, and, for $n=1,2,dots$ repeat the following.
(1) Let $Delta_n =frac{a_{n-1}+b_{n-1}}{2}$,
(2) If $fleft(Delta_nright) = Delta_n$, then $x = Delta_n$ and we are done.
(3) If $fleft(Delta_nright) < Delta_n$, set $a_n = a_{n-1}$, $b_n = Delta_n$.
(4) If $fleft(Delta_nright) > Delta_n$, set $a_n = Delta_n$, $b_n = b_{n-1}$.
This leads to the construction of a monotonically increasing sequence $left(a_nright)_{nin mathbb Z^+}$ and a monotonically decreasing sequence $left(b_nright)_{nin mathbb Z^+}$, such that
$$0=a_0 leq a_1 leq cdots leq a_n cdots leq b_n cdots leq b_1 leq b_0=1,$$
with
begin{equation}
f(b_n)<b_n,tag{1}label{eq:down}
end{equation}
and
begin{equation}
f(a_n)>a_n.tag{2}label{eq:up}
end{equation}
Furthermore we have
begin{equation}b_n - a_n leq frac{1}{2^n}.tag{3}label{eq:diff}end{equation}
So, by boundedness and monotonicity the two sequences converge (here Completeness comes into play), and by eqref{eq:diff}, they converge to the same number $alpha in [0,1]$.
Suppose now $f(alpha) > alpha$. Then, for sufficiently large $n$,
$$alpha leq b_n < f(alpha),$$
which, together with eqref{eq:down} gives
$$f(b_n) < b_n < f(alpha),$$
contradicting monotonicity of $f$. Similarly, if $f(alpha) < alpha$, then, for sufficiently large $n$,
$$f(alpha) < a_n leq alpha,$$
so that, using eqref{eq:up},
the inequality
$$ f(a_n) > a_n > f(alpha)$$
leads again to a contradiction. Thus, it must be $f(alpha) = alpha$.
Note
Completeness is necessary for the statement to hold true. As a counterexample consider the function $f: [0,1]cap Bbb Q rightarrow [0,1]cap Bbb Q$
$$f(x) = -frac{1}{x-3}.$$
This function is continuous and strictly increasing in its domain, but there is no point in the domain in which $f(x) = x$.
answered Jan 28 at 15:30
MatteoMatteo
1,242313
$endgroup$
add a comment |
$begingroup$
Similar to Mark's solution. It makes use of Completeness principle.
If $f(0) = 0$, then $x = 0$; if $f(1) = 1$, then $x = 1$; otherwise let $a_0=f(0)$, $b_0=f(1)$, and, for $n=1,2,dots$ repeat the following.
(1) Let $Delta_n =frac{a_{n-1}+b_{n-1}}{2}$,
(2) If $fleft(Delta_nright) = Delta_n$, then $x = Delta_n$ and we are done.
(3) If $fleft(Delta_nright) < Delta_n$, set $a_n = a_{n-1}$, $b_n = Delta_n$.
(4) If $fleft(Delta_nright) > Delta_n$, set $a_n = Delta_n$, $b_n = b_{n-1}$.
This leads to the construction of a monotonically increasing sequence $left(a_nright)_{nin mathbb Z^+}$ and a monotonically decreasing sequence $left(b_nright)_{nin mathbb Z^+}$, such that
$$0=a_0 leq a_1 leq cdots leq a_n cdots leq b_n cdots leq b_1 leq b_0=1,$$
with
begin{equation}
f(b_n)<b_n,tag{1}label{eq:down}
end{equation}
and
begin{equation}
f(a_n)>a_n.tag{2}label{eq:up}
end{equation}
Furthermore we have
begin{equation}b_n - a_n leq frac{1}{2^n}.tag{3}label{eq:diff}end{equation}
So, by boundedness and monotonicity the two sequences converge (here Completeness comes into play), and by eqref{eq:diff}, they converge to the same number $alpha in [0,1]$.
Suppose now $f(alpha) > alpha$. Then, for sufficiently large $n$,
$$alpha leq b_n < f(alpha),$$
which, together with eqref{eq:down} gives
$$f(b_n) < b_n < f(alpha),$$
contradicting monotonicity of $f$. Similarly, if $f(alpha) < alpha$, then, for sufficiently large $n$,
$$f(alpha) < a_n leq alpha,$$
so that, using eqref{eq:up},
the inequality
$$ f(a_n) > a_n > f(alpha)$$
leads again to a contradiction. Thus, it must be $f(alpha) = alpha$.
Note
Completeness is necessary for the statement to hold true. As a counterexample consider the function $f: [0,1]cap Bbb Q rightarrow [0,1]cap Bbb Q$
$$f(x) = -frac{1}{x-3}.$$
This function is continuous and strictly increasing in its domain, but there is no point in the domain in which $f(x) = x$.
answered Jan 28 at 15:30
MatteoMatteo
1,242313
$endgroup$
add a comment |
$begingroup$
Similar to Mark's solution. It makes use of Completeness principle.
If $f(0) = 0$, then $x = 0$; if $f(1) = 1$, then $x = 1$; otherwise let $a_0=f(0)$, $b_0=f(1)$, and, for $n=1,2,dots$ repeat the following.
(1) Let $Delta_n =frac{a_{n-1}+b_{n-1}}{2}$,
(2) If $fleft(Delta_nright) = Delta_n$, then $x = Delta_n$ and we are done.
(3) If $fleft(Delta_nright) < Delta_n$, set $a_n = a_{n-1}$, $b_n = Delta_n$.
(4) If $fleft(Delta_nright) > Delta_n$, set $a_n = Delta_n$, $b_n = b_{n-1}$.
This leads to the construction of a monotonically increasing sequence $left(a_nright)_{nin mathbb Z^+}$ and a monotonically decreasing sequence $left(b_nright)_{nin mathbb Z^+}$, such that
$$0=a_0 leq a_1 leq cdots leq a_n cdots leq b_n cdots leq b_1 leq b_0=1,$$
with
begin{equation}
f(b_n)<b_n,tag{1}label{eq:down}
end{equation}
and
begin{equation}
f(a_n)>a_n.tag{2}label{eq:up}
end{equation}
Furthermore we have
begin{equation}b_n - a_n leq frac{1}{2^n}.tag{3}label{eq:diff}end{equation}
So, by boundedness and monotonicity the two sequences converge (here Completeness comes into play), and by eqref{eq:diff}, they converge to the same number $alpha in [0,1]$.
Suppose now $f(alpha) > alpha$. Then, for sufficiently large $n$,
$$alpha leq b_n < f(alpha),$$
which, together with eqref{eq:down} gives
$$f(b_n) < b_n < f(alpha),$$
contradicting monotonicity of $f$. Similarly, if $f(alpha) < alpha$, then, for sufficiently large $n$,
$$f(alpha) < a_n leq alpha,$$
so that, using eqref{eq:up},
the inequality
$$ f(a_n) > a_n > f(alpha)$$
leads again to a contradiction. Thus, it must be $f(alpha) = alpha$.
Note
Completeness is necessary for the statement to hold true. As a counterexample consider the function $f: [0,1]cap Bbb Q rightarrow [0,1]cap Bbb Q$
$$f(x) = -frac{1}{x-3}.$$
This function is continuous and strictly increasing in its domain, but there is no point in the domain in which $f(x) = x$.
answered Jan 28 at 15:30
MatteoMatteo
1,242313
$endgroup$
Similar to Mark's solution. It makes use of Completeness principle.
If $f(0) = 0$, then $x = 0$; if $f(1) = 1$, then $x = 1$; otherwise let $a_0=f(0)$, $b_0=f(1)$, and, for $n=1,2,dots$ repeat the following.
(1) Let $Delta_n =frac{a_{n-1}+b_{n-1}}{2}$,
(2) If $fleft(Delta_nright) = Delta_n$, then $x = Delta_n$ and we are done.
(3) If $fleft(Delta_nright) < Delta_n$, set $a_n = a_{n-1}$, $b_n = Delta_n$.
(4) If $fleft(Delta_nright) > Delta_n$, set $a_n = Delta_n$, $b_n = b_{n-1}$.
This leads to the construction of a monotonically increasing sequence $left(a_nright)_{nin mathbb Z^+}$ and a monotonically decreasing sequence $left(b_nright)_{nin mathbb Z^+}$, such that
$$0=a_0 leq a_1 leq cdots leq a_n cdots leq b_n cdots leq b_1 leq b_0=1,$$
with
begin{equation}
f(b_n)<b_n,tag{1}label{eq:down}
end{equation}
and
begin{equation}
f(a_n)>a_n.tag{2}label{eq:up}
end{equation}
Furthermore we have
begin{equation}b_n - a_n leq frac{1}{2^n}.tag{3}label{eq:diff}end{equation}
So, by boundedness and monotonicity the two sequences converge (here Completeness comes into play), and by eqref{eq:diff}, they converge to the same number $alpha in [0,1]$.
Suppose now $f(alpha) > alpha$. Then, for sufficiently large $n$,
$$alpha leq b_n < f(alpha),$$
which, together with eqref{eq:down} gives
$$f(b_n) < b_n < f(alpha),$$
contradicting monotonicity of $f$. Similarly, if $f(alpha) < alpha$, then, for sufficiently large $n$,
$$f(alpha) < a_n leq alpha,$$
so that, using eqref{eq:up},
the inequality
$$ f(a_n) > a_n > f(alpha)$$
leads again to a contradiction. Thus, it must be $f(alpha) = alpha$.
Note
Completeness is necessary for the statement to hold true. As a counterexample consider the function $f: [0,1]cap Bbb Q rightarrow [0,1]cap Bbb Q$
$$f(x) = -frac{1}{x-3}.$$
This function is continuous and strictly increasing in its domain, but there is no point in the domain in which $f(x) = x$.
answered Jan 28 at 15:30
MatteoMatteo
1,242313
edited Jan 29 at 9:41
answered Jan 28 at 15:30
MatteoMatteo
1,242313
answered Jan 28 at 15:30
MatteoMatteo
1,242313
answered Jan 28 at 15:30
MatteoMatteo
1,242313
1,242313
add a comment |
add a comment |
$begingroup$
Start by defining the sequences $l_n, u_n$, where the variable names stand for "lower" and "upper". And let $x_n equiv (l_n + u_n)/2$.
$l_0 equiv 0, u_0 equiv 1$
Now inductively define $l_k, u_k$:
If $f(x_{k-1}) lt x_{k-1}$, define $u_k equiv x_{k-1}, l_k equiv l_{k-1}$ (shift the upper bound down).
If $f(x_{k-1}) > x_{k-1}$, define $u_k equiv u_{k-1}, l_k equiv x_{k-1}$ (shift the lower bound up)
(And if $f(x_{k-1}) = x_{k-1}$ we are done, so we can ignore this case).
This part is kind of like the intermediate value theorem, where we keep narrowing the search for our target.
The set $f([l_k, u_k])$ is in the square $[l_k, u_k]times[l_k, u_k]$. (Using induction and $f$ is increasing. It's kind of clear if you draw a picture.)
For any $k$, the square $[l_k, u_k]times[l_k, u_k]$ intersects the diagonal line ${ (x, x )}$ since it contains $(l_k, l_k)$, so if the sequence of nested squares converges, it converges to a point on the diagonal.
But it does converge, since $[l_k, u_k]$ converges to some singleton set ${ c }$.
Putting it all together, $forall k, f(c) in f([l_k, u_k]) subset [l_k, u_k]times[l_k, u_k]$.
$ f([c]) in cap_k [l_k, u_k]times[l_k, u_k]$.
$ f([c]) in { (c, c) }$.
$ f(c) = c $.
answered Jan 27 at 17:12
MarkMark
2,09232450
$endgroup$
$begingroup$
I read your comment on @Surb answer. Of course some "real analysis" must be necessary. For if the domain is not complete (an interval), then the statement isn't true anymore. I added a counterexample in my answer. Do you agree?
$endgroup$
– Matteo
Jan 28 at 19:12
$begingroup$
@Matteo yes the only requirement is that the set in question is a complete lattice. After after that, the tarski fixed point theorem applies a purely logical argument.
$endgroup$
– Mark
Jan 29 at 3:30
add a comment |
$begingroup$
Start by defining the sequences $l_n, u_n$, where the variable names stand for "lower" and "upper". And let $x_n equiv (l_n + u_n)/2$.
$l_0 equiv 0, u_0 equiv 1$
Now inductively define $l_k, u_k$:
If $f(x_{k-1}) lt x_{k-1}$, define $u_k equiv x_{k-1}, l_k equiv l_{k-1}$ (shift the upper bound down).
If $f(x_{k-1}) > x_{k-1}$, define $u_k equiv u_{k-1}, l_k equiv x_{k-1}$ (shift the lower bound up)
(And if $f(x_{k-1}) = x_{k-1}$ we are done, so we can ignore this case).
This part is kind of like the intermediate value theorem, where we keep narrowing the search for our target.
The set $f([l_k, u_k])$ is in the square $[l_k, u_k]times[l_k, u_k]$. (Using induction and $f$ is increasing. It's kind of clear if you draw a picture.)
For any $k$, the square $[l_k, u_k]times[l_k, u_k]$ intersects the diagonal line ${ (x, x )}$ since it contains $(l_k, l_k)$, so if the sequence of nested squares converges, it converges to a point on the diagonal.
But it does converge, since $[l_k, u_k]$ converges to some singleton set ${ c }$.
Putting it all together, $forall k, f(c) in f([l_k, u_k]) subset [l_k, u_k]times[l_k, u_k]$.
$ f([c]) in cap_k [l_k, u_k]times[l_k, u_k]$.
$ f([c]) in { (c, c) }$.
$ f(c) = c $.
answered Jan 27 at 17:12
MarkMark
2,09232450
$endgroup$
$begingroup$
I read your comment on @Surb answer. Of course some "real analysis" must be necessary. For if the domain is not complete (an interval), then the statement isn't true anymore. I added a counterexample in my answer. Do you agree?
$endgroup$
– Matteo
Jan 28 at 19:12
$begingroup$
@Matteo yes the only requirement is that the set in question is a complete lattice. After after that, the tarski fixed point theorem applies a purely logical argument.
$endgroup$
– Mark
Jan 29 at 3:30
add a comment |
$begingroup$
Start by defining the sequences $l_n, u_n$, where the variable names stand for "lower" and "upper". And let $x_n equiv (l_n + u_n)/2$.
$l_0 equiv 0, u_0 equiv 1$
Now inductively define $l_k, u_k$:
If $f(x_{k-1}) lt x_{k-1}$, define $u_k equiv x_{k-1}, l_k equiv l_{k-1}$ (shift the upper bound down).
If $f(x_{k-1}) > x_{k-1}$, define $u_k equiv u_{k-1}, l_k equiv x_{k-1}$ (shift the lower bound up)
(And if $f(x_{k-1}) = x_{k-1}$ we are done, so we can ignore this case).
This part is kind of like the intermediate value theorem, where we keep narrowing the search for our target.
The set $f([l_k, u_k])$ is in the square $[l_k, u_k]times[l_k, u_k]$. (Using induction and $f$ is increasing. It's kind of clear if you draw a picture.)
For any $k$, the square $[l_k, u_k]times[l_k, u_k]$ intersects the diagonal line ${ (x, x )}$ since it contains $(l_k, l_k)$, so if the sequence of nested squares converges, it converges to a point on the diagonal.
But it does converge, since $[l_k, u_k]$ converges to some singleton set ${ c }$.
Putting it all together, $forall k, f(c) in f([l_k, u_k]) subset [l_k, u_k]times[l_k, u_k]$.
$ f([c]) in cap_k [l_k, u_k]times[l_k, u_k]$.
$ f([c]) in { (c, c) }$.
$ f(c) = c $.
answered Jan 27 at 17:12
MarkMark
2,09232450
$endgroup$
Start by defining the sequences $l_n, u_n$, where the variable names stand for "lower" and "upper". And let $x_n equiv (l_n + u_n)/2$.
$l_0 equiv 0, u_0 equiv 1$
Now inductively define $l_k, u_k$:
If $f(x_{k-1}) lt x_{k-1}$, define $u_k equiv x_{k-1}, l_k equiv l_{k-1}$ (shift the upper bound down).
If $f(x_{k-1}) > x_{k-1}$, define $u_k equiv u_{k-1}, l_k equiv x_{k-1}$ (shift the lower bound up)
(And if $f(x_{k-1}) = x_{k-1}$ we are done, so we can ignore this case).
This part is kind of like the intermediate value theorem, where we keep narrowing the search for our target.
The set $f([l_k, u_k])$ is in the square $[l_k, u_k]times[l_k, u_k]$. (Using induction and $f$ is increasing. It's kind of clear if you draw a picture.)
For any $k$, the square $[l_k, u_k]times[l_k, u_k]$ intersects the diagonal line ${ (x, x )}$ since it contains $(l_k, l_k)$, so if the sequence of nested squares converges, it converges to a point on the diagonal.
But it does converge, since $[l_k, u_k]$ converges to some singleton set ${ c }$.
Putting it all together, $forall k, f(c) in f([l_k, u_k]) subset [l_k, u_k]times[l_k, u_k]$.
$ f([c]) in cap_k [l_k, u_k]times[l_k, u_k]$.
$ f([c]) in { (c, c) }$.
$ f(c) = c $.
answered Jan 27 at 17:12
MarkMark
2,09232450
edited Jan 27 at 17:29
answered Jan 27 at 17:12
MarkMark
2,09232450
answered Jan 27 at 17:12
MarkMark
2,09232450
answered Jan 27 at 17:12
MarkMark
2,09232450
2,09232450
$begingroup$
I read your comment on @Surb answer. Of course some "real analysis" must be necessary. For if the domain is not complete (an interval), then the statement isn't true anymore. I added a counterexample in my answer. Do you agree?
$endgroup$
– Matteo
Jan 28 at 19:12
$begingroup$
@Matteo yes the only requirement is that the set in question is a complete lattice. After after that, the tarski fixed point theorem applies a purely logical argument.
$endgroup$
– Mark
Jan 29 at 3:30
add a comment |
$begingroup$
I read your comment on @Surb answer. Of course some "real analysis" must be necessary. For if the domain is not complete (an interval), then the statement isn't true anymore. I added a counterexample in my answer. Do you agree?
$endgroup$
– Matteo
Jan 28 at 19:12
$begingroup$
@Matteo yes the only requirement is that the set in question is a complete lattice. After after that, the tarski fixed point theorem applies a purely logical argument.
$endgroup$
– Mark
Jan 29 at 3:30
$begingroup$
I read your comment on @Surb answer. Of course some "real analysis" must be necessary. For if the domain is not complete (an interval), then the statement isn't true anymore. I added a counterexample in my answer. Do you agree?
$endgroup$
– Matteo
Jan 28 at 19:12
$begingroup$
I read your comment on @Surb answer. Of course some "real analysis" must be necessary. For if the domain is not complete (an interval), then the statement isn't true anymore. I added a counterexample in my answer. Do you agree?
$endgroup$
– Matteo
Jan 28 at 19:12
$begingroup$
@Matteo yes the only requirement is that the set in question is a complete lattice. After after that, the tarski fixed point theorem applies a purely logical argument.
$endgroup$
– Mark
Jan 29 at 3:30
$begingroup$
@Matteo yes the only requirement is that the set in question is a complete lattice. After after that, the tarski fixed point theorem applies a purely logical argument.
$endgroup$
– Mark
Jan 29 at 3:30
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3089721%2fprove-f-has-a-fixed-point-if-it-is-increasing-but-not-necessarily-continuous%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
What have you tried so far?
$endgroup$
– Matteo
Jan 27 at 15:44
$begingroup$
I tried copying the IVT but could not connect it with an increasing function
$endgroup$
– The Poor Jew
Jan 27 at 15:46
1
$begingroup$
I think you can apply squeeze theorem after doing binary search
$endgroup$
– Mark
Jan 27 at 15:47
$begingroup$
For the function to be increasing, $[0,1]$ being it's range, isn't it necessary to have $f(0) = 0$? Forgive me if I'm mistaken.
$endgroup$
– Matteo
Jan 27 at 15:54
$begingroup$
@Matteo The function need not be surjective. It could be the constant function equal to $1$, for all we know.
$endgroup$
– Clement C.
Jan 27 at 16:10