Matematisk logikk - Mathematical logic

For Quines teori noen ganger kalt "Mathematical Logic", se New Foundations .
For annen bruk, se Logikk (disambiguation) .

Matematisk logikk er studiet av logikk innen matematikk . Store delområder inkluderer modellteori , bevissteori , settteori og rekursjonsteori . Forskning i matematisk logikk tar vanligvis for seg de matematiske egenskapene til formelle logikksystemer, for eksempel deres uttrykksfulle eller deduktive kraft. Imidlertid kan det også inkludere bruk av logikk for å karakterisere riktig matematisk resonnement eller for å etablere grunnlag for matematikk .

Siden starten har matematisk logikk både bidratt til, og har blitt motivert av, studiet av grunnlaget for matematikk. Denne studien begynte på slutten av 1800 -tallet med utvikling av aksiomatiske rammer for geometri , regning og analyse . I begynnelsen av det 20. århundre ble det formet av David Hilbert 's program å bevise konsistensen av grunn teorier. Resultatene til Kurt Gödel , Gerhard Gentzen og andre ga delvis oppløsning til programmet, og tydeliggjorde problemene som var involvert i å bevise konsistens. Arbeid i settteori viste at nesten all vanlig matematikk kan formaliseres når det gjelder sett, selv om det er noen teorier som ikke kan bevises i vanlige aksiomsystemer for settteori. Samtidsarbeid i grunnlaget for matematikk fokuserer ofte på å fastslå hvilke deler av matematikken som kan formaliseres i bestemte formelle systemer (som i omvendt matematikk ) i stedet for å prøve å finne teorier der all matematikk kan utvikles.

Delfelt og omfang

The Handbook of Mathematical Logic i 1977 gjør en grov inndeling av samtidens matematiske logikk i fire områder:

  1. settteori
  2. modell teori
  3. rekursjonsteori , og
  4. bevissteori og konstruktiv matematikk (betraktet som deler av et enkelt område).

Hvert område har et tydelig fokus, selv om mange teknikker og resultater deles mellom flere områder. Grensene mellom disse feltene, og linjene som skiller matematisk logikk og andre matematikkfelt, er ikke alltid skarpe. Gödels ufullstendighetssetning markerer ikke bare en milepæl innen rekursjonsteori og bevissteori, men har også ført til Löbs teorem i modal logikk. Fremgangsmåten for å tvinge anvendes i mengdelære, modell teori, og rekursjon teori, så vel som i studiet av intuitionistic matematikk.

Det matematiske feltet kategoriteori bruker mange formelle aksiomatiske metoder, og inkluderer studiet av kategorisk logikk , men kategoriteori regnes vanligvis ikke som et underfelt for matematisk logikk. På grunn av sin anvendelighet i forskjellige matematikkfelt, har matematikere inkludert Saunders Mac Lane foreslått kategoriteori som et grunnleggende system for matematikk, uavhengig av settteori. Disse fundamentene bruker toposer , som ligner generaliserte modeller av settteori som kan bruke klassisk eller ikke -klassisk logikk.

Historie

Matematisk logikk dukket opp på midten av 1800-tallet som et underfelt for matematikk, noe som gjenspeiler sammensmeltningen av to tradisjoner: formell filosofisk logikk og matematikk. "Matematisk logikk, også kalt 'logistisk', 'symbolisk logikk', ' logikkens algebra ', og mer nylig bare 'formell logikk', er settet med logiske teorier som ble utdypet i løpet av det siste [nittende] århundre ved hjelp av en kunstig notasjon og en streng deduktiv metode. " Før denne fremveksten ble logikk studert med retorikk , med beregninger , gjennom syllogismen og med filosofi . Første halvdel av 1900 -tallet så en eksplosjon av grunnleggende resultater, ledsaget av kraftig debatt om grunnlaget for matematikk.

Tidlig historie

Ytterligere informasjon: Logikkens historie

Teorier om logikk ble utviklet i mange kulturer i historien, inkludert Kina , India , Hellas og den islamske verden . Greske metoder, spesielt aristotelisk logikk (eller begrepet logikk) som den ble funnet i Organon , fant bred anvendelse og aksept i vestlig vitenskap og matematikk i årtusener. De stoikerne , spesielt Chrysippus , begynte utviklingen av predikatlogikk . I Europa fra 1700-tallet hadde forsøk på å behandle den formelle logikkens operasjoner på en symbolsk eller algebraisk måte blitt utført av filosofiske matematikere, inkludert Leibniz og Lambert , men deres arbeid forble isolert og lite kjent.

1800 -tallet

I midten av det nittende århundre presenterte George Boole og deretter Augustus De Morgan systematiske matematiske behandlinger av logikk. Arbeidet deres, som bygger på arbeid av algebraister som George Peacock , utvidet den tradisjonelle aristoteliske logikklæren til et tilstrekkelig rammeverk for å studere grunnlaget for matematikk . Charles Sanders Peirce bygde senere på arbeidet til Boole for å utvikle et logisk system for relasjoner og kvantifiseringer, som han publiserte i flere artikler fra 1870 til 1885.

Gottlob Frege presenterte en uavhengig utvikling av logikk med kvantifiseringer i hans Begriffsschrift , utgitt i 1879, et verk som generelt anses å markere et vendepunkt i logikkens historie. Freges arbeid forble imidlertid uklart til Bertrand Russell begynte å promotere det nær århundreskiftet. Den todimensjonale notasjonen Frege utviklet ble aldri bredt vedtatt og er ubrukt i samtidige tekster.

Fra 1890 til 1905 ga Ernst Schröder ut Vorlesungen über die Algebra der Logik i tre bind. Dette arbeidet oppsummerte og utvidet arbeidet til Boole, De Morgan og Peirce, og var en omfattende referanse til symbolsk logikk slik den ble forstått på slutten av 1800 -tallet.

Grunnleggende teorier

Bekymringer om at matematikk ikke hadde blitt bygget på et skikkelig grunnlag, førte til utviklingen av aksiomatiske systemer for grunnleggende matematikkområder som aritmetikk, analyse og geometri.

I logikken refererer begrepet aritmetikk til teorien om de naturlige tallene . Giuseppe Peano publiserte et sett med aksiomer for aritmetikk som kom til å bære navnet hans ( Peano axioms ), ved å bruke en variasjon av det logiske systemet til Boole og Schröder, men legge til kvantifiseringer. Peano var ikke klar over Freges arbeid på den tiden. Omtrent samtidig viste Richard Dedekind at de naturlige tallene er unikt preget av deres induksjonsegenskaper . Dedekind foreslo en annen karakterisering, som manglet den formelle logiske karakteren til Peanos aksiomer. Dedekinds arbeid viste seg imidlertid teoremer utilgjengelige i Peanos system, inkludert særegenheten til settet med naturlige tall (opptil isomorfisme) og de rekursive definisjonene av addisjon og multiplikasjon fra etterfølgerfunksjonen og matematisk induksjon.

På midten av 1800-tallet ble feil i Euklides aksiomer for geometri kjent. I tillegg til det parallelle postulatets uavhengighet , etablert av Nikolai Lobachevsky i 1826, oppdaget matematikere at visse teorier som ble tatt for gitt av Euklid faktisk ikke var bevisbare fra aksiomene hans. Blant disse er teoremet om at en linje inneholder minst to punkter, eller at sirkler med samme radius hvis sentre er atskilt med den radius må krysse hverandre. Hilbert utviklet et komplett sett med aksiomer for geometri , basert på tidligere arbeid av Pasch. Suksessen med aksiomatiserende geometri motiverte Hilbert til å søke fullstendige aksiomatiseringer av andre matematikkområder, for eksempel de naturlige tallene og den virkelige linjen . Dette skulle vise seg å være et stort forskningsområde i første halvdel av 1900 -tallet.

På 1800 -tallet ble det store fremskritt innen teorien om reell analyse , inkludert teorier om konvergens av funksjoner og Fourier -serier . Matematikere som Karl Weierstrass begynte å konstruere funksjoner som strekker seg intuisjon, for eksempel ingensteds-differensierbare kontinuerlige funksjoner . Tidligere forestillinger om en funksjon som regel for beregning, eller en jevn graf, var ikke lenger tilstrekkelige. Weierstrass begynte å gå inn for aritmetisering av analyse , som forsøkte å aksiomatisere analyse ved hjelp av egenskapene til de naturlige tallene. Den moderne (ε, δ) -definisjonen av grense- og kontinuerlige funksjoner ble allerede utviklet av Bolzano i 1817, men forble relativt ukjent. Cauchy i 1821 definerte kontinuitet når det gjelder uendelig størrelse (se Cours d'Analyse, side 34). I 1858 foreslo Dedekind en definisjon av de reelle tallene når det gjelder Dedekind -kutt av rasjonelle tall, en definisjon som fremdeles brukes i samtidige tekster.

Georg Cantor utviklet de grunnleggende begrepene om uendelig settteori. Hans tidlige resultater utviklet teorien om kardinalitet og beviste at realene og de naturlige tallene har forskjellige kardinaliteter. I løpet av de neste tjue årene utviklet Cantor en teori om transfinite tall i en serie publikasjoner. I 1891 publiserte han et nytt bevis på utalligheten av de reelle tallene som introduserte det diagonale argumentet , og brukte denne metoden for å bevise Cantors teorem om at ingen sett kan ha samme kardinalitet som dens powerset . Cantor mente at hvert sett kunne være godt bestilt , men klarte ikke å fremlegge bevis for dette resultatet, og etterlot det som et åpent problem i 1895.

Det 20. århundre

I de tidlige tiårene av 1900 -tallet var hovedområdet for studiet settteori og formell logikk. Oppdagelsen av paradokser i uformell settteori fikk noen til å lure på om matematikken i seg selv er inkonsekvent, og å lete etter bevis på konsistens.

I 1900 stilte Hilbert en berømt liste over 23 problemer for det neste århundret. De to første av disse skulle løse kontinuumhypotesen og bevise konsistensen i henholdsvis elementær aritmetikk; den tiende skulle produsere en metode som kunne avgjøre om en multivariat polynomligning over heltallene har en løsning. Etterfølgende arbeid med å løse disse problemene formet retningen til matematisk logikk, det samme gjorde forsøket på å løse Hilberts Entscheidungsproblem , som ble stilt i 1928. Dette problemet ba om en prosedyre som ville avgjøre, gitt en formalisert matematisk uttalelse, om utsagnet er sant eller usant.

Settteori og paradokser

Ernst Zermelo ga et bevis på at hvert sett kunne være godt bestilt , et resultat Georg Cantor ikke hadde klart å oppnå. For å oppnå bevis, Zermelo introduserte aksiom valg , som trakk opphetet debatt og forskning blant matematikere og pionerene innen mengdelære. Den umiddelbare kritikken av metoden førte til at Zermelo publiserte en andre utstilling av resultatet hans, og tok direkte opp kritikk av beviset hans. Denne oppgaven førte til generell aksept av aksiomet for valg i matematikkmiljøet.

Skepsis om valgaksiomet ble forsterket av nylig oppdagede paradokser i naiv settteori . Cesare Burali-Forti var den første som uttalte et paradoks: Burali-Forti-paradokset viser at samlingen av alle ordinære tall ikke kan danne et sett. Kort tid etter oppdaget Bertrand Russell Russells paradoks i 1901, og Jules Richard oppdaget Richards paradoks .

Zermelo ga det første settet med aksiomer for settteori. Disse aksiomene, sammen med det ekstra erstatningsaksiomet som ble foreslått av Abraham Fraenkel , kalles nå Zermelo - Fraenkel settteori (ZF). Zermelos aksiomer inkorporerte prinsippet om størrelsesbegrensning for å unngå Russells paradoks.

I 1910 ble det første bindet av Principia Mathematica av Russell og Alfred North Whitehead utgitt. Dette sentrale arbeidet utviklet teorien om funksjoner og kardinalitet i et helt formelt rammeverk for typeteori , som Russell og Whitehead utviklet i et forsøk på å unngå paradokser. Principia Mathematica regnes som et av de mest innflytelsesrike verkene på 1900 -tallet, selv om rammene for typeteori ikke viste seg å være populære som en grunnleggende teori for matematikk.

Fraenkel beviste at valgaksjonen ikke kan bevises ut fra aksiomene til Zermelos settteori med urelementer . Senere arbeid av Paul Cohen viste at tillegg av urelements ikke er nødvendig, og valgfrie aksiom er ikke beviselig i ZF. Cohens bevis utviklet metoden for å tvinge , som nå er et viktig verktøy for å etablere uavhengighetsresultater i settteori.

Symbolisk logikk

Leopold Löwenheim og Thoralf Skolem oppnådde Löwenheim-Skolem teoremet , som sier at første ordens logikk ikke kan kontrollere kardinalitetene i uendelige strukturer. Skolem innså at denne teoremet ville gjelde for førsteordens formaliseringer av settteori, og at det innebærer at enhver slik formalisering har en tellbar modell . Dette kontraintuitive faktum ble kjent som Skolems paradoks .

I sin doktorgradsavhandling beviste Kurt Gödel fullstendighetsteoremet , som etablerer en samsvar mellom syntaks og semantikk i første ordens logikk. Gödel brukte fullstendighetsteoremet for å bevise kompakthetsteoremet , og demonstrerte den endelige karakteren av første ordens logiske konsekvens . Disse resultatene bidro til å etablere førsteordens logikk som den dominerende logikken som ble brukt av matematikere.

I 1931 publiserte Gödel On Formally Undecidable Propositions of Principia Mathematica and Related Systems , som beviste ufullstendigheten (i en annen betydning av ordet) av alle tilstrekkelig sterke, effektive førsteordens teorier. Dette resultatet, kjent som Gödels ufullstendighetsteorem , etablerer alvorlige begrensninger på aksiomatiske grunnlag for matematikk, og slår et sterkt slag mot Hilberts program. Det viste umuligheten av å gi et konsistensbevis for aritmetikk innenfor enhver formell teori om aritmetikk. Hilbert erkjente imidlertid ikke viktigheten av ufullstendighetssetemet på en stund.

Godels teorem viser at et konsistensbevis for et tilstrekkelig sterkt, effektivt aksiomasystem ikke kan oppnås i selve systemet, hvis systemet er konsistent, eller i noe svakere system. Dette åpner muligheten for konsistensbevis som ikke kan formaliseres i systemet de anser. Gentzen beviste konsistensen i aritmetikk ved å bruke et finitistisk system sammen med et prinsipp om transfinitt induksjon . Gentzens resultat introduserte ideene om kutteliminering og bevisteoretiske ordinaler , som ble viktige verktøy i bevisteorien. Gödel ga et annet konsistensbevis, noe som reduserer konsistensen mellom klassisk aritmetikk og intuisjonistisk aritmetikk i høyere typer.

Den første læreboken om symbolisk logikk for lekmannen ble skrevet av Lewis Carroll, forfatter av Alice in Wonderland, i 1896.

Begynnelsen på de andre grenene

Alfred Tarski utviklet det grunnleggende i modellteori .

Fra 1935 samarbeidet en gruppe fremtredende matematikere under pseudonymet Nicolas Bourbaki for å publisere Éléments de mathématique , en serie encyklopediske matematikktekster. Disse tekstene, skrevet i en streng og aksiomatisk stil, understreket streng presentasjon og sett-teoretiske grunnlag. Terminologi som ble laget av disse tekstene, for eksempel ordene bijeksjon , injeksjon og innsigelse , og de teoretiske grunnlagene tekstene brukte, ble mye brukt gjennom matematikk.

Studiet av beregbarhet ble kjent som rekursjonsteori eller beregningsteori , fordi tidlige formaliseringer av Gödel og Kleene stolte på rekursive definisjoner av funksjoner. Da disse definisjonene ble vist å svare til Turings formalisering som involverte Turing -maskiner , ble det klart at et nytt konsept - den beregningsbare funksjonen - var blitt oppdaget, og at denne definisjonen var robust nok til å innrømme mange uavhengige karakteriseringer. I arbeidet med ufullstendighetsteorene i 1931 manglet Gödel et strengt konsept om et effektivt formelt system; han innså umiddelbart at de nye definisjonene av beregningsbarhet kunne brukes til dette formålet, slik at han kunne angi ufullstendighetssetningene i generalitet som bare kunne antydes i originaloppgaven.

Tallrike resultater i rekursjonsteori ble oppnådd på 1940 -tallet av Stephen Cole Kleene og Emil Leon Post . Kleene introduserte begrepene relativ beregningsbarhet, forutskygget av Turing, og det aritmetiske hierarkiet . Kleene generaliserte senere rekursjonsteori til funksjoner av høyere orden. Kleene og Georg Kreisel studerte formelle versjoner av intuisjonistisk matematikk, spesielt i sammenheng med bevissteori.

Formelle logiske systemer

I kjernen handler matematisk logikk om matematiske begreper uttrykt ved bruk av formelle logiske systemer . Disse systemene, selv om de er forskjellige i mange detaljer, deler den felles egenskapen å bare vurdere uttrykk på et fast formelt språk. Systemene for proposisjonell logikk og første ordens logikk er de mest utbredte i dag, på grunn av deres anvendelighet på grunnlaget for matematikk og på grunn av deres ønskelige bevisteoretiske egenskaper. Sterkere klassisk logikk som andreordens logikk eller uendelig logikk studeres også, sammen med ikke-klassiske logikker som intuisjonistisk logikk .

Første ordens logikk

Hovedartikkel: Første ordens logikk

Førsteordens logikk er et spesielt formelt logikksystem . Dens syntaks innebærer bare begrensede uttrykk som velformede formler , mens dens semantikk er karakterisert ved den begrensning av alle quantifiers til en fast domene av tale .

Tidlige resultater fra formell logikk etablerte begrensninger i førsteordens logikk. Den Löwenheim-Skolem teorem (1919) har vist at dersom et sett av setninger i et tellbart første-ordens språket har et uendelig modell da det har minst en modell av hvert uendelig cardinality. Dette viser at det er umulig for et sett med førsteordens aksiomer å karakterisere de naturlige tallene, de reelle tallene eller noen annen uendelig struktur opp til isomorfisme . Siden målet med tidlige grunnstudier var å produsere aksiomatiske teorier for alle deler av matematikken, var denne begrensningen spesielt sterk.

Godels fullstendighetsteorem etablerte ekvivalensen mellom semantiske og syntaktiske definisjoner av logisk konsekvens i førsteordens logikk. Det viser at hvis en bestemt setning er sann i hver modell som tilfredsstiller et bestemt sett med aksiomer, må det være en endelig fradrag av setningen fra aksiomene. Den kompakte teorem dukket først opp som et lemma i Gödel bevis av fullstendighet teorem, og det tok mange år før Logicians grep sin betydning og begynte å bruke det rutinemessig. Den sier at et sett setninger har en modell hvis og bare hvis hver begrenset delmengde har en modell, eller med andre ord at et inkonsekvent sett med formler må ha en begrenset inkonsekvent delmengde. Teoremene om fullstendighet og kompakthet gir mulighet for sofistikert analyse av logiske konsekvenser i førsteordens logikk og utvikling av modellteori , og de er en sentral årsak til fremtredelsen av førsteordens logikk i matematikk.

Gödels ufullstendighetsteoremer etablerer ytterligere grenser for førsteordens aksiomatiseringer. Den første ufullstendighetssetningen sier at for ethvert konsekvent, effektivt gitt (definert nedenfor) logisk system som er i stand til å tolke aritmetikk, eksisterer det en uttalelse som er sann (i den forstand at den holder for de naturlige tallene), men som ikke kan bevises innenfor den logiske system (og som faktisk kan mislykkes i noen ikke-standardiserte regnemodeller som kan stemme overens med det logiske systemet). For eksempel, i alle logiske systemer som er i stand til å uttrykke Peano -aksiomene , gjelder Gödel -setningen for de naturlige tallene, men kan ikke bevises.

Her sies det at et logisk system blir gitt effektivt hvis det er mulig, gitt hvilken som helst formel på systemets språk, om formelen er et aksiom, og et som kan uttrykke Peano -aksiomene kalles "tilstrekkelig sterk". Når den brukes på førsteordens logikk, innebærer den første ufullstendighetssetningen at enhver tilstrekkelig sterk, konsistent, effektiv førsteordens teori har modeller som ikke er elementært ekvivalente , en sterkere begrensning enn den som ble fastsatt av Löwenheim-Skolem-setningen. Den andre ufullstendighetssetningen sier at ingen tilstrekkelig sterke, konsekvente, effektive aksiomer for aritmetikk kan bevise sin egen konsistens, noe som har blitt tolket for å vise at Hilberts program ikke kan nås.

Andre klassiske logikker

Mange logikker i tillegg til førsteordens logikk studeres. Disse inkluderer uendelige logikker , som gjør det mulig for formler å gi uendelig mye informasjon, og høyere ordens logikk , som inkluderer en del av settteorien direkte i semantikken.

Den mest godt studerte uendelige logikken er . I denne logikken kan kvantifiseringer bare være nestet til begrensede dybder, som i første ordens logikk, men formler kan ha begrensede eller uttallige uendelige konjunksjoner og disjunksjoner i dem. Således er det for eksempel mulig å si at et objekt er et helt tall ved hjelp av en formel som f.eks

Logikk av høyere orden tillater kvantifisering ikke bare av elementer i diskursområdet , men delsett av diskursområdet, sett med slike undergrupper og andre objekter av høyere type. Semantikken er definert slik at i stedet for å ha et eget domene for hver kvantifiser av høyere type å strekke seg over, vil kvantifiseringene i stedet spenne over alle objekter av den aktuelle typen. Logikkene som ble studert før utviklingen av førsteordens logikk, for eksempel Freges logikk, hadde lignende sett-teoretiske aspekter. Selv om logikk av høyere orden er mer uttrykksfulle og tillater fullstendige aksiomatiseringer av strukturer som de naturlige tallene, tilfredsstiller de ikke analoger av fullstendighets- og kompakthetsteorene fra førsteordens logikk, og er dermed mindre utsatt for bevisteoretisk analyse.

En annen type logikk er fast punkt logiske ssom tillaterinduktive definisjoner, slik som en skriver forprimitive rekursive funksjoner.

Man kan formelt definere en forlengelse av førsteordens logikk-en forestilling som omfatter alle logikker i denne delen fordi de oppfører seg som førsteordens logikk på visse grunnleggende måter, men ikke omfatter alle logikker generelt, f.eks. Den omfatter ikke intuisjonistisk, modal eller uklar logikk .

Lindströms teorem innebærer at den eneste utvidelsen av førsteordens logikk som tilfredsstiller både kompakthetsteoremet og det nedadgående Löwenheim – Skolem-teoremet er førsteordens logikk.

Uklassisk og modal logikk

Hovedartikkel: Ikke-klassisk logikk

Modal logikk inkluderer flere modale operatører, for eksempel en operator som sier at en bestemt formel ikke bare er sann, men nødvendigvis sann. Selv om modal logikk ikke ofte brukes til å aksiomatisere matematikk, har den blitt brukt til å studere egenskapene til første ordens bevisbarhet og settteoretisk tvang.

Intuisjonistisk logikk ble utviklet av Heyting for å studere Brouwers program for intuisjonisme, der Brouwer selv unngikk formalisering. Intuisjonistisk logikk inkluderer spesifikt ikke loven i den ekskluderte midten , som sier at hver setning enten er sann eller at dens negasjon er sann. Kleenes arbeid med bevissteorien om intuisjonistisk logikk viste at konstruktiv informasjon kan gjenvinnes fra intuisjonistiske bevis. For eksempel kan enhver beviselig totalfunksjon i intuisjonistisk aritmetikk beregnes ; dette er ikke sant i klassiske teorier om regning som Peano -aritmetikk .

Algebraisk logikk

Algebraisk logikk bruker metodene for abstrakt algebra for å studere semantikken i formell logikk. Et grunnleggende eksempel er bruk av boolske algebraer for å representere sannhetsverdier i klassisk proposisjonell logikk, og bruk av Heyting -algebra for å representere sannhetsverdier i intuisjonistisk proposisjonell logikk. Sterkere logikk, for eksempel førsteordens logikk og høyere ordens logikk, studeres ved hjelp av mer kompliserte algebraiske strukturer som sylindriske algebraer .

Settteori

Hovedartikkel: Settteori

Settteori er studiet av sett , som er abstrakte samlinger av objekter. Mange av de grunnleggende forestillingene, for eksempel ordinalt og kardinalnummer, ble utviklet uformelt av Cantor før formelle aksiomatiseringer av settteori ble utviklet. Den første slike aksiomatiseringen , på grunn av Zermelo, ble utvidet litt til å bli Zermelo - Fraenkel settteori (ZF), som nå er den mest brukte grunnleggende teorien for matematikk.

Andre formaliseringer av settteori er blitt foreslått, inkludert von Neumann - Bernays - Gödel settteori (NBG), Morse - Kelley settteori (MK) og New Foundations (NF). Av disse er ZF, NBG og MK like når det gjelder å beskrive et kumulativt hierarki av sett. New Foundations tar en annen tilnærming; det tillater objekter som settet til alle settene på bekostning av begrensninger på aksiomene for eksistens. Systemet med Kripke - Platek settteori er nært knyttet til generalisert rekursjonsteori.

To kjente utsagn i settteorien er valgets aksiom og kontinuumhypotesen . Valgaksjonen, først oppgitt av Zermelo, ble bevist uavhengig av ZF av Fraenkel, men har blitt allment akseptert av matematikere. Den sier at gitt en samling av sett som ikke er unntatt, er det et enkelt sett C som inneholder nøyaktig ett element fra hvert sett i samlingen. Settet C sies å "velge" ett element fra hvert sett i samlingen. Selv om muligheten til å gjøre et slikt valg anses som åpenbar av noen, siden hvert sett i samlingen er ikke -fritatt, gjør mangelen på en generell, konkret regel som valget kan gjøres, aksiomet ikke -konstruktivt. Stefan Banach og Alfred Tarski viste at valgfritt aksiom kan brukes til å dekomponere en solid ball til et begrenset antall biter som deretter kan omorganiseres uten skalering for å lage to solide baller av den opprinnelige størrelsen. Denne teoremet, kjent som Banach – Tarski -paradokset , er et av mange kontraintuitive resultater av valgaksiomet.

Kontinuumhypotesen, først foreslått som en formodning av Cantor, ble oppført av David Hilbert som et av hans 23 problemer i 1900. Gödel viste at kontinuumhypotesen ikke kan motbevises fra aksiomene til Zermelo - Fraenkel -teorien (med eller uten aksiomet av valg), ved å utvikle det konstruerbare universet av settteori der kontinuumhypotesen må holde. I 1963 viste Paul Cohen at kontinuumhypotesen ikke kan bevises fra aksiomene til Zermelo - Fraenkel settteori. Dette uavhengighetsresultatet løste imidlertid ikke Hilberts spørsmål helt, ettersom det er mulig at nye aksiomer for settteori kunne løse hypotesen. Nylige arbeider i denne retning har blitt utført av W. Hugh Woodin , selv om viktigheten ennå ikke er klar.

Samtidsforskning innen settteori inkluderer studier av store kardinaler og determinat . Store kardinaler er kardinalnumre med spesielle egenskaper så sterke at eksistensen av slike kardinaler ikke kan bevises i ZFC. Eksistensen av den minste store kardinalen som vanligvis studeres, en utilgjengelig kardinal , innebærer allerede konsistensen av ZFC. Til tross for at store kardinaler har ekstremt høy kardinalitet , har deres eksistens mange konsekvenser for strukturen til den virkelige linjen. Determinacy refererer til den mulige eksistensen av vinnende strategier for visse to-spillerspill (spillene sies å være bestemt ). Eksistensen av disse strategiene innebærer strukturelle egenskaper til den virkelige linjen og andre polske mellomrom .

Modellteori

Hovedartikkel: Modellteori

Modellteori studerer modellene for forskjellige formelle teorier. Her er en teori et sett med formler i en bestemt formell logikk og signatur , mens en modell er en struktur som gir en konkret tolkning av teorien. Modellteori er nært knyttet til universell algebra og algebraisk geometri , selv om metodene for modellteori fokuserer mer på logiske hensyn enn disse feltene.

Settet av alle modeller av en bestemt teori kalles en elementær klasse ; klassisk modellteori søker å bestemme egenskapene til modeller i en bestemt elementær klasse, eller avgjøre om visse klasser av strukturer danner elementære klasser.

Metoden for kvantifiseringseliminering kan brukes for å vise at definerbare sett, spesielt teorier, ikke kan være for kompliserte. Tarski etablerte kvantifiseringseliminering for reelle lukkede felt , et resultat som også viser teorien om feltet med reelle tall, kan avgjøres . Han bemerket også at metodene hans var like anvendelige på algebraisk lukkede felt med vilkårlig karakteristikk. Et moderne underfelt som utvikler seg fra dette er opptatt av o-minimale strukturer .

Morleys kategorisitetsteorem , bevist av Michael D. Morley , sier at hvis en førsteordens teori i et tallbart språk er kategorisk i noen utallige kardinaliteter, dvs. alle modeller av denne kardinaliteten er isomorfe, så er den kategorisk i alle utallige kardinaliteter.

En triviell konsekvens av kontinuumhypotesen er at en komplett teori med mindre enn kontinuum mange ikke -isomorfe tellbare modeller bare kan ha mange. Vaughts formodning , oppkalt etter Robert Lawson Vaught , sier at dette er sant selv uavhengig av kontinuumhypotesen. Mange spesielle tilfeller av denne formodningen har blitt fastslått.

Rekursjonsteori

Hovedartikkel: Rekursjonsteori

Rekursjonsteori , også kalt beregningsteori , studerer egenskapene til beregningsbare funksjoner og Turing -gradene, som deler de uberegnelige funksjonene i sett som har samme nivå av ukomputerbarhet. Rekursjonsteori inkluderer også studiet av generalisert beregning og definisjon. Rekursjonsteorien vokste fra arbeidet til Rózsa Péter , Alonzo Church og Alan Turing på 1930 -tallet, som ble sterkt utvidet av Kleene og Post på 1940 -tallet.

Klassisk rekursjonsteori fokuserer på beregning av funksjoner fra de naturlige tallene til de naturlige tallene. De grunnleggende resultatene etablerer en robust, kanonisk klasse med databehandlingsfunksjoner med mange uavhengige, likeverdige karakteriseringer ved bruk av Turing -maskiner , λ -beregning og andre systemer. Mer avanserte resultater gjelder strukturen til Turing -gradene og gitteret til rekursivt tallrike sett .

Generalisert rekursjonsteori utvider ideene om rekursjonsteori til beregninger som ikke lenger nødvendigvis er begrensede. Det inkluderer studiet av beregningsbarhet i høyere typer samt områder som hyperaritmetisk teori og α-rekursjonsteori .

Samtidsforskning innen rekursjonsteori inkluderer studier av applikasjoner som algoritmisk tilfeldighet , beregningsbar modellteori og omvendt matematikk , samt nye resultater i ren rekursjonsteori.

Algoritmisk uløselige problemer

Et viktig underfelt av rekursjonsteori studerer algoritmisk uløselighet; et beslutningsproblem eller funksjonsproblem er algoritmisk uløselig hvis det ikke er noen mulig beregningsbar algoritme som returnerer riktig svar for alle juridiske innganger til problemet. De første resultatene om uløselighet, oppnådd uavhengig av Church and Turing i 1936, viste at Entscheidungsproblemet er algoritmisk uløselig. Turing beviste dette ved å fastslå uløseligheten av stoppproblemet , et resultat med vidtrekkende implikasjoner både i rekursjonsteori og informatikk.

Det er mange kjente eksempler på ubestemte problemer fra vanlig matematikk. Det ord problem for gruppene ble bevist ved hjelp av algoritmer uløselige ved Pyotr Novikov i 1955 og uavhengig av W. Boone i 1959. opptatt bever problem, som er utviklet av Tibor Rado i 1962, er en annen velkjent eksempel.

Hilberts tiende problem ba om en algoritme for å avgjøre om en multivariat polynomligning med heltallskoeffisienter har en løsning i heltallene. Delvis fremgang ble gjort av Julia Robinson , Martin Davis og Hilary Putnam . Den algoritmiske uløseligheten av problemet ble bevist av Yuri Matiyasevich i 1970.

Bevissteori og konstruktiv matematikk

Hovedartikkel: Bevissteori

Bevissteori er studiet av formelle bevis i forskjellige logiske fradragssystemer. Disse bevisene er representert som formelle matematiske objekter, noe som letter analysen ved hjelp av matematiske teknikker. Flere fradragssystemer blir ofte vurdert, inkludert fradragssystemer i Hilbert-stil , systemer for naturlig fradrag og den påfølgende beregningen utviklet av Gentzen.

Studiet av konstruktiv matematikk , i sammenheng med matematisk logikk, inkluderer studier av systemer i ikke-klassisk logikk som intuisjonistisk logikk, samt studiet av predikative systemer. En tidlig forkjemper for predikativisme var Hermann Weyl , som viste at det er mulig å utvikle en stor del av reell analyse ved å bare bruke predikative metoder.

Fordi bevis er helt endelige, mens sannhet i en struktur ikke er det, er det vanlig at arbeid i konstruktiv matematikk legger vekt på bevisbarhet. Forholdet mellom bevisbarhet i klassiske (eller ikke -konstruktive) systemer og bevisbarhet i henholdsvis intuisjonistiske (eller konstruktive) systemer er av spesiell interesse. Resultater som den negative oversettelsen fra Gödel – Gentzen viser at det er mulig å bygge inn (eller oversette ) klassisk logikk til intuisjonistisk logikk, slik at noen egenskaper om intuisjonistiske bevis kan overføres tilbake til klassiske bevis.

Nyere utvikling innen bevisteori inkluderer studiet av proof mining av Ulrich Kohlenbach og studiet av bevisteoretiske ordinaler av Michael Rathjen .

applikasjoner

"Matematisk logikk har blitt brukt ikke bare på matematikk og dens grunnlag ( G. Frege , B. Russell , D. Hilbert , P. Bernays , H. Scholz , R. Carnap , S. Lesniewski , T. Skolem ), men også til fysikk (R. Carnap, A. Dittrich, B. Russell, CE Shannon , AN Whitehead , H. Reichenbach , P. Fevrier), til biologi ( JH Woodger , A. Tarski ), til psykologi ( FB Fitch , CG Hempel ) , til lov og moral ( K. Menger , U. Klug, P. Oppenheim), til økonomi ( J. Neumann , O. Morgenstern ), til praktiske spørsmål ( EC Berkeley , E. Stamm) og til og med til metafysikk (J. [Jan] Salamucha, H. Scholz, JM Bochenski ). Dets anvendelser på logikkens historie har vist seg ekstremt fruktbare ( J. Lukasiewicz , H. Scholz, B. Mates , A. Becker, E. Moody , J. Salamucha, K . Duerr, Z. Jordan, P. Boehner , JM Bochenski, S. [Stanislaw] T. Schayer, D. Ingalls ). " "Det er også søkt om teologi (F. Drewnowski, J. Salamucha, I. Thomas)."

Forbindelser med informatikk

Hovedartikkel: Logikk i informatikk

Studiet av beregningsteori i informatikk er nært knyttet til studiet av beregningsbarhet i matematisk logikk. Det er imidlertid en forskjell i vekt. Datavitenskapere fokuserer ofte på konkrete programmeringsspråk og gjennomførbar beregningsbarhet , mens forskere i matematisk logikk ofte fokuserer på beregningsbarhet som et teoretisk konsept og på ikke -databehandling.

Teorien om semantikk i programmeringsspråk er relatert til modellteori , det samme er programverifisering (spesielt modellkontroll ). Den Curry-Howard korrespondanse mellom prøvetrykk og programmer angår bevis teori , spesielt intuitionistic logikk . Formelle beregninger som lambda calculus og kombinatorisk logikk studeres nå som idealiserte programmeringsspråk .

Datavitenskap bidrar også til matematikk ved å utvikle teknikker for automatisk kontroll eller til og med å finne bevis, for eksempel automatisert teorem -bevis og logisk programmering .

Beskrivende kompleksitetsteori relaterer logikk til beregningskompleksitet . Det første betydelige resultatet på dette området, Fagins teorem (1974) slo fast at NP nettopp er settet med språk som kan uttrykkes med setninger av eksistensiell andreordens logikk .

Grunnlaget for matematikk

Hovedartikkel: Grunnlaget for matematikk

På 1800 -tallet ble matematikere klar over logiske hull og inkonsekvenser innen sitt felt. Det ble vist at Euklides aksiomer for geometri, som hadde blitt lært i århundrer som et eksempel på den aksiomatiske metoden, var ufullstendige. Bruken av uendelige , og selve definisjonen av funksjon , ble stilt spørsmål ved analyse, ettersom patologiske eksempler som Weierstrass 'ingensteds- differensierbare kontinuerlige funksjon ble oppdaget.

Cantors studie av vilkårlige uendelige sett vakte også kritikk. Leopold Kronecker uttalte berømt "Gud skapte heltallene; alt annet er menneskets verk", og godkjente en tilbakevending til studiet av endelige, konkrete objekter i matematikk. Selv om Kroneckers argument ble videreført av konstruktivister på 1900 -tallet, avviste det matematiske samfunnet som helhet dem. David Hilbert argumenterte for studiet av det uendelige og sa "Ingen skal drive oss ut av paradiset som Cantor har skapt."

Matematikere begynte å søke etter aksiomsystemer som kunne brukes til å formalisere store deler av matematikken. I tillegg til å fjerne tvetydighet fra tidligere naive begreper som funksjon, var det håp om at denne aksiomatiseringen ville muliggjøre konsistensbevis. På 1800 -tallet var hovedmetoden for å bevise konsistensen av et sett med aksiomer å gi en modell for det. Således kan for eksempel ikke-euklidisk geometri bevises konsistent ved å definere punkt for å bety et punkt på en fast sfære og linje for å bety en stor sirkel på sfæren. Den resulterende strukturen, en modell for elliptisk geometri , tilfredsstiller aksiomene til plan geometri bortsett fra parallellpostulatet.

Med utviklingen av formell logikk spurte Hilbert om det ville være mulig å bevise at et aksiomsystem er konsistent ved å analysere strukturen til mulige bevis i systemet, og vise gjennom denne analysen at det er umulig å bevise en motsetning. Denne ideen førte til studiet av bevissteori . Videre foreslo Hilbert at analysen skulle være helt konkret, ved å bruke begrepet finitary for å referere til metodene han ville tillate, men ikke nøyaktig definere dem. Dette prosjektet, kjent som Hilberts program , ble alvorlig påvirket av Gödels ufullstendighetsteoremer, som viser at konsistensen av formelle teorier om aritmetikk ikke kan fastslås ved hjelp av metoder som kan formaliseres i disse teoriene. Gentzen viste at det er mulig å produsere et bevis på at aritmetikk er konsistent i et finitært system som er forsterket med aksiomer for transfinitt induksjon , og teknikkene han utviklet for å gjøre det var sentrale i bevissteorien.

En annen tråd i historien til grunnlaget for matematikk involverer ikke -klassisk logikk og konstruktiv matematikk . Studiet av konstruktiv matematikk inkluderer mange forskjellige programmer med forskjellige definisjoner av konstruktiv . I den mest imøtekommende enden kalles bevis i ZF -settteori som ikke bruker valgaksiomet, konstruktive av mange matematikere. Mer begrensede versjoner av konstruktivisme begrenser seg til naturlige tall , tallteoretiske funksjoner og sett med naturlige tall (som kan brukes til å representere reelle tall, noe som letter studiet av matematisk analyse ). En vanlig idé er at et konkret middel for å beregne funksjonens verdier må være kjent før selve funksjonen kan sies å eksistere.

I begynnelsen av det 20. århundre, Luitzen Egbertus Jan Brouwer stiftet intuisjonisme som en del av filosofien i matematikk . Denne filosofien, som var dårlig forstått i begynnelsen, uttalte at for at en matematisk uttalelse skal være tro mot en matematiker, må denne personen kunne intuitere utsagnet, for ikke bare å tro på sannheten, men forstå årsaken til dens sannhet. En konsekvens av denne definisjonen av sannhet var avvisningen av loven om den ekskluderte midten , for det er utsagn som ifølge Brouwer ikke kunne hevdes å være sanne, mens deres negasjoner heller ikke kunne påstås å være sanne. Brouwers filosofi var innflytelsesrik og årsaken til bitre tvister blant fremtredende matematikere. Senere ville Kleene og Kreisel studere formaliserte versjoner av intuisjonistisk logikk (Brouwer avviste formalisering, og presenterte arbeidet sitt i uformalisert naturlig språk). Med ankomsten av BHK -tolkningen og Kripke -modellene ble intuisjonismen lettere å forene med klassisk matematikk .

Se også

Merknader

Referanser

Grunntekster

  • Walicki, Michał (2011). Introduksjon til matematisk logikk . Singapore : World Scientific Publishing . ISBN 9789814343879.
  • Boolos, George ; Burgess, John; Jeffrey, Richard (2002). Beregnbarhet og logikk (4. utg.). Cambridge University Press . ISBN 9780521007580.
  • Crossley, JN; Ash, CJ; Brickhill, CJ; Stillwell, JC; Williams, NH (1972). Hva er matematisk logikk? . London, Oxford, New York City: Oxford University Press . ISBN 9780198880875. Zbl  0251.02001 .
  • Enderton, Herbert (2001). En matematisk introduksjon til logikk (2. utg.). Boston MA: Academic Press . ISBN 978-0-12-238452-3.
  • Fisher, Alec (1982). Formell tallteori og beregning: En arbeidsbok . (egnet som et første kurs for uavhengig studie) (1. utg.). Oxford University Press. ISBN 978-0-19-853188-3.
  • Hamilton, AG (1988). Logic for Mathematicians (2. utg.). Cambridge University Press. ISBN 978-0-521-36865-0.
  • Ebbinghaus, H.-D .; Flum, J .; Thomas, W. (1994). Matematisk logikk (2. utg.). New York City : Springer . ISBN 9780387942582.
  • Katz, Robert (1964). Aksiomatisk analyse . Boston MA: DC Heath and Company .
  • Mendelson, Elliott (1997). Introduksjon til matematisk logikk (4. utg.). London: Chapman & Hall . ISBN 978-0-412-80830-2.
  • Rautenberg, Wolfgang (2010). En kortfattet introduksjon til matematisk logikk (3. utg.). New York City : Springer . doi : 10.1007/978-1-4419-1221-3 . ISBN 9781441912206.
  • Schwichtenberg, Helmut (2003–2004). Matematisk logikk (PDF) . München : Mathematisches Institut der Universität München . Hentet 2016-02-24 .
  • Shawn Hedman, Et første kurs i logikk: en introduksjon til modellteori, bevissteori, beregning og kompleksitet , Oxford University Press , 2004, ISBN  0-19-852981-3 . Dekker logikk i nær forbindelse med beregningsteori og kompleksitetsteori
  • van Dalen, Dirk (2013). Logikk og struktur . Universitext. Berlin: Springer . doi : 10.1007/978-1-4471-4558-5 . ISBN 978-1-4471-4557-8.

Utdannet tekster

Forskningsartikler, monografier, tekster og undersøkelser

Klassiske artikler, tekster og samlinger

Bochenski, Jozef Maria, red. (1959). A Precis of Mathematical Logic . Synthese Library, bind. 1. Oversatt av Otto Bird. Dordrecht : Springer . doi : 10.1007/978-94-017-0592-9 . ISBN 9789048183296.

Cantor, Georg (1874). "Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen" (PDF) . Journal für die Reine und Angewandte Mathematik . 1874 (77): 258–262. doi : 10.1515/crll.1874.77.258 . S2CID  199545885 . Carroll, Lewis (1896). Symbolisk logikk . Kessinger Legacy Reprints. ISBN 9781163444955.

Soare, Robert Irving (22. desember 2011). "Beregnbarhetsteori og applikasjoner: The Art of Classical Computability" (PDF) . Institutt for matematikk . University of Chicago . Hentet 23. august 2017 . Swineshead, Richard (1498). Beregninger Suiseth Anglici (på litauisk). Papie: Per Franciscum Gyrardengum.

Eksterne linker