Wiskundige logica

Van Wikipedia, de gratis encyclopedie
Spring naar navigatie Spring naar zoeken

Wiskundige logica , ook symbolische logica, (ook verouderde logistiek ), is een tak van de wiskunde , vooral als een methode van metathematica en een toepassing van moderne formele logica . Vaak is het weer onderverdeeld in de deelgebieden modeltheorie , bewijstheorie , verzamelingenleer en recursietheorie . Onderzoek op het gebied van wiskundige logica heeft bijgedragen aan en is gemotiveerd door de studie van de grondbeginselen van de wiskunde . Als gevolg hiervan werd het ook bekend als metathematica .

Een aspect van de studie van wiskundige logica is de studie van de expressiviteit van formele logica's en formele bewijssystemen . Een manier om de complexiteit van dergelijke systemen te meten, is te bepalen wat ze kunnen bewijzen of definiëren.

verhaal

Godzijdank Frege (1878)
Kurt Godel

De term wiskundige logica werd door Giuseppe Peano gebruikt voor symbolische logica. In de klassieke versie is dit vergelijkbaar met de logica van Aristoteles , maar is geformuleerd met behulp van symbolen in plaats van natuurlijke taal . Wiskundigen met een filosofische achtergrond, zoals Leibniz of Lambert , probeerden al vroeg de operaties van de formele logica te behandelen met een symbolische of algebraïsche benadering, maar hun werk bleef grotendeels geïsoleerd en onbekend. Halverwege de 19e eeuw presenteerden George Boole en Augustus de Morgan een systematische manier om naar logica te kijken. De traditionele aristotelische doctrine van logica werd hervormd en voltooid, en het werd een geschikt instrument voor het bestuderen van de grondslagen van de wiskunde . Het zou misleidend zijn om te beweren dat alle fundamentele controverses van 1900 tot 1925 zijn opgelost, maar de filosofie van de wiskunde is grotendeels opgehelderd door de nieuwe logica.

Terwijl de Griekse ontwikkeling van de logica grote nadruk legde op vormen van argumentatie, kan de hedendaagse wiskundige logica worden omschreven als een combinatorische studie van inhoud . Dit omvat zowel de syntactische (het onderzoek van formele tekenreeksen als zodanig) als de semantische (de toewijzing van dergelijke tekenreeksen met betekenis).

Historisch belangrijke publicaties zijn het conceptuele schrijven door Gottlob Frege , Studies in Logic [1] onder redactie van Charles Sanders Peirce , Principia Mathematica door Bertrand Russell en Alfred North Whitehead en Over formeel onbeslisbare stellingen van Principia Mathematica en aanverwante systemen I door Kurt Gödel .

formele logica

Wiskundige logica houdt zich vaak bezig met wiskundige concepten die worden uitgedrukt door middel van formele logische systemen. Het systeem van eerste-orde predikaatlogica is het meest wijdverbreid, zowel vanwege zijn toepasbaarheid op het gebied van de grondbeginselen van de wiskunde als vanwege zijn eigenschappen zoals volledigheid en correctheid . Propositionele logica , sterkere klassieke logica zoals predikatenlogica van het tweede niveau, of niet-klassieke logica zoals intuïtionistische logica worden ook onderzocht.

Deelgebieden van wiskundige logica

Het Handbook of Mathematical Logic (1977) verdeelt wiskundige logica in de volgende vier gebieden:

  • Set theorie is de studie van sets , die abstract verzamelingen van objecten zijn. Terwijl eenvoudige concepten zoals subsets vaak worden behandeld op het gebied van naïeve verzamelingenleer , werkt modern onderzoek op het gebied van axiomatische verzamelingenleer , die logische methoden gebruikt om te bepalen welke wiskundige uitspraken worden gedaan in verschillende formele theorieën, zoals de Zermelo-Fraenkel verzamelingenleer (ZFC) of New Foundations , zijn aantoonbaar.
  • Bewijs theorie is de studie van formele bewijzen en verschillende systemen van logische deductie. Bewijs wordt gepresenteerd als wiskundige objecten, zodat het kan worden onderzocht met behulp van wiskundige technieken. Frege behandelde wiskundige bewijzen en formaliseerde het begrip bewijs.
  • Modeltheorie is de studie van modellen uit formele theorieën. Het geheel van alle modellen van een bepaalde theorie wordt een " elementaire klasse " genoemd. Klassieke modeltheorie probeert de eigenschappen van modellen van een bepaalde elementaire klasse te bepalen, of bepaalde klassen van structuren elementair zijn. De methode van kwantoreliminatie wordt gebruikt om aan te tonen dat de modellen van bepaalde theorieën niet te ingewikkeld kunnen zijn.
  • Recursietheorie , ook wel berekenbaarheidstheorie genoemd, is de studie van berekenbare functies en de Turing-graden , die de niet-berekenbare functies classificeren op basis van de mate van hun niet-berekenbaarheid. Verder omvat de recursietheorie ook de studie van gegeneraliseerde voorspelbaarheid en definieerbaarheid.

De grenzen tussen deze gebieden en ook tussen wiskundige logica en andere gebieden van de wiskunde zijn niet altijd precies gedefinieerd. De onvolledigheidsstelling van Gödel is bijvoorbeeld niet alleen van het grootste belang in de recursietheorie en de bewijstheorie, maar leidde ook tot de stelling van Löb , die belangrijk is in de modale logica . De categorietheorie maakt ook gebruik van veel formele, axiomatische methoden die sterk lijken op de methoden die in de wiskundige logica worden gebruikt. Categorietheorie wordt echter meestal niet gezien als onderdeel van wiskundige logica.

Verbindingen met informatica

Er zijn veel verbanden tussen wiskundige logica en informatica . Veel pioniers in de informatica, zoals Alan Turing , hebben de discipline gevormd als wiskundigen en logici. Delen van de wiskundige logica worden behandeld op het gebied van de theoretische informatica . Met name de beschrijvende complexiteitstheorie legt een nauw verband tussen de wiskundige logica en de complexiteitstheorie die in de theoretische informatica wordt behandeld. De eindige-modeltheorie is nauw verwant aan de automatentheorie, aangezien volgens de stelling van Büchi een taal kan worden gedefinieerd in MSO iff. het is regelmatig.

Belangrijke resultaten

  • De stelling van Löwenheim-Skolem (1919) stelt dat een theorie in een aftelbare eerste- ordetaal die een oneindig model heeft, modellen heeft van elke oneindige kardinaliteit.
  • De volledigheidsstelling (1929) (von Gödel ) toonde de gelijkwaardigheid aan van semantische en syntactische gevolgtrekkingen in de klassieke predikaatlogica van het eerste niveau.
  • De onvolledigheidsstelling (1931) (von Gödel) toonde aan dat geen voldoende sterk formeel systeem zijn eigen consistentie kan bewijzen.
  • De algoritmische onoplosbaarheid van het beslissingsprobleem , onafhankelijk ontdekt door Alan Turing en Alonzo Church in 1936, toonde aan dat er geen computerprogramma is dat correct beslist of een wiskundige bewering waar is.
  • De onafhankelijkheid van de continuümhypothese van ZFC toonde aan dat zowel het bewijs als de weerlegging van de hypothese onmogelijk is. Het feit dat ZFC consistent is met de continuümhypothese, als ZFC consistent is, werd in 1940 door Gödel aangetoond. Het feit dat de ontkenning van de continuümhypothese ook consistent is met ZFC (als ZFC consistent is) werd in 1963 bewezen door Paul Cohen .
  • De algoritmische onoplosbaarheid van Hilberts tiende probleem werd in 1970 aangetoond door Yuri Matiyasevich . Hij bewees dat er geen computerprogramma is dat correct beslist of een polynoom gehele nullen heeft in meerdere variabelen met gehele coëfficiënten.

literatuur

web links

Individueel bewijs

  1. ^ Studies in Logic op archive.org