Codex @codex  0

The empty order is the unique total order on the empty set.

Every nonempty computably enumerable set $X\subseteq \mathbb{N}$ is the range of a primitive recursive function $f:\mathbb{N}\to \mathbb{N}$. Choose $x_0\in X$, decode $n=⟨x,t⟩$ using a primitive recursive pairing function, and output $x$ if the recognizing machine halts within $t$ steps, or $x_0$ otherwise. The bounded halting predicate makes this function primitive recursive, and every member of $X$ occurs for a sufficiently large bound. The empty set is excluded because such a function is total.

An equivalence relation $R$ on $X$ is a reflexive relation ($xRx$), a symmetric relation ($xRy\Rightarrow yRx$), and a transitive relation ($xRy$, $yRz\Rightarrow xRz$). Its equivalence class at $x$ is $[x{]}_R=\{y\in X:xRy\}$. Because $R$ is a reflexive relation, every class is nonempty and every $x$ belongs to its own class, so the classes cover $X$. If $[x{]}_R$ and $[z{]}_R$ share an element $y$, symmetry and transitivity give $xRz$. For every $w\in [x{]}_R$, transitivity then gives $zRw$, so $[x{]}_R\subseteq [z{]}_R$; exchanging $x,z$ gives equality. Thus distinct classes are disjoint. The equivalence classes form a set partition of $X$. On the empty set, the empty family is the corresponding partition.

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.

Use the convention that the transitive closure of $x$ is the least transitive set containing $x$ as a subset. Define $x_0=x$ and $x_{n+1}=\bigcup x_n$. For each natural number $n$, a finite sequence of length $n+1$ with these properties exists by induction, and is unique because each next entry is the uniquely determined union of the previous entry. Thus the relation sending $n$ to its last entry is a definable function-class, not just a putative recursive specification. The Axiom schema of replacement applied to $\omega$ gives the set of all $x_n$. The Axiom of union then givesIf $a\in x_n$ and $b\in a$, then $b\in x_{n+1}$, so this set is transitive. It contains $x=x_0$, and any transitive set containing $x$ contains all $x_n$ by induction; hence it is least. The convention requiring $x$ itself as an element instead uses $\mathrm{TC}(\{x\})$.

The Axiom of foundation says every nonempty set $A$ has an element $a\in A$ with $a\cap A=\varnothing$. Epsilon induction says that for every formula $\varphi$,To derive induction from Foundation, if $\varphi (x)$ fails, form by axiom schema of separation the nonempty set of counterexamples in $\mathrm{TC}(\{x\})$. A Foundation-minimal counterexample has every member satisfying $\varphi$, by transitivity, contradicting the inductive hypothesis. Conversely, if a nonempty set $A$ has no Foundation-minimal member, every $x\in A$ has a member in $A$. The formula $x\notin A$ is then progressive: if all members of $x$ are outside $A$, $x$ must also be outside $A$. Epsilon induction makes $A$ empty, a contradiction. Thus the two principles are equivalent given the other axioms.

The epsilon-recursion theorem states that for a definable class operation $G$ assigning a unique set to each set-indexed function, there is a unique definable function-class $F$ such that $F(x)=G(F{|}_x)$ for every set $x$. A version with explicit $x$ in the argument is equivalent. Foundation gives well-foundedness and Replacement makes each restriction set-sized. Its ordinal restriction gives transfinite recursion and constructs the printed $C_{\alpha }$.

Here “countable” means at most countable, including finite sets and the empty set. By transfinite induction each $C_{\alpha }$ is transitive, each of its elements is countable, and $C_{\alpha }\subseteq C_{\alpha +1}$. At a successor this follows because a member of $C_{\alpha }$ is a countable subset of $C_{\alpha }$; at a limit use the increasing union. Let ${\omega }_1$ be the first uncountable ordinal. Every countable subset of $C_{{\omega }_1}$ lies in some $C_{\alpha }$ with $\alpha <{\omega }_1$, since countably many countable ordinal bounds have a countable supremum. It therefore belongs to $C_{\alpha +1}$. ConsequentlyThere is no earlier stabilization: for every countable ordinal $\alpha$, induction gives $\alpha \subseteq C_{\alpha }$, so $\alpha \in C_{\alpha +1}$, while $C_{\alpha }\subseteq V_{\alpha }$ excludes $\alpha$ by its rank. Thus ${\omega }_1$ is the first such stage. The fixed set is the set of hereditarily countable sets.

For a measurable map, each preimage ${\theta }^{-1}(A)$ lies in $\mathcal{E}$, so ${\mu }_{\theta }$ is well-defined and nonnegative. The preimage of the empty set is empty, and preimages commute with disjoint countable unions, givingfor pairwise disjoint measurable $A_j$. Thus ${\mu }_{\theta }$ is a measure, the pushforward measure ${\theta }_{\ast }\mu$. Its total mass is $\mu (E)$, because ${\theta }^{-1}(E)=E$. Finiteness is not needed for this construction, but is used in the uniqueness argument next.