Робинсон арифметикасы: Аксиомалық жүйе фрагменті

Кіріспе

Аксиомалық логикалық жүйе. Математикада Робинсон арифметикасы – бірінші реттік Пеано арифметикасының (ПА) шекті аксиомаланған фрагменті, оны алғаш рет 1950 жылы Рафаэль М. Робинсон жасаған. Ол әдетте Q деп белгіленеді. Q математикалық индукция аксиомалық схемасы болмайтынға дерлік PA-ға тең. Q, PA-дан әлсіз, бірақ олардың тілі бірдей, және екі теория да толық емес. Q маңызды және қызығушылық тудырады, себебі ол PA-ның шекті аксиомаланған фрагменті болып табылады, рекурсивті түрде толық емес және мәнін анықтау мүмкін емес.

Метаматематика

Q метаматематикасы бойынша қараңыз , , , және Q-ның мақсатты түсіндірмесі – бұл табиғи сандар және олардың әдеттегі арифметикасы, онда қосу мен көбейту әдеттегі мағынаны білдіреді, сәйкестік теңдік, ал 0 – табиғи сан нөл. Q-ның барлық аксиомаларын қанағаттандыратын кез келген модельдің (құрылымның) (3) аксиомасын қоспағанда, стандартты табиғи сандарға (N, +, ·, S, 0) изоморфты бірегей субмоделі («стандартты бөлігі») бар. (Аксиома (3) міндетті түрде қанағаттандырылуы қажет емес; мысалы, теріс емес бүтін сандар коэффициенттері бар көпмүшелер (3) аксиомасынан басқа барлық аксиомаларды қанағаттандыратын модельді құрайды.) Q, Пеано арифметикасы сияқты, барлық шексіз кардиналдардың стандартты емес модельдеріне ие. Алайда, Пеано арифметикасынан айырмашылығы, Тенненбаум теоремасы Q-ға қолданылмайды және оның есептеуге болатын стандартты емес модельдері бар. Мысалы, Q-ның есептеуге болатын моделі бар, ол оң жетекші коэффициенті бар бүтін сандық коэффициенттері бар көпмүшелерден, сондай-ақ нөлдік көпмүшеден тұрады, олардың әдеттегі арифметикалық амалдары бар. Q-ның ерекше ерекшелігі – индукцияның аксиомалық схемасының болмауы. Сондықтан Q-да табиғи сандар туралы нақты фактілердің әрбір нақты мысалын дәлелдеу мүмкін, бірақ байланысты жалпы теореманы дәлелдеу мүмкін емес. Мысалы, 5 + 7 = 7 + 5 Q-да дәлелдеуге болады, бірақ жалпы x + y = y + x емес. Сол сияқты, Sx ≠ x екенін дәлелдеуге болмайды. Q-ның стандартты фактілердің көп бөлігін қабылдамайтын моделі табиғи сандардың стандартты моделіне екі жаңа элементті a және b қосу арқылы және Sa = a, Sb = b, x + a = b және x + b = a барлық x үшін, a + n = a және b + n = b, егер n стандартты табиғи сан болса, x·0 = 0 барлық x үшін, a·n = b және b·n = a, егер n нөлдік емес стандартты табиғи сан болса, x·a = a барлық x үшін x = a, x·b = b барлық x үшін x = b, a·a = b және b·b = a анықталатын. Q-ны Зермелоның экстенсионалдылықтан, бос жиынның болуынан және қосылу аксиомасынан тұратын аксиомалық жиынтық теориясының фрагментімен түсіндіруге болады. Бұл теория S' және ST-де қараңыз, толыққанды жиынтық теориясы үшін көбірек мәлімет алу үшін. Q – Пеано арифметикасынан (PA) әлдеқайда әлсіз және аксиомалары тек бір экзистенциалдық квантордан тұратын, түпкілікті аксиомалық бірінші реттік теория. Дегенмен, PA сияқты, ол Гёдельдің толық емес теоремаларының мағынасында толық емес және толық емес, және негізінен шешілмейтін. жоғарыда көрсетілген Q аксиомаларын (1)–(7) PA-да әрбір есептелетін функцияның бейнеленетінін дәлелдеу үшін қажет PA аксиомаларын анықтау арқылы шығарды. Бұл дәлелдеу индукцияның PA аксиомалық схемасын тек жоғарыдағы (3) аксиоманы дәлелдеу үшін пайдаланады, сондықтан барлық есептелетін функциялар Q-да бейнеленеді. Гёдельдің екінші толық еместік теоремасының қорытындысы да Q үшін жарамды: Q-ның рекурсивті аксиоматизацияланған кеңейтуі өзінің тұрақтылығын дәлелдей алмайды, тіпті егер біз дәлелдемелердің Гёдель сандарын анықталатын кесімге шектесек те. Бірінші толық емес теорема тек қана қажетті кодтау құрылымдарын (оның бір бөлігі – Гёдель нөмірлеуі) орындау үшін жеткілікті арифметиканы анықтайтын аксиоматикалық жүйелерге қолданылады. Q аксиомалары осы мақсатқа жеткілікті күшті болуын қамтамасыз ету үшін арнайы таңдалды. Осылайша, бірінші толық емес теореманың әдеттегі дәлелін Q толық емес және шешілмейтінін көрсетуге болады. Бұл PA-ның толық еместігі мен шешілмейтінін оны Q-дан ерекшелейтін жалғыз аспектіге, атап айтқанда индукцияның аксиомалық схемасына кінәлауға болмайтындығын көрсетеді. Жоғарыда көрсетілген жеті аксиоманың кез келгенін тастағанда, Гёдель теоремалары орындалмайды. Q-ның бұл фрагменттері шешілмейтін болып қалады, бірақ олар енді негізінен шешілмейтін емес: олардың тұрақты шешілетін кеңейтулері, сондай-ақ қызықты емес модельдері бар (яғни стандартты табиғи сандардың соңғы кеңейтулері емес модельдер).

On the metamathematics of Q see , , , and The intended interpretation of Q is the natural numbers and their usual arithmetic in which addition and multiplication have their customary meaning, identity is equality, and 0 is the natural number zero. Any model (structure) that satisfies all axioms of Q except possibly axiom (3) has a unique submodel ("the standard part") isomorphic to the standard natural numbers (N, +, ·, S, 0). (Axiom (3) need not be satisfied; for example the polynomials with non negative integer coefficients forms a model that satisfies all axioms except (3).) Q, like Peano arithmetic, has nonstandard models of all infinite cardinalities. However, unlike Peano arithmetic, Tennenbaum's theorem does not apply to Q, and it has computable non standard models. For instance, there is a computable model of Q consisting of integer coefficient polynomials with positive leading coefficient, plus the zero polynomial, with their usual arithmetic. A notable characteristic of Q is the absence of the axiom scheme of induction. Hence it is often possible to prove in Q every specific instance of a fact about the natural numbers, but not the associated general theorem. For example, 5 + 7 = 7 + 5 is provable in Q, but the general statement x + y = y + x is not. Similarly, one cannot prove that Sx ≠ x. A model of Q that fails many of the standard facts is obtained by adjoining two distinct new elements a and b to the standard model of natural numbers and defining Sa = a, Sb = b, x + a = b and x + b = a for all x, a + n = a and b + n = b if n is a standard natural number, x·0 = 0 for all x, a·n = b and b·n = a if n is a non zero standard natural number, x·a = a for all x except x = a, x·b = b for all x except x = b, a·a = b, and b·b = a.

Q is interpretable in a fragment of Zermelo's axiomatic set theory, consisting of extensionality, existence of the empty set, and the axiom of adjunction. This theory is S' in and ST in See general set theory for more details. Q is a finitely axiomatized first order theory that is considerably weaker than Peano arithmetic (PA), and whose axioms contain only one existential quantifier. Yet like PA it is incomplete and incompletable in the sense of Gödel's incompleteness theorems, and essentially undecidable. derived the Q axioms (1)–(7) above by noting just what PA axioms are required to prove that every computable function is representable in PA. The only use this proof makes of the PA axiom schema of induction is to prove a statement that is axiom (3) above, and so, all computable functions are representable in Q. The conclusion of Gödel's second incompleteness theorem also holds for Q: no consistent recursively axiomatized extension of Q can prove its own consistency, even if we additionally restrict Gödel numbers of proofs to a definable cut. The first incompleteness theorem applies only to axiomatic systems defining sufficient arithmetic to carry out the necessary coding constructions (of which Gödel numbering forms a part). The axioms of Q were chosen specifically to ensure they are strong enough for this purpose. Thus the usual proof of the first incompleteness theorem can be used to show that Q is incomplete and undecidable. This indicates that the incompleteness and undecidability of PA cannot be blamed on the only aspect of PA differentiating it from Q, namely the axiom schema of induction. Gödel's theorems do not hold when any one of the seven axioms above is dropped. These fragments of Q remain undecidable, but they are no longer essentially undecidable: they have consistent decidable extensions, as well as uninteresting models (i. e., models that are not end extensions of the standard natural numbers).