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:
 mængdelære
 modelteori
 rekursionsteori, og
 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

Noter

Referencer

Tekster på bachelorniveau 
 .

 .
 .
 .
 .
 .
 .
 .
 .
 Shawn Hedman, A first course in logic: an introduction to model theory, proof theory, computability, and complexity, Oxford University Press, 2004, . Dækker logik tæt sammen med teori om beregnelighed og kompleksitetsteori

Tekster på kandidatniveau 
 .
 .
 .
 .
 .
 .

Forskningsudgivelser, monografer, tekster og undersøgelser 
 .
 , genudgivet som et appendiks i Martin Davis, Computability and Unsolvability, Dover reprint 1982. JStor
 . JSTOR
 . JStor
 , vil udkomme. Elektronisk udgivelse af journalen
 .
 .
 .
 .
 . PDF

Klassiske artikler, tekster og samlinger 
 , reprinted in van Heijenoort 1976, pp. 104–111.
 . Engelsk oversættelse med titlen: "Consistency and irrational numbers".
 {{Citation
  | first1=Richard
  | last1=Dedekind
  | year=1888
  | title=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.
  (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.

 , reprinted in English translation in Gentzen's Collected works, M. E. Szabo, ed., North-Holland, Amsterdam, 1969.
 . Engelsk oversættelse med titlen: "Completeness of the logical calculus".
 . Engelsk oversættelse med titlen: "The completeness of the axioms of the calculus of logical functions".
 , se On Formally Undecidable Propositions of Principia Mathematica and Related Systems for detaljer om engelske oversættelser.
 , genudgivet i engelsk oversættelse i Gödel's Collected Works, vol II, Soloman Feferman et al., eds. Oxford University Press, 1990.
 
 , Engelsk udgave fra 1902 (The Foundations of Geometry) genudgivet i 1980, Open Court, Chicago.
 . 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.
 .
  (Tysk). Genudgivet i engelsk oversættelse som "Geometric Investigations on the Theory of Parallel Lines" i Non-Euclidean Geometry, Robert Bonola (ed.), Dover, 1955. 
  (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.
 .
 .
  (Italiensk), uddrag genudgivet i engelsk oversættelse som "The principles of arithmetic, presented by a new method", van Heijenoort 1976, pp. 83 97.
  (Fransk), genudgivet i engelsk oversættelse som "The principles of mathematics and the problems of sets", van Heijenoort 1976, pp. 142–144.
 .
 
 
  (Tysk), genudgivet i engelsk oversættelse som "Proof that every set can be well-ordered", van Heijenoort 1976, s. 139–141.
  (Tysk), genudgivet i engelsk oversættelse som "A new proof of the possibility of a well-ordering", van Heijenoort 1976, pp. 183–198.
 .

 Eksterne henvisninger 

 Mathematical Logic around the world 
 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  offers many suggestions on what to read, depending on the student's familiarity with the subject:
 Mathematical Logic 
 Set Theory & Further Logic 
 Philosophy of Mathematics 

 
Logik
Matematiske discipliner