Matematička logika

Matematička logika je podoblast matematike i logike. Sastoji se od matematičkog proučavanja logike i premena ovog proučavanja na druge oblasti matematike. Matematička logika ima bliske veze sa računarstvom i filozofskom logikom. Među osnovnim temama koje se provlače kroz matematičku logiku su izražajna moć formalnih logika i deduktivna moć dokazivačkih sistema.

Od svog nastanka, matematička logika je doprinela i njen razvoj je bio motivisan proučavanjem osnova matematike. Ovo proučavanje je počelo krajem 19. veka razvojem aksiomatskih okvira za geometriju, aritmetiku i analizu. Početkom 20. veka ju je oblikovao David Hilbert u svom programu za dokazivanje konzistentosti osnovnih teorija. Rezultati Kurta Gedela, Gerharda Gencena, i drugih su dali delimično rešenje programa i razjasnili bitna pitanja kod dokazivanja konzistentnosti. Rad u teoriji skupova je pokazao da skoro cela matematika može da se formalizuje terminima skupova, mada neke teoreme ne mogu da se dokažu u uobičajenim sistemima aksioma za teoriju skupova. Savremeni rad u oblasti osnova matematike se često koncentriše na određivanje koji delovi matematike mogu da se formalizuju u određenom formalnom sistemu, umesto da pokušava da pronađe teorije iz kojih može da se razvije cela matematika.

Matematička logika se često deli u sledeće podoblasti: teorija skupova, teorija modela, teorija rekurzije, teorija dokaza i konstruktivna matematika.

Istorija

Matematička logika je počela da se odvaja kao zasebno polje sredinom 19. veka (Ferreirós (2001). pp. 443). Do tada, logika je proučavana sa retorikom, kroz silogizme, i sa filozofijom. Sofisticirane logičke teorije su razvijane u mnogim kulturama; na zapadu su najpoznatije Aristotelova teorija silogizama i Euklidove aksiome planarne geometrije. U 18. veku su načinjeni pokušaji da se operacije formalne logike tretiraju na simbolički ili algebarski način. Ovime su se bavili matematičari poput Lajbnica i Lamberta, ali je njihov trud ostao izolovan i malo poznat.

19. vek

Sredinom 19. veka Bul a zatim i De Morgan su predstavili sistematsku matematičku obradu logike. Njihov rad, zasnovan na algebarskom radu matematičara poput Džordža Pikoka engl. George Peacock, je reformisao i proširio tradicionalnu aristotelovsku doktrinu logike i razvio odgovarajuće instrumente za proučavanje osnovnihpojmova matematike (Katz (1998). pp. 686).

Čarls Pirs je oslanjajući se na Bulove rezultate razvio logički sistem za relacije i kvantifikatore, koji je objavio u nekoliko radova od 1870. do 1885.

Gotlob Frege je predstavio nezavisan razvoj logike sa kvantifikatorima u svom radu Begriffsschrift, objavljenom 1879. Međutim, Fregeov rad je ostao relativno nepoznat dok ga Rasel kasnije nije promovisao. Dvodimenziona notacija koju je frege razvio nikada nije šire prihvaćena, i ne koristi se u savremenim tekstovima.

Od 1890. do 1905, Ernst Šreder je objavio Vorlesungen über die Algebra der Logik u tri toma. Ovo delo je sumiralo i proširilo rad Bula, De Morgana i Pirsa, i predstavljalo je značajan izvor za razumevanje simboličke logike krajem 19. veka.

Osnovne teorije

Razvoj formalne logike, zajedno sa zabrinutošću da matematika nije izgrađena na odgovarajućim osnovama je doveo do razvoja aksiomatskih sistema za fundamentalne oblasti matematike kao što su aritmetika, analiza i geometrija.

U logici, izraz aritmetika se odnosi na teoriju prirodnih brojeva. Đuzepe Peano (Peano, Giuseppe (1888), Arithmetices principia, nova methodo exposita) je objavio skup aksioma za aritmetiku, koristeći varijaciju logičkog sistema Bula i Šredera, uz dodatak kvantifikatora. Peano tada nije bio svestan Fregeovog rada. Otprilike u isto vreme, Rihard Dedekind je pokazao da su prirodni brojevi jedinstveno karakterizovani svojim indukcionim svojstvima. Dedekind (Dedekind, Richard (1888), Was sind und was sollen die Zahlen?) je predložio drugačiju karakterizaciju, kojoj je nedostajao formalni logički karakter Peanovih aksioma. Međutim, Dedekind je svojim radom dokazao teoreme nedostupne iz Peanovog sistema, uključujući jedinstvenost skupa prirodnih brojeva (do na izomorfizam) i rekurzivne definicije sabiranja i množenja iz funkcije naslednika i matematičke indukcije.

Sredinom 19. veka, su postale vidljive mane u Euklidovim aksiomama za geometriju. Osim nezavisnosti postulata paralelnosti, koji je uspostavio Nikolaj Lobačevski 1826. (Lobachevsky, Nikolai (1840), Geometrishe Untersuchungen zur Theorie der Parellellinien), matematičari su otkrili da određene teoreme koje je Euklid uzimao zdravo za gotovo u stvari nisu dokazive iz njegovih aksioma. Među njima je teorema da prava sadrži najmanje dve tačke, ili da krugovi istog poluprečnika čiji su centri udaljeni za taj poluprečnik moraju da se presecaju. Hilbert (1899) je razvio kompletan skup aksioma za geometriju, baziran na prethodnom radu Paša (1882). Uspeh u aksiomatizaciji geometrije je motivisao Hilberta da se da u potragu za kompletnim aksiomatizacijama drugih oblasti matematike, kao što su realna prava i prirodni brojevi. Ovo je postalo jedna od najvećih oblasti istraživanja u prvoj polovini 20. veka.

U 19. veku je došlo do velikih napredaka u teoriji realne analize, uključujući teoriju konvergencije funkcija i Furijeove redove. Matematičari poput Karla Vajerštrasa su počeli da konstruišu funkcije neobične za intuiciju, poput nigde-diferencijabilne neprekidne funkcije. Prethodna shvatanja funkcije kao pravila za računanje ili glatkog grafika, više nisu bila prihvatljiva. Vajerštras je počeo da se zalaže za aritmetizaciju analize, koja je težila da aksiomatizuje analizu korišćenjem svojstava prirodnih brojeva. Bolcano i Koši su između 1817. i 1823. razvili modernu "ε-δ" definiciju limesa i neprekidnih funkcija (Felscher, Walter (2000), “Bolzano, Cauchy, Epsilon, Delta”, The American Mathematical Monthly . 107 (9): 844—862.  ). 1858, Dedekind je predložio definiciju realnih brojeva u terminima Dedekindovih sečenja racionalnih brojeva (Dedekind, Richard (1872), Stetigkeit und irrationale Zahlen), što je definicija koja se još uvek koristi u savremenim tekstovima.

Georg Kantor je razvio fundamentalne koncepte beskonačne teorije skupova. Njegovi rani rezultati su razvili teoriju kardinalnosti i dokazali da realni i prirodni brojevi imaju različitu kardinalnost (Cantor 1874). Tokom narednih dvadeset godina, Kantor je razvio teoriju transfinitnih brojeva u nizu publikacija. 1891, je objavio novi dokaz neprebrojivosti realnih brojeva, koji je uveo Kantorov dijagonalni postupak, i koristio ovaj metod da dokaže Kantorovu teoremu da nijedan skup ne može da bude iste kardinalnosti kao i njegov partitivni skup. Kantor je verovao da za svaki skup postoji dobro uređenje, ali nije mogao ovo da dokaže, pa je to ostavio kao otvoreno pitanje .

20. vek

U početnim decenijama 20. veka, glavne oblasti proučavanja su bile teorija skupova i formalna logika. Otkriće paradoksa u neformalnoj teoriji skupova je učinilo da se neki zapitaju da li je i sama matematika nekonzistentna, i da se daju u potragu za dokazima konzistentnosti.

1900, Hilbert je dao svoj čuveni spisak 23 problema za naredni vek. Prva dva problema su se ticala razrešenja hipoteze kontinuuma i dokazivanja konzistentnosti elementarne aritmetike, redom; deseti je bio pronalaženje metoda koji bi odredio da li multivarijantne polinomijalne jednačine nad celim brojevima imaju rešenje. Dalji rad na rešavanju ovih problema je oblikovao smer razvoja matematičke logike, kao što je učinio i napor da se reši Hilbertov Entscheidungsproblem, postavljen 1928. Ovaj problem je tražio proceduru koja bi za dati formalizovani matematički iskaz odlučila da li je istinit ili neistinit.

Literatura

• Predrag Janičić, Matematička logika u računarstvu, Matematički fakultet. . Beograd. 2007. ISBN 978-86-7589-040-9.  .
• Zoran Ognjanović, Nenad Krdžavac, Uvod u teorijsko računarstvo, FON, Beograd, 2004.
• Milan Božić, Pregled istorije i filozofije matematike, Zavod za udžbenike i nastavna sredstva. . Beograd. 2002. str. 230—269. ISBN 86-17-10124-5.  .
• Dirk J. Strojk, Kratak pregled istorije matematike, Zavod za izdavanje udžbenika, Beograd, 1969

Dodiplomski tekstovi

• 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 izd.), 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 izd.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3 .
• Fisher, Alec (1982), Formal Number Theory and Computability: A Workbook (1st izd.), 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 izd.), Cambridge: Cambridge University Press, ISBN 978-0-521-36865-0 .
• Ebbinghaus, H.-D.; Flum, J.; Thomas, W. (1994), Mathematical Logic (2nd izd.), 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 izd.), London: Chapman & Hall, ISBN 978-0-412-80830-2 .
• Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic (3rd izd.), 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, Pristupljeno 2016-02-24 .
• Shawn Hedman, A first course in logic: an introduction to model theory, proof theory, computability, and complexity, Oxford University Press, (2004) ISBN 0-19-852981-3. 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 .

Diplomski tekstovi

• Andrews, Peter B. (2002), An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof (2nd izd.), Boston: Kluwer Academic Publishers, ISBN 978-1-4020-0763-7 .
• Barwise, Jon, ur. (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 izd.), 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 izd.), Cambridge: Cambridge University Press, ISBN 978-0-521-77911-1 .

Istraživački članci, monografije, tekstovi, i pregledi

• 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, 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, Arhivirano iz originala (PDF) 02. 02. 2023. g., Pristupljeno 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

Klasične publikacije, tekstovi, i kolekcije

• 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 (1901). Essays on the Theory of Numbers. 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, str. 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, ur. (1976) [1967], From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931 (3rd izd.), 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, Arhivirano iz originala 08. 09. 2017. g., Pristupljeno 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, Robert Bonola (ed.), Dover. ISBN 0-486-60027-0.
• 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, Arhivirano iz originala 08. 09. 2017. g., Pristupljeno 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 Univ. Press: 228–251.
• Mancosu, Paolo, ur. (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, Arhivirano iz originala 05. 03. 2016. g., Pristupljeno 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, Arhivirano iz originala 08. 09. 2017. g., Pristupljeno 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, Arhivirano iz originala 08. 09. 2017. g., Pristupljeno 26. 12. 2020 

Spoljašnje veze

• Hazewinkel Michiel, ur. (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)