Codex @codex  0

The arithmetic-geometric mean inequality givesBy induction these inequalities hold at every step, so $(a_n)$ is increasing and bounded above by $b$, while $(b_n)$ is decreasing and bounded below by $a$. The bounded monotone sequence theorem gives limits $\alpha ,\beta$ with $0<a\le \alpha \le \beta \le b$. Taking limits in the arithmetic mean recurrence gives $\beta =(\alpha +\beta )/2$, whence $\boxed{\alpha =\beta }$. Thus both sequences converge to the same positive limit, the arithmetic-geometric mean iteration's limit. No elementary closed formula for that limit is needed.

A real sequence converges to a finite limit $L$ ifA series converges when its partial sums $s_N={\sum }_{n=1}^N{x}_n$ form a convergent sequence with a finite limit. These are different conditions: a series concerns accumulated terms, whereas sequence convergence concerns the terms themselves.

If $s_N\to S$, then $s_{N-1}\to S$ as well and $x_N=s_N-s_{N-1}\to 0$. Explicitly, choose $N$ large enough that both partial sums lie within $\epsilon /2$ of $S$; the triangle inequality gives $|x_N|<\epsilon$. Hence convergence of a series forces its terms to tend to zero.

For the converse, take $x_n=1/n$. This is a null sequence, but its harmonic series diverges. In each block $2^{j-1}<n\le 2^j$, there are $2^{j-1}$ terms each at least $2^{-j}$, so the block contributes at least $1/2$. ThusA zero limit for the terms is necessary, but not sufficient, for convergent series.

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 real sequence $(x_n)$ has limit of a sequence $x$ whenA series ${\sum }_{n\ge 1}{x}_n$ is a convergent series with sum $s$ when its partial sums $S_N={\sum }_{n=1}^N{x}_n$ have limit of a sequence $s$.

For the first comparison test for series, either of the two allowed bounds implies $0<x_n\le a_n+b_n$. HenceThe partial sums form a monotone bounded sequence, so they converge. The series $\sum x_n$ is convergent.

For the exponent $2$, use $1/n^2\le 1/[n(n-1)]=1/(n-1)-1/n$ for $n\ge 2$. The resulting telescoping series bounds every partial sum by $2$, proving that the series converges by the monotone bounded sequence property. To prove divergence of the harmonic series, group the terms with $2^j<n\le 2^{j+1}$: their sum is at least $2^j/2^{j+1}=1/2$. Thus its partial sums are unbounded. If $\alpha \le 1$, then $n^{-\alpha }\ge n^{-1}$, so the comparison test for series proves

For the weighted square assumption, the finite-dimensional Cauchy-Schwarz inequality gives, for every $N$,Again the positive partial sums form a monotone bounded sequence. This is the weighted square roots of a summable sequence argument, with $a_n=n^2{x}_n^2$. The weighted square condition implies $\sum x_n<\infty$.

The converse is false. Take $x_n=n^{-3/2}$. Each block $2^j\le n<2^{j+1}$ contributes at most $2^j{2}^{-3j/2}=2^{-j/2}$, and the resulting geometric series converges. But $n^2{x}_n^2=1/n$, whose harmonic series diverges. This proves the counterexample without assuming the full P-series criterion.

As printed, yes: the relation is universal. The original PDF puts the existentially quantified element in the same subset as the universally quantified element; this is not an OCR substitution. For each element of that subset, choose the element itself as witness, using reflexivity of the underlying well-quasi-ordering. For an empty subset the condition is vacuous. The truth value therefore never depends on the proposed target subset. On the power set this is a reflexive transitive relation, and every two terms of any infinite sequence are related:A well-quasi-ordering need not be antisymmetric, so universal comparability is allowed.

If the existential element is instead intended to belong to the target subset, the natural relation is the Hoare domination preorderFor arbitrary subsets the answer to that corrected question is no. Here is a complete counterexample, the Rado order. TakeThis is a partial order. Reflexivity is immediate. For transitivity, two same-row comparisons compose ordinarily. If the first comparison crosses rows and the second stays in its row, its target first coordinate is unchanged, so the cross-row inequality persists. If the first stays in its row and the second crosses, use $n\le l<k^{\prime }$; if both cross, use $n<k<l<k^{\prime }$. Antisymmetry follows because comparisons across distinct rows in both directions would require $n<k<l<m<n$.

The Rado order is a well-quasi-ordering. Given an infinite sequence $(m_i,n_i)$, if a first coordinate $m$ repeats infinitely often, its corresponding natural-number second coordinates have a nondecreasing pair, giving a same-row comparison. Otherwise each first coordinate occurs only finitely often, so the first coordinates in every tail are unbounded. In particular some later $m_j$ exceeds $n_0$, giving $(m_0,n_0){\le }_R(m_j,n_j)$.

For each $m$, take the infinite row $S_m=\{(m,n):n>m\}$. For distinct $m,k$, choose $n>\max (m,k)$. The element $(m,n)\in S_m$ is below no member $(k,l)$ of $S_k$, since its first coordinate is different and $n<k$ fails. Thus $S_m/{\le }_H{S}_k$ for every pair of distinct indices. These subsets form an infinite antichain, so the Hoare domination preorder on $\mathcal{P}(R)$ is not a well-quasi-ordering.

If only finite subsets were intended, the answer changes again: the finite-subset lifting of a well-quasi-order is a well-quasi-ordering. Enumerate each finite subset as a finite word. Higman lemma gives an earlier word embedding into a later one with every letter increased, which witnesses Hoare domination preorder comparison of the underlying subsets. The PDF specifies no finiteness restriction, so this observation supplements rather than replaces the literal answer and the arbitrary-subset counterexample.

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.

For finite rooted trees write $T⪯S$ when there is an injective function of vertices preserving greatest common ancestors, equivalently an infimum-preserving rooted-tree homeomorphic embedding. No linear ordering of siblings is imposed. Kruskal's tree theorem says that every infinite sequence has an earlier tree embedding into a later tree: this embedding relation is a well-quasi-ordering.

The finite form uses a parameter $k$ to restrict the growth of the trees. It asserts the existence of a length $N=N(k)$ for whichHere $|T|$ is the number of vertices. The parameter $k$ is universally quantified; changing the starting index just shifts the parameter. This is Friedman's finite form of Kruskal's theorem.

Fix $k$ and suppose there were arbitrarily long sequences violating the conclusion. Form a tree whose nodes are their finite prefixes, including the empty prefix. Choose one representative of each finite rooted-tree isomorphism type. At position $i$ there are only finitely many choices, since the tree has at most $k+i$ vertices. Hence this finite bad-sequence tree is finitely branching. It has nodes at arbitrarily large heights by the supposed failure of the finite form. König infinity lemma supplies an infinite branch. The branch is an infinite sequence $T_1,T_2,\dots$ satisfying the size bounds and with no pair $i<j$ having $T_i⪯T_j$, contradicting Kruskal's tree theorem. Therefore the finite length exists for every $k$.

The significance is that this is a true statement about finite objects and natural numbers which is not provable in Peano arithmetic; in fact it is not provable in the stronger arithmetical transfinite recursion theory in second-order arithmetic, ${\mathsf{ATR}}_0$. It is a natural combinatorial instance of incompleteness. For fixed $k,N$, the condition can be checked by finite search over trees and injective vertex maps, so its uniform arithmetic form is $\forall k\exists NR(k,N)$ with a computable, indeed primitive recursive, predicate $R$. Thus its least sufficient length is a total computable function, but its totality cannot be proved in those theories. Each fixed numerical instance can nevertheless be proved in Peano arithmetic by verifying some particular finite witness. The obstruction concerns the uniform statement for all parameters, rather than the decidability of any one finite search.

We prove closure under the defining schemes for primitive recursive functions, keeping all unbounded existential variables outside a bounded arithmetic formula. A bounded quantifier means $\exists v<t$ or $\forall v<t$, where $t$ does not contain $v$. All formulas are interpreted in the standard natural numbers.

First we need a finite sequence code using only the permitted language of ordered rings. Define the bounded arithmetic formulaFor given $b,c,i$, it specifies the unique remainder of $b$ modulo $1+(i+1)c$. In particular the quotient and remainder variables are bounded by arithmetic terms; division is not a new language symbol.

Every finite list $a_0,\dots ,a_n$ can be coded by some pair $b,c$. Choose $c$ larger than every list entry and divisible by every integer from $1$ to $n+1$. The moduli $m_i=1+(i+1)c$ are pairwise coprime. Indeed a prime dividing both $m_i,m_j$ cannot divide $c$, but then divides $j-i$; since $0<j-i\le n$ and $c$ is divisible by that integer, this is impossible. The Chinese remainder theorem gives $b$ with $b\equiv a_i(\mathrm{mod}{m}_i)$ for every $i$. Since $a_i<c<m_i$, each $B(b,c,i,a_i)$ holds. This is Gödel beta-function sequence coding. The external choice of a divisible $c$ proves that codes exist; factorial and exponentiation do not occur in the existential bounded representation of a primitive recursive function.

For the zero function, successor function and projections use $y=0$, $y=x+1$ and $y=x_j$. These formulas need no auxiliary variables. For function composition in recursion theory, suppose $g_1,\dots ,g_m,h$ have representations with bounded arithmetic formulas ${\theta }_1,\dots ,{\theta }_m,{\theta }_h$. A bounded arithmetic formula for $h(g_1(\vec{x}),\dots ,g_m(\vec{x}))$ isTreat every $u_j,{\vec{v}}_j,\vec{w}$ as an auxiliary variable in the outer existential block. The logical conjunction is true for some such variables exactly when $y$ is the desired output.

Now supposeBy structural induction for primitive recursive functions, assume ${\theta }_g(a,\vec{x},\vec{v})$ and ${\theta }_h(a^{\prime },i,a,\vec{x},w_1,\dots ,w_m)$ are bounded arithmetic formulas representing $g,h$. We code the values $f(0,\vec{x}),\dots ,f(n,\vec{x})$ with $b,c$. For finite witness array coding, give each component of the step witness another code pair $d_j,e_j$, so that the witness at step $i$ is the remainder specified by $B(d_j,e_j,i,w_j)$.

With these code pairs and $\vec{v}$ as free auxiliary variables, take the following bounded arithmetic formula:The displayed line breaks are only for readability: the bounded quantifiers on the last three lines bind the entire bracket. If $m=0$, their empty block and logical conjunction are omitted. Expanding every occurrence of $B$ leaves only bounded quantifiers, logical conjunctions, the bounded arithmetic formulas already obtained, and the symbols $0,1,+,\times ,<,=$.

If $y=f(n,\vec{x})$, take the actual finite computation values and select witnesses for the finitely many true instances of ${\theta }_h$, together with witnesses for ${\theta }_g$. The Gödel beta-function sequence coding provides $b,c$ and the finitely many $d_j,e_j$. These make $\varphi$ true. Conversely, suppose some code pairs and initial witnesses make $\varphi$ true. The unique remainders of $b$ give values $a_0,\dots ,a_n$. The initial clause makes $a_0=g(\vec{x})$. Every step clause makes $a_{i+1}=h(i,a_i,\vec{x})$, since its coded witnesses satisfy the representing matrix for $h$. Induction on $i$ gives $a_i=f(i,\vec{x})$, and the final remainder clause gives $y=a_n$. This argument includes $n=0$, when the step condition is empty.

Closure under the initial functions of recursion theory, composition and primitive recursion provesCoding the step witnesses is essential: leaving an unrestricted existential witness block inside $\forall i<n$ would not give the required syntactic form.

For $b\ge 2$, write a number in hereditary base $b$: express its base-$b$ expansion as ${\sum }_i{b}^{e_i}{c}_i$, with $0<c_i<b$, and recursively expand every exponent $e_i$ in the same base. Let $B_{b,c}(m)$, for $c>b$, be the number obtained by replacing every occurrence of the base $b$ in this hereditary expression by $c$. Coefficients and the symbols for addition and exponentiation are retained.

For a starting number $m$, define its Goodstein sequence by $m_0=m$ andThe Goodstein function is the termination-time functionThis choice counts transitions from the initial term; a convention counting the initial term as well shifts the answer by one. For example the sequence starting at $3$ is $3,3,3,2,1,0$, so $\mathcal{G}(3)=5$. Starting at $4$ gives $4,26,41,60,83,\dots$, illustrating why descent of the numerical terms is not the termination argument.

Define the ordinal rank of a Goodstein term ${\rho }_b(m)$ by replacing the base $b$ in the hereditary expansion by $\omega$, at every exponent depth. The result is in Cantor normal form and lies below ${ϵ}_0$, called epsilon zero, the least nonzero solution of ${\omega }^{\alpha }=\alpha$. Finite hereditary expressions have finite nesting depth, so their ranks are bounded by a sufficiently high finite tower of powers of $\omega$.

For a fixed base, ${\rho }_b$ is strictly increasing. To see this, compare two ordinary base-$b$ expansions at their largest differing exponent. By induction through the hereditary exponent expressions, their exponents have the same ordering after replacing $b$ by $\omega$; computable Cantor normal form notation then uses the same first differing exponent or coefficient. AlsoIndeed after the base change all coefficients remain below $c$, the recursively changed exponents remain correctly ordered, and replacing the new base by $\omega$ gives exactly the original ordinal expression. These facts can be proved together by structural induction for primitive recursive functions on the hereditary expression.

Consequently, whenever $m_s>0$,An infinite nonzero Goodstein sequence would give an infinite descending sequence of ordinals below ${ϵ}_0$, impossible because ordinals are well-ordered. Thus the Goodstein function is total. Its steps are effective finite operations, so simulating the sequence until zero also proves that it is a total computable function.

The same ordinal notation system gives the requested decidable well-order. Let $D$ consist of canonical finite terms for zero and for expressionswhere the exponents are themselves canonical terms. Membership in $D$ is decidable by recursively checking the syntax, positive coefficients and decreasing exponents. Comparison is decidable by recursive computable Cantor normal form notation, first of exponents, then coefficients, and then the remaining summands. All recursive calls inspect proper subterms, so the algorithm terminates.

Interpreting these terms as ordinals gives every ordinal below ${ϵ}_0$, uniquely. One way to connect this directly to hereditary base representations is to choose, for a given finite ordinal term, a base larger than every coefficient anywhere in that term. Replacing $\omega$ by that base evaluates it to a natural number whose hereditary representation recovers the ordinal term. Thus all bases together supply the complete notation system; a single fixed base is not enough.

Choose an effective injective coding of finite terms by natural numbers, and enumerate the valid codes in increasing numerical order. The resulting bijection $d:\mathbb{N}\to D$ is computable: validity is decidable and there are infinitely many finite-ordinal terms. Its inverse is computable by counting valid codes below a given code. DefineThis is a decidable relation on all of $\mathbb{N}$. The interpretation into ordinals is an order isomorphism onto ${ϵ}_0$, provingDecidability here concerns comparing two notations. Well-foundedness is supplied by their ordinal interpretation, the same mathematical descent principle used to prove Goodstein's theorem.

The two preliminary sequence limit laws follow directly from the triangle inequality. For the sum, choose indices so that $|x_n-x|<\epsilon /2$ and $|y_n-y|<\epsilon /2$ beyond their respective cutoffs. Beyond the larger cutoff,Thus

For the reciprocal, convergence to nonzero $x$ gives $|x_n-x|<|x|/2$ eventually. The reverse triangle inequality then gives $|x_n|\ge |x|/2$, and consequentlyChoosing the eventual error smaller than both $|x|/2$ and $\epsilon |x{|}^2/2$ provesThe nonzero limit gives the denominator a positive lower bound; nonzero individual terms alone would not do so. The assumption $x_n\ne 0$ ensures the reciprocal sequence is defined even before this eventual bound applies.

A sequence $(x_n)$ is a convergent sequence with limit $x$ ifThe index $N$ may depend on $\epsilon$, but must work for every later term.

Fix $\epsilon >0$. Choose $N$ such that $|x_i-x|<\epsilon /2$ for $i\ge N$, and putThis is a fixed finite number. For $n\ge N$, the triangle inequality givesChoose $n$ sufficiently large that $C/n<\epsilon /2$ as well. The error is then less than $\epsilon$, provingTaking successive arithmetic averages preserves the limit. This is the Cesaro theorem for convergent sequences: any troublesome initial terms contribute only a fixed numerator divided by $n$.