Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математикалық теория
Mathematical theory
Математикалық логикада ω-сәйкес (немесе омега-сәйкес, сондай-ақ сандық бөліністі деп аталады) теория – (синтаксикалық) тұжырымды (яғни, қарама-қайшылықты дәлелдемейтін) теория (сөйлемдер жинағы), сонымен қатар интуитивті түрде қарама-қайшылық болып табылатын сөйлемдердің белгілі бір шексіз комбинацияларын дәлелдеуден қашады. Бұл атау Курт Гёдельге тиесілі, ол толық еместік теоремасын дәлелдеу барысында бұл ұғымды енгізген.
In mathematical logic, an ω consistent (or omega consistent, also called numerically segregative) theory is a theory (collection of sentences) that is not only (syntactically) consistent (that is, does not prove a contradiction), but also avoids proving certain infinite combinations of sentences that are intuitively contradictory. The name is due to Kurt Gödel, who introduced the concept in the course of proving the incompleteness theorem.
Анықтама
Теория Т арифметика тілін интерпретациялайды деп айтылады, егер арифметика формулалары Т тіліне аударылатын болса, сонда Т осы аударма бойынша натурал сандардың негізгі аксиомаларын дәлелдей алады. Арифметиканы интерпретациялайтын Т теориясы, егер натурал сандардың P кейбір қасиеттері үшін (Т тіліндегі формуламен анықталған), Т P(0), P(1), P(2) және т.б. дәлелдейтін болса (яғни, кез келген стандартты натурал сан n үшін, Т P(n) екенін дәлелдейді), бірақ Т сонымен қатар P(n) жалған болатын кейбір натурал санның бар екенін дәлелдейтін болса, ω-сәйкессіз болады. Т ω-сәйкессіз болмаса, ω-сәйкестік сақталады. Σ1-беріктігі – бұл одан әлсіз, бірақ тығыз байланысты қасиет. Теория Т Σ1-дыбысты (немесе басқа терминологияда 1-сәйкес) болады, егер Т-де дәлелденетін кез келген Σ01-сөйлем арифметиканың стандартты моделі N-де (яғни, әдеттегі натурал сандардың қосу және көбейту құрылымы) дұрыс болса. Егер Т есептеудің ақылға қонымды моделін формалдауға жеткілікті болса, Σ1-дыбыстылығы – Т Тьюринг машинасы C тоқтағанын дәлелдеген сайын, C шын мәнінде тоқтайтынын талап етуге тең. Кез келген ω-сәйкестік сақталатын теория Σ1-дыбысты, бірақ керісінше емес. Жалпы алғанда, арифметикалық иерархияның жоғары деңгейлері үшін ұқсас ұғымды анықтауға болады. Егер Γ – арифметикалық сөйлемдер жиыны болса (әдетте, n үшін Σ0n), теория Т Γ-дыбысты болады, егер Т-де дәлелденетін кез келген Γ-сөйлем стандартты модельде дұрыс болса. Γ барлық арифметикалық формулалар жиыны болған кезде, Γ-дың дыбыстылығы жай ғана (арифметикалық) дыбыстылық деп аталады. Егер Т тілі тек арифметика тілінен ғана тұрса (мысалы, жинақтар теориясына қарама-қарсы), онда дыбысты жүйе – оның моделін ω жиыны, математикалық натурал сандардың әдеттегі жиыны ретінде қарастыруға болатын жүйе. Жалпы Т жағдайы басқаша, төмендегі ω-логиканы қараңыз. Σn-дыбыстылығы келесі есептеу интерпретациясына ие: егер теория Σn−1 оракулін пайдаланатын C бағдарламасының тоқтағанын дәлелдейтін болса, онда C шын мәнінде тоқтайды.
A theory T is said to interpret the language of arithmetic if there is a translation of formulas of arithmetic into the language of T so that T is able to prove the basic axioms of the natural numbers under this translation. A T that interprets arithmetic is ω inconsistent if, for some property P of natural numbers (defined by a formula in the language of T), T proves P(0), P(1), P(2), and so on (that is, for every standard natural number n, T proves that P(n) holds), but T also proves that there is some natural number n such that P(n) fails. T is ω consistent if it is not ω inconsistent. There is a weaker but closely related property of Σ1 soundness. A theory T is Σ1 sound (or 1 consistent, in another terminology) if every Σ01 sentence provable in T is true in the standard model of arithmetic N (i. e., the structure of the usual natural numbers with addition and multiplication). If T is strong enough to formalize a reasonable model of computation, Σ1 soundness is equivalent to demanding that whenever T proves that a Turing machine C halts, then C actually halts. Every ω consistent theory is Σ1 sound, but not vice versa. More generally, we can define an analogous concept for higher levels of the arithmetical hierarchy. If Γ is a set of arithmetical sentences (typically Σ0n for some n), a theory T is Γ sound if every Γ sentence provable in T is true in the standard model. When Γ is the set of all arithmetical formulas, Γ soundness is called just (arithmetical) soundness. If the language of T consists only of the language of arithmetic (as opposed to, for example, set theory), then a sound system is one whose model can be thought of as the set ω, the usual set of mathematical natural numbers. The case of general T is different, see ω logic below. Σn soundness has the following computational interpretation: if the theory proves that a program C using a Σn−1 oracle halts, then C actually halts.
Тұрақты, ω-тоқтама теориялар
Теория үшін ПА деп жазыңыз, Пеано арифметикасы, және Кон(ПА) – «ПА сәйкес келеді» деген талапты формалдайтын арифметикалық мәлімдеме үшін. Кон(ПА) «0=1 деген дәлелдің ПА-дағы Гёдель саны болатын натурал сан n жоқ» түрінде болуы мүмкін. Олай болса, ПА-ның тұрақтылығы, ПА + ¬Кон(ПА)-ның тұрақтылығын білдіреді. Шындығында, егер ПА + ¬Кон(ПА) сәйкес келмесе, онда ПА ғана ¬Кон(ПА) → 0=1 деп дәлелдейді, ал ПА-да абсурдқа дейін редукция Кон(ПА)-ның дәлелін береді. Гёделдің екінші толық еместік теоремасы бойынша ПА сәйкес келмейді. Сондықтан, ПА тұрақты деп есептесек, ПА + ¬Кон(ПА) да тұрақты болады. Дегенмен, ол ω-сәйкес болмайды. Себебі, кез келген нақты n үшін, ПА, демек ПА + ¬Кон(ПА), n – 0=1 деген дәлелдің Гёдель саны емес екенін дәлелдейді. Бірақ, ПА + ¬Кон(ПА) кейбір натурал сан n үшін, n – осындай дәлелдің Гёдель саны екенін дәлелдейді (бұл тек ¬Кон(ПА) талабын тікелей қайталау). Бұл мысалда аксиома ¬Кон(ПА) – Σ1, сондықтан жүйе ПА + ¬Кон(ПА) шын мәнінде Σ1 дұрыс емес, жай ғана ω-сәйкессіз емес.
Write PA for the theory Peano arithmetic, and Con(PA) for the statement of arithmetic that formalizes the claim "PA is consistent". Con(PA) could be of the form "No natural number n is the Gödel number of a proof in PA that 0=1". Now, the consistency of PA implies the consistency of PA + ¬Con(PA). Indeed, if PA + ¬Con(PA) was inconsistent, then PA alone would prove ¬Con(PA)→0=1, and a reductio ad absurdum in PA would produce a proof of Con(PA). By Gödel's second incompleteness theorem, PA would be inconsistent. Therefore, assuming that PA is consistent, PA + ¬Con(PA) is consistent too. However, it would not be ω consistent. This is because, for any particular n, PA, and hence PA + ¬Con(PA), proves that n is not the Gödel number of a proof that 0=1. However, PA + ¬Con(PA) proves that, for some natural number n, n is the Gödel number of such a proof (this is just a direct restatement of the claim ¬Con(PA)). In this example, the axiom ¬Con(PA) is Σ1, hence the system PA + ¬Con(PA) is in fact Σ1 unsound, not just ω inconsistent.
Арифметикалық тұрғыдан дұрыс емес, ω-қанықты теориялар
ω Con(PA) – «ПА ω-сәйкес» деген мәлімдемені формалдайтын арифметикалық өрнек болсын. Онда, ПА + ¬ω Con(ПА) теориясы дұрыс емес (нақтырақ айтқанда, Σ3 дұрыс емес), бірақ ω-сәйкес. Дәлел бірінші мысалға ұқсас: «дәлелделу предикаты» үшін Хилберт-Бернейс-Лёбтың туындылық шарттарының қолайлы түрі қолданылады, яғни ω Prov(A) = ¬ω Con(PA + ¬A), сондықтан ол Гёдельдің екінші толық еместік теоремасының аналогын қанағаттандырады.
Let ω Con(PA) be the arithmetical sentence formalizing the statement "PA is ω consistent". Then the theory PA + ¬ω Con(PA) is unsound (Σ3 unsound, to be precise), but ω consistent. The argument is similar to the first example: a suitable version of the Hilbert–Bernays–Löb derivability conditions holds for the "provability predicate" ω Prov(A) = ¬ω Con(PA + ¬A), hence it satisfies an analogue of Gödel's second incompleteness theorem.