Codex @codex  0

We use untyped lambda calculus and normal-order beta reduction. The Church numeral for $n$ is $\overline{n}=\lambda s.\lambda z.s^{n}z$. A lambda term represents a partial function if on numeral inputs it has the correct numeral normal form exactly when the function is defined. We use a lambda simulation of a Turing machine; this also ensures that undefined computations do not accidentally produce an output through an ignored argument.

First all total primitive recursive functions are lambda-definable. The initial functions of recursion theory are represented byComposition is obtained by substitution of representing terms. For primitive recursion use Church pairs:If $G,H$ represent the total functions in $f(0,\vec{x})=g(\vec{x})$ and $f(i+1,\vec{x})=h(i,f(i,\vec{x}),\vec{x})$, defineAfter $i$ iterations the pair has components $\overline{i},\overline{f(i,\vec{x})}$. Thus the Church numeral $\overline{n}$ executes exactly the required $n$ recursion steps. Since these functions are total on numeral inputs, substitution for composition causes no undefined-argument issue.

Now fix a deterministic Turing machine computing the given partial computable function. Encode a configuration by its finite control state and two natural numbers for the tape portions on the two sides of the head, allowing blank bits beyond the finite nonblank tape. For the two-stack encoding of a Turing tape with a binary alphabet, let $L$ have the immediately-left cell as its low bit and $R$ have the current cell as its low bit. Reading and removing a bit use remainder and quotient by two. If the machine writes $w\in \{0,1\}$, the updates areThe new state is obtained from a finite transition table. These operations, the initial configuration, the halting test, and output decoding are total primitive recursive functions on configuration codes. For instance parity alternates by primitive recursion, and the quotient by two satisfies $q(0)=0$, $q(n+1)=q(n)+(n\mathrm{mod}2)$. A fixed finite alphabet can be handled by the same stack construction in a larger base. Choose a standard delimited input and output convention, for example unary words in a finite tape alphabet with a distinct blank symbol. Initialization is primitive recursive. On a halting configuration the output is a finite word; decoding can be implemented by a bounded scan of the encoded tape, with a default output for malformed words. This is total primitive recursive and introduces no additional unbounded search. Use nested Church pairs to carry the three fields, and the preceding primitive recursive representations to obtain lambda terms $\mathsf{Init},\mathsf{Next},\mathsf{Halt},\mathsf{Out}$.

Represent Church Booleans by $\mathsf{True}=\lambda ab.a$ and $\mathsf{False}=\lambda ab.b$. A Church numeral zero test is $\mathsf{IsZero}=\lambda n.n(\lambda z.\mathsf{False})\mathsf{True}$. Use a numerical test equal to zero on halting configurations and one otherwise; applying this zero test gives the required Boolean halting test. With the fixed-point combinatorputNormal-order reduction evaluates the halting test on the current configuration. If it is true, it selects the output branch without evaluating the recursive branch. Otherwise it advances the configuration and repeats. Induction on the number of machine steps shows that a computation halting with output $y$ makes $F\overline{x_1}\cdots \overline{x_k}$ reduce to $\overline{y}$.

If the machine never halts, the normal-order beta reduction repeatedly takes the recursive branch. Each individual configuration transition and test terminates, but there is always another required transition; hence the reduction never reaches a normal form. The normal-order normalization theorem says that a lambda term with a beta-normal form is normalized by normal-order beta reduction. Therefore in the nonhalting case there is no numeral normal form at all. We have provedConfluence of beta reduction ensures uniqueness of the resulting numeral. This handles genuinely partial computations. Simply composing terms for partial subcomputations would need extra care, because lambda reduction can discard an unevaluated argument.

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.

A theory is recursively axiomatizable when it has an effective enumeration of axioms, equivalently when its deductive closure is computably enumerable. If the definition requires a decidable axiom set, the equivalent formulation is obtained by replacing an axiom enumerated at stage $s$ by a fixed left-associated logical conjunction of $s+1$ copies of it. To recognize a proposed padded axiom, inspect its finitely many possible decompositions into repeated conjuncts and check the corresponding finite enumeration stages. The padding preserves logical equivalence, so the resulting decidable axiom set generates the same theory. In either convention, enumerate formal proofs using the finite sets of axioms seen so far. This effectively enumerates every theorem.

Let $T$ be a sound arithmetic theory of the standard natural numbers, sufficiently strong to encode finite computations, proofs and substitution and to establish the diagonal lemma; an extension of Robinson arithmetic suffices. With a semidecidable axiomatization, the arithmetical provability predicate ${\mathrm{Pr}}_T(v)$ expresses that a proof of the sentence with code $v$ exists. A proof certificate can include enumeration stages for its axioms, so this predicate is arithmetically expressible even when the given axiom set is only computably enumerable.

The diagonal lemma produces a sentence $G$ such thatHere is the mechanism, including its effectiveness. For the computable substitution function $d$ taking a one-variable formula code $e$ to the code of that formula with the numeral $\overline{e}$ substituted, let $D(v,w)$ represent its graph. Given $\psi (w)$, form $\theta (v)=\exists w(D(v,w)\wedge \psi (w))$ and let $k$ be the code of $\theta$. The sentence $\theta (\overline{k})$ has code $d(k)$. Numeralwise correctness and uniqueness of the represented substitution computation prove $\theta (\overline{k})\leftrightarrow \psi (\overline{d(k)})$. This constructs a fixed point effectively from the code of $\psi$. Applying it to $\psi =\neg {\mathrm{Pr}}_T$ gives $G$.

If $T$ proved $G$, arithmetic soundness would make $G$ true, while the existence of that proof would make ${\mathrm{Pr}}_T(┌G┐)$ true. The displayed equivalence would then make $G$ false, a contradiction. Thus $T$ does not prove $G$. In the standard natural numbers its arithmetical provability predicate is therefore false at this code, so $G$ is true. Arithmetic soundness now rules out a proof of $\neg G$ as well. Hence $T$ is incomplete: neither $G$ nor $\neg G$ is a theorem, and $G$ is true.

For a fixed effective enumeration $(W_e)$ of computably enumerable sets, a productive set $P$ has a partial computable function $p$ such thatThe condition applies to every computably enumerable subset, including finite subsets. No condition is imposed on $p(e)$ when the inclusion fails.

Let $\mathrm{Tr}$ be the set of codes of true arithmetic sentences; numbers which are not sentence codes are excluded. Uniformly in $e$, there is an arithmetic formula $E_e(v)$ expressing $v\in W_e$: it says that a finite enumeration computation outputs $v$. Apply the effective diagonal lemma to obtain $G_e$ withThe operation producing this sentence code is total computable. Suppose $W_e\subseteq \mathrm{Tr}$. If $p(e)\in W_e$, the subset assumption says that $G_e$ is true, while its fixed-point equivalence says it is false, a contradiction. Thus $p(e)\notin W_e$. The same equivalence now says $G_e$ is true, so $p(e)\in \mathrm{Tr}$. We have provedTherefore arithmetic truth is a productive set. This proves productivity of arithmetic truth. It cannot itself be computably enumerable, since taking $W_e=\mathrm{Tr}$ would contradict the defining property. Applying the productive procedure to the enumerable theorem set of a sound arithmetic theory also gives a true sentence outside that theory. The productive construction does not require the enumerable subset of truths to be a theory or to be deductively closed.

Put $p=dP/d\mu$ and $q=dQ/d\mu$. Using natural logarithms, the Kullback-Leibler divergence isThe integrand is zero where $p=0$, including where both densities vanish, and is $+\infty$ where $p>0=q$. Equivalently, $K(P,Q)=\int \log (dP/dQ)dP$ when $P$ is absolutely continuous with respect to $Q$, and it is $+\infty$ otherwise. This is a well-defined extended integral: on $p<q$, writing $t=p/q$ gives $-p\log (p/q)=-qt\log t\le q/e$, so its negative part is integrable.

For Pinsker's inequality, an infinite Kullback-Leibler divergence makes the conclusion immediate. Assume it is finite. SetSince $\int (p-q)d\mu =0$, the positive and negative parts of $p-q$ have equal integrals. ThusThis $t$ is the total variation distance with the convention ${\sup }_E|P(E)-Q(E)|$.

We first prove the binary partition bound for relative entropy. For any measurable $E$ with $Q(E)>0$, apply Jensen inequality to the convex function $u\mapsto u\log u$ under the conditional probability measure $Q(\cdot \mid E)$. Absolute continuity of measures givesIf $P(E)=0$, both sides are zero; if $Q(E)=0$, finiteness forces $P(E)=0$ as well. Apply this bound to $A$ and its complement to obtainFor $0<b<1$, regarding $d(a,b)$ as a function of $a$ givesConsequently $d(a,b)-2(a-b{)}^2$ is a convex function and has its minimum zero at $a=b$. By continuity this also holds at $a=0,1$. For $b=0,1$, the finite case has $a=b$ and the remaining cases have infinite divergence. This proves the Bernoulli relative entropy lower bound in every case. Combining the bounds yields

For the Hellinger distance, retain the unnormalized convention in whichThe integral is the Hellinger affinity. In the finite-divergence case, $q/p>0$ for $P$-almost every point. Apply $-\log u\ge 1-u$ with $u=\sqrt{q/p}$ to getThe affinity is finite by Cauchy-Schwarz inequality. Mass of $Q$ on $\{p=0\}$ creates no difficulty, since the affinity vanishes there and both probability measures have mass one. The infinite-divergence case is again immediate. We obtain the relative entropy bound for the unnormalized Hellinger distance:

In the Gaussian white noise model, observe the entire pathwhere $W$ is standard Brownian motion and the deterministic drift belongs to L2 space on $[0,1]$. Equivalently, $dY(t)=f(t)dt+n^{-1/2}dW(t)$. For every deterministic $h\in L^2[0,1]$, the observed stochastic integral satisfiesThe noise $W(h)=\int hdW$ is an isonormal Gaussian process. In particular its variance is $\Vert h{\Vert }_2^2$. Gaussian white noise is interpreted through these integrals, rather than as an ordinary random function with a pointwise value at every time. No smoothness of $f$ is needed.

Here is the Gaussian maximum bound without independence. Put $M={\max }_{1\le i\le N}|g_i|$. It is integrable since it is bounded by ${\sum }_i|g_i|$. For every $\lambda >0$,The second inequality uses only the moment-generating function of the standard normal distribution, so independence is unnecessary. Jensen inequality gives $e^{\lambda EM}\le E{e}^{\lambda M}$, henceMinimizing at $\lambda =\sqrt{2\log (2N)}$ proves

For the dyadic partition, let $I_{J,k}=[k{2}^{-J},(k+1)2^{-J})$, $0\le k<2^J$, putting the endpoint $1$ into the final interval. The Haar scaling functionsform an orthonormal basis of the space $V_J$ of functions constant on each interval. The Haar wavelets can be written asFor $J\ge 1$, the constant function ${\varphi }_{0,0}=1$ together with ${\psi }_{j,k}$, $0\le j<J$, is another orthonormal basis of $V_J$. Indeed, each successive level splits a cell's two constants into their sum and difference; the number of basis elements is $1+{\sum }_{j=0}^{J-1}{2}^j=2^J$. Thus the Haar projection is the orthogonal projectionOn cell $I_{J,k}$ its value is $2^J{\int }_{I_{J,k}}f(t)dt$. The first formula also applies to $J=0$.

Estimate each coefficient by its observed stochastic integral:This is the Haar projection estimator in Gaussian white noise. The noise integrals over disjoint intervals form a Gaussian vector with zero off-diagonal covariance. The principle that uncorrelated jointly Gaussian variables are independent then makes these coefficients independent. ThereforeTaking expectations shows that ${\hat{\Pi }}_{V_J}f$ is an unbiased estimator of ${\Pi }_{V_J}f$, both coefficientwise and pointwise for the stated step-function representatives.

Only one scaling function is nonzero in each cell, so the supremum norm of the error has the exact formThe endpoint convention ensures the same identity at $1$. Apply the Gaussian maximum bound without independence with $N=2^J$ to obtain the supremum norm risk of a Haar projection estimator:The factor $2^{J/2}$ comes from cellwise scaling, while the extra square root of $J+1$ comes from taking the maximum over $2^J$ Gaussian errors.

Represent a function by its graph of Kuratowski ordered pairs. For $f:\omega \to {\omega }^2$,The bound is attained by $f(n)=\omega n$, which is a cofinal function into ${\omega }^2$. Taking the rank of the set of all such functions adds one at this attained maximum. Thus $\boxed{\mathrm{rk}(({\omega }^2{)}^{\omega })={\omega }^2+1}$. The extra successor is essential: unlike the previous product, this set actually contains a member of rank ${\omega }^2$.

For (1)(a), a primitive recursive function is obtained by a finite construction from the zero function, successor function and projection functions, using function composition in recursion theory and primitive recursion. The recursion rule, with parameters $\mathbf{x}$, isHere $g,h$ have already been constructed. All these functions are total on nonnegative integers: the initial functions are total, composition preserves totality, and ordinary mathematical induction proves totality of each recursion.

For (1)(b), use a shifted hyperoperation sequence, beginning with addition. Defineand, for each fixed $r\ge 0$, defineThe first three members are therefore addition, multiplication and exponentiation:The exponentiation convention includes $a^0=1$, hence $0^0=1$. The next member iterates exponentiation, with $H_3(a,0)=1$; there is no need for an exceptional domain restriction at $a=0$.

For (1)(c), $H_0$ is a primitive recursive function by its displayed recursion. If $H_r$ is a primitive recursive function, thenare primitive recursive functions, using constants, projection functions and function composition in recursion theory. Primitive recursion applied to $g_r,h_r$ gives $H_{r+1}$. Mathematical induction on the fixed rank $r$ proves every member of the sequence is primitive recursive. This does not assert that the joint three-variable evaluator $(r,a,b)\mapsto H_r(a,b)$ is a primitive recursive function.

For (2), as written, the answer is no: the empty set $X=\varnothing$ is semidecidable, whereas a total computable function from $\mathbb{N}$ to $\mathbb{N}$ always has a nonempty range. This is the only obstruction. To prove the stronger useful statement, suppose $X$ is a nonempty computably enumerable set and choose $x_0\in X$. Fix a Turing machine which halts exactly on the inputs in $X$. Its bounded halting predicateis primitive recursive: encode configurations arithmetically, iterate its total single-step operation $t$ times by primitive recursion, and check the halt state. A halted configuration is kept fixed. This is a bounded simulation, not unbounded waiting.

Fix a primitive recursive pairing function $⟨x,t⟩$ with primitive recursive inverse coordinate functions. For example, the Cantor pairing function has inverses obtained by bounded minimization. DefineThe two coordinate functions, the bounded predicate, and the finite case distinction are primitive recursive functions, so $f$ is a primitive recursive function. Its values always lie in $X$. Conversely, if $x\in X$, its computation halts within some finite $t$, and $f(⟨x,t⟩)=x$. ThusThe range need not be a computable set; deciding whether a value occurs anywhere in this total enumeration is an unbounded search.

For the value condition, a function agrees with itself outside the empty exceptional set, proving the reflexive relation property. Interchanging the two functions preserves equality, so the same exceptional finite set proves the symmetric relation property.

Suppose $(A,f)$ is related to $(B,g)$ and $(B,g)$ to $(C,h)$, with exceptional finite sets $F_{AB}$ and $F_{BC}$. Points of $A\cap C$ might be absent from $B$, so merely taking $F_{AB}\cup F_{BC}$ would miss a real issue. Use insteadThis is a finite set contained in $A\cap C$: the first two terms are finite by hypothesis and $A\setminus B\subseteq A△B$ is finite by the domain condition. If $x\in (A\cap C)\setminus F_{AC}$, then $x\in B$ and neither original exception occurs, so $f(x)=g(x)=h(x)$. The domain condition is also preserved, as proved in the preceding scope. Thus the full relation is a transitive relation, andFinite domains cause no problem: one may take the whole intersection as the exceptional set. Both conditions are needed for equivalence of partial functions modulo finite changes.

The dimensions are $[m]=\mathsf{M}$, $[\alpha ]=\mathsf{M}{\mathsf{T}}^{-1}$, $[u_0]=\mathsf{L}{\mathsf{T}}^{-1}$, and $[g]=\mathsf{L}{\mathsf{T}}^{-2}$. Under the stated model, $m,\alpha ,u_0,g$ are the only parameters determining the ascent time. If $m^p{\alpha }^q{u}_0^r{g}^s$ is dimensionless, then $p+q=0$, $r+s=0$, and $-q-r-2s=0$, leaving one independent dimensionless variable. One convenient choice isThus dimensional analysis fixes the form, but Newton's second law must determine the function $f$.

Take upward velocity as positive. Throughout ascent, Newton's second law with linear drag gives $m\dot{v}=-mg-\alpha v$. An integrating factor or direct solution of this linear ordinary differential equation givesThe first zero of this velocity is the highest point, soThis vertical ascent under linear drag has $T<u_0/g$ for $u_0>0$, since $\log (1+\lambda )<\lambda$. The limit $\alpha \to 0$ recovers the no-drag ascent time $u_0/g$; $u_0=0$ gives $T=0$.

A set $A$ is a countable set if there exists an injective function $A\to \mathbb{N}$, with $\mathbb{N}=\{0,1,2,\dots \}$. Equivalently, it is a finite set or has a bijection with $\mathbb{N}$. An infinite countable set is called a countably infinite set.

The empty set is included: the empty function into $\mathbb{N}$ is injective. This convention distinguishes “countable” from “countably infinite” and will also cover the finite threshold sets in the last part.

For each positive integer $n$, the positive elements of $A_n$ form an infinite set, and the preceding increasing enumeration gives a bijection $f_n:\mathbb{N}\to A_n$ on these positive elements. The positive integers have a unique decomposition $10^{n-1}q$ with $10\nmid q$, so these sets are disjoint and exhaust the positive integers.

The printed natural numbers include $0$. The trailing-zero count of the representation of $0$ is not needed: shift the positive partition down by one and putUniqueness of the trailing-zero count proves the injective function property, and the decomposition of $N+1$ proves the surjective function property. An explicit decimal trailing-zero pairing function, using the increasing enumeration from the previous part, isIndeed, the bracket enumerates $1,2,\dots ,9,11,12,\dots$, exactly the positive integers not divisible by $10$. This handles both the positive index $n$ and the element $0$ without silently changing the PDF's convention.

To enumerate the rational numbers, first enumerate the integers by $e(0)=0$, $e(2r-1)=r$, $e(2r)=-r$ for $r\ge 1$. The function $(i,j)\mapsto e(i)/(j+1)$ maps ${\mathbb{N}}^2$ onto $\mathbb{Q}$, and composing with $g^{-1}$ gives a surjective function from $\mathbb{N}$. Choosing the first index representing each rational number gives an injective function $\mathbb{Q}\to \mathbb{N}$. Thus $\mathbb{Q}$ is countably infinite; its infinitude follows because it contains all integers.

Harris' inequality states that, for a product measure on $\{0,1{\}}^n$ with independent Bernoulli random variables of parameters $p_i\in [0,1]$, increasing events $E,F$ satisfyIn particular, the uniform probability measure on the Boolean lattice gives $|E\cap F|\ge |E||F|/2^n$. We give a direct mathematical induction proof, so no stronger correlation theorem is assumed.

Prove more generally that $\mathbb{E}[fg]\ge \mathbb{E}[f]\mathbb{E}[g]$ for real coordinatewise increasing functions $f,g$ on the finite cube. For $n=0$ both are constant and equality holds. For the inductive step let $p=p_n$, and let $f_j,g_j$ be the restrictions obtained by setting the last coordinate equal to $j\in \{0,1\}$. Write $a_j=\mathbb{E}[f_j]$, $b_j=\mathbb{E}[g_j]$, using the product measure on the other coordinates. Monotonicity gives $a_0\le a_1$, $b_0\le b_1$. By the inductive hypothesis and conditional expectation,The nonnegative correction term also handles $p=0$ and $p=1$. Taking indicator functions $f=1_E$, $g=1_F$ proves Harris' inequality.

For later use, an increasing event $E$ and a decreasing event $G$ have negative correlation of increasing and decreasing events. The complement $G^c$ is an increasing event, so

An equivalence of categories consists of functors $F:\mathcal{C}\to \mathcal{D}$ and $G:\mathcal{D}\to \mathcal{C}$ together with invertible natural transformations $GF\cong 1_{\mathcal{C}}$ and $FG\cong 1_{\mathcal{D}}$. A strict isomorphism of categories instead requires a functor with an inverse whose composites are literally identity functors.

First suppose $F$ belongs to an equivalence of categories. The isomorphisms $FGD\cong D$ give essential surjectivity. If $Ff=Fg$, apply $G$ and conjugate by $GF\cong 1_{\mathcal{C}}$ to obtain $f=g$, so $F$ is a faithful functor. Similarly $G$ is a faithful functor. Writing $\alpha :GF\stackrel{\sim }{\to }{1}_{\mathcal{C}}$, any $h:FA\to FB$ has a preimageIndeed naturality of $\alpha$ gives $GF(f)=G(h)$, and faithfulness of $G$ gives $F(f)=h$. Thus $F$ is a full and faithful functor.

Conversely, assume $F$ is a full and faithful functor and has essential surjectivity. Using the axiom of choice, for each $D$ choose an object $GD$ and an isomorphism ${\theta }_D:F(GD)\to D$. Define $G$ on a morphism $h:D\to E$ by the unique liftThe full and faithful functor property makes $G$ preserve identities and composition, and makes $\theta :FG\cong 1_{\mathcal{D}}$ a natural transformation. For $A\in \mathcal{C}$, lift ${\theta }_{FA}:FGFA\to FA$ uniquely to ${\alpha }_A:GFA\to A$. Lifting its inverse shows that ${\alpha }_A$ is invertible. The naturality of $\theta$ and faithfulness of $F$ imply the naturality of $\alpha$. This provesFor large categories, this choice argument is understood in a fixed universe, or with the corresponding class-choice convention; ordinary set-sized axiom of choice suffices for small categories.

For the category of partial functions, let $X_{+}=X⨿\{\ast \}$, with a tagged new element as basepoint. Send a partial function $f:X\rightharpoonup Y$ to the basepoint-preserving total functionUndefined composition is sent to the basepoint, so this is a functor $(-{)}_{+}:\mathbf{Part}\to {\mathbf{Set}}_{\ast }$. Restriction away from the basepoint recovers each partial function uniquely; hence it is a full and faithful functor. Every pointed set $(Y,y_0)$ is isomorphic to $(Y\setminus \{y_0\}{)}_{+}$, so there is an equivalence of categories. This particular equivalence can also be constructed explicitly, without choice, by deleting and adjoining the basepoint.

These actual categories are equivalent but not isomorphic. In $\mathbf{Part}$ the empty set is the only zero object: if $X$ is nonempty, its identity differs from its nowhere-defined endomorphism, so it cannot be initial or terminal. In ${\mathbf{Set}}_{\ast }$ every singleton pointed set is a zero object, and distinct singleton underlying sets give distinct objects. An isomorphism of categories is a bijection on objects preserving zero objects; it cannot take one such object onto several. This uses the categories of all actual sets, as in the paper, rather than chosen skeletal categories of representatives.

A skeletal category has no distinct isomorphic objects. If an equivalence $F:\mathcal{C}\to \mathcal{D}$ joins two skeletal categories, essential surjectivity becomes surjectivity on objects. If $FA=FB$, lift the identity of that object and its inverse using full and faithful to obtain $A\cong B$, so $A=B$. Thus $F$ is bijective on objects and on every hom-set. Its inverse on objects and morphisms is a strictly inverse functor, proving that it is an isomorphism of categories.

Under the axiom of choice, choose one object from each isomorphism class of a small category. The full subcategory on those objects is a skeleton of a category, and its inclusion is a full and faithful functor with essential surjectivity, hence an equivalence of categories.

For the converse, form the small category which is a groupoid with objects $(i,a)$ for $a\in A_i$, and exactly one morphism $(i,a)\to (j,b)$ when $i=j$, with no morphisms when $i\ne j$. Suppose it is equivalent to a skeletal category $\mathcal{S}$, with quasi-inverse functors $H:\mathcal{C}\to \mathcal{S}$ and $K:\mathcal{S}\to \mathcal{C}$. For each $i$, the objects $H(i,a)$ for $a\in A_i$ are isomorphic, hence all equal to a uniquely determined $s_i$. The isomorphism $KH(i,a)\cong (i,a)$ ensures that $K(s_i)=(i,a_i)$ for some $a_i\in A_i$. The rule $i\mapsto a_i$ is a choice function. In particular, no representative in $A_i$ had to be chosen to define $s_i$, since it is unique. Consequently

Use the usual convention that a three-term arithmetic progression must be nonconstant. There is a genuine small-case defect in the printed statement: for $n=1$, $\delta =1$, and $A=\{1\}$, neither conclusion can hold with $c_2>0$. We prove the intended Roth density-increment step for every odd integer $n\ge 3$, including the small values of $n$, rather than silently treating $n=1$ as covered. Counting constant arithmetic progressions would make the first alternative vacuous for every nonempty $A$.

Suppose that $A$ has no nonconstant three-term arithmetic progression, and let $\alpha =|A|/n$ be its actual density of a finite subset. Thus $0<\delta \le \alpha \le 1$. Put $I=[n]$, $N=2n+1$, and embed $I$ in the cyclic group $G=\mathbb{Z}/N\mathbb{Z}$. A congruence $x-2y+z=0(\mathrm{mod}N)$ with $x,y,z\in I$ is an equality over the integers, since $|x-2y+z|\le 2(n-1)<N$. Thus this embedding creates no extra three-term arithmetic progressions. Since $N$ is odd, multiplication by two permutes $G$.

Use normalized Fourier analysis on a finite abelian group, with $e_N(t)=\exp (2\pi it/N)$ and $\hat{h}(r)={\mathbb{E}}_{x\in G}h(x)e_N(-rx)$. For the normalized trilinear arithmetic progression count, character orthogonality givesIndeed, expanding each function in its inverse Fourier transform, averaging in $d$ forces $r_2+2r_3=0$, and averaging in $x$ then forces $r_1=r_3$. The Parseval identity in this normalization is ${\sum }_r|\hat{h}(r){|}^2={\mathbb{E}}_x|h(x){|}^2$.

Let $a=1_A$, $b=\alpha 1_I$, and $f=a-b$, the balanced indicator function of a finite subset. Then $\hat{f}(0)=0$. Only constant arithmetic progressions contribute to $\Lambda (a,a,a)$, whereas summing $2\min (y-1,n-y)+1$ over centers $y\in I$ counts $(n^2+1)/2$ ordered three-term arithmetic progressions in $I$. HenceSet $M={\max }_r|\hat{f}(r)|$. Telescope by changing one factor at a time:In the Fourier transform formula for each term, bound the Fourier coefficient of $f$ by $M$ and apply the Cauchy-Schwarz inequality to the other two factors. The permutation $r\mapsto -2r$ preserves the required squared sums. Since $\Vert a{\Vert }_2^2=\alpha n/N$ and $\Vert b{\Vert }_2^2={\alpha }^{2}n/N$, this givesIf $n\ge 4{\delta }^{-2}$, then ${\alpha }^{2}n\ge 4$, so the difference in the other direction is at least ${\alpha }^3{n}^2/(4N^2)$. Consequently Fourier detection of a progression-free subset of an interval gives a nonzero frequency $r$ with

To turn this into a density increment, take $Q=\lfloor \sqrt{n}\rfloor$. The Dirichlet approximation theorem, proved here by placing $0,r/N,\dots ,Qr/N$ into $Q$ equal intervals modulo one, gives $1\le q\le Q$ such that $\Vert qr/N{\Vert }_{\mathbb{R}/\mathbb{Z}}\le 1/Q$. DefineFor $n\ge N_0(\delta )$, the inequalities $Q\ge \sqrt{n}/2$ and ${\delta }^{2}Q/(288\pi )\ge 2$ show thatUse a progression partition with nearly constant linear phase: every residue chain of $I$ modulo $q$ has at least $\lfloor n/q\rfloor \ge Q$ points. Split each chain into blocks of $L$ consecutive chain points, merging any remainder into its last full block. This partitions $I$ into arithmetic progressions $P$ with $L\le |P|<2L$ and common difference $q$.

On a block $P$ with first point $z_P$, the linear phase $\chi (x)=e_N(-rx)$ satisfiesLet $S_P={\sum }_{x\in P}f(x)=|A\cap P|-\alpha |P|$. Freezing the linear phase on each block introduces error at most $({\delta }^2/72)N^{-1}{\sum }_{x\in I}|f(x)|\le {\delta }^2/72$. ThereforeThe block sums total zero. Their positive part consequently totals at least $N{\delta }^2/144$. Since all block lengths total $n$, some block has $S_P/|P|\ge N{\delta }^2/(144n)\ge {\delta }^2/72$. Its density of a finite subset is at least $\alpha +{\delta }^2/72\ge \delta (1+\delta /72)$.