Tennenbaum phenomena in models of arithmetic

Abstract

The main aim of this text is to present and investigate some basic arithmetical func- tions and relations with regard to being recursive in a countable non-standard model of Peano arithmetic, PA for short, or some weaker fragment, like I∆0 or IΣ1, of PA. In PART I, we present a known result called Tennenbaum's theorem. It states that every non-standard model M of PA with domain N can have neither +M nor ×M recursive. Moreover, we present the case for + in a strengthened version for I∆0, which is due to K. McAloon. To show that not everything is lost, we also present a well know result stating that < and the successor function can be simultaneously recursive in some non-standard model of PA with domain N. In PART II, we make our own investigation into the questions related to whether there can be a non-standard model of PA s.t. x div y, the quotient function, and x mod y, the remainder function, are recursive in it. Furthermore, we often restrict y to some standard number n. To give a non-exhaustive list of problems we have solved, we showed that there can be no non-standard model of PA with both x div n and x mod n recursive. Furthermore, there can be no non-standard model of IΣ1 with x div y recursive. On the other hand, x div n and x mod n can be separately recursive in a non-standard model of PA. 1

Hlavným cieľom tohto textu je skúmať, či už prezentovaním známych výsledkov alebo našich vlastných, niektoré aritmetické funkcie a relácie z pohľadu ich rekurzívnosti v spočetných neštandardných modeloch Peanovej aritmetiky, skratkou PA, alebo niekt- orého jej slabšieho fragmentu ako I∆0 alebo IΣ1. V prvej časti prezentujeme Tennenbaumovu vetu, ktorá je známym výsledkom danej oblasti. Veta tvrdí, že v každom neštandardnom modeli M, Peanovej aritmetiky, s doménou N nemôže byť +M ani ×M rekurzívnou funkciou. Navyše, prezentujeme daný výsledok pre + v silnejšie podobe a to pre teóriu I∆0, daný výsledok pochádza od K. McAloona. Aby sme ukázali že nie je všetko stratené, prezentujem ďalší známy výsledok tvrdiaci, že relácia < a funkcia nasledovník, S, môžu byť simultánne rekurzívne v nejakom neštandardnom modeli PA s doménou N. V druhej časti prezentujeme naše vlastné výsledky ktoré sme dostali pýtaním sa otázok o rekurzívnosti funkcií x div y, celočíselné delenie, a x mod y, zvyšok po celočíselnom delení, v modeloch PA. Taktiež častokrát uvažujeme reštrikcie x div y a x mod y na x div n a x mod n, kde n je štandardné číslo. Aby sme spomenuli niekoľko výsledkov ku ktorým sme prišli, ukázali sme, že neexistuje neštandardný model PA kde by boli obe funkcie x div n a x mod n rekurzívne. Ďalej, nemôže existovať...