0
votes
1answer
32 views

Prove uniqueness of recursive function

I am currently reading Cutland's Computability and would like to figure out how to solve Theorem 4.2 which states: Let $x=(x_1 \dotsc x_n)$, and suppose that $f(x)$ and $g(x,y,z)$ are functions; ...
3
votes
0answers
65 views

Induction on Primitive Recursive Function

The set $F_{n}$ of primitive recursive function symbols of arity $n$ can be defined inductively as: \begin{align} & Z, \text{Succ} \in F_{1} & \\ &\pi_{j}^{n} \in F_{n} \quad \text{for ...
0
votes
2answers
131 views

Termination of a Fast Exponentiation problem

Here's the problem I am stuck on. There exists a fast exponentiation program like the following: Given inputs a in the set of all Real numbers, b in the set of Natural numbers, initialize ...
3
votes
1answer
145 views

Why do $\omega$-models of subsystems of $\mathsf{Z}_2$ satisfy full induction?

Richard Shore, in his 2010 paper in the Bulletin of Symbolic Logic, 'Reverse Mathematics: The Playground of Logic', writes that Obviously, if an $\omega$-model $\mathcal{M}$ (those with $M = ...