Reports on Mathematical Logic

logo of Jagiellonian University in Krakow

On Rudimentarity, Primitive Recursivity and Representability

Publication date: 20.08.2020

Number 55

Reports on Mathematical Logic, 2020, pp. 73 - 85



Saeed Salehi


It is quite well-known from Kurt G¨odel’s (1931) ground-breaking Incompleteness Theorem that rudimentary relations (i.e., those definable by bounded formulae) are primitive recursive, and that primitive recursive functions are representable in sufficiently strong arithmetical theories. It is also known, though perhaps not as well-known as the former one, that some primitive recursive relations are not rudimentary. We present a simple and elementary proof of this fact in the first part of the paper. In the second part, we review some possible notions of representability of functions studied in the literature, and give a new proof of the equivalence of the weak representability with the (strong)  representability of functions in sufficiently strong arithmetical theories.

AMS Subject Classification: primary 03F40; secondary 03D20, 03F30


[1] C. Calude, Super-Exponentials Non-Primitive Recursive, but Rudimentary, Information Processing Letters 25:5 (1987), 311–315. http://bit.do/eVPAB.

[2] S.A. Cook, Lecture Notes on Computability and Logic (Fall 2008). http://bit.do/fxeza

[3] V. Dyson (Huber-), On the Strong Representability of Number-Theoretic Functions, Hughes Aircraft Company Research Report, Californa (1965) 5 pages.

[4] H-A. Esbelin, M. More, Rudimentary Relations and Primitive Recursion: A Toolbox, Theoretical Computer Science 193:1-2 (1998), 129–148.

[5] K. G¨odel, ¨Uber formal unentscheidbare S¨atze der Principia Mathematica und verwandter Systeme, I., Monatshefte f¨ur Mathematik und Physik 38:1 (1931), 173–198. (in German). English Translation in: Kurt G¨odel Collected Works, Volume I: Publications 1929–1936 (Eds. S. Feferman et al.), Oxford University Press (1986), pp. 135–152.

[6] P. H´ajek, P. Pudl´ak, Metamathematics of First-Order Arithmetic, Springer-Verlag, 2nd print, 1998.

[7] S. Hedman, A First Course in Logic: An Introduction to Model Theory, Proof Theory, Computability, and Complexity, Oxford University Press, 2nd print, 2006.

[8] J.P. Jones, J.C. Shepherdson, Variants of Robinson’s Essentially Undecidable Theory R, Archive for Mathematical Logic 23:1 (1983), 61–64.

[9] R. Kaye, Models of Peano Arithmetic, Oxford University Press, 1991.

[10] L. Kirby, Review of [9], Notre Dame Journal of Formal Logic 33:3 (1992), 461–463. http://bit.do/fxeRD

[11] J. Lambek, P.J. Scott, Introduction to Higher-Order Categorical Logic, Cambridge University Press, 1986.

[12] H. Lessan, Models of Arithmetic, Ph.D. Dissertation (Manchester University, 1978). Reprinted in: New Studies in Weak Arithmetics (Eds. P. C´egielski, Ch. Cornaros, C. Dimitracopoulos), CSLI Lecture Notes, Volume 211, CSLI Publications (2013) pp. 389–448.

[13] E. Mendelson, Introduction to Mathematical Logic (1st ed. D. van Nostrand Co. 1964), (2nd ed. D. van Nostrand Co. 1979), (3rd ed. The Wadsworth & Brooks/Cole 1987), (4th ed. Chapman & Hall 1997), (5th ed. CRC Press 2009), (6th ed. CRC Press 2015).

[14] J.R. Myhill, Linear Bounded Automata, WADD Technical Note 60-165, Wright Air Development Division, Wright-Patterson Air Force Base, New York 1960.

[15] P. Odifreddi, Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers, Volume I, North Holland, 1992.

[16] J.B. Paris, C. Dimitracopoulos, Truth Definitions for ¤0 Formulae, in: Logic and Algorithmic (An International Symposium Held in Honour of Ernst Specker), Monographies de L’Enseignement Math´ematique, Volume 30, Universit´e de Gen`eve, 1982, pp. 317–329. http://bit.do/fxeCM

[17] W. Rautenberg, A Concise Introduction to Mathematical Logic, Springer, 3rd ed. 2010.

[18] S. Salehi, On the Notions of Rudimentarity, Primitive Recursivity and Representability of Functions and Relations, 2020. https://arxiv.org/abs/1907.00658

[19] M.H. Sørensen, P. Urzyczyn, Lectures on the Curry-Howard Isomorphism, Elsevier, 2006.

[20] A. Tarski (in collaboration with A. Mostowski, R.M. Robinson), Undecidable Theories, North–Holland, 1953, reprinted by Dover Publications 2010.


Information: Reports on Mathematical Logic, 2020, pp. 73 - 85

Article type: Original research article



On Rudimentarity, Primitive Recursivity and Representability


Research Institute for Fundamental Sciences University of Tabriz, 29 Bahman Boulevard P.O.Box 51666-16471, Tabriz, Iran

Published at: 20.08.2020

Received at: 01.11.2019

Article status: Open

Licence: CC BY-NC-ND  licence icon

Percentage share of authors:

Saeed Salehi ( Author) - 100%

Article corrections:


Publication languages:


View count: 2

Number of downloads: 0