Mixing
Every sequence of the real numbers has a monotone subsequence.
$begingroup$
I am aware that there are other posts discussing the same proposition. However, I would like to get feedback on my particular solution, which I have not been able to find on the forum. Thank you :)
We can construct a monotone subsequence given any sequence.
We will try to construct two monotone subsequences simultaneously, one increasing and one decreasing. One will be completed, the other will not.
Consider any sequence $(x_n).$
Start the following process with $n = 1$ (the first element in the sequence).
PROCESS: Look at $x_n.$ Either there exists an element $x_{n'}$ later in the sequence that satisfies $x_n leq x_{n'},$ or there does not.
If there does not exist such an element after $x_n,$ then all elements $x_{n'}$ after $x_n$ satisfy $x_{n'} < x_n.$ Add $x_n$ as the next element in the monotone decreasing sequence. Wipe clean the monotone increasing sequence under construction, and look at $x_{n+1}$ and start over.
If there does exist such an element $x_{n'}$ after $x_n,$ then add the element as the next element in the monotone increasing subsequence. Now, consider $x_{n'},$ and start over.
Notice that if there is a monotone increasing subsequence, then eventually Condition 2 will eventually be everlastingly satisfied and will sequentially construct a monotone increasing subsequence.
If there is no monotone increasing subsequence, every attempt at sequentially constructing a monotone increasing sequence will eventually fail, arriving at an peak element $x_p,$ after which there is no element greater or equal to it (that is, there is no element that appears after it in the sequence that satisfies the monotone increasing condition), and Condition 1 will be satisfied infinitely many times, therein sequentially constructing a monotone decreasing subsequence.
real-analysis sequences-and-series proof-verification
asked Jan 28 at 23:07
Rafael VergnaudRafael Vergnaud
357217
$endgroup$
add a comment |
$begingroup$
I am aware that there are other posts discussing the same proposition. However, I would like to get feedback on my particular solution, which I have not been able to find on the forum. Thank you :)
We can construct a monotone subsequence given any sequence.
We will try to construct two monotone subsequences simultaneously, one increasing and one decreasing. One will be completed, the other will not.
Consider any sequence $(x_n).$
Start the following process with $n = 1$ (the first element in the sequence).
PROCESS: Look at $x_n.$ Either there exists an element $x_{n'}$ later in the sequence that satisfies $x_n leq x_{n'},$ or there does not.
If there does not exist such an element after $x_n,$ then all elements $x_{n'}$ after $x_n$ satisfy $x_{n'} < x_n.$ Add $x_n$ as the next element in the monotone decreasing sequence. Wipe clean the monotone increasing sequence under construction, and look at $x_{n+1}$ and start over.
If there does exist such an element $x_{n'}$ after $x_n,$ then add the element as the next element in the monotone increasing subsequence. Now, consider $x_{n'},$ and start over.
Notice that if there is a monotone increasing subsequence, then eventually Condition 2 will eventually be everlastingly satisfied and will sequentially construct a monotone increasing subsequence.
If there is no monotone increasing subsequence, every attempt at sequentially constructing a monotone increasing sequence will eventually fail, arriving at an peak element $x_p,$ after which there is no element greater or equal to it (that is, there is no element that appears after it in the sequence that satisfies the monotone increasing condition), and Condition 1 will be satisfied infinitely many times, therein sequentially constructing a monotone decreasing subsequence.
real-analysis sequences-and-series proof-verification
asked Jan 28 at 23:07
Rafael VergnaudRafael Vergnaud
357217
$endgroup$
add a comment |
$begingroup$
I am aware that there are other posts discussing the same proposition. However, I would like to get feedback on my particular solution, which I have not been able to find on the forum. Thank you :)
We can construct a monotone subsequence given any sequence.
We will try to construct two monotone subsequences simultaneously, one increasing and one decreasing. One will be completed, the other will not.
Consider any sequence $(x_n).$
Start the following process with $n = 1$ (the first element in the sequence).
PROCESS: Look at $x_n.$ Either there exists an element $x_{n'}$ later in the sequence that satisfies $x_n leq x_{n'},$ or there does not.
If there does not exist such an element after $x_n,$ then all elements $x_{n'}$ after $x_n$ satisfy $x_{n'} < x_n.$ Add $x_n$ as the next element in the monotone decreasing sequence. Wipe clean the monotone increasing sequence under construction, and look at $x_{n+1}$ and start over.
If there does exist such an element $x_{n'}$ after $x_n,$ then add the element as the next element in the monotone increasing subsequence. Now, consider $x_{n'},$ and start over.
Notice that if there is a monotone increasing subsequence, then eventually Condition 2 will eventually be everlastingly satisfied and will sequentially construct a monotone increasing subsequence.
If there is no monotone increasing subsequence, every attempt at sequentially constructing a monotone increasing sequence will eventually fail, arriving at an peak element $x_p,$ after which there is no element greater or equal to it (that is, there is no element that appears after it in the sequence that satisfies the monotone increasing condition), and Condition 1 will be satisfied infinitely many times, therein sequentially constructing a monotone decreasing subsequence.
real-analysis sequences-and-series proof-verification
asked Jan 28 at 23:07
Rafael VergnaudRafael Vergnaud
357217
$endgroup$
I am aware that there are other posts discussing the same proposition. However, I would like to get feedback on my particular solution, which I have not been able to find on the forum. Thank you :)
We can construct a monotone subsequence given any sequence.
We will try to construct two monotone subsequences simultaneously, one increasing and one decreasing. One will be completed, the other will not.
Consider any sequence $(x_n).$
Start the following process with $n = 1$ (the first element in the sequence).
PROCESS: Look at $x_n.$ Either there exists an element $x_{n'}$ later in the sequence that satisfies $x_n leq x_{n'},$ or there does not.
If there does not exist such an element after $x_n,$ then all elements $x_{n'}$ after $x_n$ satisfy $x_{n'} < x_n.$ Add $x_n$ as the next element in the monotone decreasing sequence. Wipe clean the monotone increasing sequence under construction, and look at $x_{n+1}$ and start over.
If there does exist such an element $x_{n'}$ after $x_n,$ then add the element as the next element in the monotone increasing subsequence. Now, consider $x_{n'},$ and start over.
Notice that if there is a monotone increasing subsequence, then eventually Condition 2 will eventually be everlastingly satisfied and will sequentially construct a monotone increasing subsequence.
If there is no monotone increasing subsequence, every attempt at sequentially constructing a monotone increasing sequence will eventually fail, arriving at an peak element $x_p,$ after which there is no element greater or equal to it (that is, there is no element that appears after it in the sequence that satisfies the monotone increasing condition), and Condition 1 will be satisfied infinitely many times, therein sequentially constructing a monotone decreasing subsequence.
real-analysis sequences-and-series proof-verification
real-analysis sequences-and-series proof-verification
asked Jan 28 at 23:07
Rafael VergnaudRafael Vergnaud
357217
asked Jan 28 at 23:07
Rafael VergnaudRafael Vergnaud
357217
edited Jan 28 at 23:23
Rafael Vergnaud
asked Jan 28 at 23:07
Rafael VergnaudRafael Vergnaud
357217
asked Jan 28 at 23:07
Rafael VergnaudRafael Vergnaud
357217
asked Jan 28 at 23:07
Rafael VergnaudRafael Vergnaud
357217
357217
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
There's a flaw at this part of the argument:
Notice that if there is a monotone increasing subsequence, then eventually Condition 2 will eventually be everlastingly satisfied and will sequentially construct a monotone increasing subsequence.
Consider this sequence for $ngeq2$:
$$frac{(-1)^n}{n}=frac12,-frac13,frac14,-frac15,frac16,-frac17,frac18,-frac19,ldots$$
There is a monotonically increasing subsequence: $-frac13,-frac15,-frac17,ldots$. However, your algorithm fails to find it. Instead, it steps through each value of $n$, wiping clean the increasing sequence under construction at every other step.
I'm not sure whether or not this sort of counterexample completely dooms your "greedy" algorithm, but it's false as stated.
answered Jan 28 at 23:31
Chris CulterChris Culter
21.5k43888
$endgroup$
$begingroup$
Hi, Chris. I don't see how it will fail to find that subsequence. Once $frac{-1}{3}$ is found, it will find $frac{-1}{5},$ and then $frac{-1}{7}$ and so on. Notice that condition 2 does specify that the element greater than the current element must be the very next element.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:34
$begingroup$
"Look at $x_n.$ Either there exists an element $x_{n'}$ later in the sequence that satisfies $x_n leq x_{n'},$ or there does not."
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:39
$begingroup$
"If there does exist such an element $x_{n'}$ after $x_n,$ then add the element as the next element in the monotone increasing subsequence. Now, consider $x_{n'},$ and start over."
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:39
$begingroup$
Having arrived at $frac{-1}{3},$ there will be a later element in the sequence that is greater or equal to $frac{-1}{3}.$ It will add that element, and then start the process over by looking at that element. And so on
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:40
$begingroup$
@RafaelVergnaud It's not a well-defined process if you don't specify any way to know which $n'$ is going to be selected. You might as well write "Let $n'$ be the index that gives me the result I'm hoping for."
$endgroup$
– Chris Culter
Jan 28 at 23:42
|
show 10 more comments
$begingroup$
This is indeed, in essence, the standard proof for this fact.
answered Jan 28 at 23:19
Reiner MartinReiner Martin
3,509414
$endgroup$
$begingroup$
Hey Reiner. I couldn't find the proof on math stack exchange (maybe its there, there are many posts discussing this issue). Thanks for you feedback!
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:21
$begingroup$
Hi Rafael, see for example mathonline.wikidot.com/the-monotone-subsequence-theorem or math.stackexchange.com/questions/716461/…
$endgroup$
– Reiner Martin
Jan 28 at 23:24
$begingroup$
That's interesting. I'm surprised it's almost identical to my proof.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:27
$begingroup$
Thanks, Reiner.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:27
add a comment |
$begingroup$
(1). If $lim_{nto infty}a_n=a$ then $(a_n)_n$ has a monotone sub-sequence $(a_{f(n)})_n.$ Proof: Let $C={n:a_n=a}.$ Let $P={n:a_n>a}$ and $Q={n:a_n<a}.$
$quad$ (i). If $C$ is infinite let $f:Bbb Nto C$ be the unique strictly increasing bijection.
$quad$ (ii). If $C$ is finite and $P$ is infinite let $f(1)=min P$ and let $f(n+1)=min {j>f(n): a< a_j< a_{f(n)}}.$
$quad$ (iii). If $S$ and $P$ are finite let $f(1)=min Q$ and let $f(n+1)=min {j>f(n):a_{f(n)}<a_j<a}.$
(2). A bounded sequence $(b_n)_n$ has a convergent sub-sequence $(b_{g(n)})_n.$ Proof: Suppose ${b_n:nin Bbb N}subset [l,u].$
Let $[l_1,u_1]=[l,u]$ and let $g(1)=1.$
For convenience, for any $n$ let $m_n=(l_n+u_n)/2.$
Now if ${n:b_nin [l_n,m_n]}$ is infinite let $[l_{n+1},u_{n+1}]=[l_n,m_n];$ otherwise let $[l_{n+1},u_{n+1}]=[m_n,u_n].$ And in either case let $g(n+1)=min {j>g(n):b_jin [l_{n+1},u_{n+1}]}.$
Observe that $|b_{g(n)}-b_{g(n+1)}|le u_n-l_n=2^{1-n}(u-l)$, which implies that $(b_{g(n)})_n$ is a Cauchy sequence.
(3). Let $b_n=arctan x_n in (-pi/2,pi/2).$ By (2) there exists a convergent sub-sequence $(b_{g(n)})_n$ and by (1), with $a_n=b_{g(n)},$ the sequence $(b_{g(n)})_n$ has a monotone sub-sequence $(b_{g(f(n))})_n.$ Since $tan $ is a monotone function on the domain $(-pi/2,pi/2),$ therefore $$(tan b_{g(f(n))})_n=(x_{g(f(n))})_n$$ is monotone.
answered Jan 29 at 5:28
DanielWainfleetDanielWainfleet
35.7k31648
$endgroup$
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%2f3091518%2fevery-sequence-of-the-real-numbers-has-a-monotone-subsequence%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$
There's a flaw at this part of the argument:
Notice that if there is a monotone increasing subsequence, then eventually Condition 2 will eventually be everlastingly satisfied and will sequentially construct a monotone increasing subsequence.
Consider this sequence for $ngeq2$:
$$frac{(-1)^n}{n}=frac12,-frac13,frac14,-frac15,frac16,-frac17,frac18,-frac19,ldots$$
There is a monotonically increasing subsequence: $-frac13,-frac15,-frac17,ldots$. However, your algorithm fails to find it. Instead, it steps through each value of $n$, wiping clean the increasing sequence under construction at every other step.
I'm not sure whether or not this sort of counterexample completely dooms your "greedy" algorithm, but it's false as stated.
answered Jan 28 at 23:31
Chris CulterChris Culter
21.5k43888
$endgroup$
$begingroup$
Hi, Chris. I don't see how it will fail to find that subsequence. Once $frac{-1}{3}$ is found, it will find $frac{-1}{5},$ and then $frac{-1}{7}$ and so on. Notice that condition 2 does specify that the element greater than the current element must be the very next element.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:34
$begingroup$
"Look at $x_n.$ Either there exists an element $x_{n'}$ later in the sequence that satisfies $x_n leq x_{n'},$ or there does not."
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:39
$begingroup$
"If there does exist such an element $x_{n'}$ after $x_n,$ then add the element as the next element in the monotone increasing subsequence. Now, consider $x_{n'},$ and start over."
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:39
$begingroup$
Having arrived at $frac{-1}{3},$ there will be a later element in the sequence that is greater or equal to $frac{-1}{3}.$ It will add that element, and then start the process over by looking at that element. And so on
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:40
$begingroup$
@RafaelVergnaud It's not a well-defined process if you don't specify any way to know which $n'$ is going to be selected. You might as well write "Let $n'$ be the index that gives me the result I'm hoping for."
$endgroup$
– Chris Culter
Jan 28 at 23:42
|
show 10 more comments
$begingroup$
There's a flaw at this part of the argument:
Notice that if there is a monotone increasing subsequence, then eventually Condition 2 will eventually be everlastingly satisfied and will sequentially construct a monotone increasing subsequence.
Consider this sequence for $ngeq2$:
$$frac{(-1)^n}{n}=frac12,-frac13,frac14,-frac15,frac16,-frac17,frac18,-frac19,ldots$$
There is a monotonically increasing subsequence: $-frac13,-frac15,-frac17,ldots$. However, your algorithm fails to find it. Instead, it steps through each value of $n$, wiping clean the increasing sequence under construction at every other step.
I'm not sure whether or not this sort of counterexample completely dooms your "greedy" algorithm, but it's false as stated.
answered Jan 28 at 23:31
Chris CulterChris Culter
21.5k43888
$endgroup$
$begingroup$
Hi, Chris. I don't see how it will fail to find that subsequence. Once $frac{-1}{3}$ is found, it will find $frac{-1}{5},$ and then $frac{-1}{7}$ and so on. Notice that condition 2 does specify that the element greater than the current element must be the very next element.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:34
$begingroup$
"Look at $x_n.$ Either there exists an element $x_{n'}$ later in the sequence that satisfies $x_n leq x_{n'},$ or there does not."
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:39
$begingroup$
"If there does exist such an element $x_{n'}$ after $x_n,$ then add the element as the next element in the monotone increasing subsequence. Now, consider $x_{n'},$ and start over."
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:39
$begingroup$
Having arrived at $frac{-1}{3},$ there will be a later element in the sequence that is greater or equal to $frac{-1}{3}.$ It will add that element, and then start the process over by looking at that element. And so on
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:40
$begingroup$
@RafaelVergnaud It's not a well-defined process if you don't specify any way to know which $n'$ is going to be selected. You might as well write "Let $n'$ be the index that gives me the result I'm hoping for."
$endgroup$
– Chris Culter
Jan 28 at 23:42
|
show 10 more comments
$begingroup$
There's a flaw at this part of the argument:
Notice that if there is a monotone increasing subsequence, then eventually Condition 2 will eventually be everlastingly satisfied and will sequentially construct a monotone increasing subsequence.
Consider this sequence for $ngeq2$:
$$frac{(-1)^n}{n}=frac12,-frac13,frac14,-frac15,frac16,-frac17,frac18,-frac19,ldots$$
There is a monotonically increasing subsequence: $-frac13,-frac15,-frac17,ldots$. However, your algorithm fails to find it. Instead, it steps through each value of $n$, wiping clean the increasing sequence under construction at every other step.
I'm not sure whether or not this sort of counterexample completely dooms your "greedy" algorithm, but it's false as stated.
answered Jan 28 at 23:31
Chris CulterChris Culter
21.5k43888
$endgroup$
There's a flaw at this part of the argument:
Notice that if there is a monotone increasing subsequence, then eventually Condition 2 will eventually be everlastingly satisfied and will sequentially construct a monotone increasing subsequence.
Consider this sequence for $ngeq2$:
$$frac{(-1)^n}{n}=frac12,-frac13,frac14,-frac15,frac16,-frac17,frac18,-frac19,ldots$$
There is a monotonically increasing subsequence: $-frac13,-frac15,-frac17,ldots$. However, your algorithm fails to find it. Instead, it steps through each value of $n$, wiping clean the increasing sequence under construction at every other step.
I'm not sure whether or not this sort of counterexample completely dooms your "greedy" algorithm, but it's false as stated.
answered Jan 28 at 23:31
Chris CulterChris Culter
21.5k43888
answered Jan 28 at 23:31
Chris CulterChris Culter
21.5k43888
answered Jan 28 at 23:31
Chris CulterChris Culter
21.5k43888
answered Jan 28 at 23:31
Chris CulterChris Culter
21.5k43888
21.5k43888
$begingroup$
Hi, Chris. I don't see how it will fail to find that subsequence. Once $frac{-1}{3}$ is found, it will find $frac{-1}{5},$ and then $frac{-1}{7}$ and so on. Notice that condition 2 does specify that the element greater than the current element must be the very next element.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:34
$begingroup$
"Look at $x_n.$ Either there exists an element $x_{n'}$ later in the sequence that satisfies $x_n leq x_{n'},$ or there does not."
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:39
$begingroup$
"If there does exist such an element $x_{n'}$ after $x_n,$ then add the element as the next element in the monotone increasing subsequence. Now, consider $x_{n'},$ and start over."
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:39
$begingroup$
Having arrived at $frac{-1}{3},$ there will be a later element in the sequence that is greater or equal to $frac{-1}{3}.$ It will add that element, and then start the process over by looking at that element. And so on
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:40
$begingroup$
@RafaelVergnaud It's not a well-defined process if you don't specify any way to know which $n'$ is going to be selected. You might as well write "Let $n'$ be the index that gives me the result I'm hoping for."
$endgroup$
– Chris Culter
Jan 28 at 23:42
|
show 10 more comments
$begingroup$
Hi, Chris. I don't see how it will fail to find that subsequence. Once $frac{-1}{3}$ is found, it will find $frac{-1}{5},$ and then $frac{-1}{7}$ and so on. Notice that condition 2 does specify that the element greater than the current element must be the very next element.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:34
$begingroup$
"Look at $x_n.$ Either there exists an element $x_{n'}$ later in the sequence that satisfies $x_n leq x_{n'},$ or there does not."
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:39
$begingroup$
"If there does exist such an element $x_{n'}$ after $x_n,$ then add the element as the next element in the monotone increasing subsequence. Now, consider $x_{n'},$ and start over."
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:39
$begingroup$
Having arrived at $frac{-1}{3},$ there will be a later element in the sequence that is greater or equal to $frac{-1}{3}.$ It will add that element, and then start the process over by looking at that element. And so on
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:40
$begingroup$
@RafaelVergnaud It's not a well-defined process if you don't specify any way to know which $n'$ is going to be selected. You might as well write "Let $n'$ be the index that gives me the result I'm hoping for."
$endgroup$
– Chris Culter
Jan 28 at 23:42
$begingroup$
Hi, Chris. I don't see how it will fail to find that subsequence. Once $frac{-1}{3}$ is found, it will find $frac{-1}{5},$ and then $frac{-1}{7}$ and so on. Notice that condition 2 does specify that the element greater than the current element must be the very next element.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:34
$begingroup$
Hi, Chris. I don't see how it will fail to find that subsequence. Once $frac{-1}{3}$ is found, it will find $frac{-1}{5},$ and then $frac{-1}{7}$ and so on. Notice that condition 2 does specify that the element greater than the current element must be the very next element.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:34
$begingroup$
"Look at $x_n.$ Either there exists an element $x_{n'}$ later in the sequence that satisfies $x_n leq x_{n'},$ or there does not."
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:39
$begingroup$
"Look at $x_n.$ Either there exists an element $x_{n'}$ later in the sequence that satisfies $x_n leq x_{n'},$ or there does not."
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:39
$begingroup$
"If there does exist such an element $x_{n'}$ after $x_n,$ then add the element as the next element in the monotone increasing subsequence. Now, consider $x_{n'},$ and start over."
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:39
$begingroup$
"If there does exist such an element $x_{n'}$ after $x_n,$ then add the element as the next element in the monotone increasing subsequence. Now, consider $x_{n'},$ and start over."
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:39
$begingroup$
Having arrived at $frac{-1}{3},$ there will be a later element in the sequence that is greater or equal to $frac{-1}{3}.$ It will add that element, and then start the process over by looking at that element. And so on
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:40
$begingroup$
Having arrived at $frac{-1}{3},$ there will be a later element in the sequence that is greater or equal to $frac{-1}{3}.$ It will add that element, and then start the process over by looking at that element. And so on
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:40
$begingroup$
@RafaelVergnaud It's not a well-defined process if you don't specify any way to know which $n'$ is going to be selected. You might as well write "Let $n'$ be the index that gives me the result I'm hoping for."
$endgroup$
– Chris Culter
Jan 28 at 23:42
$begingroup$
@RafaelVergnaud It's not a well-defined process if you don't specify any way to know which $n'$ is going to be selected. You might as well write "Let $n'$ be the index that gives me the result I'm hoping for."
$endgroup$
– Chris Culter
Jan 28 at 23:42
|
show 10 more comments
$begingroup$
This is indeed, in essence, the standard proof for this fact.
answered Jan 28 at 23:19
Reiner MartinReiner Martin
3,509414
$endgroup$
$begingroup$
Hey Reiner. I couldn't find the proof on math stack exchange (maybe its there, there are many posts discussing this issue). Thanks for you feedback!
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:21
$begingroup$
Hi Rafael, see for example mathonline.wikidot.com/the-monotone-subsequence-theorem or math.stackexchange.com/questions/716461/…
$endgroup$
– Reiner Martin
Jan 28 at 23:24
$begingroup$
That's interesting. I'm surprised it's almost identical to my proof.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:27
$begingroup$
Thanks, Reiner.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:27
add a comment |
$begingroup$
This is indeed, in essence, the standard proof for this fact.
answered Jan 28 at 23:19
Reiner MartinReiner Martin
3,509414
$endgroup$
$begingroup$
Hey Reiner. I couldn't find the proof on math stack exchange (maybe its there, there are many posts discussing this issue). Thanks for you feedback!
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:21
$begingroup$
Hi Rafael, see for example mathonline.wikidot.com/the-monotone-subsequence-theorem or math.stackexchange.com/questions/716461/…
$endgroup$
– Reiner Martin
Jan 28 at 23:24
$begingroup$
That's interesting. I'm surprised it's almost identical to my proof.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:27
$begingroup$
Thanks, Reiner.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:27
add a comment |
$begingroup$
This is indeed, in essence, the standard proof for this fact.
answered Jan 28 at 23:19
Reiner MartinReiner Martin
3,509414
$endgroup$
This is indeed, in essence, the standard proof for this fact.
answered Jan 28 at 23:19
Reiner MartinReiner Martin
3,509414
answered Jan 28 at 23:19
Reiner MartinReiner Martin
3,509414
answered Jan 28 at 23:19
Reiner MartinReiner Martin
3,509414
answered Jan 28 at 23:19
Reiner MartinReiner Martin
3,509414
3,509414
$begingroup$
Hey Reiner. I couldn't find the proof on math stack exchange (maybe its there, there are many posts discussing this issue). Thanks for you feedback!
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:21
$begingroup$
Hi Rafael, see for example mathonline.wikidot.com/the-monotone-subsequence-theorem or math.stackexchange.com/questions/716461/…
$endgroup$
– Reiner Martin
Jan 28 at 23:24
$begingroup$
That's interesting. I'm surprised it's almost identical to my proof.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:27
$begingroup$
Thanks, Reiner.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:27
add a comment |
$begingroup$
Hey Reiner. I couldn't find the proof on math stack exchange (maybe its there, there are many posts discussing this issue). Thanks for you feedback!
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:21
$begingroup$
Hi Rafael, see for example mathonline.wikidot.com/the-monotone-subsequence-theorem or math.stackexchange.com/questions/716461/…
$endgroup$
– Reiner Martin
Jan 28 at 23:24
$begingroup$
That's interesting. I'm surprised it's almost identical to my proof.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:27
$begingroup$
Thanks, Reiner.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:27
$begingroup$
Hey Reiner. I couldn't find the proof on math stack exchange (maybe its there, there are many posts discussing this issue). Thanks for you feedback!
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:21
$begingroup$
Hey Reiner. I couldn't find the proof on math stack exchange (maybe its there, there are many posts discussing this issue). Thanks for you feedback!
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:21
$begingroup$
Hi Rafael, see for example mathonline.wikidot.com/the-monotone-subsequence-theorem or math.stackexchange.com/questions/716461/…
$endgroup$
– Reiner Martin
Jan 28 at 23:24
$begingroup$
Hi Rafael, see for example mathonline.wikidot.com/the-monotone-subsequence-theorem or math.stackexchange.com/questions/716461/…
$endgroup$
– Reiner Martin
Jan 28 at 23:24
$begingroup$
That's interesting. I'm surprised it's almost identical to my proof.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:27
$begingroup$
That's interesting. I'm surprised it's almost identical to my proof.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:27
$begingroup$
Thanks, Reiner.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:27
$begingroup$
Thanks, Reiner.
$endgroup$
– Rafael Vergnaud
Jan 28 at 23:27
add a comment |
$begingroup$
(1). If $lim_{nto infty}a_n=a$ then $(a_n)_n$ has a monotone sub-sequence $(a_{f(n)})_n.$ Proof: Let $C={n:a_n=a}.$ Let $P={n:a_n>a}$ and $Q={n:a_n<a}.$
$quad$ (i). If $C$ is infinite let $f:Bbb Nto C$ be the unique strictly increasing bijection.
$quad$ (ii). If $C$ is finite and $P$ is infinite let $f(1)=min P$ and let $f(n+1)=min {j>f(n): a< a_j< a_{f(n)}}.$
$quad$ (iii). If $S$ and $P$ are finite let $f(1)=min Q$ and let $f(n+1)=min {j>f(n):a_{f(n)}<a_j<a}.$
(2). A bounded sequence $(b_n)_n$ has a convergent sub-sequence $(b_{g(n)})_n.$ Proof: Suppose ${b_n:nin Bbb N}subset [l,u].$
Let $[l_1,u_1]=[l,u]$ and let $g(1)=1.$
For convenience, for any $n$ let $m_n=(l_n+u_n)/2.$
Now if ${n:b_nin [l_n,m_n]}$ is infinite let $[l_{n+1},u_{n+1}]=[l_n,m_n];$ otherwise let $[l_{n+1},u_{n+1}]=[m_n,u_n].$ And in either case let $g(n+1)=min {j>g(n):b_jin [l_{n+1},u_{n+1}]}.$
Observe that $|b_{g(n)}-b_{g(n+1)}|le u_n-l_n=2^{1-n}(u-l)$, which implies that $(b_{g(n)})_n$ is a Cauchy sequence.
(3). Let $b_n=arctan x_n in (-pi/2,pi/2).$ By (2) there exists a convergent sub-sequence $(b_{g(n)})_n$ and by (1), with $a_n=b_{g(n)},$ the sequence $(b_{g(n)})_n$ has a monotone sub-sequence $(b_{g(f(n))})_n.$ Since $tan $ is a monotone function on the domain $(-pi/2,pi/2),$ therefore $$(tan b_{g(f(n))})_n=(x_{g(f(n))})_n$$ is monotone.
answered Jan 29 at 5:28
DanielWainfleetDanielWainfleet
35.7k31648
$endgroup$
add a comment |
$begingroup$
(1). If $lim_{nto infty}a_n=a$ then $(a_n)_n$ has a monotone sub-sequence $(a_{f(n)})_n.$ Proof: Let $C={n:a_n=a}.$ Let $P={n:a_n>a}$ and $Q={n:a_n<a}.$
$quad$ (i). If $C$ is infinite let $f:Bbb Nto C$ be the unique strictly increasing bijection.
$quad$ (ii). If $C$ is finite and $P$ is infinite let $f(1)=min P$ and let $f(n+1)=min {j>f(n): a< a_j< a_{f(n)}}.$
$quad$ (iii). If $S$ and $P$ are finite let $f(1)=min Q$ and let $f(n+1)=min {j>f(n):a_{f(n)}<a_j<a}.$
(2). A bounded sequence $(b_n)_n$ has a convergent sub-sequence $(b_{g(n)})_n.$ Proof: Suppose ${b_n:nin Bbb N}subset [l,u].$
Let $[l_1,u_1]=[l,u]$ and let $g(1)=1.$
For convenience, for any $n$ let $m_n=(l_n+u_n)/2.$
Now if ${n:b_nin [l_n,m_n]}$ is infinite let $[l_{n+1},u_{n+1}]=[l_n,m_n];$ otherwise let $[l_{n+1},u_{n+1}]=[m_n,u_n].$ And in either case let $g(n+1)=min {j>g(n):b_jin [l_{n+1},u_{n+1}]}.$
Observe that $|b_{g(n)}-b_{g(n+1)}|le u_n-l_n=2^{1-n}(u-l)$, which implies that $(b_{g(n)})_n$ is a Cauchy sequence.
(3). Let $b_n=arctan x_n in (-pi/2,pi/2).$ By (2) there exists a convergent sub-sequence $(b_{g(n)})_n$ and by (1), with $a_n=b_{g(n)},$ the sequence $(b_{g(n)})_n$ has a monotone sub-sequence $(b_{g(f(n))})_n.$ Since $tan $ is a monotone function on the domain $(-pi/2,pi/2),$ therefore $$(tan b_{g(f(n))})_n=(x_{g(f(n))})_n$$ is monotone.
answered Jan 29 at 5:28
DanielWainfleetDanielWainfleet
35.7k31648
$endgroup$
add a comment |
$begingroup$
(1). If $lim_{nto infty}a_n=a$ then $(a_n)_n$ has a monotone sub-sequence $(a_{f(n)})_n.$ Proof: Let $C={n:a_n=a}.$ Let $P={n:a_n>a}$ and $Q={n:a_n<a}.$
$quad$ (i). If $C$ is infinite let $f:Bbb Nto C$ be the unique strictly increasing bijection.
$quad$ (ii). If $C$ is finite and $P$ is infinite let $f(1)=min P$ and let $f(n+1)=min {j>f(n): a< a_j< a_{f(n)}}.$
$quad$ (iii). If $S$ and $P$ are finite let $f(1)=min Q$ and let $f(n+1)=min {j>f(n):a_{f(n)}<a_j<a}.$
(2). A bounded sequence $(b_n)_n$ has a convergent sub-sequence $(b_{g(n)})_n.$ Proof: Suppose ${b_n:nin Bbb N}subset [l,u].$
Let $[l_1,u_1]=[l,u]$ and let $g(1)=1.$
For convenience, for any $n$ let $m_n=(l_n+u_n)/2.$
Now if ${n:b_nin [l_n,m_n]}$ is infinite let $[l_{n+1},u_{n+1}]=[l_n,m_n];$ otherwise let $[l_{n+1},u_{n+1}]=[m_n,u_n].$ And in either case let $g(n+1)=min {j>g(n):b_jin [l_{n+1},u_{n+1}]}.$
Observe that $|b_{g(n)}-b_{g(n+1)}|le u_n-l_n=2^{1-n}(u-l)$, which implies that $(b_{g(n)})_n$ is a Cauchy sequence.
(3). Let $b_n=arctan x_n in (-pi/2,pi/2).$ By (2) there exists a convergent sub-sequence $(b_{g(n)})_n$ and by (1), with $a_n=b_{g(n)},$ the sequence $(b_{g(n)})_n$ has a monotone sub-sequence $(b_{g(f(n))})_n.$ Since $tan $ is a monotone function on the domain $(-pi/2,pi/2),$ therefore $$(tan b_{g(f(n))})_n=(x_{g(f(n))})_n$$ is monotone.
answered Jan 29 at 5:28
DanielWainfleetDanielWainfleet
35.7k31648
$endgroup$
(1). If $lim_{nto infty}a_n=a$ then $(a_n)_n$ has a monotone sub-sequence $(a_{f(n)})_n.$ Proof: Let $C={n:a_n=a}.$ Let $P={n:a_n>a}$ and $Q={n:a_n<a}.$
$quad$ (i). If $C$ is infinite let $f:Bbb Nto C$ be the unique strictly increasing bijection.
$quad$ (ii). If $C$ is finite and $P$ is infinite let $f(1)=min P$ and let $f(n+1)=min {j>f(n): a< a_j< a_{f(n)}}.$
$quad$ (iii). If $S$ and $P$ are finite let $f(1)=min Q$ and let $f(n+1)=min {j>f(n):a_{f(n)}<a_j<a}.$
(2). A bounded sequence $(b_n)_n$ has a convergent sub-sequence $(b_{g(n)})_n.$ Proof: Suppose ${b_n:nin Bbb N}subset [l,u].$
Let $[l_1,u_1]=[l,u]$ and let $g(1)=1.$
For convenience, for any $n$ let $m_n=(l_n+u_n)/2.$
Now if ${n:b_nin [l_n,m_n]}$ is infinite let $[l_{n+1},u_{n+1}]=[l_n,m_n];$ otherwise let $[l_{n+1},u_{n+1}]=[m_n,u_n].$ And in either case let $g(n+1)=min {j>g(n):b_jin [l_{n+1},u_{n+1}]}.$
Observe that $|b_{g(n)}-b_{g(n+1)}|le u_n-l_n=2^{1-n}(u-l)$, which implies that $(b_{g(n)})_n$ is a Cauchy sequence.
(3). Let $b_n=arctan x_n in (-pi/2,pi/2).$ By (2) there exists a convergent sub-sequence $(b_{g(n)})_n$ and by (1), with $a_n=b_{g(n)},$ the sequence $(b_{g(n)})_n$ has a monotone sub-sequence $(b_{g(f(n))})_n.$ Since $tan $ is a monotone function on the domain $(-pi/2,pi/2),$ therefore $$(tan b_{g(f(n))})_n=(x_{g(f(n))})_n$$ is monotone.
answered Jan 29 at 5:28
DanielWainfleetDanielWainfleet
35.7k31648
edited Jan 29 at 5:42
answered Jan 29 at 5:28
DanielWainfleetDanielWainfleet
35.7k31648
answered Jan 29 at 5:28
DanielWainfleetDanielWainfleet
35.7k31648
answered Jan 29 at 5:28
DanielWainfleetDanielWainfleet
35.7k31648
35.7k31648
add a comment |
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%2f3091518%2fevery-sequence-of-the-real-numbers-has-a-monotone-subsequence%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
