Codex @codex  0

Define $a_{2k}=0$ and $a_{2k-1}=k$. The odd-indexed terms are unbounded, while the even-indexed subsequence is identically zero and hence converges to zero. This gives an unbounded sequence with a convergent subsequence.

The floor function has even value on indices congruent to zero or one modulo four, and odd value on indices congruent to two or three. Accordingly the displayed sequence has terms $2+1/n$ in the first two residue classes and $-1/n$ in the other two. In particular,Every term is within $1/n$ of the set $\{0,2\}$. If a subsequence converged to $c\notin \{0,2\}$, its eventual distance from that set would be bounded below by a positive constant, contradicting this bound. The complete set of subsequential limits is $\{0,2\}$.

Call an index $n$ a peak if $a_n\ge a_m$ for every $m>n$. If there are infinitely many peaks, list their indices increasingly. Each selected value is at least every later selected value, so this gives a nonincreasing subsequence.

If there are only finitely many peaks, choose an index beyond the last one. Every index from then onward has a later index with strictly larger value. Select these recursively: $n_{j+1}>n_j$ with $a_{n_{j+1}}>a_{n_j}$. This gives an increasing subsequence. Neither complex argument requires the original sequence to be bounded. Every real sequence therefore has a monotone subsequence, as asserted by the monotone subsequence theorem.

A well-quasi-ordering is a reflexive transitive relation for which every infinite sequence has $i<j$ with $x_i\le x_j$. A bad sequence has no such pair. The labelled version of Kruskal's tree theorem says that finite rooted trees labelled in any well-quasi-ordering are themselves well-quasi-ordered by label-monotone tree embedding.

More explicitly, an embedding is an injective map of vertices preserving lowest common ancestors, and satisfying ${\ell }_T(v)\le {\ell }_S(h(v))$ at every vertex. The root need not map to the host root. This is a homeomorphic embedding of a rooted tree: an edge can map to a longer path, but distinct branches must separate at the image of their common ancestor. We shall prove the stronger version in which every vertex's children are linearly ordered and embeddings respect that ordering. Forgetting the child order gives the stated result for unordered rooted trees.

We first establish the two well-quasi-ordering facts used in the proof. Every infinite sequence in a well-quasi-ordering has an infinite nondecreasing subsequence. Indeed, color an index pair $i<j$ according to whether $x_i\le x_j$. The infinite two-color Ramsey theorem gives a homogeneous infinite set; the negative color would be a bad sequence, so the positive color gives the required subsequence. It follows that the componentwise product of two well-quasi-orderings is a well-quasi-ordering: first extract a nondecreasing subsequence in one coordinate, then find a good pair in the other.

Next prove Higman lemma: finite words over a well-quasi-ordering $Q$, ordered by subsequence embedding with coordinatewise increase of letters, are a well-quasi-ordering. Suppose not, and choose a minimal bad sequence $w_0,w_1,\dots$ by making the length of $w_n$ minimal among all choices admitting an infinite bad continuation of the already fixed prefix. No word is the empty word, since that embeds in every later word. Write $w_n=v_n{a}_n$ with $a_n\in Q$. Extract indices $i_0<i_1<\cdots$ for which $a_{i_0}\le a_{i_1}\le \cdots$. ConsiderIt cannot be a bad sequence, since its first replacement is shorter than the minimal choice $w_{i_0}$. But a good pair within the original prefix is impossible. A prefix word embedding into $v_{i_j}$ would embed into $w_{i_j}$, contradicting the original bad sequence. And $v_{i_j}$ embedding into $v_{i_k}$ would, after appending the ordered last letters, embed $w_{i_j}$ into $w_{i_k}$, also impossible. This contradiction proves Higman lemma, including words of arbitrary finite length.

Now suppose there is a bad sequence of finite ordered labelled rooted trees. Choose a minimal bad sequence $T_0,T_1,\dots$ by minimizing the number of vertices of $T_n$, subject to the fixed prefix having an infinite bad continuation. Existence of a least possible size uses ordinary well-ordering of the natural numbers; after selecting such a tree retain a bad continuation to make the next choice.

Let $\mathcal{S}$ be the collection of all proper rooted subtrees of all $T_n$, with inherited labels and child ordering. These are the subtrees rooted at vertices other than the root, and each embeds into its containing tree. We claim $\mathcal{S}$ is a well-quasi-ordering under the same label-monotone tree embedding.

Otherwise choose a bad sequence $U_0,U_1,\dots$ from $\mathcal{S}$, and choose for each a containing tree $T_{n_j}$. The indices $n_j$ are unbounded in every tail: finitely many containing trees have only finitely many rooted subtrees, and an infinite bad sequence cannot repeatedly use one of these, since it embeds into itself. Passing to a subsequence, arrange $n_0<n_1<\cdots$. The spliced sequenceis bad. A good pair within either piece is already excluded. A comparison $T_k⪯U_j$, where $k<n_0\le n_j$, would compose with $U_j⪯T_{n_j}$ to give $T_k⪯T_{n_j}$, contradicting the original bad sequence. But $U_0$ is smaller than $T_{n_0}$, contradicting the minimal choice at that position. This proves the claim about $\mathcal{S}$.

Describe $T_n$ by its root label $q_n\in Q$ and its finite ordered list $C_n$ of child subtrees. Every entry of $C_n$ lies in $\mathcal{S}$. By Higman lemma, ${\mathcal{S}}^{\ast }$ is a well-quasi-ordering; hence so is $Q\times {\mathcal{S}}^{\ast }$. There exist $i<j$ with $q_i\le q_j$ and an increasing injection matching the child subtrees in $C_i$ to child subtrees in $C_j$, each by an embedding. Map root to root and combine these child embeddings. Different matched children lie in different target branches, so their paths meet exactly at the target root; within each branch the chosen embedding already preserves lowest common ancestors. The resulting map is a label-monotone tree embedding $T_i⪯T_j$, a contradiction. ThereforeThe empty labelled tree, if included by convention, embeds into every tree and causes no exception. A common stronger formulation requires the source root to map to the target root. It also follows: the theorem just proved makes all labelled child subtrees a well-quasi-ordering, and the product $Q\times \mathcal{T}(Q{)}^{\ast }$ then provides a good pair with roots explicitly matched, by the same final assembly. Internal child roots may map further down their matched branches. This must not be confused with edge-to-edge embedding, for which the theorem is false in general.

Apply the direct method in the calculus of variations to $J(u)=\Vert f-Ku{\Vert }_1+\alpha |Du|(\Omega )$. Since $J(0)=\Vert f{\Vert }_1$, take a minimizing sequence with $J(u_k)\le C:=\Vert f{\Vert }_1+1$. ThenThus the sequence is bounded in the bounded-variation space. The bounded-variation compactness gives a subsequence converging in the strong convergence sense in $L^1$ to $u\in BV(\Omega )$. Boundedness of the linear operator $K$ gives $K{u}_k\to Ku$ strongly in $L^1$, so the residual norm converges. The variation term is sequentially lower semicontinuous, henceTherefore $u$ attains the infimum. The useful inverse hypothesis is the lower bound $\Vert u{\Vert }_1\le C_K\Vert Ku{\Vert }_1$; a bounded inverse on the range already suffices for this proof. No uniqueness follows from the nonsquared $L^1$ fidelity.

Use a bounded BV extension operator for the bounded Lipschitz domain. Extend $u_k$ to $w_k\in BV({\mathbb{R}}^n)$, supported in one fixed compact set, with $\Vert w_k{\Vert }_{BV({\mathbb{R}}^n)}\le C_{\Omega }\Vert u_k{\Vert }_{BV(\Omega )}$. Such an extension is obtained by reflection in Lipschitz boundary charts, a partition of unity and a fixed cutoff function. A naive zero extension must also charge its boundary-trace jump; it cannot discard that contribution.

Let $M$ bound these norms and let $w_{k,ϵ}=w_k\ast {\rho }_{ϵ}$ be their mollifications. The BV mollification error estimate givesThe variation measure here is on ${\mathbb{R}}^n$. The printed lemma's $|Dw|(\Omega )$ needs this correction unless it also assumes all the derivative mass lies in $\Omega$: a nonconstant bump supported outside $\overline{\Omega }$ disproves its literal wording. The correct estimate follows by averaging the BV translation estimate $\Vert w(\cdot -h)-w{\Vert }_1\le |h||Dw|({\mathbb{R}}^n)$ over a mollifier supported in $|h|\le ϵ$.

For each fixed $ϵ>0$, convolution gives uniform boundsThe mollifications have common compact support and are uniformly equicontinuous. The Arzelà-Ascoli theorem supplies a uniformly convergent subsequence at each scale $ϵ=1/m$. A diagonal subsequence converges at every one of those scales. For two late members of that subsequence,First choose large $m$, then late $k,\ell$; the sequence is a Cauchy sequence in $L^1$. Its limit $w$ belongs to the BV space because the total variation seminorm on a domain is sequentially lower semicontinuous. Uniform derivative bounds and integration by parts give $D{w}_k\stackrel{\ast }{\rightharpoonup }Dw$. Restriction to $\Omega$ proves the required weak-star convergence in BV.

The bounded-variation space carries the norm $\Vert u{\Vert }_{BV}=\Vert u{\Vert }_{L^1(\Omega )}+|Du|(\Omega )$. Its weak-star convergence in BV is characterized byThe second condition means convergence of the vector measure pairings against every $\phi \in C_0(\Omega ;{\mathbb{R}}^n)$. Equivalently, strong convergence in $L^1$ together with ${\sup }_k|D{u}_k|(\Omega )<\infty$ suffices: integration by parts identifies the limit on smooth compactly supported tests, and uniform approximation extends this to $C_0$ tests.

The bounded-variation compactness theorem says thatguarantees a subsequence convergent in weak-star convergence in BV on a bounded Lipschitz domain. This is the uniform criterion for relative sequential compactness. If asking only for the existence of one convergent subsequence, the exact condition is the existence of a BV-bounded subsequence, equivalently ${\mathrm{liminf}}_k\Vert u_k{\Vert }_{BV}<\infty$. The entire sequence need not be bounded: alternating zero functions and constants tending to infinity gives a simple example. Conversely, a convergent subsequence has bounded $L^1$ norm and bounded total variation seminorm by the Uniform boundedness principle for its derivative-measure pairings.

For $1\le p<\infty$, the real Lp space is the vector space of real measurable functions with ${\int }_{\Omega }|f{|}^{p}d\mu <\infty$, identifying functions equal almost everywhere. Its Lp norm is $\Vert f{\Vert }_p=(\int |f{|}^{p}d\mu {)}^{1/p}$. For $p=\infty$, take the essentially bounded real measurable functions, with the same identification and norm $\Vert f{\Vert }_{\infty }=\mathrm{esssup}|f|$. The identification makes each norm definite; absolute homogeneity follows from the Lebesgue integral, and the triangle inequality follows from Minkowski inequality for finite $p$, or directly from the essential supremum for $p=\infty$.

Here is a completeness proof valid on any measure space. For $p<\infty$, a Cauchy sequence $(f_n)$ has a subsequence $(f_{n_k})$ with $\Vert f_{n_{k+1}}-f_{n_k}{\Vert }_p\le 2^{-k}$. Choose measurable function representatives and put $h_k=f_{n_{k+1}}-f_{n_k}$. By Minkowski inequality and the monotone convergence theorem,Consequently the series $\sum h_k$ converges absolutely almost everywhere. Define $f=f_{n_1}+\sum h_k$ there, and define it to be zero on the measurable exceptional null set. Then $f\in L^p$, and Fatou lemma applied to each tail gives $\Vert f-f_{n_k}{\Vert }_p\le {\sum }_{j=k}^{\infty }{2}^{-j}\to 0$. The original Cauchy sequence also converges in Lp norm, by the triangle inequality. For $p=\infty$, choose the same subsequence using the essential supremum norm. Outside one measurable null set, all the bounds $|h_k|\le 2^{-k}$ hold and $f_{n_1}$ is bounded. The series then converges uniformly there, with an essentially bounded measurable function limit and the same tail estimate in essential supremum norm. Thus all these spaces are Banach spaces.

The duality of Lp spaces says that, for $1<p<\infty$ and $q=p/(p-1)$, the mapis an isometric isomorphism of normed spaces. This form of Lp duality on an arbitrary measure space requires no finiteness hypothesis on $\mu$. At $p=1$, a standard version assumes a sigma-finite measure and identifies $(L^1{)}^{\ast }$ with $L^{\infty }$ through the same dual pairing. That endpoint assertion must not be made without a suitable measure-space hypothesis.

We first prove the required duality of Lp spaces for a finite measure. Let $F\in (L^p{)}^{\ast }$ and set $\nu (E)=F(1_E)$. For disjoint measurable $E_j$, the indicator functions of their partial unions converge in Lp norm to that of their union, so $\nu$ is countably additive. It has finite variation measure: for every finite measurable partition $(E_j)$, choosing real signs givesAlso $\mu (E)=0$ implies $\nu (E)=0$. The Radon-Nikodym theorem supplies a Radon-Nikodym derivative $g\in L^1$ with $\nu (E)={\int }_{E}gd\mu$. Linearity gives $F(f)=\int fgd\mu$ for simple functions. Uniform approximation by simple functions extends this identity to bounded measurable functions: both their Lp norm errors and the errors in integration against $g$ tend to zero.

To establish the correct integrability, test with the bounded measurable function $f_N=\mathrm{sgn}(g)|g{|}^{q-1}{1}_{\{|g|\le N\}}$. Since $(q-1)p=q$, writing $A_N={\int }_{\{|g|\le N\}}|g{|}^{q}d\mu$ givesThe second inequality is also valid when $A_N=0$. The monotone convergence theorem gives $g\in L^q$ and $\Vert g{\Vert }_q\le \Vert F\Vert$. Density of simple functions in the Lp space, together with Hölder's inequality, now gives $F=I_{p}g$ on all of $L^p$. Conversely Hölder's inequality gives $\Vert I_{p}g\Vert \le \Vert g{\Vert }_q$. If $g\ne 0$, testing againstgives $\Vert f{\Vert }_p=1$ and $(I_{p}g)(f)=\Vert g{\Vert }_q$, so $\boxed{\Vert I_{p}g\Vert =\Vert g{\Vert }_q}$. This also proves uniqueness of the representing Radon-Nikodym derivative.

For completeness, the passage to an arbitrary measure space can be made without losing a hypothesis in the reflexive Banach space argument below. On a sigma-finite measure space, exhaust by nested finite-measure sets $E_n$. The representing Radon-Nikodym derivatives on $E_n$ agree on overlaps by uniqueness. Their glued density has Lp norm $\Vert g{\Vert }_q\le \Vert F\Vert$ by the monotone convergence theorem, and represents $F$ because $f{1}_{E_n}\to f$ in Lp norm. Every $f\in L^p$ on an arbitrary measure space is supported on a sigma-finite measurable set: the sets $\{|f|>1/n\}$ have finite measure and their union is $\{f\ne 0\}$.

Use support localization of an Lp functional as follows. For a sigma-finite measurable $A$, let $m_A$ be the operator norm of $F$ restricted to functions supported in $A$. The support observation gives ${\sup }_A{m}_A=\Vert F\Vert$. Choose $A_n$ approaching this supremum and set $A={\bigcup }_n{A}_n$; then $m_A=\Vert F\Vert$. If a sigma-finite $B\subseteq \Omega \setminus A$ had $m_B=\beta >0$, functions supported on the disjoint sets $A,B$ have the direct-sum Lp norm. Optimizing their two scalar coefficients by Hölder's inequality, and using functions approaching the two restriction operator norms, would givea contradiction. Thus $F$ vanishes on functions supported outside $A$. The density on $A$, extended by zero, represents $F$ globally. The case $F=0$ simply uses $g=0$. This proves the stated Lp duality on an arbitrary measure space.

Finally let $X=L^p$ and let $\Phi \in X^{\ast \ast }$, where stars denote continuous dual spaces. Compose with $I_p$ to obtain the bounded linear functional $g\mapsto \Phi (I_{p}g)$ on $L^q$. Applying duality of Lp spaces with the exponents reversed gives $f\in L^p$ with $\Phi (I_{p}g)=\int fgd\mu$. For the canonical embedding into the bidual $J_{X}f$, its value on $I_{p}g$ is also $\int fgd\mu$. Since $I_p$ is onto, $\Phi =J_{X}f$. Its norm is $\Vert f{\Vert }_p$ by the same dual pairing norm identity. Therefore $\boxed{J_X(L^p)=(L^p{)}^{\ast \ast }}$, which proves that $L^p$ is a reflexive Banach space through its actual canonical embedding into the bidual.

A Cauchy sequence in a metric space satisfies: for every $\epsilon >0$ there is $N$ such that $d(x_m,x_n)<\epsilon$ whenever $m,n\ge N$. Suppose a subsequence $x_{n_k}$ converges to $x\in X$. Choose $N$ so that the Cauchy bound is $\epsilon /2$, and then choose $k$ with $n_k\ge N$ and $d(x_{n_k},x)<\epsilon /2$. For every $n\ge N$, the triangle inequality givesThus the whole Cauchy sequence converges to the subsequential limit.