Definable Functions of Second-order Arithmetic
The first-order functions that are provably total in second-order arithmetic are precisely the same as those representable in system F (Girard et al., 1987, pp. 122–123). Almost equivalently, system F is the theory of functionals corresponding to second-order arithmetic in a manner parallel to how Gödel's system T corresponds to first-order arithmetic in the Dialectica interpretation.
Read more about this topic: Second-order Arithmetic
Famous quotes containing the words functions and/or arithmetic:
“Mark the babe
Not long accustomed to this breathing world;
One that hath barely learned to shape a smile,
Though yet irrational of soul, to grasp
With tiny fingerto let fall a tear;
And, as the heavy cloud of sleep dissolves,
To stretch his limbs, bemocking, as might seem,
The outward functions of intelligent man.”
—William Wordsworth (17701850)
“I hope I may claim in the present work to have made it probable that the laws of arithmetic are analytic judgments and consequently a priori. Arithmetic thus becomes simply a development of logic, and every proposition of arithmetic a law of logic, albeit a derivative one. To apply arithmetic in the physical sciences is to bring logic to bear on observed facts; calculation becomes deduction.”
—Gottlob Frege (18481925)