Every sequence has a monotone subsequence

Every sequence has a monotone subsequence
Tag	`0MHGJRZMTM`
URI	`m2://0MHGJRZMTM`
Kind	statement, lemma
Writing	W0 stub
MSC	40A05
Status	This copy of the site has no build data. Run `m2 status 0MHGJRZMTM`.
Uses	Subsequence, Monotone sequence

Markdown · JSON · Edit

Statement

Let $(a_n)$ be a real sequence. Then $(a_n)$ has a subsequence that is monotone.

Remarks

The usual proof uses peaks. An index $n$ is a peak if $a_m \le a_n$ for all $m > n$ . If there are infinitely many peaks, the terms at the peaks form a decreasing subsequence. If there are finitely many peaks, start after the last one. Each index then has a later index with a larger term, and this gives a strictly increasing subsequence. With the monotone convergence theorem, the lemma gives the Bolzano–Weierstrass theorem.

Explanations

L1 human

Think of the terms as heights of hills seen from left to right. Either infinitely many hills have no higher hill to their right, or from some point on you can always find a higher hill further right.

What this node needs for W1

an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a node is. They do not measure its truth.

What this needs

To read this node, read these 5 nodes in this order. The foundations come first, and the list ends with this node.

Each node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.

no evidence level

Sequence definition
Real sequence definition
Subsequence definition
Monotone sequence definition
Every sequence has a monotone subsequence statement

What depends on this

101 nodes use this node, directly or through other nodes.

Power series are differentiable inside the radius of convergence 002X7EK91H
A function with zero derivative is constant 003QDZ4T16
Natural logarithm 0044CPHJBV
A differentiable function is convex iff its derivative is increasing 005JT76HCK
Taylor's theorem with the Cauchy remainder 005Q84BMAD
Euler–Mascheroni constant 00C5P9JZBK
The logarithm grows slower than any power 00DGYY10FV
Derivative of sine 00R4MWW532
1 + x is at most exp x 012C7GFF20
Reduction formula 012RYET5E2
Rolle's theorem 0194DY35BG
Weierstrass function 01A0MK1730
First derivative test 01A2EGXJEM
cos pi = -1 01A8JGR4JM
sin x / x tends to 1 01QSSKS5C1
Uniformly Cauchy sequence of functions 01XAY17QA3
A function with nonnegative derivative is increasing 026BJBQNGJ
Inverse trigonometric functions 02HTDK1FBD
Cauchy mean value theorem 02SYZAWM2K
Leibniz formula for pi 037FD5NBRT
Integral of exp(-x) over the half line 039JAF7ZAN
Pythagorean trigonometric identity 03H7WZ4T3K
log x is at most x - 1 04CBRA4JRK
Inverse hyperbolic functions 04D7CHT5V1
Integral of cosine 04WTBQ7APQ
Derivative of arctangent 05P4B4Q22V
Harmonic numbers grow like log n 05S2GSPMGA
First fundamental theorem of calculus 063H5KJC69
Integral of the exponential function 06D0EWR2DV
Power series of the exponential function 06JZGMYTYD
Cauchy criterion for series 06PVXMY0TH
Continuous functions are Riemann integrable 06SESV7GQY
Continuous image of a closed interval is a closed interval 06ZARTQTQE
A function with positive derivative is strictly increasing 07J5X2T1ZX
Derivative of the logarithm 07X1QA6BRW
Integration by parts 08Y1BBQTK9
Boundedness theorem 0ATVXC3NCC
Arcsine 0B89D93YA1
Mean value theorem 0BARQY52N5
Power series converge uniformly on smaller discs inside the radius of convergence 0BWXV7GADW
pi 0C1VYVNV2N
Uniform convergence of derivatives allows term-by-term differentiation 0CS42KEM5C
Integration by substitution 0D37QFPEZE
The exponential function is convex 0D7GRZ2ADX
Basel problem 0DMY75D6FV
Trigonometric substitution 0EAR3KNRTN
The gamma function extends the factorial 0FDCW77H44
Second derivative test 0FZFHK97P7
Derivative of arcsine 0GA6G43EA9
Area under a curve 0GXA8Z205E
Integral of sine 0GXCXCX3QN
Dirichlet integral 0GZNSHMG4Q
Taylor's theorem with the Lagrange remainder 0H5ZAZCX2T
Logarithm of a quotient 0J7PHRBNNS
Weierstrass approximation theorem 0JQE130DHW
L'Hôpital's rule 0JWT4PPQ7B
Integral of 1/x 0K1N1Y4EGZ
Logarithm of a product 0K2FNY6DYV
Stirling's formula 0KC0F51T6A
Bolzano–Weierstrass theorem 0KDJD249DT
The exponential function is strictly increasing 0KN2V7840E
Derivative of x^a 0KY08TWDMQ
Mean value theorem for integrals 0N91N98EG5
The integral of a continuous function is an antiderivative 0NC2A3HWGT
Fundamental theorem of calculus 0NHGY0N0JB
Weierstrass M-test 0NX5NWAFC9
Sine is 2π-periodic 0P4NQD746K
A function with bounded derivative is Lipschitz 0P64VE79X3
Integral of a power 0Q3HYFT9RQ
Darboux's theorem 0Q5A47J48D
Irrationality of pi 0QHZX1PK8V
Continuity of the sum of a uniformly convergent series of functions 0R0MYT0BJD
pi is greater than 3 0R7SVNYTJS
Arccosine 0RDP2HEFEW
Logarithm is the inverse of the exponential 0RKW2X63YR
A continuous nowhere differentiable function 0RXK2Z808Q
Power-reduction formula for cosine 0S049HG1W5
Indeterminate form 0S7G92KKA7
Derivative of tangent 0SAMR34WXC
Normal convergence 0T0EJDGHMB
Power series of arctangent 0T32ME0A6H
Term-by-term differentiation 0TJ8QBJX5K
Real exponentiation 0TV07AQT62
Derivative of cosine 0V2DV29EGT
Logarithm of a power 0V948DE5KA
Dirichlet's test 0V9ME8GQE7
Improper integral of x^p on an unbounded interval 0VGKB2NC4T
Continuous functions on a closed bounded interval are uniformly continuous 0W0TZDRF9C
Tangent half-angle substitution 0W8ETY2AZ6
Integration by partial fractions 0WBTWFXJQG
x^2 sin(1/x) is differentiable with discontinuous derivative 0WDAKKN4NC
Taylor's theorem with the integral remainder 0WJGR81HBD
Extreme value theorem 0WS1A8E2P9
Wallis product 0XCYA4YERS
Dini's theorem 0XRRYF1HPE
Second fundamental theorem of calculus 0XYAFCN0PT
Absolutely convergent series converge 0Y123X48GA
Mercator series 0YZXNE3HFR
A function with nonnegative second derivative is convex 0Z41C17TGP
Cauchy criterion for sequences 0ZA4AX4MW3
The logarithm is strictly concave 0ZS54B9GJF