On rudimentarity, primitive recursivity and representability

• Autorzy: Salehi Saeed

Identyfikatory

DOI

10.4467/20842589RM.20.004.12436

• Języki publikacji: EN

Abstrakty

EN

It is quite well-known from Kurt Gödel’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.

Słowa kluczowe

EN

incompleteness theorem; bounded formula; rudimentary relation; primitive recursive function; primitive recursive relation; representability

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Reports on Mathematical Logic
• Rocznik: 2020
• Tom: Vol. 55
• Strony: 73--85
• Opis fizyczny: Bibliogr. 20 poz., rys.

Twórcy

autor

Salehi Saeed

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

Bibliografia

• [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.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).