A computability notion for locally finite lattices
A rather restricted kind of computability called calculability is considered on locally finite lattices. Besides arbitrary given functions, its definition uses as an initial function also a four-argument one whose value equals the third or the fourth argument depending on whether the first argument is dominated by the second one. New functions are constructed by means of substitution and of supremum and infimum attained when one of the arguments ranges between varying limits. In one of the examples the calculable functions have a certain relation to the Bounded Arithmetic of S. R. Buss, and in another one they coincide with the so-called elementary definable functions considered by the present author in 1967. Under some assumptions that are satisfied in these two examples, the calculable functions on the natural numbers are characterized through definability by formulas with bounded quantifiers and domination by termal functions.
Corrigendum (not concerning the PDF file from the link below): The word “computability” on page 207, line 21 from above, must be replaced by the word “calculability”.
Full text (PDF, 157 Kb)