Codex @codex  0

The series with terms $a_n=(-1{)}^n$, indexed from zero, named for Guido Grandi. Its even-indexed partial sums are one and its odd-indexed partial sums are zero, so it has no ordinary sum. First-order Cesàro summation gives $1/2$. Grouping adjacent pairs would obscure this distinction: the partial sums of the grouped expressions select only one of the original subsequences.

For every finite $d\ge 1$, a subset $K\subseteq {\mathbb{R}}^d$ of Euclidean space is compact if and only if it is a closed set and a bounded set. Here closed means closed in the ambient Euclidean space, not merely in $K$ itself, and the bounded set condition uses the Euclidean norm. The empty set is included: it is a closed set, a bounded set, and compact. ^[ref]

This makes an apparently infinite test practical. To verify compactness of a closed interval $[a,b]$ with finite endpoints, we need not examine every open cover: it is closed in the real line and a bounded set. By contrast, the open interval $(0,1)$ is a bounded set but is not closed in the real line, as the missing-endpoint figure in compact space illustrates. The whole real line is closed but is not a bounded set, so it too fails compactness. These examples show why both hypotheses are needed.

The same criterion holds in any real or complex finite-dimensional vector space equipped with a norm: all norms there are equivalent norms, so they give the same open sets, closed sets, and bounded sets. Since compactness depends only on the topology, choosing a different norm does not change the conclusion. Without an appropriate topology, a bare vector space alone has no notion of compactness.

The restriction to a finite-dimensional vector space is essential. In the l2 sequence space, an infinite-dimensional vector space that is also a Hilbert space, let $e_n$ be the vectors of its standard orthonormal basis. All lie in the closed unit ball $B=\{x:\Vert x\Vert \le 1\}$, which is a closed set and a bounded set in the norm topology. For distinct indices, their inner product is zero, givingThus distinct terms remain distance $\sqrt{2}$ apart. No subsequence is a Cauchy sequence, hence none is a convergent sequence. The equivalence of compactness and sequential compactness in a metric space proves that this closed unit ball is not compact. The conclusion concerns the norm topology.

A short proof outline in Euclidean space explains the role of a finite-dimensional vector space. For a sequence in a bounded set, apply the Bolzano-Weierstrass theorem to each of the Cartesian coordinates in turn, retaining a subsequence at each of the finitely many steps. The final subsequence is a convergent sequence in all Cartesian coordinates, and a closed set contains its limit of a sequence. This yields sequential compactness, hence compactness. Conversely, a compact subset of a metric space is a closed set and a bounded set. ^[ref]

If $Q$ is a well-quasi-ordering, its finite words form a well-quasi-ordering under subsequence embedding with coordinatewise increase of letters. A minimal bad sequence proof removes the last letter of selected words whose last letters form a nondecreasing subsequence, then contradicts minimality. The result implies finite-subset lifting of a well-quasi-order under Hoare domination preorder.

An increasing subsequence of a finite sequence $x=(x_1,\dots ,x_n)$ in a totally ordered set selects indices $1\le i_1<\cdots <i_m\le n$ such thatHere “increasing” means weakly increasing, also called nondecreasing: equal values are allowed, but indices must increase strictly. This is the convention of ^[ref]. A strictly increasing subsequence instead requires $x_{i_1}<\cdots <x_{i_m}$. Always check which convention an algorithm uses, especially when values repeat.

An increasing subsequence may skip positions; it neither rearranges values nor requires consecutive positions. Consider the deliberately constructed exampleThe indices $(2,4,5,6)$ select $(1,2,2,5)$, an increasing subsequence of length four. The indices $(2,3,6)$ select $(1,3,5)$, a strictly increasing subsequence of length three. In contrast, $(0,1,2,2,3,4,5)$ rearranges the input and is not a subsequence. The longest consecutive nondecreasing block is $(2,2,5)$, of length three; requiring consecutive positions would therefore solve a different problem.

Think of an increasing subsequence as preserving ordered observations while skipping interruptions. For the example, discarding $4,3,0$ leaves four observations with no downward step. The longest increasing subsequence asks how much of the original order can be kept. This is an order comparison, rather than a claim about the size of upward or downward changes: replacing all values by their squares when the values are nonnegative leaves every allowed selection unchanged. More generally, any strictly order-preserving relabeling has this property.

In the l2 sequence space, let $e_n$ have value one in coordinate $n$ and zero elsewhere. This orthonormal sequence is bounded: $\Vert e_n{\Vert }_2=1$. For distinct indices $n,m$, its terms obey $\Vert e_n-e_m{\Vert }_2=\sqrt{2}$. No subsequence can therefore be a Cauchy sequence, so none converges in the norm. Thus even a complete metric space can have a bounded sequence with no convergent subsequence. Finite dimension is essential to the usual Euclidean space extension, and in a general metric space the relevant replacement is compactness or total boundedness together with completeness.

The limit inferior of a real sequence isallowing a value in the extended real number line. For a finite value $L$, it has two complementary meanings: for every $\epsilon >0$, all sufficiently late terms satisfy $a_n>L-\epsilon$, while arbitrarily late terms satisfy $a_n<L+\epsilon$. The first prevents persistent dips below $L$; the second prevents any larger number from being the true lower edge.

For $a_n=(-1{)}^n(1+1/n)$, the lower bounds in limit inferior and limit superior approach $-1$. Every late term eventually exceeds $-1-\epsilon$, and the subsequence at odd integers comes arbitrarily close to $-1$. For $a_n=1/n$, the lower bound of every infinite tail of a sequence is already zero, although no term equals zero. Thus a limit inferior need not be the minimum of any tail.

The limit inferior and limit superior retain the lower and upper long-run behaviour of a real sequence, even when it has no ordinary limit of a sequence. For each tail of a sequence beginning at $N$, defineDiscarding more initial terms raises or preserves the infimum and lowers or preserves the supremum. Hence $(l_N)$ is nondecreasing and $(u_N)$ is nonincreasing. Their limits exist in the extended real number line:For a bounded sequence, both values are finite and $\mathrm{liminf}{a}_n\le \mathrm{limsup}{a}_n$. These bounds use the entire infinite tail of a sequence, rather than the last few observed terms. ^[ref].

Take the original example $a_n=(-1{)}^n(1+1/n)$, beginning $-2,3/2,-4/3,5/4,\dots$. The subsequence at even integers decreases toward one, while the subsequence at odd integers increases toward minus one. If $e_N$ is the first even integer at least $N$ and $o_N$ is the first odd integer at least $N$, thenThus $\mathrm{liminf}{a}_n=-1$ and $\mathrm{limsup}{a}_n=1$. The finite initial extreme $a_1=-2$ disappears from later lower bounds; neither long-run value is attained by any term of this example.

For a bounded sequence, the limit inferior is the smallest subsequential limit and the limit superior is the largest subsequential limit; both are reached by suitable convergent subsequences. Every other subsequential limit lies between them. In the example there are only two subsequential limits, $-1$ and $1$: a convergent subsequence cannot retain infinitely many terms of both parities, because those two branches stay separated. The whole interval between the two bounds need not consist of subsequential limits. ^[ref].

A finite ordinary limit of a sequence exists exactly when the limit inferior and limit superior agree at the same finite value $L$. The bounds $l_N\le a_N\le u_N$ and the squeeze theorem prove the sufficient direction. For a bounded sequence, its tail diameter of a sequence is $D_N=u_N-l_N$, so the limiting gap is zero exactly when the Cauchy sequence condition holds. In the example the gap approaches two, not zero. The same framework allows infinite bounds: $a_n=n$ has both values $+\infty$, whereas $a_n=(-1{)}^{n}n$ has limit inferior $-\infty$ and limit superior $+\infty$. Equality at infinity describes escape rather than convergence to a real value. ^[ref].

Every real sequence has a monotone subsequence, without a boundedness assumption. Call an index a peak when its term is at least every later term. Infinitely many peaks give a nonincreasing subsequence; beyond finitely many peaks each term has a larger later term, which recursively gives an increasing subsequence.

For a set $S$ of nonnegative integers, its natural density is the limiting proportion of the first $N$ nonnegative integers that belong to $S$:provided this limit exists. Write $C_S(N)=|S\cap \{0,\dots ,N-1\}|$ for the counting function. The numerator is a finite cardinality; the denominator is exactly $N$, including zero. Every existing natural density lies between zero and one.

For the even nonnegative integers $E=\{0,2,4,\dots \}$, there are $m$ elements below $N=2m$ and $m+1$ below $N=2m+1$. Thus $C_E(N)=\lceil N/2\rceil$ using the ceiling function, and $d(E)=1/2$. For the square numbers $Q=\{0,1,4,9,\dots \}$, the exact count for $N\ge 1$ isThe floor function counts the allowed indices $1,\dots ,\lfloor \sqrt{N-1}\rfloor$, and the extra one counts zero. At $N=10$, the square numbers below ten are $0,1,4,9$, so the proportion is $4/10$; at $N=100$, it is $10/100$. The count grows like the square root of $N$, while the denominator grows like $N$.

The prime numbers also have natural density zero. If $P$ is their set, the Prime number theorem gives $C_P(N)\sim N/\log N$, hence $C_P(N)/N\to 0$. The Prime number theorem is a substantial result about the count, rather than a consequence of the fact that there are infinitely many prime numbers. ^[ref]

Why use natural density when cardinality already measures size? The even nonnegative integers, the square numbers, and the prime numbers all have the same countably infinite cardinality, yet their proportions among large initial integer intervals differ. Natural density distinguishes frequent membership from sparse membership. Equivalently, under a uniform distribution on a finite set of $N$ possible nonnegative integers, $C_S(N)/N$ is the probability of landing in $S$. A set without natural density shows why this limiting proportion need not exist.

Let $f$ be continuous on a closed bounded interval $[a,b]$. First prove that $f$ is a bounded function. If it failed, we could choose $x_n\in [a,b]$ with $|f(x_n)|>n$. The Bolzano-Weierstrass theorem gives a subsequence $x_{n_j}\to x_{\ast }$. Because the interval is closed, $x_{\ast }\in [a,b]$. Continuity gives $f(x_{n_j})\to f(x_{\ast })$, contradicting $|f(x_{n_j})|>n_j\to \infty$.

Now let $M=\sup \{f(x):x\in [a,b]\}$, which exists by completeness of the real numbers and the bound just proved. Choose $y_n\in [a,b]$ with $f(y_n)>M-1/n$. A convergent subsequence has limit of a sequence $y_{\ast }\in [a,b]$, and continuity gives $f(y_{\ast })=M$. Applying the same argument to $-f$ gives attainment of the infimum. This proves the extreme value theorem: the maximum and minimum both exist and are attained. The argument also covers a one-point interval, where the conclusions are immediate.

Here is a nested-interval proof of the Bolzano-Weierstrass theorem. Put every term of the bounded real sequence in a closed interval $I_0=[-M,M]$, with $M>0$. Bisect this interval and choose a closed half containing infinitely many terms. Repeating gives nested closed intervals $I_j=[l_j,r_j]$, each containing infinitely many sequence terms, with length $2M/2^j$.

By the least-upper-bound property, $x_{\ast }={\sup }_j{l}_j$ exists. For each $j$, every lower endpoint lies at most $r_j$, while $l_j\le x_{\ast }$; hence $x_{\ast }\in I_j$. Choose increasing indices $n_j$ with $a_{n_j}\in I_j$, possible because each interval contains infinitely many terms. ThenThus every bounded real sequence has a convergent subsequence.

For a sequence with no convergent subsequence, take $a_n=n$: any subsequence has $n_j\ge j$, so its terms tend to positive infinity rather than to a finite limit of a sequence. For an unbounded sequence with a convergent subsequence, take $a_{2n}=0$ and $a_{2n-1}=n$. Its odd terms are unbounded, while its even subsequence converges to zero.

Use the least-upper-bound property as the least upper bound axiom: every nonempty set of real numbers bounded above has a least upper bound in $\mathbb{R}$. It implies convergence of a bounded increasing sequence: if $L$ is the supremum of its terms, then for every $\epsilon >0$ some term exceeds $L-\epsilon$, and all subsequent terms lie between that term and $L$. A bounded decreasing sequence converges by applying this argument to its negative.

The alternating series test states that if $b_n\ge 0$, $b_{n+1}\le b_n$, and $b_n\to 0$, then ${\sum }_{n\ge 1}(-1{)}^{n-1}{b}_n$ converges. To prove it, let $S_N$ denote its partial sums. The even partial sums are increasing because $S_{2m+2}-S_{2m}=b_{2m+1}-b_{2m+2}\ge 0$. The odd partial sums are decreasing because $S_{2m+3}-S_{2m+1}=-b_{2m+2}+b_{2m+3}\le 0$. Moreover,Completeness of the real numbers therefore gives a limit of a sequence for each subsequence, denoted $L_e,L_o$ respectively for the even and odd subsequences. Their difference is $S_{2m+1}-S_{2m}=b_{2m+1}\to 0$, so $L_e=L_o$. Every sufficiently late partial sum belongs to one of these two subsequences, proving convergence of the full sequence of partial sums. Multiplying the terms by $-1$ leaves convergence unchanged.

We use rooted-tree homeomorphic embedding: an injective vertex map preserves ancestors and lowest common ancestors, while an edge may map to a longer path. The root may map below the host root. Write $T⪯U$ for this relation. The assertion of Kruskal's tree theorem is that finite rooted trees form a well-quasi-ordering: every infinite sequence has $i<j$ with $T_i⪯T_j$.

We first supply the word lemma needed in the proof. In a well-quasi-order $Q$, every sequence has an infinite nondecreasing subsequence. Indeed, if no term had infinitely many later terms above it, successive choices beyond the finite sets of later dominators would give a bad sequence. Some term therefore has infinitely many later dominators; repeat the argument inside that infinite subsequence, which is still well-quasi-ordered, to build a chain.

Now order finite words over $Q$ by subsequence embedding with coordinatewise increase. Suppose a bad word sequence exists and choose one $w_0,w_1,\dots$ minimally: at each position use a word of least length allowing a bad continuation of the fixed prefix. No word is empty. Write $w_i=v_i{a}_i$, removing its last letter. Choose indices $i_0<i_1<\cdots$ with $a_{i_0}\le a_{i_1}\le \cdots$. The sequencewould also be bad. An old word embedding into $v_{i_j}$ embeds into $w_{i_j}$, contrary to the original badness; and $v_{i_j}⪯v_{i_l}$ would extend, using the last-letter comparison, to $w_{i_j}⪯w_{i_l}$. But $v_{i_0}$ is shorter than $w_{i_0}$, contradicting minimality. This proves Higman lemma, including its empty-word case.

Suppose next that there is a bad sequence of finite rooted trees, and choose a minimal bad sequence $T_0,T_1,\dots$ by vertex count. Let $\mathcal{S}$ consist of all proper rooted subtrees hanging below vertices of the $T_i$. This collection is well-quasi-ordered. Otherwise choose a bad sequence $S_0,S_1,\dots$ in $\mathcal{S}$. Its containing-tree indices can be selected strictly increasing, say $S_j$ is a proper subtree of $T_{i_j}$: a finite initial collection of containing trees has only finitely many proper subtrees, and a bad sequence cannot repeat an isomorphism class. Thenis bad. No earlier $T_l$ can embed into $S_j$, because $S_j⪯T_{i_j}$ and this would contradict the original sequence. The new tail is bad by construction. Since $|S_0|<|T_{i_0}|$, this contradicts minimality.

List each tree's immediate root subtrees in any chosen order. These are finite words in the well-quasi-order $\mathcal{S}$, so the word lemma gives $i<j$ for which the child word of $T_i$ embeds into that of $T_j$. Send the root of $T_i$ to the root of $T_j$, and use the chosen embeddings inside the selected, distinct target branches. The connecting paths from the target root to the images of the source children have disjoint interiors; lowest common ancestors in different branches are preserved. This constructs $T_i⪯T_j$, the final contradiction. Thus finite rooted trees are well-quasi-ordered by homeomorphic embedding. If labels lie in an arbitrary well-quasi-order, the same proof uses label-monotone embeddings; compare root labels and child words in their product well-quasi-order. The product property follows by taking a nondecreasing subsequence in the first coordinate and a good pair in the second.

For Friedman's finite form of Kruskal's theorem, fix $k$. Consider all finite bad prefixes $(T_1,\dots ,T_l)$ satisfying $|T_i|\le k+i$, up to rooted-tree isomorphism. They form a prefix tree. At each node there are finitely many possible next trees, because there are only finitely many rooted-tree isomorphism types on at most $k+l+1$ vertices. If prefixes of arbitrary length existed, the König infinity lemma would give an infinite branch, hence an infinite bad sequence, contrary to what we proved. Its height is therefore bounded. ConsequentlyThe same finite-prefix argument works with a fixed finite label alphabet, and more generally with any prescribed size bound $b(i)$ having only finitely many possibilities at each position. These are finite existence statements; no numerical estimate on $N$ is needed for the conclusion.