|
|
Tennenbaum phenomena in models of arithmetic
Kriško, Lukáš ; Thapen, Neil (vedoucí práce) ; Bulín, Jakub (oponent)
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ť...
|
host ::
RSS.