Математичка логика

Математичка логика је подобласт математике и логике. Састоји се од математичког проучавања логике и премена овог проучавања на друге области математике. Математичка логика има блиске везе са рачунарством и филозофском логиком. Међу основним темама које се провлаче кроз математичку логику су изражајна моћ формалних логика и дедуктивна моћ доказивачких система.

Од свог настанка, математичка логика је допринела и њен развој је био мотивисан проучавањем основа математике. Ово проучавање је почело крајем 19. века развојем аксиоматских оквира за геометрију, аритметику и анализу. Почетком 20. века ју је обликовао Давид Хилберт у свом програму за доказивање конзистентости основних теорија. Резултати Курта Гедела, Герхарда Генцена, и других су дали делимично решење програма и разјаснили битна питања код доказивања конзистентности. Рад у теорији скупова је показао да скоро цела математика може да се формализује терминима скупова, мада неке теореме не могу да се докажу у уобичајеним системима аксиома за теорију скупова. Савремени рад у области основа математике се често концентрише на одређивање који делови математике могу да се формализују у одређеном формалном систему, уместо да покушава да пронађе теорије из којих може да се развије цела математика.

Математичка логика се често дели у следеће подобласти: теорија скупова, теорија модела, теорија рекурзије, теорија доказа и конструктивна математика.

Историја

Математичка логика је почела да се одваја као засебно поље средином 19. века (Ferreirós (2001). pp. 443). До тада, логика је проучавана са реториком, кроз силогизме, и са филозофијом. Софистициране логичке теорије су развијане у многим културама; на западу су најпознатије Аристотелова теорија силогизама и Еуклидове аксиоме планарне геометрије. У 18. веку су начињени покушаји да се операције формалне логике третирају на симболички или алгебарски начин. Овиме су се бавили математичари попут Лајбница и Ламберта, али је њихов труд остао изолован и мало познат.

19. век

Средином 19. века Бул а затим и Де Морган су представили системaтску математичку обраду логике. Њихов рад, заснован на алгебарском раду математичара попут Џорџа Пикока енгл. George Peacock, је реформисао и проширио традиционалну аристотеловску доктрину логике и развио одговарајуће инструменте за проучавање основнихпојмова математике (Katz (1998). pp. 686).

Чарлс Пирс је ослањајући се на Булове резултате развио логички систем за релације и квантификаторе, који је објавио у неколико радова од 1870. до 1885.

Готлоб Фреге је представио независан развој логике са квантификаторима у свом раду Begriffsschrift, објављеном 1879. Међутим, Фрегеов рад је остао релативно непознат док га Расел касније није промовисао. Дводимензиона нотација коју је фреге развио никада није шире прихваћена, и не користи се у савременим текстовима.

Од 1890. до 1905, Ернст Шредер је објавио Vorlesungen über die Algebra der Logik у три тома. Ово дело је сумирало и проширило рад Була, Де Моргана и Пирса, и представљало је значајан извор за разумевање симболичке логике крајем 19. века.

Основне теорије

Развој формалне логике, заједно са забринутошћу да математика није изграђена на одговарајућим основама је довео до развоја аксиоматских система за фундаменталне области математике као што су аритметика, анализа и геометрија.

У логици, израз аритметика се односи на теорију природних бројева. Ђузепе Пеано (Peano, Giuseppe (1888), Arithmetices principia, nova methodo exposita) је објавио скуп аксиома за аритметику, користећи варијацију логичког система Була и Шредера, уз додатак квантификатора. Пеано тада није био свестан Фрегеовог рада. Отприлике у исто време, Рихард Дедекинд је показао да су природни бројеви јединствено карактеризовани својим индукционим својствима. Дедекинд (Dedekind, Richard (1888), Was sind und was sollen die Zahlen?) је предложио другачију карактеризацију, којој је недостајао формални логички карактер Пеанових аксиома. Међутим, Дедекинд је својим радом доказао теореме недоступне из Пеановог система, укључујући јединственост скупа природних бројева (до на изоморфизам) и рекурзивне дефиниције сабирања и множења из функције наследника и математичке индукције.

Средином 19. века, су постале видљиве мане у Еуклидовим аксиомама за геометрију. Осим независности постулата паралелности, који је успоставио Николај Лобачевски 1826. (Lobachevsky, Nikolai (1840), Geometrishe Untersuchungen zur Theorie der Parellellinien), математичари су открили да одређене теореме које је Еуклид узимао здраво за готово у ствари нису доказиве из његових аксиома. Међу њима је теорема да права садржи најмање две тачке, или да кругови истог полупречника чији су центри удаљени за тај полупречник морају да се пресецају. Хилберт (1899) је развио комплетан скуп аксиома за геометрију, базиран на претходном раду Паша (1882). Успех у аксиоматизацији геометрије је мотивисао Хилберта да се да у потрагу за комплетним аксиоматизацијама других области математике, као што су реална права и природни бројеви. Ово је постало једна од највећих области истраживања у првој половини 20. века.

У 19. веку је дошло до великих напредака у теорији реалне анализе, укључујући теорију конвергенције функција и Фуријеове редове. Математичари попут Карла Вајерштраса су почели да конструишу функције необичне за интуицију, попут нигде-диференцијабилне непрекидне функције. Претходна схватања функције као правила за рачунање или глатког графика, више нису била прихватљива. Вајерштрас је почео да се залаже за аритметизацију анализе, која је тежила да аксиоматизује анализу коришћењем својстава природних бројева. Болцано и Коши су између 1817. и 1823. развили модерну "ε-δ" дефиницију лимеса и непрекидних функција (Felscher, Walter , “Bolzano, Cauchy, Epsilon, Delta”, The American Mathematical Monthly. 107 (9): 844—862. 2000.  ). 1858, Дедекинд је предложио дефиницију реалних бројева у терминима Дедекиндових сечења рационалних бројева (Dedekind, Richard (1872), Stetigkeit und irrationale Zahlen), што је дефиниција која се још увек користи у савременим текстовима.

Георг Кантор је развио фундаменталне концепте бесконачне теорије скупова. Његови рани резултати су развили теорију кардиналности и доказали да реални и природни бројеви имају различиту кардиналност (Cantor 1874). Током наредних двадесет година, Кантор је развио теорију трансфинитних бројева у низу публикација. 1891, је објавио нови доказ непребројивости реалних бројева, који је увео Канторов дијагонални поступак, и користио овај метод да докаже Канторову теорему да ниједан скуп не може да буде исте кардиналности као и његов партитивни скуп. Кантор је веровао да за сваки скуп постоји добро уређење, али није могао ово да докаже, па је то оставио као отворено питање .

20. век

У почетним деценијама 20. века, главне области проучавања су биле теорија скупова и формална логика. Откриће парадокса у неформалној теорији скупова је учинило да се неки запитају да ли је и сама математика неконзистентна, и да се дају у потрагу за доказима конзистентности.

1900, Хилберт је дао свој чувени списак 23 проблема за наредни век. Прва два проблема су се тицала разрешења хипотезе континуума и доказивања конзистентности елементарне аритметике, редом; десети је био проналажење метода који би одредио да ли мултиваријантне полиномијалне једначине над целим бројевима имају решење. Даљи рад на решавању ових проблема је обликовао смер развоја математичке логике, као што је учинио и напор да се реши Хилбертов Entscheidungsproblem, постављен 1928. Овај проблем је тражио процедуру која би за дати формализовани математички исказ одлучила да ли је истинит или неистинит.

Литература

• Предраг Јаничић, Математичка логика у рачунарству, Математички факултет. . Београд. 2007. ISBN 978-86-7589-040-9.  .
• Зоран Огњановић, Ненад Крџавац, Увод у теоријско рачунарство, ФОН, Београд, 2004.
• Милан Божић, Преглед историје и филозофије математике, Завод за уџбенике и наставна средства. . Београд. 2002. стр. 230—269. ISBN 86-17-10124-5.  .
• Дирк Ј. Стројк, Кратак преглед историје математике, Завод за издавање уџбеника, Београд, 1969

Додипломски текстови

• Walicki, Michał (2011), Introduction to Mathematical Logic, Singapore: World Scientific Publishing, ISBN 978-981-4343-87-9 .

• Boolos, George; Burgess, John; Jeffrey, Richard (2002), Computability and Logic (4th изд.), Cambridge: Cambridge University Press, ISBN 978-0-521-00758-0 .
• Crossley, J.N.; Ash, C.J.; Brickhill, C.J.; Stillwell, J.C.; Williams, N.H. (1972), What is mathematical logic?, London-Oxford-New York: Oxford University Press, ISBN 978-0-19-888087-5, Zbl 0251.02001 .
• Enderton, Herbert (2001), A mathematical introduction to logic (2nd изд.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3 .
• Fisher, Alec (1982), Formal Number Theory and Computability: A Workbook (1st изд.), USA: Oxford University Press, ISBN 978-0-19-853188-3 . Suitable as a first course for independent study.
• Hamilton, A.G. (1988), Logic for Mathematicians (2nd изд.), Cambridge: Cambridge University Press, ISBN 978-0-521-36865-0 .
• Ebbinghaus, H.-D.; Flum, J.; Thomas, W. (1994), Mathematical Logic (2nd изд.), New York: Springer, ISBN 978-0-387-94258-2 .
• Katz, Robert (1964), Axiomatic Analysis, Boston, MA: D. C. Heath and Company .
• Mendelson, Elliott (1997), Introduction to Mathematical Logic (4th изд.), London: Chapman & Hall, ISBN 978-0-412-80830-2 .
• Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic (3rd изд.), New York: Springer Science+Business Media, ISBN 978-1-4419-1220-6, doi:10.1007/978-1-4419-1221-3 .
• Schwichtenberg, Helmut (2003—2004), Mathematical Logic (PDF), Munich, Germany: Mathematisches Institut der Universität München, Приступљено 2016-02-24 .
• Shawn Hedman,. A first course in logic: an introduction to model theory, proof theory, computability, and complexity. Oxford University Press. ISBN 0-19-852981-3. . (2004) . Covers logics in close relation with computability theory and complexity theory
• van Dalen, Dirk (2013), Logic and Structure, Universitext, Berlin: Springer-Verlag, ISBN 978-1-4471-4557-8, doi:10.1007/978-1-4471-4558-5 .

Дипломски текстови

• Andrews, Peter B. (2002), An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof (2nd изд.), Boston: Kluwer Academic Publishers, ISBN 978-1-4020-0763-7 .
• Barwise, Jon, ур. (1989). Handbook of Mathematical Logic. Studies in Logic and the Foundations of Mathematics. North Holland. ISBN 978-0-444-86388-1. .
• Hodges, Wilfrid (1997), A shorter model theory, Cambridge: Cambridge University Press, ISBN 978-0-521-58713-6 .
• Jech, Thomas (2003), Set Theory: Millennium Edition, Springer Monographs in Mathematics, Berlin, New York: Springer-Verlag, ISBN 978-3-540-44085-7 .
• Kleene, Stephen Cole.(1952), Introduction to Metamathematics. New York: Van Nostrand. (Ishi Press: 2009 reprint).
• Kleene, Stephen Cole (1967=). Mathematical Logic. Dover: John Wiley. ISBN 0-486-42533-9. OCLC 523472. 
• Shoenfield, Joseph R. (2001) [1967], Mathematical Logic (2nd изд.), A K Peters, ISBN 978-1-56881-135-2 .
• Troelstra, Anne Sjerp; Schwichtenberg, Helmut (2000), Basic Proof Theory, Cambridge Tracts in Theoretical Computer Science (2nd изд.), Cambridge: Cambridge University Press, ISBN 978-0-521-77911-1 .

Истраживачки чланци, монографије, текстови, и прегледи

• Augusto, Luis M. (2017). Logical consequences. Theory and applications: An introduction. London: College Publications. ISBN 978-1-84890-236-7. 
• Boehner, Philotheus, Medieval Logic, Manchester 1950.
• Cohen, P. J. (1966), Set Theory and the Continuum Hypothesis, Menlo Park, CA: W. A. Benjamin .
• Cohen, Paul Joseph (2008) [1966]. Set theory and the continuum hypothesis. Mineola, New York: Dover Publications. ISBN 978-0-486-46921-8. .
• J.D. Sneed, (1971). The Logical Structure of Mathematical Physics. . Reidel, Dordrecht, 1971 (revised edition 1979).
• Davis, Martin (1973), „Hilbert's tenth problem is unsolvable”, The American Mathematical Monthly, 80 (3): 233—269, JSTOR 2318447, doi:10.2307/2318447 , reprinted as an appendix in Martin Davis, Computability and Unsolvability, Dover reprint 1982.
• Felscher, Walter (2000), „Bolzano, Cauchy, Epsilon, Delta”, The American Mathematical Monthly, 107 (9): 844—862, JSTOR 2695743, doi:10.2307/2695743 .
• Ferreirós, José (2001), „The Road to Modern Logic-An Interpretation” (PDF), Bulletin of Symbolic Logic, 7 (4): 441—484, JSTOR 2687794, doi:10.2307/2687794, hdl:11441/38373, Архивирано из оригинала (PDF) 02. 02. 2023. г., Приступљено 26. 12. 2020 .
• Hamkins, Joel David; Löwe, Benedikt (2007), „The modal logic of forcing”, Transactions of the American Mathematical Society, 360 (4): 1793—1818, S2CID 14724471, arXiv:math/0509616 , doi:10.1090/s0002-9947-07-04297-3 
• Katz, Victor J. (1998), A History of Mathematics, Addison–Wesley, ISBN 978-0-321-01618-8 .
• Morley, Michael (1965), „Categoricity in Power”, Transactions of the American Mathematical Society, 114 (2): 514—538, JSTOR 1994188, doi:10.2307/1994188  .
• Soare, Robert I. (1996), „Computability and recursion”, Bulletin of Symbolic Logic, 2 (3): 284—321, CiteSeerX 10.1.1.35.5803 , JSTOR 420992, doi:10.2307/420992 .
• Solovay, Robert M. (1976), „Provability Interpretations of Modal Logic”, Israel Journal of Mathematics, 25 (3–4): 287—304, S2CID 121226261, doi:10.1007/BF02757006 .
• Woodin, W. Hugh (2001), „The Continuum Hypothesis, Part I”, Notices of the American Mathematical Society, 48 (6) . PDF

Класичне публикације, текстови, и колекције

• Burali-Forti, Cesare (1897), A question on transfinite numbers , reprinted in van Heijenoort 1976, pp. 104–111.
• Dedekind, Richard (1872), Stetigkeit und irrationale Zahlen . English translation of title: "Consistency and irrational numbers".
• Dedekind, Richard (1888), Was sind und was sollen die Zahlen?  Two English translations:
  • 1963 Essays on the Theory of Numbers. 1901. . Beman, W. W., ed. and trans. Dover.
  • 1996. In From Kant to Hilbert: A Source Book in the Foundations of Mathematics, 2 vols, Ewald, William B., ed., Oxford University Press: 787–832.
• Fraenkel, Abraham A. (1922), „Der Begriff 'definit' und die Unabhängigkeit des Auswahlsaxioms”, Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-mathematische Klasse, стр. 253—257  (German), reprinted in English translation as "The notion of 'definite' and the independence of the axiom of choice", van Heijenoort 1976, pp. 284–289.
• Frege, Gottlob (1879), Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle a. S.: Louis Nebert. Translation: Concept Script, a formal language of pure thought modelled upon that of arithmetic, by S. Bauer-Mengelberg in Jean Van Heijenoort, ed., 1967. From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931. Harvard University Press. .
• Frege, Gottlob (1884), Die Grundlagen der Arithmetik: eine logisch-mathematische Untersuchung über den Begriff der Zahl. Breslau: W. Koebner. Translation: J. L. Austin, 1974. The Foundations of Arithmetic: A logico-mathematical enquiry into the concept of number, 2nd ed. Blackwell.
• Gentzen, Gerhard (1936), „Die Widerspruchsfreiheit der reinen Zahlentheorie”, Mathematische Annalen, 112: 132—213, S2CID 122719892, doi:10.1007/BF01565428 , reprinted in English translation in Gentzen's Collected works, M. E. Szabo, ed., North-Holland, Amsterdam, 1969.
• Gödel, Kurt (1929), Über die Vollständigkeit des Logikkalküls, doctoral dissertation, University Of Vienna . English translation of title: "Completeness of the logical calculus".
• Gödel, Kurt (1930), „Die Vollständigkeit der Axiome des logischen Funktionen-kalküls”, Monatshefte für Mathematik und Physik, 37: 349—360, S2CID 123343522, doi:10.1007/BF01696781 . English translation of title: "The completeness of the axioms of the calculus of logical functions".
• Gödel, Kurt (1931), „Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I”, Monatshefte für Mathematik und Physik, 38 (1): 173—198, S2CID 197663120, doi:10.1007/BF01700692 , see On Formally Undecidable Propositions of Principia Mathematica and Related Systems for details on English translations.
• Gödel, Kurt (1958), „Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes”, Dialectica. International Journal of Philosophy, 12 (3–4): 280—287, doi:10.1111/j.1746-8361.1958.tb01464.x , reprinted in English translation in Gödel's Collected Works, vol II, Solomon Feferman et al., eds. Oxford University Press, 1990.
• van Heijenoort, Jean, ур. (1976) [1967], From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931 (3rd изд.), Cambridge, Mass: Harvard University Press, ISBN 978-0-674-32449-7, (pbk.) 
• Hilbert, David (1899), Grundlagen der Geometrie, Leipzig: Teubner , English 1902 edition (The Foundations of Geometry) republished 1980, Open Court, Chicago.
• Hilbert, David (1929), „Probleme der Grundlegung der Mathematik”, Mathematische Annalen, 102: 1—9, S2CID 122870563, doi:10.1007/BF01782335, Архивирано из оригинала 08. 09. 2017. г., Приступљено 26. 12. 2020 . Lecture given at the International Congress of Mathematicians, 3 September 1928. Published in English translation as "The Grounding of Elementary Number Theory", in Mancosu 1998, pp. 266–273.
• Hilbert, David; Bernays, Paul (1934). Grundlagen der Mathematik. I. Die Grundlehren der mathematischen Wissenschaften. 40. Berlin, New York: Springer-Verlag. ISBN 978-3-540-04134-4. JFM 60.0017.02. MR 0237246. 
• Kleene, Stephen Cole (1943), „Recursive Predicates and Quantifiers”, American Mathematical Society Transactions, 54 (1): 41—73, JSTOR 1990131, doi:10.2307/1990131  .
• Lobachevsky, Nikolai (1840), Geometrishe Untersuchungen zur Theorie der Parellellinien  (German). Reprinted in English translation as "Geometric Investigations on the Theory of Parallel Lines" in Non-Euclidean Geometry. ISBN 0-486-60027-0. , Robert Bonola (ed.), Dover.
• Löwenheim, Leopold (1915), „Über Möglichkeiten im Relativkalkül”, Mathematische Annalen, 76 (4): 447—470, ISSN 0025-5831, S2CID 116581304, doi:10.1007/BF01458217, Архивирано из оригинала 08. 09. 2017. г., Приступљено 26. 12. 2020  (German). Translated as "On possibilities in the calculus of relatives" in Jean van Heijenoort, 1967. A Source Book in Mathematical Logic, 1879–1931. Harvard University Press. : 228–251.
• Mancosu, Paolo, ур. (1998), From Brouwer to Hilbert. The Debate on the Foundations of Mathematics in the 1920s, Oxford: Oxford University Press .
• Pasch, Moritz (1882), Vorlesungen über neuere Geometrie .
• Peano, Giuseppe (1889), Arithmetices principia, nova methodo exposita  (Latin), excerpt reprinted in English translation as "The principles of arithmetic, presented by a new method", van Heijenoort 1976, pp. 83 97.
• Richard, Jules (1905), „Les principes des mathématiques et le problème des ensembles”, Revue Générale des Sciences Pures et Appliquées, 16: 541  (French), reprinted in English translation as "The principles of mathematics and the problems of sets", van Heijenoort 1976, pp. 142–144.
• Skolem, Thoralf (1920), „Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem Theoreme über dichte Mengen”, Videnskapsselskapet Skrifter, I. Matematisk-naturvidenskabelig Klasse, 6: 1—36 .
• Tarski, Alfred (1948), A decision method for elementary algebra and geometry, Santa Monica, California: RAND Corporation 
• Turing, Alan M. (1939), „Systems of Logic Based on Ordinals”, Proceedings of the London Mathematical Society, 45 (2): 161—228, doi:10.1112/plms/s2-45.1.161, hdl:21.11116/0000-0001-91CE-3  
• Zermelo, Ernst (1904), „Beweis, daß jede Menge wohlgeordnet werden kann”, Mathematische Annalen, 59 (4): 514—516, S2CID 124189935, doi:10.1007/BF01445300, Архивирано из оригинала 05. 03. 2016. г., Приступљено 26. 12. 2020  (German), reprinted in English translation as "Proof that every set can be well-ordered", van Heijenoort 1976, pp. 139–141.
• Zermelo, Ernst (1908a), „Neuer Beweis für die Möglichkeit einer Wohlordnung”, Mathematische Annalen, 65: 107—128, ISSN 0025-5831, S2CID 119924143, doi:10.1007/BF01450054, Архивирано из оригинала 08. 09. 2017. г., Приступљено 26. 12. 2020  (German), reprinted in English translation as "A new proof of the possibility of a well-ordering", van Heijenoort 1976, pp. 183–198.
• Zermelo, Ernst (1908b), „Untersuchungen über die Grundlagen der Mengenlehre”, Mathematische Annalen, 65 (2): 261—281, S2CID 120085563, doi:10.1007/BF01449999, Архивирано из оригинала 08. 09. 2017. г., Приступљено 26. 12. 2020 

Спољашње везе

• Hazewinkel Michiel, ур. (2001). „Mathematical logic”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104. 
• Polyvalued logic and Quantity Relation Logic
• forall x: an introduction to formal logic, a free textbook by P. D. Magnus.
• A Problem Course in Mathematical Logic, a free textbook by Stefan Bilaniuk.
• Detlovs, Vilnis, and Podnieks, Karlis (University of Latvia), Introduction to Mathematical Logic. (hyper-textbook).
• Classical Logic by Stewart Shapiro.
• First-order Model Theory by Wilfrid Hodges.
• In the „London Philosophy Study Guide”.  Архивирано на сајту Wayback Machine (23. септембар 2009)
• „Mathematical Logic”.  Архивирано на сајту Wayback Machine (25. јануар 2009)
• „Set Theory & Further Logic”.  Архивирано на сајту Wayback Machine (27. фебруар 2009)
• „Philosophy of Mathematics”.  Архивирано на сајту Wayback Machine (20. јун 2009)