Математикалық логика – математика ішіндегі формалды логиканы зерттейтін сала. Модельдер теориясы, дәлелдеу теориясы, жиын теориясы, есептеу теориясы кіреді.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математиканың кіші саласы
Subfield of mathematics
Математикалық логика – математика ішіндегі формальды логиканы зерттеу. Басты кіші салалары модельдер теориясы, дәлелдеу теориясы, жиын теориясы және рекурсия теориясы (сондай-ақ есептеу теориясы деп те аталады) болып табылады. Математикалық логикадағы зерттеулер көбінесе логиканың формальды жүйелерінің математикалық қасиеттерін, мысалы, олардың экспрессивті немесе дедуктивті күшін қарастырады. Дегенмен, бұл логиканы дұрыс математикалық ойлауды сипаттауға немесе математиканың негізін қалауға пайдалануды да қамти алады. Математикалық логика пайда болған сәтінен бастап математика негіздерін зерттеуге үлес қосып, сонымен бірге осы зерттеулерге ынталанды. Бұл зерттеу 19 ғасырдың соңында геометрия, арифметика және анализ үшін аксиоматикалық негіздерді жасаумен басталды. 20 ғасырдың басында Дэвид Гильберттің негізгі теориялардың дәйектілігін дәлелдеу бағдарламасымен қалыптасты. Курт Гёдель, Герхард Гентцен және басқалардың нәтижелері бағдарламаны ішінара шешіп, дәйектілікті дәлелдеуге байланысты мәселелерді анықтады. Жиын теориясындағы жұмыстар математиканың көп бөлігін жиындар арқылы формалдауға болатынын көрсетті, бірақ жиын теориясының жалпы аксиомалық жүйелерінде дәлелдеуге болмайтын теоремалар да бар. Қазіргі кезде математика негіздері бойынша жұмыс көбінесе математиканың қандай бөліктерін нақты формальды жүйелерде формалдауға болатынын анықтауға (мысалы, кері математикада) бағытталған, математиканың барлық бөлігін дамытуға болатын теорияларды табуға талпынудан гөрі.
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establish foundations of mathematics. Since its inception, mathematical logic has both contributed to and been motivated by the study of foundations of mathematics. This study began in the late 19th century with the development of axiomatic frameworks for geometry, arithmetic, and analysis. In the early 20th century it was shaped by David Hilbert's program to prove the consistency of foundational theories. Results of Kurt Gödel, Gerhard Gentzen, and others provided partial resolution to the program, and clarified the issues involved in proving consistency. Work in set theory showed that almost all ordinary mathematics can be formalized in terms of sets, although there are some theorems that cannot be proven in common axiom systems for set theory. Contemporary work in the foundations of mathematics often focuses on establishing which parts of mathematics can be formalized in particular formal systems (as in reverse mathematics) rather than trying to find theories in which all of mathematics can be developed.
Тарих
Математикалық логика 19-ғасырдың ортасында математиканың кіші саласы ретінде пайда болды, бұл формалды философиялық логика мен математика екі дәстүрінің тоғысуын көрсетеді. Математикалық логика, сондай-ақ "логистика", "символикалық логика", "логика алгебрасы" және, соңғы кезде, жай ғана "формальдық логика" деп те аталады, – бұл 19-ғасырда жасалған жасанды нотация және қатаң дедуктивті әдіс арқылы дамытылған логикалық теориялардың жиынтығы. Осыған дейін логика риторика, есептеулер, силлогизм және философия арқылы зерттелді. 20-ғасырдың бірінші жартысында математика негіздері жөніндегі белсенді пікірталастармен бірге маңызды жаңалықтардың көптеген табыстары орын алды.
Mathematical logic emerged in the mid 19th century as a subfield of mathematics, reflecting the confluence of two traditions: formal philosophical logic and mathematics. Mathematical logic, also called 'logistic', 'symbolic logic', the 'algebra of logic', and, more recently, simply 'formal logic', is the set of logical theories elaborated in the course of the nineteenth century with the aid of an artificial notation and a rigorously deductive method. Before this emergence, logic was studied with rhetoric, with calculationes, through the syllogism, and with philosophy. The first half of the 20th century saw an explosion of fundamental results, accompanied by vigorous debate over the foundations of mathematics.
Ерте тарих
Логика теориясы тарих бойы Қытай, Үндістан, Грекия және Ислам әлемі сияқты көптеген мәдениеттерде дамыды. Грек әдістері, әсіресе Аристотельдік логика (немесе термин логикасы), Органон еңбектерінде келгендей, мыңжылдықтар бойы Батыс ғылымы мен математикасында кең қолданысқа ие болып, қабылдауға алынды. Стоиктер, әсіресе Хрисипп, предикаттық логиканы дамытуды бастады. 18 ғасырдағы Еуропада Лейбниц және Ламберт сияқты философиялық математиктер формальды логиканың амалдарын символдық немесе алгебралық түрде қарастыруға тырысты, бірақ олардың еңбектері жеке-жеке және көпке танылмады.
Theories of logic were developed in many cultures in history, including China, India, Greece and the Islamic world. Greek methods, particularly Aristotelian logic (or term logic) as found in the Organon, found wide application and acceptance in Western science and mathematics for millennia. The Stoics, especially Chrysippus, began the development of predicate logic. In 18th century Europe, attempts to treat the operations of formal logic in a symbolic or algebraic way had been made by philosophical mathematicians including Leibniz and Lambert, but their labors remained isolated and little known.
19 ғасыр
XIX ғасырдың ортасында Джордж Буль, содан кейін Август Де Морган логиканы жүйелі математикалық тұрғыдан қарастыруды ұсынды. Олардың жұмысы Джордж Пикок сияқты алгебраистердің еңбектеріне негізделіп, дәстүрлі Аристотельдің логика туралы ілімін математика негіздерін зерттеуге жеткілікті аяға жеткізді. 1847 жылы Ватрослав Бертич Бульден тәуелсіз түрде логиканы алгебралау бойынша маңызды жұмыс жасады. Чарльз Сандерс Пирс кейіннен Бульдің еңбегіне сүйене отырып, қатынастар мен кванторлар үшін логикалық жүйе құрастырды, оны 1870 жылдан 1885 жылға дейін бірнеше мақаласында жариялады. Готтлоб Фреге 1879 жылы жарық көрген "Begriffsschrift" еңбегінде кванторлары бар логиканың тәуелсіз дамуын ұсынды, бұл еңбек логика тарихындағы шешімді кезең ретінде қарастырылады. Дегенмен, Фреге еңбегі Бертран Рассел оны ғасыр басында насияттағанға дейін көпке белгісіз болып қалды. Фреге жасаған екі өлшемді нотация кеңінен қолданылмады және қазіргі заманғы мәтіндерде қолданылмайды. 1890-1905 жылдары Эрнст Шредер "Vorlesungen über die Algebra der Logik" атты үш томдық еңбегін жариялады. Бұл жұмыс Буль, Де Морган және Пирстің еңбектерін жинақтап, дамытты және 19 ғасырдың соңында түсінілгендей, символдық логикаға толық сілтеме болып табылды.
In the middle of the nineteenth century, George Boole and then Augustus De Morgan presented systematic mathematical treatments of logic. Their work, building on work by algebraists such as George Peacock, extended the traditional Aristotelian doctrine of logic into a sufficient framework for the study of foundations of mathematics. In 1847. Vatroslav Bertić made substantial work on algebraization of logic, independently from Boole. Charles Sanders Peirce later built upon the work of Boole to develop a logical system for relations and quantifiers, which he published in several papers from 1870 to 1885. Gottlob Frege presented an independent development of logic with quantifiers in his Begriffsschrift, published in 1879, a work generally considered as marking a turning point in the history of logic. Frege's work remained obscure, however, until Bertrand Russell began to promote it near the turn of the century. The two dimensional notation Frege developed was never widely adopted and is unused in contemporary texts. From 1890 to 1905, Ernst Schröder published Vorlesungen über die Algebra der Logik in three volumes. This work summarized and extended the work of Boole, De Morgan, and Peirce, and was a comprehensive reference to symbolic logic as it was understood at the end of the 19th century.
Негізгі теориялар
Математиканың дұрыс негізге салынбағаны туралы алаңдаушылықтар математиканың арифметика, талдау және геометрия сияқты негізгі салалары үшін аксиоматикалық жүйелерді дамытуға әкелді. Логикада арифметика термині табиғи сандар теориясын білдіреді. Джузеппе Пеано Буль мен Шредердің логикалық жүйесінің өзгертілген нұсқасын қолданып, бірақ кванторларды қосып, арифметика үшін аксиомалар жиынтығын жариялады. Пеано сол кезде Фрегедің жұмысынан хабарсыз болды. Шамамен сол уақытта Ричард Дедекинд табиғи сандардың индукциялық қасиеттерімен толық сипатталатынын көрсетті. Дедекинд Пеано аксиомаларының формалды логикалық сипатына ие болмаған басқа сипаттаманы ұсынды. Дедекиндтің жұмысы, алайда, Пеано жүйесінде қолжетімсіз теоремаларды дәлелдеді, соның ішінде табиғи сандар жиынының бірегейлігі (изоморфизмге дейін) және жаңару функциясы мен математикалық индукциядан қосу және көбейтудің рекурсивті анықтамалары. 19 ғасырдың ортасында Евклидтің геометрия аксиомаларындағы қателер анықталды. 1826 жылы Николай Лобачевскийдің параллельдік постулатының тәуелсіздігіне қоса, математиктер Евклидтің өздері үшін айқын деп санайтын кейбір теоремалардың оның аксиомаларынан дәлелденбейтінін анықтады. Олардың арасында түзу сызықта кем дегенде екі нүкте болуы керек немесе орталары сол радиуспен бөлінген бірдей радиустағы шеңберлердің қиылысуы керек деген теорема бар. Гильберт Паштің бұрынғы жұмысына сүйене отырып, геометрия үшін аксиомалардың толық жиынтығын жасады. Геометрияны аксиоматизациялаудағы табыс Гильбертті математиканың басқа салаларын, мысалы, табиғи сандар мен нақты сызықты толық аксиоматизациялауға талпындырды. Бұл 20 ғасырдың бірінші жартысындағы маңызды зерттеу саласы болды. 19 ғасырда нақты талдау теориясында үлкен жетістіктер болды, оның ішінде функциялардың және Фурье қатарларының жуықтасу теориясы да бар. Карл Вейерштрасс сияқты математиктер интуицияны күйрететін функцияларды, мысалы, ешқандай жерде туындысы жоқ үздіксіз функцияларды құра бастады. Функцияны есептеу ережесі немесе тегіс график ретіндегі бұрынғы түсініктер енді жеткіліксіз болды. Вейерштрасс талдауды арифметикалық тұрғыдан қарастыруды жақтады, ол табиғи сандардың қасиеттерін пайдаланып талдауды аксиоматизациялауға бағытталды. Қазіргі заманғы (ε, δ) шек және үздіксіз функциялардың анықтамасы 1817 жылы Болцаномен әзірленген, бірақ салыстырмалы түрде белгісіз қалды. Коши 1821 жылы үздіксіздікті шексіз кішкентай шамалар тұрғысынан анықтады (Cours d'Analyse, 34-бет). 1858 жылы Дедекинд рационал сандардың Дедекинд кесулері арқылы нақты сандардың анықтамасын ұсынды, бұл анықтама қазіргі заманғы оқулықтарда да қолданылады. Георг Кантор шексіз жиын теориясының негізгі ұғымдарын дамытты. Оның алғашқы нәтижелері кардиналдық теорияны дамытты және нақты және табиғи сандардың әртүрлі кардиналдықтары бар екенін дәлелдеді. Келесі жиырма жылда Кантор бірнеше жарияланымдарда трансфинит сандар теориясын дамытты. 1891 жылы ол диагональ аргументін енгізген нақты сандардың санауға келмейтінінің жаңа дәлелін жариялады және осы әдісті Кантор теоремасын дәлелдеу үшін қолданды, ешбір жиын өзінің қуат жиынымен бірдей кардиналдыққа ие бола алмайды. Кантор әрбір жиынды жақсы реттеуге болады деп сенді, бірақ осы нәтижеге дәлел келтіре алмады, оны 1895 жылы ашық мәселе ретінде қалдырды.
Concerns that mathematics had not been built on a proper foundation led to the development of axiomatic systems for fundamental areas of mathematics such as arithmetic, analysis, and geometry. In logic, the term arithmetic refers to the theory of the natural numbers. Giuseppe Peano published a set of axioms for arithmetic that came to bear his name (Peano axioms), using a variation of the logical system of Boole and Schröder but adding quantifiers. Peano was unaware of Frege's work at the time. Around the same time Richard Dedekind showed that the natural numbers are uniquely characterized by their induction properties. Dedekind proposed a different characterization, which lacked the formal logical character of Peano's axioms. Dedekind's work, however, proved theorems inaccessible in Peano's system, including the uniqueness of the set of natural numbers (up to isomorphism) and the recursive definitions of addition and multiplication from the successor function and mathematical induction. In the mid 19th century, flaws in Euclid's axioms for geometry became known. In addition to the independence of the parallel postulate, established by Nikolai Lobachevsky in 1826, mathematicians discovered that certain theorems taken for granted by Euclid were not in fact provable from his axioms. Among these is the theorem that a line contains at least two points, or that circles of the same radius whose centers are separated by that radius must intersect. Hilbert developed a complete set of axioms for geometry, building on previous work by Pasch. The success in axiomatizing geometry motivated Hilbert to seek complete axiomatizations of other areas of mathematics, such as the natural numbers and the real line. This would prove to be a major area of research in the first half of the 20th century. The 19th century saw great advances in the theory of real analysis, including theories of convergence of functions and Fourier series. Mathematicians such as Karl Weierstrass began to construct functions that stretched intuition, such as nowhere differentiable continuous functions. Previous conceptions of a function as a rule for computation, or a smooth graph, were no longer adequate. Weierstrass began to advocate the arithmetization of analysis, which sought to axiomatize analysis using properties of the natural numbers. The modern (ε, δ) definition of limit and continuous functions was already developed by Bolzano in 1817, but remained relatively unknown. Cauchy in 1821 defined continuity in terms of infinitesimals (see Cours d'Analyse, page 34). In 1858, Dedekind proposed a definition of the real numbers in terms of Dedekind cuts of rational numbers, a definition still employed in contemporary texts. Georg Cantor developed the fundamental concepts of infinite set theory. His early results developed the theory of cardinality and proved that the reals and the natural numbers have different cardinalities. Over the next twenty years, Cantor developed a theory of transfinite numbers in a series of publications. In 1891, he published a new proof of the uncountability of the real numbers that introduced the diagonal argument, and used this method to prove Cantor's theorem that no set can have the same cardinality as its powerset. Cantor believed that every set could be well ordered, but was unable to produce a proof for this result, leaving it as an open problem in 1895.
20 ғасыр
20 ғасырдың басындағы онжылдықтарда жиын теориясы және формальды логика зерттеудің басты салалары болды. Бейресми жиын теориясындағы парадокстардың табылуы кейбір ғалымдарды математиканың өзі дұрыс емес пе деп ойландырып, тұрақтылығын дәлелдеуге тырыстырды. 1900 жылы Гильберт келесі ғасырға арналған 23 мәселенің танымал тізімін ұсынды. Олардың бірінші екеуі континуум гипотезасын шешу және элементар арифметиканың тұрақтылығын дәлелдеу болды; ал оныншысы – бүтін сандардағы көп айнымалы полиномдық теңдеудің шешімі бар-жоғын анықтайтын әдіс табу болды. Осы мәселелерді шешуге жасалған жұмыстар математикалық логиканың даму бағытын анықтады, сондай-ақ 1928 жылы қойылған Гильберттің Entscheidungsproblem мәселесін шешуге жасалған күш-жігер де маңызды рөл атқарды. Бұл мәселе берілген математикалық тұжырымның дұрыс немесе бұрыс екенін анықтайтын процедураны сұрады.
In the early decades of the 20th century, the main areas of study were set theory and formal logic. The discovery of paradoxes in informal set theory caused some to wonder whether mathematics itself is inconsistent, and to look for proofs of consistency. In 1900, Hilbert posed a famous list of 23 problems for the next century. The first two of these were to resolve the continuum hypothesis and prove the consistency of elementary arithmetic, respectively; the tenth was to produce a method that could decide whether a multivariate polynomial equation over the integers has a solution. Subsequent work to resolve these problems shaped the direction of mathematical logic, as did the effort to resolve Hilbert's Entscheidungsproblem, posed in 1928. This problem asked for a procedure that would decide, given a formalized mathematical statement, whether the statement is true or false.
Жинақтар теориясы және парадокстар
Эрнст Зермело кез келген жиынның жақсы реттелген болуын дәлелдеді, бұл нәтижені Георг Канторға қол жеткізе алмады. Дәлелге жету үшін Зермело таңдау аксиомасын енгізді, ол математиктер мен жиын теориясының негізін қалаушылары арасында қызу пікірталас пен зерттеулерге себеп болды. Әдістің бірден сынға ұшырауы Зермелоны оның дәлеліне қатысты сын-тегеурістерге тікелей жауап бере отырып, нәтижесінің екінші баяндамасын жариялауға итермеледі. Бұл еңбек математикалық қауымдастықта таңдау аксиомасын қабылдауға әкелді. Таңдау аксиомасына деген күмәнділік, жақында наив жиын теориясында ашылған парадокстармен күшейді. Чезаре Бурали Форти алғаш рет парадокс айтты: Бурали Форти парадоксі барлық реттік сандар жиыны жиын құрай алмайтынын көрсетеді. Одан көп ұзамай, 1901 жылы Бертран Рассел Расселдің парадоксын, ал Жюль Ришар Ришардың парадоксын ашты. Зермело жиын теориясы үшін аксиомалардың алғашқы жиынтығын ұсынды. Бұл аксиомалар, Абрахам Френкель ұсынған қосымша алмастыру аксиомасымен бірге, қазір Зермело-Френкель жиын теориясы (ZF) деп аталады. Зермело аксиомалары Расселдің парадоксінен аулақ болу үшін өлшемді шектеу принципін қамтыды. 1910 жылы Рассел мен Альфред Норт Уайтхедтің Principia Mathematica еңбегінің бірінші томы жарық көрді. Бұл маңызды еңбек функциялар теориясын және кардиналдылықты типтер теориясының толыққанды формалды шеңберінде дамытты, оны Рассел мен Уайтхед парадокстардан сақтану үшін жасады. Principia Mathematica 20-ғасырдың ең ықпалды еңбектерінің бірі саналады, бірақ типтер теориясы математиканың негізгі теориясы ретінде кең танылмады. Френкель таңдау аксиомасын Зермелоның элементарлық жиындары бар жиын теориясының аксиомаларынан дәлелдеуге болмайтынын дәлелдеді. Пол Коэннің кейінгі жұмыстары элементарлық жиындарды қосудың қажеті жоқ екенін көрсетті, ал таңдау аксиомасы ZF-де дәлелденбейді. Коэннің дәлелі мәжбүрлеу әдісін дамытты, ол қазір жиын теориясында тәуелсіздік нәтижелерін орнату үшін маңызды құрал болып табылады.
Ernst Zermelo gave a proof that every set could be well ordered, a result Georg Cantor had been unable to obtain. To achieve the proof, Zermelo introduced the axiom of choice, which drew heated debate and research among mathematicians and the pioneers of set theory. The immediate criticism of the method led Zermelo to publish a second exposition of his result, directly addressing criticisms of his proof. This paper led to the general acceptance of the axiom of choice in the mathematics community. Skepticism about the axiom of choice was reinforced by recently discovered paradoxes in naive set theory. Cesare Burali Forti was the first to state a paradox: the Burali Forti paradox shows that the collection of all ordinal numbers cannot form a set. Very soon thereafter, Bertrand Russell discovered Russell's paradox in 1901, and Jules Richard discovered Richard's paradox. Zermelo provided the first set of axioms for set theory. These axioms, together with the additional axiom of replacement proposed by Abraham Fraenkel, are now called Zermelo–Fraenkel set theory (ZF). Zermelo's axioms incorporated the principle of limitation of size to avoid Russell's paradox. In 1910, the first volume of Principia Mathematica by Russell and Alfred North Whitehead was published. This seminal work developed the theory of functions and cardinality in a completely formal framework of type theory, which Russell and Whitehead developed in an effort to avoid the paradoxes. Principia Mathematica is considered one of the most influential works of the 20th century, although the framework of type theory did not prove popular as a foundational theory for mathematics. Fraenkel proved that the axiom of choice cannot be proved from the axioms of Zermelo's set theory with urelements. Later work by Paul Cohen showed that the addition of urelements is not needed, and the axiom of choice is unprovable in ZF. Cohen's proof developed the method of forcing, which is now an important tool for establishing independence results in set theory.
Символикалық логика
Леопольд Лёвенхайм мен Торальф Сколем Лёвенхайм-Сколем теоремасын алды, ол бірінші реттік логика шексіз құрылымдардың кардиналдықтарын бақылауға мүмкіндік бермейді дейді. Сколем бұл теорема жинақтар теориясының бірінші реттік формализацияларына да қатысты екенін, және оның нәтижесінде кез келген мұндай формализацияның саналатын модельі болатынын түсінді. Бұл интуицияға қайшы келетін факті Сколемнің парадоксы деп аталды. Курт Гёдель өз докторлық диссертациясында бірінші реттік логикадағы синтаксис пен семантика арасындағы сәйкестікті орнататын толықтық теоремасын дәлелдеді. Гёдель толықтық теоремасын бірінші реттік логикалық салдардың шекті табиғатын көрсететін тұйықталғандық теоремасын дәлелдеу үшін пайдаланды. Бұл нәтижелер математиктер қолданатын басым логика ретінде бірінші реттік логиканың орнауына көмектесті. 1931 жылы Гёдель «Principia Mathematica және байланысты жүйелердің формальды түрде шешілмейтін ұсыныстары туралы» еңбегін жариялады, ол жеткілікті күшті және тиімді бірінші реттік теориялардың толық еместігін (сөздің басқа мағынасында) дәлелдеді. Бұл нәтиже Гёдельдің толық емес теоремасы деп белгілі, ол математиканың аксиоматикалық негіздеріне қатысты маңызды шектеулерді қояды және Гилберт бағдарламасына күшті соққы береді. Ол арифметиканың кез келген формальды теориясы шеңберінде арифметиканың дәйектілігін дәлелдеудің мүмкін еместігін көрсетті. Алайда, Гилберт толық емес теореманың маңыздылығын бірден мойындамады. Гёдельдің теоремасы, егер жүйе дәйекті болса, кез келген жеткілікті күшті және тиімді аксиомалық жүйенің өзінде немесе одан әлсіз жүйеде дәйектілік дәлелін алу мүмкін еместігін көрсетеді. Бұл олар қарастыратын жүйеде формалдауға болмайтын дәйектілік дәлелдерінің болу мүмкіндігін ашып береді. Гентцен трансфиниттік индукция принципімен бірге шекті жүйе арқылы арифметиканың дәйектілігін дәлелдеді. Гентценнің нәтижесі кесуді жою және дәлелдеу теориялық ординалдар идеяларын енгізді, олар дәлелдеу теориясының маңызды құралдарына айналды. Гёдель басқаша дәйектілік дәлелін ұсынды, ол классикалық арифметиканың дәйектілігін жоғары типтегі интуициялық арифметикаға дейін келтіреді. Символикалық логика бойынша алғашқы оқулықты 1896 жылы «Алисаның ғажайыптар еліндегі оқиғалары» атты кітабының авторы Льюис Кэрролл жазды.
Leopold Löwenheim and Thoralf Skolem obtained the Löwenheim–Skolem theorem, which says that first order logic cannot control the cardinalities of infinite structures. Skolem realized that this theorem would apply to first order formalizations of set theory, and that it implies any such formalization has a countable model. This counterintuitive fact became known as Skolem's paradox. In his doctoral thesis, Kurt Gödel proved the completeness theorem, which establishes a correspondence between syntax and semantics in first order logic. Gödel used the completeness theorem to prove the compactness theorem, demonstrating the finitary nature of first order logical consequence. These results helped establish first order logic as the dominant logic used by mathematicians. In 1931, Gödel published On Formally Undecidable Propositions of Principia Mathematica and Related Systems, which proved the incompleteness (in a different meaning of the word) of all sufficiently strong, effective first order theories. This result, known as Gödel's incompleteness theorem, establishes severe limitations on axiomatic foundations for mathematics, striking a strong blow to Hilbert's program. It showed the impossibility of providing a consistency proof of arithmetic within any formal theory of arithmetic. Hilbert, however, did not acknowledge the importance of the incompleteness theorem for some time. Gödel's theorem shows that a consistency proof of any sufficiently strong, effective axiom system cannot be obtained in the system itself, if the system is consistent, nor in any weaker system. This leaves open the possibility of consistency proofs that cannot be formalized within the system they consider. Gentzen proved the consistency of arithmetic using a finitistic system together with a principle of transfinite induction. Gentzen's result introduced the ideas of cut elimination and proof theoretic ordinals, which became key tools in proof theory. Gödel gave a different consistency proof, which reduces the consistency of classical arithmetic to that of intuitionistic arithmetic in higher types. The first textbook on symbolic logic for the layman was written by Lewis Carroll, author of Alice's Adventures in Wonderland, in 1896.
Басқа салалардың басталуы
Альфред Тарски модель теориясының негіздерін жасады. 1935 жылдан бастап белгілі математиктер тобы Николас Бурбаки деген псевдониммен бірлесіп, математиканың энциклопедиялық мәтіндерінің сериясы – Éléments de mathématique-ді жариялады. Бұл мәтіндер қатаң және аксиомалық стильде жазылған, қатаң баяндауға баса назар аударды және жиын теориясы негіздерін құрды. Осы мәтіндерде жасалған терминология, мысалы, биекция, инъекция және сюржеция сөздері, сондай-ақ мәтіндер қолданған жиын теориясы негіздері математиканың барлық саласында кеңінен қолданылды. Есептеуге қабілеттілікті зерттеу рекурсия теориясы немесе есептеу қабілеттілігі теориясы деп аталды, өйткені Гёдель мен Клейннің алғашқы формализациялары функциялардың рекурсивті анықтамаларына негізделген. Бұл анықтамалар Тьюринг машиналарын қолданатын Тьюрингтің формализациясына эквивалентті болып көрінген кезде, жаңа түсінік – есептеуге болатын функция – ашылғаны және бұл анықтама көптеген тәуелсіз сипаттамаларды қабылдауға жеткілікті берік екендігі анық болды. 1931 жылы толымсыздық теоремалары бойынша жұмысында Гёдельдің тиімді формальды жүйе туралы қатаң тұжырымдамасы болмады; ол дереу есептеудің жаңа анықтамасы осы мақсатта қолданылатынын, оған толымсыздық теоремаларын бастапқы мақалада ғана айтуға болатын жалпылама түрде көрсетуге мүмкіндік беретінін түсінді. Рекурсия теориясының көптеген нәтижелерін 1940 жылдары Стивен Коул Клин және Эмиль Леон Пост алды. Клин Тьюринг болжаған салыстырмалы есептеу және арифметикалық иерархия түсініктерін енгізді. Кейін Клин рекурсия теориясын жоғары ретті функционалдарға жалпылады. Клин мен Георг Крайзель интуиционисттік математиканың, әсіресе дәлелдеу теориясының формальды нұсқаларын зерттеді.
Alfred Tarski developed the basics of model theory. Beginning in 1935, a group of prominent mathematicians collaborated under the pseudonym Nicolas Bourbaki to publish Éléments de mathématique, a series of encyclopedic mathematics texts. These texts, written in an austere and axiomatic style, emphasized rigorous presentation and set theoretic foundations. Terminology coined by these texts, such as the words bijection, injection, and surjection, and the set theoretic foundations the texts employed, were widely adopted throughout mathematics. The study of computability came to be known as recursion theory or computability theory, because early formalizations by Gödel and Kleene relied on recursive definitions of functions. When these definitions were shown equivalent to Turing's formalization involving Turing machines, it became clear that a new concept – the computable function – had been discovered, and that this definition was robust enough to admit numerous independent characterizations. In his work on the incompleteness theorems in 1931, Gödel lacked a rigorous concept of an effective formal system; he immediately realized that the new definitions of computability could be used for this purpose, allowing him to state the incompleteness theorems in generality that could only be implied in the original paper. Numerous results in recursion theory were obtained in the 1940s by Stephen Cole Kleene and Emil Leon Post. Kleene introduced the concepts of relative computability, foreshadowed by Turing, and the arithmetical hierarchy. Kleene later generalized recursion theory to higher order functionals. Kleene and Georg Kreisel studied formal versions of intuitionistic mathematics, particularly in the context of proof theory.
Формалды логикалық жүйелер
Математикалық логиканың мәні – формалды логикалық жүйелерді пайдалану арқылы математикалық ұғымдарды өрнектеуде. Бұл жүйелер көптеген егжей-тегжейлі айырмашылықтарға қарамастан, тек белгілі бір формалды тілдегі өрнектерді қарастыру қасиетімен ортақ. Қағидалық логика және бірінші реттік логика жүйелері математика негіздеріне қолданылуы және олардың дәлелдеу теориясының қасиеттеріне байланысты бүгінге дейін ең көп зерттелген. Екінші реттік логика немесе шексіз логика сияқты күшті классикалық логикалар, сондай-ақ интуиционистік логика сияқты классикалық емес логикалар да зерттеледі.
At its core, mathematical logic deals with mathematical concepts expressed using formal logical systems. These systems, though they differ in many details, share the common property of considering only expressions in a fixed formal language. The systems of propositional logic and first order logic are the most widely studied today, because of their applicability to foundations of mathematics and because of their desirable proof theoretic properties. Stronger classical logics such as second order logic or infinitary logic are also studied, along with Non classical logics such as intuitionistic logic.
Бірінші реттік логика
Бірінші реттік логика – логиканың нақты бір формальды жүйесі. Оның синтаксисі тек шекті өрнектер мен дұрыс құрылған формулаларды қамтиды, ал семантикасы барлық кванторлардың дискурстың белгілі бір доменімен шектелуімен сипатталады. Формальды логиканың алғашқы нәтижелері бірінші реттік логиканың шектеулерін көрсетті. Лёвенхайм-Сколем теоремасы (1919) егер бірінші реттік тілдегі сөйлемдер жиынында шексіз модель болса, онда ол әрбір шексіз кардиналдықтағы кем дегенде бір модельге ие екенін көрсетті. Бұл бірінші реттік аксиомалар жиыны табиғи сандарды, нақты сандарды немесе изоморфизмге дейін кез келген басқа шексіз құрылымды толыққанды сипаттамайтынын көрсетеді. Математиканың барлық бөлімдері үшін аксиоматикалық теориялар жасау алғашқы іргелі зерттеулердің мақсаты болғандықтан, бұл шектеу ерекше көзге түсті. Гёдельдің толықтық теоремасы бірінші реттік логикадағы логикалық салдардың семантикалық және синтаксикалық анықтамаларының эквиваленттігін орнатты. Ол егер белгілі бір сөйлем белгілі бір аксиомалар жиынын қанағаттандыратын әрбір модельде дұрыс болса, онда бұл сөйлем аксиомалардан шекті түрде шығарылуы керек екенін көрсетеді. Компакттылық теоремасы алғаш рет Гёдельдің толықтық теоремасын дәлелдеуде лемма ретінде пайда болды, және логиктер оның маңыздылығын ұғып, оны жүйелі түрде қолдануға көп уақыт кетті. Ол сөйлемдер жиынында модель бар, егер және тек егер әрбір шекті ішкі жиынында модель болса, яғни, формулалардың қайшы жиынында шекті қайшы ішкі жиыны болуы керек. Толықтық және компакттылық теоремалары бірінші реттік логикадағы логикалық салдарды терең талдауға және модельдер теориясын дамытуға мүмкіндік береді, сонымен қатар математикада бірінші реттік логиканың маңыздылығының басты себебі болып табылады. Гёдельдің толық еместік теоремалары бірінші реттік аксиоматизацияларға қосымша шектеулер қояды. Бірінші толық еместік теоремасы, арифметиканы интерпретациялай алатын, дәйекті және тиімді берілген (төменде анықталған) кез келген логикалық жүйе үшін, бұл жүйеде дәлелдеуге болмайтын, бірақ табиғи сандар үшін дұрыс болатын (яғни, оларға қатысты дұрыс) бір мәлімдеме бар екенін айтады (сонымен қатар, бұл мәлімдеме логикалық жүйемен үйлесімді болатын арифметиканың кейбір стандартты емес модельдерінде жалған болуы мүмкін). Мысалы, Пеано аксиомаларын білдіре алатын кез келген логикалық жүйеде Гёдель сөйлемі табиғи сандар үшін дұрыс, бірақ дәлелдеуге болмайды. Логикалық жүйе тиімді берілген деп есептеледі, егер жүйе тіліндегі кез келген формула берілгенде, бұл формула аксиома болып табыла ма, жоқ па, дегенді анықтау мүмкін болса, ал Пеано аксиомаларын білдіре алатын жүйе "жеткілікті күшті" деп аталады. Бірінші реттік логикаға қолданғанда, бірінші толық еместік теоремасы кез келген жеткілікті күшті, дәйекті және тиімді бірінші реттік теорияда элементарлық эквивалентті емес модельдер бар екенін білдіреді, бұл Лёвенхайм-Сколем теоремасымен белгіленгеннен де күшті шектеу. Екінші толық еместік теоремасы арифметика үшін жеткілікті күшті, дәйекті және тиімді аксиомалық жүйе өзінің дәйектілігін дәлелдей алмайды деп мәлімдейді, бұл Гилберт бағдарламасына қол жеткізу мүмкін емес екенін көрсетеді.
First order logic is a particular formal system of logic. Its syntax involves only finite expressions as well formed formulas, while its semantics are characterized by the limitation of all quantifiers to a fixed domain of discourse. Early results from formal logic established limitations of first order logic. The Löwenheim–Skolem theorem (1919) showed that if a set of sentences in a countable first order language has an infinite model then it has at least one model of each infinite cardinality. This shows that it is impossible for a set of first order axioms to characterize the natural numbers, the real numbers, or any other infinite structure up to isomorphism. As the goal of early foundational studies was to produce axiomatic theories for all parts of mathematics, this limitation was particularly stark. Gödel's completeness theorem established the equivalence between semantic and syntactic definitions of logical consequence in first order logic. It shows that if a particular sentence is true in every model that satisfies a particular set of axioms, then there must be a finite deduction of the sentence from the axioms. The compactness theorem first appeared as a lemma in Gödel's proof of the completeness theorem, and it took many years before logicians grasped its significance and began to apply it routinely. It says that a set of sentences has a model if and only if every finite subset has a model, or in other words that an inconsistent set of formulas must have a finite inconsistent subset. The completeness and compactness theorems allow for sophisticated analysis of logical consequence in first order logic and the development of model theory, and they are a key reason for the prominence of first order logic in mathematics. Gödel's incompleteness theorems establish additional limits on first order axiomatizations. The first incompleteness theorem states that for any consistent, effectively given (defined below) logical system that is capable of interpreting arithmetic, there exists a statement that is true (in the sense that it holds for the natural numbers) but not provable within that logical system (and which indeed may fail in some non standard models of arithmetic which may be consistent with the logical system). For example, in every logical system capable of expressing the Peano axioms, the Gödel sentence holds for the natural numbers but cannot be proved. Here a logical system is said to be effectively given if it is possible to decide, given any formula in the language of the system, whether the formula is an axiom, and one which can express the Peano axioms is called "sufficiently strong." When applied to first order logic, the first incompleteness theorem implies that any sufficiently strong, consistent, effective first order theory has models that are not elementarily equivalent, a stronger limitation than the one established by the Löwenheim–Skolem theorem. The second incompleteness theorem states that no sufficiently strong, consistent, effective axiom system for arithmetic can prove its own consistency, which has been interpreted to show that Hilbert's program cannot be reached.
Басқа классикалық логикалар
Бірінші реттік логикадан басқа көптеген логикалар зерттеледі. Олардың ішінде формулалардың шексіз көлемде ақпарат беруіне мүмкіндік беретін шексіз логикалар, сондай-ақ семантикасына тікелей жиын теориясының бір бөлігін енгізетін жоғары реттік логикалар бар. Ең көп зерттелген шексіз логика – бұл логикада кванторлар бірінші реттік логикадағыдай тек шекті тереңдікке ғана орналасады, бірақ формулалар шекті немесе санаулы шексіз конъюнкциялар мен дизъюнкцияларды қамтуы мүмкін. Мысалы, объектінің бүтін сан екенін формула арқылы көрсетуге болады.
Many logics besides first order logic are studied. These include infinitary logics, which allow for formulas to provide an infinite amount of information, and higher order logics, which include a portion of set theory directly in their semantics. The most well studied infinitary logic is In this logic, quantifiers may only be nested to finite depths, as in first order logic, but formulas may have finite or countably infinite conjunctions and disjunctions within them. Thus, for example, it is possible to say that an object is a whole number using a formula of such as
Жоғары реттік логикалар дискурс доменінің элементтері ғана емес, сонымен қатар оның ішкі жиындары, осындай ішкі жиындардың жиындары және басқа да жоғары типтегі объектілерді квантификациялауға мүмкіндік береді. Семантика осылай анықталады: әр жоғары реттік квантор үшін жеке домен болуының орнына, кванторлар тиісті типтегі барлық объектілер бойынша жүреді. Бірінші реттік логиканың дамуына дейін зерттелген логика, мысалы, Фреге логикасы, ұқсас жиын теориялық аспектілерге ие болды. Жоғары реттік логикалар көбірек экспрессивті болғанымен, табиғи сандар сияқты құрылымдарды толық аксиоматизациялауға мүмкіндік береді, бірақ олар бірінші реттік логиканың толықтық және ықшамдық теоремаларының аналогтарын қанағаттандырмайды, сондықтан дәлелдемелік теориялық талдауға жақын емес. Логиканың тағы бір түрі – индуктивті анықтамаларды қолданатын логика, мысалы, примитивті рекурсивті функциялар үшін жазылатындай. Бірінші реттік логиканың кеңейтілуін формалды түрде анықтауға болады – бұл ұғым осы бөлімдегі барлық логиканы қамтиды, өйткені олар белгілі бір негізгі қағидалар бойынша бірінші реттік логика сияқты жұмыс істейді, бірақ жалпы алғанда барлық логиканы қамтымайды, мысалы, интуиционистік, модальдық немесе бұлыңғыр логиканы қамтымайды. Линдстрем теоремасы тұтастық теоремасы мен төменгі Лёвенхейм-Сколем теоремасын қанағаттандыратын бірінші реттік логиканың жалғыз кеңейтімі – өзі бірінші реттік логика екенін көрсетеді.
Higher order logics allow for quantification not only of elements of the domain of discourse, but subsets of the domain of discourse, sets of such subsets, and other objects of higher type. The semantics are defined so that, rather than having a separate domain for each higher type quantifier to range over, the quantifiers instead range over all objects of the appropriate type. The logics studied before the development of first order logic, for example Frege's logic, had similar set theoretic aspects. Although higher order logics are more expressive, allowing complete axiomatizations of structures such as the natural numbers, they do not satisfy analogues of the completeness and compactness theorems from first order logic, and are thus less amenable to proof theoretic analysis. Another type of logics are s that allow inductive definitions, like one writes for primitive recursive functions. One can formally define an extension of first order logic — a notion which encompasses all logics in this section because they behave like first order logic in certain fundamental ways, but does not encompass all logics in general, e. g. it does not encompass intuitionistic, modal or fuzzy logic. Lindström's theorem implies that the only extension of first order logic satisfying both the compactness theorem and the downward Löwenheim–Skolem theorem is first order logic.
Классикалық емес және модальдық логика
Модальдық логикаларға қосымша модальдық операторлар кіреді, мысалы, белгілі бір формуланың тек шын емес, сонымен қатар қажетті түрде шын екенін көрсететін оператор. Модальдық логика математиканы аксиомалау үшін жиі қолданылмаса да, ол бірінші реттік дәлелдемелердің қасиеттерін зерттеу және жиындық теориялық мәжбүрлеуді зерттеу үшін пайдаланылған. Интуиционистік логика Гейтинг тарапынан Браувердің интуиционизм бағдарламасын зерттеу үшін жасалған, онда Браувердің өзі формалдаудан қашып жүрді. Интуиционистік логикаға ерекше, әрбір мәлімдеме шын немесе оның жоқтығы шын деп күндіздік білдіретін, шеттестірілген заң кірмейді. Клиннің интуиционистік логиканың дәлелдеу теориясымен жұмысы интуиционистік дәлелдемелерден құрылымдық ақпаратты алуға болатынын көрсетті. Мысалы, интуиционистік арифметикада дәлелмен толық функция есептелуге болады; бұл Пеано арифметикасы сияқты классикалық арифметика теорияларында дұрыс емес.
Modal logics include additional modal operators, such as an operator which states that a particular formula is not only true, but necessarily true. Although modal logic is not often used to axiomatize mathematics, it has been used to study the properties of first order provability and set theoretic forcing. Intuitionistic logic was developed by Heyting to study Brouwer's program of intuitionism, in which Brouwer himself avoided formalization. Intuitionistic logic specifically does not include the law of the excluded middle, which states that each sentence is either true or its negation is true. Kleene's work with the proof theory of intuitionistic logic showed that constructive information can be recovered from intuitionistic proofs. For example, any provably total function in intuitionistic arithmetic is computable; this is not true in classical theories of arithmetic such as Peano arithmetic.
Алгебралық логика
Алгебралық логика формальды логиканың семантикасын зерттеу үшін абстрактілік алгебраның әдістерін пайдаланады. Классикалық пропозициялық логикадағы шындық мәндерін бейнелеу үшін Буль алгебрасын қолдану және интуиционистік пропозициялық логикадағы шындық мәндерін бейнелеу үшін Хейтинг алгебрасын қолдану – бұл негізгі мысал. Бірінші реттік логика және жоғары реттік логика сияқты күшті логикалар цилиндрлік алгебралар сияқты күрделі алгебралық құрылымдарды қолдана отырып зерттеледі.
Algebraic logic uses the methods of abstract algebra to study the semantics of formal logics. A fundamental example is the use of Boolean algebras to represent truth values in classical propositional logic, and the use of Heyting algebras to represent truth values in intuitionistic propositional logic. Stronger logics, such as first order logic and higher order logic, are studied using more complicated algebraic structures such as cylindric algebras.
Жинақ теориясы
Жинақтар теориясы — объектілердің абстрактілік жиынтықтарын зерттейтін ғылым. Ординалдық және кардиналдық сандар сияқты көптеген негізгі ұғымдар Кантордың жинақтар теориясының формалды аксиоматизациялары жасалмас бұрын бейресми түрде дамытылған. Зермело ұсынған алғашқы аксиоматизация сәл кеңейтіліп, қазір математиканың ең көп қолданылатын негізгі теориясы болып табылатын Зермело-Франкель жинақтар теориясы (ZF) аталды. Жинақтар теориясының басқа формализациялары да ұсынылды, оның ішінде фон Нейманн-Бернейс-Гёдель жинақтар теориясы (NBG), Морзе-Келли жинақтар теориясы (MK) және Жаңа негіздер (NF). Олардың ішінде ZF, NBG және MK жинақтардың жиынтық иерархиясын сипаттауда ұқсас. Жаңа негіздер басқаша көзқарас ұсынады; ол барлық жинақтар жиынтығы сияқты объектілерге, жинақтардың болу аксиомаларына шектеулер қойып рұқсат береді. Крипке-Платек жинақтар теориясы жүйесі жалпыланған рекурсия теориясымен тығыз байланысты. Жинақтар теориясындағы екі белгілі мәлімдеме — таңдау аксиомасы және континуум гипотезасы. Таңдау аксиомасы, алғаш рет Зермело айтқан, Френкельдің ZF-тан тәуелсіз екенін дәлелдегенімен, математиктер арасында кеңінен қабылданды. Ол бос емес жинақтар жиынтығы берілген жағдайда, жинақтағы әрбір жинақтан бір ғана элементті қамтитын жалғыз C жинағы бар екенін күйейді. C жинағы жинақтағы әрбір жинақтан бір элементті «таңдайды» делінеді. Кейбір адамдар мұндай таңдау жасау мүмкіндігін анық деп санайды, өйткені жинақтағы әрбір жинақ бос емес, бірақ таңдау жасалуын қамтамасыз ететін жалпы, нақты ереже болмауы аксиоманы конструкциялық емес етеді. Стефан Банах және Альфред Тарски таңдау аксиомасын қатты шардың шекті сандағы бөліктерге бөлу үшін пайдалануға болатынын көрсетті, содан кейін оларды масштабтамай, бастапқы көлемдегі екі қатты шар жасау үшін қайта жинауға болады. Банах-Тарски парадоксы деп аталатын бұл теорема таңдау аксиомасының көптеген интуитивті емес нәтижелерінің бірі болып табылады. Кантор алғаш ұсынған континуум гипотезасы 1900 жылы Дэвид Гилберт өзінің 23 проблемасының бірі ретінде тізімге енгізді. Гёдель континуум гипотезасын Зермело-Франкель жинақтар теориясының аксиомаларынан (таңдау аксиомасымен немесе одан басқа) бұра алмайтынын, конструктирленген әлемді дамыту арқылы көрсетті, онда континуум гипотезасы орындалуы керек. 1963 жылы Пол Коэн континуум гипотезасын Зермело-Франкель жинақтар теориясының аксиомаларынан бұра алмайтынын көрсетті. Бұл тәуелсіздік нәтижесі Гилберттің сұрағын толық шешпеді, өйткені жинақтар теориясының жаңа аксиомалары гипотезаны шеше алады. Осы бағыттағы соңғы жұмыстарды У. Хью Вуддин жүргізді, бірақ оның маңыздылығы әлі анық емес. Жинақтар теориясындағы қазіргі зерттеулерге үлкен кардиналдар мен детерминизмді зерттеу кіреді. Үлкен кардиналдар — ZFC-де мұндай кардиналдардың бар екенін дәлелдеу мүмкін емес, ерекше қасиеттері бар кардиналдар. Әдетте зерттелетін ең кішкентай үлкен кардиналдың, қолжетімді емес кардиналдың болуы ZFC-нің тұрақтылығын білдіреді. Үлкен кардиналдардың өте жоғары кардиналдығына қарамастан, олардың болуы нақты сызықтың құрылымына көптеген салдарлары бар. Детерминизм екі ойыншы ойнайтын ойындарда (ойындар анықталған деп айтылады) жеңіске жету стратегиясының болуы мүмкіндігін білдіреді. Мұндай стратегиялардың болуы нақты сызықтың және басқа поляк кеңістіктерінің құрылымдық қасиеттерін білдіреді.
Set theory is the study of sets, which are abstract collections of objects. Many of the basic notions, such as ordinal and cardinal numbers, were developed informally by Cantor before formal axiomatizations of set theory were developed. The first such axiomatization, due to Zermelo, was extended slightly to become Zermelo–Fraenkel set theory (ZF), which is now the most widely used foundational theory for mathematics. Other formalizations of set theory have been proposed, including von Neumann–Bernays–Gödel set theory (NBG), Morse–Kelley set theory (MK), and New Foundations (NF). Of these, ZF, NBG, and MK are similar in describing a cumulative hierarchy of sets. New Foundations takes a different approach; it allows objects such as the set of all sets at the cost of restrictions on its set existence axioms. The system of Kripke–Platek set theory is closely related to generalized recursion theory. Two famous statements in set theory are the axiom of choice and the continuum hypothesis. The axiom of choice, first stated by Zermelo, was proved independent of ZF by Fraenkel, but has come to be widely accepted by mathematicians. It states that given a collection of nonempty sets there is a single set C that contains exactly one element from each set in the collection. The set C is said to "choose" one element from each set in the collection. While the ability to make such a choice is considered obvious by some, since each set in the collection is nonempty, the lack of a general, concrete rule by which the choice can be made renders the axiom nonconstructive. Stefan Banach and Alfred Tarski showed that the axiom of choice can be used to decompose a solid ball into a finite number of pieces which can then be rearranged, with no scaling, to make two solid balls of the original size. This theorem, known as the Banach–Tarski paradox, is one of many counterintuitive results of the axiom of choice. The continuum hypothesis, first proposed as a conjecture by Cantor, was listed by David Hilbert as one of his 23 problems in 1900. Gödel showed that the continuum hypothesis cannot be disproven from the axioms of Zermelo–Fraenkel set theory (with or without the axiom of choice), by developing the constructible universe of set theory in which the continuum hypothesis must hold. In 1963, Paul Cohen showed that the continuum hypothesis cannot be proven from the axioms of Zermelo–Fraenkel set theory. This independence result did not completely settle Hilbert's question, however, as it is possible that new axioms for set theory could resolve the hypothesis. Recent work along these lines has been conducted by W. Hugh Woodin, although its importance is not yet clear. Contemporary research in set theory includes the study of large cardinals and determinacy. Large cardinals are cardinal numbers with particular properties so strong that the existence of such cardinals cannot be proved in ZFC. The existence of the smallest large cardinal typically studied, an inaccessible cardinal, already implies the consistency of ZFC. Despite the fact that large cardinals have extremely high cardinality, their existence has many ramifications for the structure of the real line. Determinacy refers to the possible existence of winning strategies for certain two player games (the games are said to be determined). The existence of these strategies implies structural properties of the real line and other Polish spaces.
Үлгі теориясы
Модель теориясы әр түрлі формальды теориялардың модельдерін зерттейді. Мұнда теория – белгілі бір формальды логика мен қолтаңбадағы формулалар жиынтығы, ал модель – теорияның нақты түсіндірмесін беретін құрылым. Модель теориясы әмбебап алгебра және алгебралық геометриямен тығыз байланысты, бірақ модель теориясының әдістері осы салаларға қарағанда логикалық мәселелерге көбірек назар аударады. Белгілі бір теорияның барлық модельдерінің жиынтығы элементарлық сынып деп аталады; классикалық модель теориясы белгілі бір элементарлық сыныптағы модельдердің қасиеттерін анықтауға немесе құрылымдардың белгілі бір сыныптары элементарлық сыныптар құрайтынын анықтауға тырысады. Квантификаторды жою әдісі белгілі бір теорияларда анықталатын жиынтықтардың тым күрделі бола алмайтынын көрсету үшін қолданылуы мүмкін. Тарски нақты жабық өрістер үшін квантификаторды жоюды орнатты, бұл нәтиже нақты сандар өрісінің теориясы шешілетін екенін көрсетеді. Ол сондай-ақ өзінің әдістері кез келген сипаттағы алгебралық жабық өрістерге де бірдей қолданылатындығын атап өтті. Осыдан дамып келе жатқан қазіргі заманғы саланың бірі – минималды құрылымдар. Майкл Д. Морли дәлелдеген Морлидің категорикалық теоремасы, егер саналатын тілдегі бірінші реттік теория санаусыз бір кардинальдық мәнде категорикалық болса, яғни осы кардинальдық мәннің барлық модельдері изоморфты болса, онда ол санаусыз барлық кардинальдық мәндерде категорикалық болады деп мәлімдейді. Континуум гипотезасының қарапайым салдары – континуумнан кем санда көп изоморфты емес саналатын модельдері бар толық теорияда саналатын ғана модельдер болуы мүмкін. Роберт Лоусон Воуттың есімімен аталған Воуттың болжамы, бұл континуум гипотезасына тәуелсіз де дұрыс екенін айтады. Бұл болжамның көптеген ерекше жағдайлары расталған.
Model theory studies the models of various formal theories. Here a theory is a set of formulas in a particular formal logic and signature, while a model is a structure that gives a concrete interpretation of the theory. Model theory is closely related to universal algebra and algebraic geometry, although the methods of model theory focus more on logical considerations than those fields. The set of all models of a particular theory is called an elementary class; classical model theory seeks to determine the properties of models in a particular elementary class, or determine whether certain classes of structures form elementary classes. The method of quantifier elimination can be used to show that definable sets in particular theories cannot be too complicated. Tarski established quantifier elimination for real closed fields, a result which also shows the theory of the field of real numbers is decidable. He also noted that his methods were equally applicable to algebraically closed fields of arbitrary characteristic. A modern subfield developing from this is concerned with o minimal structures. Morley's categoricity theorem, proved by Michael D. Morley, states that if a first order theory in a countable language is categorical in some uncountable cardinality, i. e. all models of this cardinality are isomorphic, then it is categorical in all uncountable cardinalities. A trivial consequence of the continuum hypothesis is that a complete theory with less than continuum many nonisomorphic countable models can have only countably many. Vaught's conjecture, named after Robert Lawson Vaught, says that this is true even independently of the continuum hypothesis. Many special cases of this conjecture have been established.
Рекурсиялық теория
Рекурсиялық теория, сондай-ақ есептеу теориясы деп аталады, есептелуге болатын функциялардың қасиеттерін және Тьюринг дәрежесін зерттейді, ол есептелмейтін функцияларды бірдей есептелмейтін деңгейге ие жиынтықтарға бөледі. Рекурсиялық теорияға жалпыланған есептеу және анықтамалық қабілетті зерттеу де кіреді. Рекурсия теориясы 1930 жылдары Роза Петер, Алонзо Черч және Алан Тьюрингтің жұмыстарынан өркендеді, ал 1940 жылдары Клейн мен Пост оны одан әрі кеңейтті. Классикалық рекурсиялық теория натурал сандардан натурал сандарға функциялардың есептелуіне назар аударады. Негізгі нәтижелер Тьюринг машиналарын, λ-есептеуін және басқа жүйелерді пайдалана отырып, көптеген тәуелсіз, эквивалентті сипаттамалары бар есептелетін функциялардың берік, канондық класын құрады. Алға қойылған нәтижелер Тьюринг дәрежесінің құрылымы мен рекурсивті түрде саналатын жиынтықтардың торларына қатысты. Жалпыланған рекурсиялық теория рекурсия теориясының идеяларын енді міндетті түрде шекті емес есептеулерге дейін кеңейтеді. Ол жоғары типтегі есептеуді, сондай-ақ гиперарифметикалық теория және α-рекурсия теориясы сияқты салаларды қамтиды. Рекурсия теориясындағы қазіргі заманғы зерттеулер алгоритмдік кездейсоқтық, есептелетін модельдер теориясы және кері математика сияқты қолданыстарды, сондай-ақ таза рекурсия теориясындағы жаңа нәтижелерді зерттеуді қамтиды.
Recursion theory, also called computability theory, studies the properties of computable functions and the Turing degrees, which divide the uncomputable functions into sets that have the same level of uncomputability. Recursion theory also includes the study of generalized computability and definability. Recursion theory grew from the work of Rózsa Péter, Alonzo Church and Alan Turing in the 1930s, which was greatly extended by Kleene and Post in the 1940s. Classical recursion theory focuses on the computability of functions from the natural numbers to the natural numbers. The fundamental results establish a robust, canonical class of computable functions with numerous independent, equivalent characterizations using Turing machines, λ calculus, and other systems. More advanced results concern the structure of the Turing degrees and the lattice of recursively enumerable sets. Generalized recursion theory extends the ideas of recursion theory to computations that are no longer necessarily finite. It includes the study of computability in higher types as well as areas such as hyperarithmetical theory and α recursion theory. Contemporary research in recursion theory includes the study of applications such as algorithmic randomness, computable model theory, and reverse mathematics, as well as new results in pure recursion theory.
Алгоритмдік тұрғыдан шешілмейтін мәселелер
Рекурсиялық теорияның маңызды саласы алгоритмдік шешілмейтіндікті зерттейді; шешімдік есеп немесе функциялық есеп алгоритмдік тұрғыдан шешілмейтін болады, егер есептің барлық заңды кірістері үшін дұрыс жауап беретін есептеуге болатын алгоритм болмаса. Шешілмейтіндік туралы алғашқы нәтижелерді 1936 жылы Черч және Тьюринг дербес алды, олар Entscheidungsproblem алгоритмдік тұрғыдан шешілмейтінін көрсетті. Тьюринг бұл мәселені тоқтау есебінің шешілмейтіндігін дәлелдеу арқылы рекурсиялық теория және компьютерлік ғылым салаларында кең ауқымды салдарлары бар нәтижені орнатып берді. Күнделікті математикадан шешілмейтін есептердің көптеген мысалдары белгілі. Топтар үшін сөз есебін Пётр Новиков 1955 жылы және дербес В. Буун 1959 жылы алгоритмдік тұрғыдан шешуге болмайтынын дәлелдеді. Тибор Радо 1962 жылы ұсынған "шаруалы бобр" есебі тағы бір мәшһүр мысал. Хилберттің оныншы мәселесі бүтін коэффициенттері бар көпөлшемді полиномдық теңдеудің бүтін сандарда шешімі бар-жоғын анықтауға арналған алгоритмді сұрады. Джулия Робинсон, Мартин Дэвис және Хилари Путнам осы мәселені шешуде жарым-жартылай жетістіктерге қол жеткізді. Есептің алгоритмдік шешілмейтіндігін 1970 жылы Юрий Матиясевич дәлелдеді.
An important subfield of recursion theory studies algorithmic unsolvability; a decision problem or function problem is algorithmically unsolvable if there is no possible computable algorithm that returns the correct answer for all legal inputs to the problem. The first results about unsolvability, obtained independently by Church and Turing in 1936, showed that the Entscheidungsproblem is algorithmically unsolvable. Turing proved this by establishing the unsolvability of the halting problem, a result with far ranging implications in both recursion theory and computer science. There are many known examples of undecidable problems from ordinary mathematics. The word problem for groups was proved algorithmically unsolvable by Pyotr Novikov in 1955 and independently by W. Boone in 1959. The busy beaver problem, developed by Tibor Radó in 1962, is another well known example. Hilbert's tenth problem asked for an algorithm to determine whether a multivariate polynomial equation with integer coefficients has a solution in the integers. Partial progress was made by Julia Robinson, Martin Davis and Hilary Putnam. The algorithmic unsolvability of the problem was proved by Yuri Matiyasevich in 1970.
Дәлел теориясы және конструктивті математика
Дәлел теориясы – әр түрлі логикалық дедукция жүйелеріндегі формальды дәлелдемелерді зерттеу саласы. Бұл дәлелдер формальды математикалық объектілер ретінде ұсынылады, осылайша математикалық әдістермен талдау мүмкіндігі жеңілдеді. Гилберт стиліндегі дедукция жүйелері, табиғи дедукция жүйелері және Гентцен жасаған тізбекті есептеулер сияқты бірнеше дедукция жүйелері кеңінен қарастырылады. Математикалық логика контекстінде конструктивті математиканы зерттеу, интуиционистік логика сияқты классикалық емес логикадағы жүйелерді, сондай-ақ предикативтік жүйелерді зерттеуді қамтиды. Предикативизмнің ерте жақтаушысы Герман Вейль болды, ол тек предикативтік әдістерді қолдана отырып, нақты анализдің үлкен бөлігін дамытуға болатынын көрсетті. Дәлелдер толыққанды шекті болса, ал құрылымдағы шындық солай болмаса, конструктивті математикадағы зерттеулерде дәлелдемеге баса назар аудару жиі кездеседі. Классикалық (немесе конструктивті емес) жүйелердегі дәлелдемелік пен интуиционистік (немесе конструктивті) жүйелердегі дәлелдемелік арасындағы байланысқа ерекше қызығушылық танылады. Гёдель-Гентценнің кері аудармасы сияқты нәтижелер классикалық логиканы интуиционистік логикаға енгізуге (немесе аударуға) болатынын көрсетеді, бұл интуиционистік дәлелдерге қатысты кейбір қасиеттерді классикалық дәлелдерге қайтаруға мүмкіндік береді. Дәлел теориясының соңғы жетістіктеріне Ульрих Коленбахтың дәлел табу саласындағы зерттеулері және Майкл Ратхеннің дәлелдік теориялық ординалдарды зерттеуі жатады.
Proof theory is the study of formal proofs in various logical deduction systems. These proofs are represented as formal mathematical objects, facilitating their analysis by mathematical techniques. Several deduction systems are commonly considered, including Hilbert style deduction systems, systems of natural deduction, and the sequent calculus developed by Gentzen. The study of constructive mathematics, in the context of mathematical logic, includes the study of systems in non classical logic such as intuitionistic logic, as well as the study of predicative systems. An early proponent of predicativism was Hermann Weyl, who showed it is possible to develop a large part of real analysis using only predicative methods. Because proofs are entirely finitary, whereas truth in a structure is not, it is common for work in constructive mathematics to emphasize provability. The relationship between provability in classical (or nonconstructive) systems and provability in intuitionistic (or constructive, respectively) systems is of particular interest. Results such as the Gödel–Gentzen negative translation show that it is possible to embed (or translate) classical logic into intuitionistic logic, allowing some properties about intuitionistic proofs to be transferred back to classical proofs. Recent developments in proof theory include the study of proof mining by Ulrich Kohlenbach and the study of proof theoretic ordinals by Michael Rathjen.
Қолданбалар
Математикалық логика тек математика мен оның негіздеріне ғана емес (Г. Фреге, Б. Рассел, Д. Хилберт, П. Бернейс, Х. Шолц, Р. Карнап, С. Лесневский, Т. Сколем), сонымен қатар физикаға (Р. Карнап, А. Диттрих, Б. Рассел, С. Э. Шэннон, А. Н. Уайтхед, Х. Рейхенбах, П. Февриер), биологияға (Ж. Х. Вудгер, А. Тарски), психологияға (Ф. Б. Фитч, С. Г. Хемпел), заң мен моральға (К. Менгер, У. Клуг, П. Оппенхайм), экономикаға (Ж. Нейман, О. Моргенстерн), практикалық мәселелерге (Е. С. Беркли, Е. Стамм), тіпті метафизикаға (Ж. [Ян] Саламуха, Х. Шолц, Ж. М. Боченский) сәтті қолданылған. Оның логика тарихына қолданылуы өте жемісті болып шықты (J. Lukasiewicz, H. Scholz, B. Mates, A. Becker, E. Moody, J. Salamucha, K. Duerr, Z. Jordan, P. Boehner, J. M. Bochenski, S. [Станислав] T. Schayer, D. Ингалл). Теология саласында да қолданылған жағдайлар бар (Ф. Дрюновский, Дж. Саламуха, I. Томас).
"Mathematical logic has been successfully applied not only to mathematics and its foundations (G. Frege, B. Russell, D. Hilbert, P. Bernays, H. Scholz, R. Carnap, S. Lesniewski, T. Skolem), but also to physics (R. Carnap, A. Dittrich, B. Russell, C. E. Shannon, A. N. Whitehead, H. Reichenbach, P. Fevrier), to biology (J. H. Woodger, A. Tarski), to psychology (F. B. Fitch, C. G. Hempel), to law and morals (K. Menger, U. Klug, P. Oppenheim), to economics (J. Neumann, O. Morgenstern), to practical questions (E. C. Berkeley, E. Stamm), and even to metaphysics (J. [Jan] Salamucha, H. Scholz, J. M. Bochenski). Its applications to the history of logic have proven extremely fruitful (J. Lukasiewicz, H. Scholz, B. Mates, A. Becker, E. Moody, J. Salamucha, K. Duerr, Z. Jordan, P. Boehner, J. M. Bochenski, S. [Stanislaw] T. Schayer, D. Ingalls)." "Applications have also been made to theology (F. Drewnowski, J. Salamucha, I. Thomas)."
Компьютерлік ғылыммен байланысы
Компьютерлік ғылымдағы есептеу теориясын зерттеу математикалық логикадағы есептеуді зерттеумен тығыз байланысты. Дегенмен, араларында айырмашылық бар. Компьютерлік ғалымдар көбінесе нақты бағдарламалау тілдеріне және іс жүзіндегі есептеу мүмкіндіктеріне назар аударады, ал математикалық логика зерттеушілері есептеуді теориялық ұғым ретінде және есептелмейтін нәрселерді зерттейді. Бағдарламалау тілдерінің семантикасы теориясы модель теориясымен байланысты, сондай-ақ бағдарламаны тексеру (әсіресе, модельді тексеру) де осыған қатысты. Дәлелдемелер мен бағдарламалар арасындағы Кури-Ховард сәйкестігі дәлелдеме теориясына, әсіресе интуиционистік логикаға қатысты. Ламбда-есептеу және комбинаторлық логика сияқты формальды есептеулер қазір идеалдандырылған бағдарламалау тілдері ретінде зерттеледі. Компьютерлік ғылым математикаға дәлелдемелерді автоматты түрде тексеру немесе тіпті табу үшін, мысалы, автоматты теорема дәлелдеу және логикалық бағдарламалау сияқты әдістерді әзірлеу арқылы да үлес қосады. Сипаттамалық күрделілік теориясы логиканы есептеу күрделігімен байланыстырады. Бұл саладағы алғашқы маңызды нәтиже – Фагин теоремасы (1974), ол NP-нің экзистенциалды екінші реттік логиканың өрнектерімен сипатталатын тілдер жиыны екенін көрсетті.
The study of computability theory in computer science is closely related to the study of computability in mathematical logic. There is a difference of emphasis, however. Computer scientists often focus on concrete programming languages and feasible computability, while researchers in mathematical logic often focus on computability as a theoretical concept and on noncomputability. The theory of semantics of programming languages is related to model theory, as is program verification (in particular, model checking). The Curry–Howard correspondence between proofs and programs relates to proof theory, especially intuitionistic logic. Formal calculi such as the lambda calculus and combinatory logic are now studied as idealized programming languages. Computer science also contributes to mathematics by developing techniques for the automatic checking or even finding of proofs, such as automated theorem proving and logic programming. Descriptive complexity theory relates logics to computational complexity. The first significant result in this area, Fagin's theorem (1974) established that NP is precisely the set of languages expressible by sentences of existential second order logic.
Математика негіздері
XIX ғасырда математиктер өздерінің салаларындағы логикалық олқылықтар мен сәйкессіздіктерді байқады. Евклидтің ғасырлар бойы аксиоматикалық әдістің үлгісі ретінде оқытылып келген геометрияға арналған аксиомаларының толық еместігі көрсетілді. Инфинитезимальдарды қолдану және функцияның өзіндік анықтамасы талдау кезінде сұраққа түсті, өйткені Вейерштрастың еш жерде дифференциалданбайтын үздіксіз функциясы сияқты патологиялық мысалдар табылды. Кантордың кездейсоқ шексіз жиынтықтарын зерттеуі де сынға ұшырады. Леопольд Кронекер "Құдай бүтін сандарды жаратты, қалғандарының бәрі адамның жұмысы" деп математикадағы шекті, нақты объектілерді зерттеуге оралуды қолдады. Кронэкердің дәлелін 20-ғасырда конструктивистер алға тартса да, математикалық қауым оларды тұтастай алғанда қабылдамады. Дэвид Гильберт шексізді зерттеуді жақтап: "Бізді Кантор жасаған жұмақтан ешкім шығара алмайды" деп айтқан. Математиктер математиканың үлкен бөліктерін ресмилендіру үшін қолданылатын аксиомалық жүйелерді іздеуді бастады. Бұрын функциялар сияқты нағыз терминдердің түсініксіздігін жоюмен қатар, бұл аксиоматизация тұтастықты дәлелдеуге мүмкіндік береді деп үміттенді. 19 ғасырда аксиомалар жиынтығының сәйкестігін дәлелдеудің негізгі әдісі оған модель беру болды. Мысалы, Евклидтік емес геометрияны тұрақты сферадағы нүкте мен сферадағы үлкен шеңберді білдіретін сызықты анықтау арқылы дәйекті деп дәлелдеуге болады. Нәтижесінде пайда болған құрылым, эллиптік геометрияның моделі, параллельдік постулаттан басқа жазықтық геометрияның аксиомаларын қанағаттандырады. Формалды логиканың дамуымен Гилберт аксиомалар жүйесінің жүйедегі ықтимал дәлелдемелердің құрылымын талдау арқылы сәйкес келетінін дәлелдеу мүмкін бола ма деп сұрады және осы талдау арқылы қарама-қайшылықты дәлелдеу мүмкін еместігін көрсетті. Бұл идея дәлел теориясын зерттеуге әкелді. Сонымен қатар, Гильберт талдаудың толығымен нақты болуы керектігін ұсынды, ол шекті терминді әдістерге сілтеме жасау үшін қолданады, бірақ оларды дәл анықтамайды. Гильберт бағдарламасы деп аталатын бұл жобаға Гёдельдің толық емес теоремалары қатты әсер етті, олар формалды арифметика теорияларының сәйкестігін осы теорияларда формалданатын әдістерді қолдану арқылы орнатуға болмайтынын көрсетеді. Гентцен трансфинитті индукцияның аксиомаларымен толықтырылған шекті жүйеде арифметиканың тұрақтылығын дәлелдеу мүмкін екенін көрсетті, ал ол үшін әзірлеген әдістер дәлелдеу теориясында маңызды болды. Математика негіздерінің тарихындағы екінші желі классикалық емес логика мен конструктивті математиканы қамтиды. Конструктивті математиканы зерттеу құрама сөздің әртүрлі анықтамасы бар көптеген түрлі бағдарламаларды қамтиды. Ең қолайлы жағдайда ZF жиындар теориясындағы таңдау аксиомасын қолданбайтын дәлелдемелерді көптеген математиктер конструктивті деп атайды. Конструктивизмнің шектеулі нұсқалары табиғи сандарға, сандық теориялық функцияларға және табиғи сандар жиынтықтарына (нақты сандарды бейнелеу үшін, математикалық талдауды зерттеуді жеңілдету үшін пайдаланылуы мүмкін) шектеледі. Жалпы идеясы - функцияның өзін бар деп айтуға дейін функцияның мәндерін есептеудің нақты құралы белгілі болуы керек. XX ғасырдың басында Люциен Эгберт Ян Браувер математика философиясының бір бөлігі ретінде интуиционизмді құрды. Бұл философия, бастапқыда нашар түсінілген, математикалық мәлімдеме математик үшін шындық болуы үшін, ол адам мәлімдемені интуициямен түсіну керек, оның шындыққа сену ғана емес, оның шындық себебін түсіну керек. Шындықтың осы анықтамасынан кейін ортаның алынып тасталуы туралы заң қабылданбады, өйткені Браувердің пікірінше, олардың жалғандығы шындық деп танылмайтын мәлімдемелер бар. Брауердің философиясы ықпалды болды және көрнекті математиктер арасында қызу дау-дамайлардың себебі болды. Кейін Клейн мен Крейзель интуиционисттік логиканың формалды нұсқаларын зерттеді (Браувер формалдылықты қабылдамады және өз жұмысын формалды емес табиғи тілде ұсынды). BHK интерпретациясы мен Крипке модельдерінің пайда болуымен интуиционизмді классикалық математикамен татуластыру оңайырақ болды.
In the 19th century, mathematicians became aware of logical gaps and inconsistencies in their field. It was shown that Euclid's axioms for geometry, which had been taught for centuries as an example of the axiomatic method, were incomplete. The use of infinitesimals, and the very definition of function, came into question in analysis, as pathological examples such as Weierstrass' nowhere differentiable continuous function were discovered. Cantor's study of arbitrary infinite sets also drew criticism. Leopold Kronecker famously stated "God made the integers; all else is the work of man," endorsing a return to the study of finite, concrete objects in mathematics. Although Kronecker's argument was carried forward by constructivists in the 20th century, the mathematical community as a whole rejected them. David Hilbert argued in favor of the study of the infinite, saying "No one shall expel us from the Paradise that Cantor has created." Mathematicians began to search for axiom systems that could be used to formalize large parts of mathematics. In addition to removing ambiguity from previously naive terms such as function, it was hoped that this axiomatization would allow for consistency proofs. In the 19th century, the main method of proving the consistency of a set of axioms was to provide a model for it. Thus, for example, non Euclidean geometry can be proved consistent by defining point to mean a point on a fixed sphere and line to mean a great circle on the sphere. The resulting structure, a model of elliptic geometry, satisfies the axioms of plane geometry except the parallel postulate. With the development of formal logic, Hilbert asked whether it would be possible to prove that an axiom system is consistent by analyzing the structure of possible proofs in the system, and showing through this analysis that it is impossible to prove a contradiction. This idea led to the study of proof theory. Moreover, Hilbert proposed that the analysis should be entirely concrete, using the term finitary to refer to the methods he would allow but not precisely defining them. This project, known as Hilbert's program, was seriously affected by Gödel's incompleteness theorems, which show that the consistency of formal theories of arithmetic cannot be established using methods formalizable in those theories. Gentzen showed that it is possible to produce a proof of the consistency of arithmetic in a finitary system augmented with axioms of transfinite induction, and the techniques he developed to do so were seminal in proof theory. A second thread in the history of foundations of mathematics involves nonclassical logics and constructive mathematics. The study of constructive mathematics includes many different programs with various definitions of constructive. At the most accommodating end, proofs in ZF set theory that do not use the axiom of choice are called constructive by many mathematicians. More limited versions of constructivism limit themselves to natural numbers, number theoretic functions, and sets of natural numbers (which can be used to represent real numbers, facilitating the study of mathematical analysis). A common idea is that a concrete means of computing the values of the function must be known before the function itself can be said to exist. In the early 20th century, Luitzen Egbertus Jan Brouwer founded intuitionism as a part of philosophy of mathematics This philosophy, poorly understood at first, stated that in order for a mathematical statement to be true to a mathematician, that person must be able to intuit the statement, to not only believe its truth but understand the reason for its truth. A consequence of this definition of truth was the rejection of the law of the excluded middle, for there are statements that, according to Brouwer, could not be claimed to be true while their negations also could not be claimed true. Brouwer's philosophy was influential, and the cause of bitter disputes among prominent mathematicians. Later, Kleene and Kreisel would study formalized versions of intuitionistic logic (Brouwer rejected formalization, and presented his work in unformalized natural language). With the advent of the BHK interpretation and Kripke models, intuitionism became easier to reconcile with classical mathematics.
Бакалавриат мәтіндері
Шон Хедман, Логикаға кіріспе: модельдер теориясы, дәлелдеу теориясы, есептеу мүмкіндігі және күрделілік, Оксфорд университетінің баспасы, 2004 жыл. Есептеу мүмкіндігі және күрделілік теорияларымен тығыз байланыста логиканы қарастырады.
Shawn Hedman, A first course in logic: an introduction to model theory, proof theory, computability, and complexity, Oxford University Press, 2004, Covers logics in close relation with computability theory and complexity theory
Жоғары оқу орындарының мәтіндері
Клин, Стивен Коул. (1952), Метаматематикаға кіріспе. Нью-Йорк: Ван Ностранд. (Иши баспасы: 2009 жылғы қайта басылымы). Клин, Стивен Коул. (1967), Математикалық логика. Джон Уайли. Довер баспасы, 2002 жылғы қайта басылымы.
Kleene, Stephen Cole. (1952), Introduction to Metamathematics. New York: Van Nostrand. (Ishi Press: 2009 reprint). Kleene, Stephen Cole. (1967), Mathematical Logic. John Wiley. Dover reprint, 2002. .