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 finger—to 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 (1770–1850)
“O! O! another stroke! that makes the third.
He stabs me to the heart against my wish.
If that be so, thy state of health is poor;
But thine arithmetic is quite correct.”
—A.E. (Alfred Edward)