Matematisk logik

Matematisk logik(også kendt somsymbolsk logik) er et felt imatematikkenmed tæt forbindelse tilmatematikkens grundlag,datalogiogfilosofisk logik.^[1]Feltet inkluderer både det matematiske studie aflogikog anvendelsen af formel logik på andre områder af matematikken. De samlende temaer i matematisk logik inkluderer studiet af udtrykskraften iformelle systemerog den deduktive kraft af formelle systemer forbeviser.

Matematisk logik deles ofte ind i felternemængdelære,modelteori,rekursionsteoriogbevisteori.Disse områder deler grundlæggende resultater fra logikken, særligtprædikatslogikog definérbare sæt. I datalogien (særligt i det engelskeACM 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 afmatematikkens grundlag.Dette studie begyndte i slutningen af 1800-tallet med udviklingen afaksiomatiskrammeværktøjer tilgeometri,aritmetikoganalyse.

I begyndelsen af 1900-tallet blev den udformet afDavid Hilberts programtil bevisførelse for konsistensen af grundlagsteorier. Resultater fraKurt Gödel,Gerhard Gentzenog 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.^[2]Logikken blev før denne fremkomst studeret viaretorik,gennemsyllogismerneog viafilosofi.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, herunderKina,Indien,Grækenlandog 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, herunderLeibnizogLambert,men deres indsatser forblev isoleret og stort set ukendte.

1800-tallet

I midten af 1800-tallet fremkomGeorge Booleog derefterAugustus De Morganmed systematiske, matematiske behandlinger af logikken. Deres arbejde, byggende på arbejde af skikkelser indenfor for algebra såsomGeorge Peacock,udvidede den traditionelle aristoteliske doktrin over logikken, til et tilstrækkeligt rammeværktøj for studiet afmatematikkens grundlag.^[3]

Charles Sanders Peircebyggede videre på Booles arbejde, og udviklede et logisk system for relationer og kvantifikatorer, hvilket han udgav i adskillige artikler fra 1870 til 1875. Gottlob Fregepræsenterede en uafhængig udvikling af logikken med kvantifikatorer i hansBegriffsschrift,der blev udgivet i 1879, et værk som generelt betragtes som et drejepunkt i logikkens historie. Freges værk forblev ukendt, indtilBertrand Russellbegyndte 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 udgavErnst SchröderVorlesungen über die Algebra der Logiki 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 termenaritmetiktil teorien om denaturlige 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 visteRichard Dedekind,at naturlige tal kendetegnes unikt gennem deresinduktiveegenskaber. 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 frasuccessor-funktionenog matematisk induktion.

I midten af 1800-tallet blev det kendt, at der var mangler i Euklids aksiomer for geometri.^[4]I tillæg til uafhængigheden afparallel-postulatet,der blev grundlagt afNikolaj Lobatjevskiji 1826,^[5]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 afaksiomer for geometrien,der byggede påtidligere arbejdeaf 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 denreelle tallinje.Disse viste sig at blive et kæmpe forskningsområde i første halvdel af 1900-tallet.

Symbolsk logik

Leopold Löwenheim(1915) ogThoralf Skolem(1920) nåede frem tilLöwenheim–Skolem-teoremet,der siger at førsteordens prædikatlogik ikke kan kontrollerekardinaliteterneaf 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 entællelig model.Dette kontraintutive faktum blev kendt somSkolems paradoks.

Kurt Gödelbeviste sitfuldstændighedsteoremi sin doktorafhandling (1929), der fastlægger en korrespondance mellem syntaks og semantik iførsteordens prædikatslogik.Gödel anvendte fuldstændighedsteoremet til at bevisekompakthedsteoremet,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 Tarskiudviklede grundlaget formodelteorien.

Begyndende i 1935, samarbejdede en gruppe prominente matematikere underpseudonymet 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 sombijektiv,injektivogsurjektiv,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.^[6]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 afStephen Cole KleeneogEmil 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

BogenHandbook of Mathematical Logicinddeler, i grove træk nutidig matematisk logik i fire områder:

mængdelære
modelteori
rekursionsteori,og
bevisteoriogkonstruktiv 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ödelsufuldstæ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 feltkategoriteorianvender mange formelle, aksiomatiske metoder, og inkluderer studiet afkategorisk 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, herunderSaunders Mac Laneforeslået kategoriteori som et grundlagssystem for matematik, uafhængigt af mængdelæren. Disse grundlag gør brug aftoposteorien,der minder om generaliserede modeller for mængdelæren, der kan gøre brug af klassisk eller ikke-klassisk logik.

Se også

Noter

^Tekster på bachelorniveau inkluderer Boolos, Burgess og Jeffrey(2002),Enderton (2001),samt Mendelson(1997).En klassisk tekst på kandidatniveau af Shoenfield(2001)kom frem i 1967.
^Ferreirós 2001, s. 443
^Katz 1998, s. 686.
^Katz 1998, s. 774
^Lobachevsky 1840
^Et detaljeret studie af denne terminologi fås hos Soare (1996).

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. IFrom 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 inJean 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'sCollected 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,seOn Formally Undecidable Propositions of Principia Mathematica and Related Systemsfor 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'sCollected 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" iNon-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" inJean 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 Commonshar flere filer relateret tilMatematisk logik
Mathematical Logic around the world Arkiveret8. april 2007 hosWayback Machine
Polyvalued Logic (PVL) och Quantity Relation Logic (QRL)
forall x: an introduction to formal logic,byP.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– byStewart Shapiro.
Stanford Encyclopedia of Philosophy:First-order Model Theory– byWilfrid Hodges.
TheLondon Philosophy Study GuideArkiveret23. september 2009 hosWayback Machineoffers many suggestions on what to read, depending on the student's familiarity with the subject:
- Mathematical Logic Arkiveret25. januar 2009 hosWayback Machine
- Set Theory & Further Logic Arkiveret27. februar 2009 hosWayback Machine
- Philosophy of Mathematics Arkiveret20. juni 2009 hosWayback Machine

[1] Tekster på bachelorniveau inkluderer Boolos, Burgess og Jeffrey(2002),Enderton (2001),samt Mendelson(1997).En klassisk tekst på kandidatniveau af Shoenfield(2001)kom frem i 1967.

[2] Ferreirós 2001, s. 443

[3] Katz 1998, s. 686.

[4] Katz 1998, s. 774

[5] Lobachevsky 1840

[6] Et detaljeret studie af denne terminologi fås hos Soare (1996).

[1]

[2]

[3]

[4]

[5]

[6]