Matematisk logik

Matematisk logik (også kendt som symbolsk logik) er et felt i matematikken med tæt forbindelse til matematikkens grundlag, datalogi og filosofisk logik. Feltet inkluderer både det matematiske studie af logik og anvendelsen af formel logik på andre områder af matematikken. De samlende temaer i matematisk logik inkluderer studiet af udtrykskraften i formelle systemer og den deduktive kraft af formelle systemer for beviser.

Matematisk logik deles ofte ind i felterne mængdelære, modelteori, rekursionsteori og bevisteori. Disse områder deler grundlæggende resultater fra logikken, særligt prædikatslogik og definérbare sæt. I datalogien (særligt i det engelske ACM Classification), omfatter matematisk logik yderligere emner, der ikke indgår i denne artikel.

Matematisk logik har siden begyndelsen både bidraget til, og været motiveret af, studiet af matematikkens grundlag. Dette studie begyndte i slutningen af 1800-tallet med udviklingen af aksiomatisk rammeværktøjer til geometri, aritmetik og analyse.

I begyndelsen af 1900-tallet blev den udformet af David Hilberts program til bevisførelse for konsistensen af grundlagsteorier. Resultater fra Kurt Gödel, Gerhard Gentzen og andre, gav delvise løsninger til programmet, og klargjorde udfordringerne som indgik i at bevise konsistensen. Arbejdet i mængdelære viste, at næsten alle ordinære matematikker kan formaliseres med brug af termer for sæt, selv om der er teoremer, der ikke kan bevises i almindelige aksiomsystemer for mængdelære. Nuværende arbejde i grundlagsmatematik fokuserer ofte på, at fastslå hvilke dele af matematikken, der kan formaliseres i partikulære formelle systemer, frem for at forsøge at nå frem til teorier, hvori al matematik kan udvikles fra.

Historie

Matematisk logik fremkom i midten af 1800-tallet som et felt i matematikken, der var uafhængigt af det traditionelle studie af logik. Logikken blev før denne fremkomst studeret via retorik, gennem syllogismerne og via filosofi. I den første halvdel af 1900-tallet skete der en eksplosiv udvikling, der bidrog med grundlæggende resultater, ledsaget af en livlig debat om matematikkens grundlag.

Den tidlige historie

Logiske teorier blev udviklet i mange kulturer gennem historien, herunder Kina, Indien, Grækenland og den islamiske verden. I 1700-tallets Europa, var der forsøg på at behandle operationer fra formel logik, på en symbolsk eller algebraisk facon. Forsøg, der blev foretaget af filosofiske matematikere, herunder Leibniz og Lambert, men deres indsatser forblev isoleret og stort set ukendte.

1800-tallet

I midten af 1800-tallet fremkom George Boole og derefter Augustus De Morgan med systematiske, matematiske behandlinger af logikken. Deres arbejde, byggende på arbejde af skikkelser indenfor for algebra såsom George Peacock, udvidede den traditionelle aristoteliske doktrin over logikken, til et tilstrækkeligt rammeværktøj for studiet af matematikkens grundlag.

Charles Sanders Peirce byggede videre på Booles arbejde, og udviklede et logisk system for relationer og kvantifikatorer, hvilket han udgav i adskillige artikler fra 1870 til 1875. Gottlob Frege præsenterede en uafhængig udvikling af logikken med kvantifikatorer i hans Begriffsschrift, der blev udgivet i 1879, et værk som generelt betragtes som et drejepunkt i logikkens historie. Freges værk forblev ukendt, indtil Bertrand Russell begyndte at promovere det omkring århundredeskiftet. Den todimensionelle notation som Frege havde udviklet, blev aldrig vidt udbredt, og anvendes ikke i nutidige tekster.

Fra 1890 til 1905 udgav Ernst Schröder Vorlesungen über die Algebra der Logik i tre værker. Dette værk opsummerede og udvidede værker fra Boole, De Morgan og Peirce, og var et omfattende referenceværk til symbolsk logik, som den blev forstået ved udgangen af 1800-tallet.

Grundlagsteorier

Bekymringer over at matematikken ikke var bygget på et egnet grundlag, ledte til udviklingen af aksiomatiske systemer for grundlæggende områder af matematikken, såsom aritmetik, analyse og geometri.

I logikken henviser termen aritmetik til teorien om de naturlige tal. Giuseppe Peano (1888) udgav et sæt af aksiomer for aritmetikken, der senere har båret hans navn (Peano-aksiomer), der anvendte en variation af det logiske system fra Boole og Schröder, men tilføjede kvantifikatorer. Peano kendte ikke til Freges samtidige arbejde. Omkring samme tid viste Richard Dedekind, at naturlige tal kendetegnes unikt gennem deres induktive egenskaber. Dedekind (1888) foreslå en anden karakterisering, der ikke indeholdt den formelle logiske karakter fra Peanos aksiomer. Dedekinds værk beviste dog teoremer, der var utilgængelige i Peanos system, inklusive det unikke ved sæt af naturlige tal (op til isomorfisme) og de rekursive definitioner fra addition og multiplikation fra successor-funktionen og matematisk induktion.

I midten af 1800-tallet blev det kendt, at der var mangler i Euklids aksiomer for geometri. I tillæg til uafhængigheden af parallel-postulatet, der blev grundlagt af Nikolaj Lobatjevskij i 1826, så opdagede matematikere at visse teoremer, der blev taget for givet af Euklid, faktisk ikke kunne bevises fra hans aksiomer. Blandt disse er teoremet om at en linje mindst indeholder to punkter, eller at cirkler med samme radius, hvis midtepunkter er adskilte af denne radius, må skære hinanden. Hilbert (1899) udviklede et komplet sæt af aksiomer for geometrien, der byggede på tidligere arbejde af Pasch (1882). Successen med at aksiomatisering af geometrien, motiverede Hilbert til at søge komplet aksiomatisering på andre områder af matematikken, såsom de naturlige tal og den reelle tallinje. Disse viste sig at blive et kæmpe forskningsområde i første halvdel af 1900-tallet.

Symbolsk logik

Leopold Löwenheim (1915) og Thoralf Skolem (1920) nåede frem til Löwenheim–Skolem-teoremet, der siger at førsteordens prædikatlogik ikke kan kontrollere kardinaliteterne af infinitte strukturer. Skolem opdagede at dette ville gælde for førsteordens-formaliseringer af mængdelæren, og at det implicerer at enhver sådan formalisering har en tællelig model. Dette kontraintutive faktum blev kendt som Skolems paradoks.

Kurt Gödel beviste sit fuldstændighedsteorem i sin doktorafhandling (1929), der fastlægger en korrespondance mellem syntaks og semantik i førsteordens prædikatslogik. Gödel anvendte fuldstændighedsteoremet til at bevise kompakthedsteoremet, der demonstrerede finitte natur af logiske konskevenser af første ordener. Disse resultater bidrog til at etablere en førsteordens prædikatslogik som den dominerende logik, der anvendes af matematikere.

Starten på andre grene

Alfred Tarski udviklede grundlaget for modelteorien.

Begyndende i 1935, samarbejdede en gruppe prominente matematikere under pseudonymet Nicolas Bourbaki, at udgive en række matematiske leksikon-tekster. Disse tekster, der blev skrevet i en sparsom og aksiomatisk stil, betonede en stringent præsentation og mængdelære som grundlag. Terminologi som blev skabt i disse tekster, var ord som bijektiv, injektiv og surjektiv, samt den grundlæggende mængdelære som teksterne anvendte, blev vidt udbredt i hele matematikken.

Studiet er beregnelighed blev kendt som rekursionsteori, fordi tidlige formaliseringer af Gödel og Kleen hvilede på rekursive definitioner af funktioner. Da disse definitioner blev vist at være ækvivalente med Turings formalisering, involverende Turing-maskiner, blev det klart at et nyt begreb – den beregnelige funktion – var blevet opdaget, og at denne definition var tilstrækkelig robust til at tillade adskillige, uafhængige karakteristiker. I sit arbejde med ufuldstændighedssætningerne i 1931, manglede Gödel et stringent begreb for et effektivt, formelt system; han indså straks at de nye definitioner for beregnelighed kunne anvendes til dette formål, hvilket tillod ham at udtrykke ufuldstændighedssætningerne generelt, hvor de i den oprindelige artikel antydet.

Adskillige resultater i rekursionsteori blev nået i 1940'erne af Stephen Cole Kleene og Emil Leon Post. Kleene (1943) introducerede begreberne om relativ beregnelighed, foregrebet af Turing (1939), aritmetisk hierarki. Kleene generaliserede senere rekursionsteori til funktionaler af højere orden. Kleene og Kreisel studerede formelle versioner af intuitionistisk matematik, særligt i konteksten af bevisteori.

Underområder og omfang

Bogen Handbook of Mathematical Logic inddeler, i grove træk nutidig matematisk logik i fire områder:

1. mængdelære
2. modelteori
3. rekursionsteori, og
4. bevisteori og konstruktiv matematik (betragtes som dele af et enkelt område).

Hvert område har forskelligt fokus, selv om mange teknikker og resultater deles mellem flere områder. Grænselinjerne mellem disse felter, og inddelingerne mellem matematisk logik og andre felter i matematikken, er ikke altid skarpe. Gödels ufuldstændighedssætning markerer ikke blot en milepæl i rekursionsteori og bevisteori, men har også ført til Löbs sætning i modallogikken. Metoden, der på engelsk kaldes forcing, bliver anvendt i mængdelære, modelteori og rekursionsteori, samt i studidet af intuitionistisk matematik.

Det matematiske felt kategoriteori anvender mange formelle, aksiomatiske metoder, og inkluderer studiet af kategorisk logik, men kategoriteori bliver normalt ikke anset som en underområde af matematisk logik. Grundet dets anvendelighed i forskellige felter af matematikken, så har matematikere, herunder Saunders Mac Lane foreslået kategoriteori som et grundlagssystem for matematik, uafhængigt af mængdelæren. Disse grundlag gør brug af toposteorien, der minder om generaliserede modeller for mængdelæren, der kan gøre brug af klassisk eller ikke-klassisk logik.

Se også

• Logik
• Matematik
• Prædikatslogik

Referencer

Tekster på bachelorniveau

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

• Boolos, George; Burgess, John; Jeffrey, Richard (2002), Computability and Logic (4th udgave), Cambridge: Cambridge University Press, ISBN 978-0-521-00758-0, (pbk.).
• Enderton, Herbert (2001), A mathematical introduction to logic (2nd udgave), Boston, MA: Academic Press, ISBN 978-0-12-238452-3.
• Hamilton, A.G. (1988), Logic for Mathematicians (2nd udgave), Cambridge: Cambridge University Press, ISBN 978-0-521-36865-0.
• Ebbinghaus, H.-D.; Flum, J.; Thomas, W. (1994), Mathematical Logic (2nd udgave), New York: Springer, ISBN 0-387-94258-0.
• Katz, Robert (1964), Axiomatic Analysis, Boston, MA: D. C. Heath and Company.
• Mendelson, Elliott (1997), Introduction to Mathematical Logic (4th udgave), London: Chapman & Hall, ISBN 978-0-412-80830-2.
• Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic (3rd udgave), New York: Springer Science+Business Media, doi:10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6{{citation}}: CS1-vedligeholdelse: url-status (link).
• Schwichtenberg, Helmut (2003-2004), Mathematical Logic (PDF), Munich, Germany: Mathematisches Institut der Universität München.
• 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. Dækker logik tæt sammen med teori om beregnelighed og kompleksitetsteori

Tekster på kandidatniveau

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

Forskningsudgivelser, monografer, tekster og undersøgelser

• Cohen, P. J. (1966), Set Theory and the Continuum Hypothesis, Menlo Park, CA: W. A. Benjamin.
• Davis, Martin (1973), "Hilbert's tenth problem is unsolvable", The American Mathematical Monthly, The American Mathematical Monthly, Vol. 80, No. 3, 80 (3): 233-269, doi:10.2307/2318447, JSTOR 2318447, genudgivet som et appendiks i Martin Davis, Computability and Unsolvability, Dover reprint 1982. JStor
• Felscher, Walter (2000), "Bolzano, Cauchy, Epsilon, Delta", The American Mathematical Monthly, The American Mathematical Monthly, Vol. 107, No. 9, 107 (9): 844-862, doi:10.2307/2695743, JSTOR 2695743. JSTOR
• Ferreirós, José (2001), "The Road to Modern Logic-An Interpretation", Bulletin of Symbolic Logic, The Bulletin of Symbolic Logic, Vol. 7, No. 4, 7 (4): 441-484, doi:10.2307/2687794, JSTOR 2687794. JStor
• Hamkins, Joel David; Löwe, Benedikt, "The modal logic of forcing", Transactions of the American Mathematical Society, vil udkomme. Elektronisk udgivelse af journalen (Webside ikke længere tilgængelig)
• Katz, Victor J. (1998), A History of Mathematics, Addison–Wesley, ISBN 0-321-01618-1.
• Morley, Michael (1965), "Categoricity in Power", Transactions of the American Mathematical Society, Transactions of the American Mathematical Society, Vol. 114, No. 2, 114 (2): 514-538, doi:10.2307/1994188, JSTOR 1994188.
• Soare, Robert I. (1996), "Computability and recursion", Bulletin of Symbolic Logic, The Bulletin of Symbolic Logic, Vol. 2, No. 3, 2 (3): 284-321, doi:10.2307/420992, JSTOR 420992.
• Solovay, Robert M. (1976), "Provability Interpretations of Modal Logic", Israel Journal of Mathematics, 25 (3-4): 287-304, doi:10.1007/BF02757006.
• Woodin, W. Hugh (2001), "The Continuum Hypothesis, Part I", Notices of the American Mathematical Society, 48 (6). PDF

Klassiske artikler, tekster og samlinger

• Burali-Forti, Cesare (1897), A question on transfinite numbers, reprinted in van Heijenoort 1976, pp. 104–111.
• Dedekind, Richard (1872), Stetigkeit und irrationale Zahlen. Engelsk oversættelse med titlen: "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. I From Kant to Hilbert: A Source Book in the Foundations of Mathematics, to værker, 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, s. 253-257 (German), genudgivet i engelsk oversættelse som "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. Engelsk oversættelse: Concept Script, a formal language of pure thought modelled upon that of arithmetic, af 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. Engelsk oversættelse: 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, 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. Engelsk oversættelse med titlen: "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, doi:10.1007/BF01696781. Engelsk oversættelse med titlen: "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, doi:10.1007/BF01700692, se On Formally Undecidable Propositions of Principia Mathematica and Related Systems for detaljer om engelske oversættelser.
• 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, genudgivet i engelsk oversættelse i Gödel's Collected Works, vol II, Soloman Feferman et al., eds. Oxford University Press, 1990.
• van Heijenoort, Jean, red. (1976) [1967], From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931 (3rd printing with corrections udgave), Cambridge, Mass: Harvard University Press, ISBN 0-674-32449-8, (pbk.)
• Hilbert, David (1899), Grundlagen der Geometrie, Leipzig: Teubner, Engelsk udgave fra 1902 (The Foundations of Geometry) genudgivet i 1980, Open Court, Chicago.
• David, Hilbert (1929), "Probleme der Grundlegung der Mathematik", Mathematische Annalen, 102: 1-9, doi:10.1007/BF01782335. Forelæsning afholdt ved International Congress of Mathematicians, 3. september 1928. Udgivet i engelsk oversættelse som "The Grounding of Elementary Number Theory", i Mancosu 1998, pp. 266–273.
• Kleene, Stephen Cole (1943), "Recursive Predicates and Quantifiers", American Mathematical Society Transactions, Transactions of the American Mathematical Society, Vol. 53, No. 1, 54 (1): 41-73, doi:10.2307/1990131, JSTOR 1990131.
• Lobachevsky, Nikolai (1840), Geometrishe Untersuchungen zur Theorie der Parellellinien (Tysk). Genudgivet i engelsk oversættelse som "Geometric Investigations on the Theory of Parallel Lines" i Non-Euclidean Geometry, Robert Bonola (ed.), Dover, 1955. ISBN 0-486-60027-0
• Löwenheim, Leopold (1915), "Über Möglichkeiten im Relativkalkül", Mathematische Annalen, 76 (4): 447-470, doi:10.1007/BF01458217, ISSN 0025-5831 (Tysk). Oversat som "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, red. (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 (1888), Arithmetices principia, nova methodo exposita (Italiensk), uddrag genudgivet i engelsk oversættelse som "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 (Fransk), genudgivet i engelsk oversættelse som "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
• Zermelo, Ernst (1904), "Beweis, daß jede Menge wohlgeordnet werden kann", Mathematische Annalen, 59 (4): 514-516, doi:10.1007/BF01445300 (Tysk), genudgivet i engelsk oversættelse som "Proof that every set can be well-ordered", van Heijenoort 1976, s. 139–141.
• Zermelo, Ernst (1908a), "Neuer Beweis für die Möglichkeit einer Wohlordnung", Mathematische Annalen, 65: 107-128, doi:10.1007/BF01450054, ISSN 0025-5831 (Tysk), genudgivet i engelsk oversættelse som "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, doi:10.1007/BF01449999.

Eksterne henvisninger

• Wikimedia Commons har flere filer relateret til Matematisk logik
• Mathematical Logic around the world Arkiveret 8. april 2007 hos Wayback Machine
• Polyvalued Logic (PVL) och Quantity Relation Logic (QRL)
• forall x: an introduction to formal logic, by P.D. Magnus, is a free textbook.
• A Problem Course in Mathematical Logic, by Stefan Bilaniuk, is another free textbook.
• Detlovs, Vilnis, and Podnieks, Karlis (University of Latvia) Introduction to Mathematical Logic. A hyper-textbook.
• Stanford Encyclopedia of Philosophy: Classical Logic – by Stewart Shapiro.
• Stanford Encyclopedia of Philosophy: First-order Model Theory – by Wilfrid Hodges.
• The London Philosophy Study Guide Arkiveret 23. september 2009 hos Wayback Machine offers many suggestions on what to read, depending on the student's familiarity with the subject:
  • Mathematical Logic Arkiveret 25. januar 2009 hos Wayback Machine
  • Set Theory & Further Logic Arkiveret 27. februar 2009 hos Wayback Machine
  • Philosophy of Mathematics Arkiveret 20. juni 2009 hos Wayback Machine