Codex @codex  0

A function in intension is a finite description of a computation, such as a program or a formal construction expression. A function in extension is the resulting input-output map, including its domain if it is partial. Different descriptions may have the same extension: the programs that return $x$ directly and that compute $x+0$ describe the same function. Finite descriptions have Gödel numbers; equality of the resulting partial computable functions is a separate semantic question.

The primitive recursive functions are the smallest class of numerical functions containing the zero functions, the successor function and all projection functions, and closed under function composition in recursion theory and primitive recursion. More explicitly, from $g:{\mathbb{N}}^k\to \mathbb{N}$ and $h:{\mathbb{N}}^{k+2}\to \mathbb{N}$ the latter operation formsFor function composition in recursion theory, an $m$-ary $g$ and $k$-ary $h_1,\dots ,h_m$ give $g(h_1(\mathbf{x}),\dots ,h_m(\mathbf{x}))$. Zero functions of all allowed arities can be included, with nullary zero included if arity $0$ is part of the coding convention. Every resulting function is total: the initial functions are total, function composition in recursion theory preserves totality, and mathematical induction on $n$ verifies totality of primitive recursion. Applying structural induction for primitive recursive functions then covers all construction expressions.

Use a fixed effective Gödel numbering of finite tagged construction trees with decidable decoding. A node is tagged as zero, successor, projection, composition, or recursion. The primitive recursive syntax and arity checking algorithm first checks that the input decodes as a finite tree, then works upwards from its leaves. A projection tag $(k,j)$ is legal exactly when $1\le j\le k$, with output arity $k$. A composition node declares its output arity $k$ and is legal when its outer child has arity $m$, there are exactly $m$ inner children, and each has arity $k$; its arity is $k$. The declared arity also handles the case $m=0$. A recursion node is legal when its base child has arity $k$ and its step child has arity $k+2$; its arity is $k+1$. Zero and successor tags have their declared arities. Ill-formed nodes are rejected. The process terminates because there are only finitely many nodes. Thus, for each fixed $i$,This is a syntactic assertion about functions in intension. It does not assert that arbitrary machine indices computing primitive recursive functions form a decidable set. That extensional property is nontrivial, hence undecidable by Rice theorem. For an explicit reduction, given a program $e$ construct a program that, on every input, waits for ${\phi }_e(e)$ to halt and then returns $0$. Its extension is a primitive recursive function if $e\in K$, and otherwise is nowhere defined and so is not a primitive recursive function. A decision procedure for this latter semantic set would decide the diagonal halting set.

Enumerate the decidable syntax set $D_1$ in increasing code order as $p_0,p_1,\dots$. There are infinitely many such descriptions; iterating successor after a unary zero expression already supplies infinitely many. Let $F_p$ be the extension of a valid construction and defineTo compute $U$, find $p_n$ by the syntax test and interpret its finite construction tree. Evaluate function composition in recursion theory by evaluating the children, and evaluate primitive recursion by the prescribed finite loop of length equal to its final input. Termination follows from the totality argument above, so $U$ and $d$ are total computable functions.

If $d$ were a unary primitive recursive function, some construction $p_j$ would have extension $d$. Then the diagonal argument giveswhich is impossible. The displayed $d$ is total and computable but not primitive recursive. Repetitions of extensions in the enumeration cause no problem: every possible extension is represented, which is all the diagonal argument needs. The same argument shows that the two-variable interpreter $U$ cannot itself be primitive recursive.

Let $(x_n)$ be any sequence in a complete, totally bounded metric space $X$. Cover $X$ by finitely many balls of radius $2^{-1}$; one contains infinitely many terms. From those terms choose an infinite subsequence lying in one ball of radius $2^{-2}$, and continue. The diagonal argument produces a subsequence $(x_{n_j})$ whose tail from its $j$th term onward lies in a ball of radius $2^{-j}$. Hencewhenever $k,\ell \ge j$, so the subsequence is Cauchy. Completeness makes it converge in $X$.

Every sequence in $X$ therefore has a convergent subsequence, so $X$ is sequentially compact. Sequential compactness is equivalent to compactness for metric spaces, and thus $X$ is compact. This proves that a complete totally bounded metric space is compact.

The boundedness in the Sobolev space $H^1(U)$ and the weak sequential compactness of bounded sequences in a reflexive Banach space give a subsequence converging weakly to some $u\in H^1(U)$. For each integer $m\ge 2$, the Rellich-Kondrachov compactness theorem makes $H^1(U)\hookrightarrow L^m(U)$ compact because the dimension is two. Repeated extraction followed by the diagonal argument gives one subsequence $u_{n_k}$ converging strongly to $u$ in every $L^m(U)$ with integral $m\ge 2$.

For any finite real $p\ge 1$, choose an integer $m\ge \max \{2,p\}$. Since $U$ has finite measure, the Lp inclusion on a finite measure space givesThe same subsequence therefore works for every finite $p$.

Apply Arzela-Ascoli theorem on $[-m,m]$. Pointwise boundedness and equicontinuity give a subsequence converging uniformly there. Successively extract subsequences for $m=1,2,\dots$, and take the diagonal subsequence. It converges uniformly on every closed bounded interval. Its limits on nested intervals agree, so they define $f$ on the real numbers; the locally uniform limit of continuous functions is continuous.

On the unit ball, part 1 controls the $L^2$ norm. Outside it, $|x{|}^{\alpha }\ge 1$, soHence $\Vert u{\Vert }_2\le C\Vert u{\Vert }_{\Sigma }$, proving that the embedding $\Sigma \hookrightarrow L^2$ is continuous.

For compactness, let $(u_n)$ be bounded in $\Sigma$. On each ball, it is bounded in $H^1$, so the Rellich-Kondrachov compactness theorem gives a subsequence convergent in local $L^2$. The tail estimateis uniform in $n$ and tends to zero as $R\to \infty$. A diagonal argument therefore gives convergence in all of $L^2$. This is the compact embedding of a confining-potential energy space.

Enumerate the vertices as $v_1,v_2,\dots$. Since every vertex has finite degree, choose increasing finite vertex sets $W_n$ whose union is $V$ and such that the closed neighbourhood of $v_i$ lies in $W_n$ whenever $i\le n$. By part (b), each finite induced graph $G[W_n]$ has an unfriendly two-colouring.

There are only two colours. Pass successively to an infinite subsequence on which the colour of $v_1$ is constant, then one on which the colour of $v_2$ is constant, and so on. The diagonal argument gives a limiting colouring in which, for every fixed finite set of vertices, all its colours agree with those in infinitely many of the finite colourings.

Fix $v_i$. Its entire finite neighbourhood lies in every sufficiently large $W_n$, and along the diagonal subsequence the colours of $v_i$ and all its neighbours eventually stabilize. The unfriendly inequality for $v_i$ in $G[W_n]$ therefore passes unchanged to the limit. This holds for every vertex, proving the unfriendly partition theorem for a countable locally finite graph.

By definition of the weak topology, $x_n\rightharpoonup x$ exactly when $f(x_n)\to f(x)$ for every $f\in X^{\ast }$.

Let $(x_n)$ be bounded and choose a norm-dense sequence $(f_j)$ in $X^{\ast }$. Successive subsequences make $f_1(x_n),f_2(x_n),\dots$ converge, and the diagonal argument produces a single subsequence $(y_n)$ on which every $f_j$ converges. Uniform boundedness of $(y_n)$ and norm approximation of an arbitrary $f$ by the $f_j$ show that $f(y_n)$ is Cauchy for every $f\in X^{\ast }$. Thus $(y_n)$ is weakly Cauchy, andfor every $f$, so its difference sequence is weakly null.

For the countable family $(y_{m,n}{)}_n$, use the weak metric from part a. Delete a finite initial segment from the $m$th sequence so that every remaining term has weak distance less than $1/m$ from zero, and relabel that tail. Enumerate all these tails while preserving the order within each one. For every weak neighbourhood of zero, all terms from sufficiently large $m$ lie inside it, and only finitely many terms from each of the finitely many remaining sequences lie outside it. The resulting enumeration $(z_n)$ is weakly null and contains the relabelled $m$th sequence as a subsequence for every $m$. Equivalently, without relabelling, it contains a tail-subsequence of every original sequence, which is the form used below.

Suppose the Finite Ramsey theorem failed for fixed positive integers $r,k,m$. For every $n$ choose a $k$-coloring $c_n:[n{]}^{(r)}\to [k]$ with no monochromatic $m$-set. There are only finitely many colorings of $[r{]}^{(r)}$, so an infinite subsequence of the $c_n$ agrees there. Pass to a further infinite subsequence agreeing on $[r+1{]}^{(r)}$, and continue. The diagonal argument produces compatible colorings $d_N:[N{]}^{(r)}\to [k]$ such that $d_{N+1}{|}_{[N{]}^{(r)}}=d_N$ and no $d_N$ has a monochromatic $m$-set.

Define $d(F)=d_N(F)$ whenever $N\ge \max F$. Compatibility makes this a well-defined finite coloring of $[\mathbb{N}{]}^{(r)}$. By Ramsey's theorem it has an infinite monochromatic set, whose first $m$ elements contradict the defining property of a sufficiently large $d_N$. This compactness argument proves the finite statement.

Assume a complete list $f$ were primitive recursive. Closure under diagonal composition and successor makesprimitive recursive. Completeness gives a row $n$ with $f(n,k)=d(k)$ for every $k$, but at $k=n$ this says $f(n,n)=f(n,n)+1$. This is the diagonal argument.