Wiskundige logica

De wiskundige logica is een deelgebied van de wiskunde. De wiskundige logica wordt onderverdeeld in de vier deelgebieden verzamelingenleer, bewijstheorie, modeltheorie en berekenbaarheid. Zo is in de wiskunde de groepentheorie verbonden met de verzamelingenleer, de getaltheorie met de bewijstheorie en is de berekenbaarheid een onderdeel van de computationele complexiteitstheorie. Onderzoek op het gebied van de wiskundige logica heeft bijgedragen aan de grondslagen van de wiskunde, die weer de logica in het algemeen ondersteunden. Maar er zijn ook onderdelen van de wiskundige logica die zich niet met grondslag van de wiskunde bezighouden. De wiskundige logica geeft de voorwaarden aan, waaraan een wiskundig bewijs moet voldoen.

Vroeger werd de wiskundige logica ook wel symbolische logica genoemd en op één lijn getrokken met disciplines waar qua onderzoeksgebied enige overlap mee is, met name met de filosofische logica en de metawiskunde. De eerste discipline betreft vooral de algemene logica, maar wordt soms ook nog gebruikt voor de wiskundige logica. Metawiskunde heeft vooral betrekking op bepaalde aspecten van de bewijstheorie.

In de vorige eeuw was het programma van Hilbert, genoemd naar David Hilbert en het onderzoek van de consistentie binnen de wiskunde door onder meer Kurt Gödel van belang.

Deelgebieden van de wiskundige logica

Het 'Handbook of Mathematical Logic' (1977) deelt de wiskundige logica onder in vier gebieden:

Verzamelingenleer

De verzamelingenleer is de studie van de verzamelingen, in het bijzonder de abstracte verzamelingen van objecten. Terwijl eenvoudige concepten zoals de deelverzameling vaak binnen het terrein van de naïeve verzamelingenleer worden behandeld, houdt het moderne onderzoek zich bezig met de axiomatische verzamelingenleer, die logische methoden gebruikt om vast te stellen welke wiskundige uitspraken in verschillende formele theorieën kunnen worden bewezen. voorbeelden hiervan zijn de Zermelo-Fraenkel-verzamelingenleer van Ernst Zermelo en Adolf Fraenkel en de New Foundations van Willard Van Orman Quine.

Bewijstheorie

De bewijstheorie is de studie van formele bewijzen en verschillende logische deductiesystemen. Bewijzen worden als wiskundige objecten neergezet om ze door middel van wiskundige technieken te kunnen onderzoeken. Frege hield zich met de wiskundige bewijzen bezig en formaliseerde het begrip bewijs.

Modeltheorie

De modeltheorie is de studie van formele theorieën, waarvoor de basis is gelegd door Alfred Tarski. De verzameling van alle modellen van een bepaalde theorie noemt men een elementaire klasse. De klassieke modeltheorie probeert de eigenschappen van modellen van een bepaalde elementaire klasse te bepalen of onderzoekt of bepaalde klassen van structuren elementair zijn. De methode van de kwantoreliminatie wordt gebruikt om aan te tonen dat bepaalde theorieën niet te gecompliceerd kunnen zijn.

Berekenbaarheid

De berekenbaarheidstheorie, is de studie van berekenbare functies en de Turinggraden, die de niet berekenbare functies naar de graad classificeren, dat zij niet-berekenbaar zijn. Deze theorie is een onderdeel van de computationele complexiteitstheorie.

De grenzen tussen deze gebieden maar ook tussen de wiskundige logica en de andere gebieden binnen de wiskunde zijn niet altijd precies gedefinieerd. Bijvoorbeeld zijn de onvolledigheidsstellingen van Gödel niet alleen in de berekenbaarheids- en de bewijstheorie van groot belang, maar leidden ze ook tot de stelling van Löb, genoemd naar Löb, die van belang is in de modale logica. De categorieëntheorie maakt eveneens gebruik van veel formele, axiomatische methoden die grote overeenkomsten vertonen met de wiskundige logica, terwijl de categorieëntheorie in het algemeen niet tot de wiskundige logica wordt gerekend.

Raakvlakken met de informatica

Er bestaat veel overlap en verbinding tussen de wiskundige logica en de informatica. Delen van de wiskundige logica worden onder andere in de theoretische informatica behandeld. Veel pioniers in de informatica, zoals Alan Turing, waren zowel wiskundige als logicus. De studie van programmeertalen hangt nauw samen met de modeltheorie. Het Curry–Howard-isomorfisme heeft te maken met bewijstheorie en in het bijzonder met de intuïtionistische logica. Formele calculi zoals de lambdacalculus en de combinatorische logica worden nu bestudeerd als geïdealiseerde programmeertalen.

Computerwetenschappers concentreren zich in het algemeen vooral op programmeertalen, terwijl in de mathematische logica vooral theoretisch is.

Geschiedenis

18e eeuw

Wiskundigen met een filosofische achtergrond, zoals Gottfried Leibniz en Johann Heinrich Lambert probeerden al in de 18e eeuw de formele wiskunde vanuit een symbolische of algebraïsche benadering te behandelen, maar hun werk bleef grotendeels onbekend.

19e eeuw

In het midden van de 19e eeuw kwamen George Boole en Augustus De Morgan met een systematische logica. Dit werk was gebaseerd op eerder onderzoek van algebraci, zoals George Peacock. De traditionele, aristotelische logica werd hervormd en uitgebreid als instrument om de grondslagen van de wiskunde te onderzoeken. Aristoteles' leer van het syllogisme en Euclides' vlakke meetkunde vormden de voornaamste uitgangspunten. Charles Peirce ging verder met het werk van Boole en ontwikkelde en publiceerde een logisch systeem voor relaties en kwantoren. Gottlob Frege publiceerde in 1879 een eigen uitwerking van de logica met kwantoren in zijn Begriffsschrift. Dit werk bleef onopgemerkt totdat Bertrand Russell het rond de eeuwwisseling meer bekendheid gaf. De door Frege gehanteerde tweedimensionale notatie heeft echter nooit veel ingang gevonden en wordt tegenwoordig niet gebruikt. Van 1890 tot 1905 publiceerde Ernst Schröder in drie delen zijn Vorlesungen über die Algebra der Logik, waarin het werk van Boole, De Morgan en Peirce werd samengevat.

Symbolische logica werd door Giuseppe Peano wiskundige logica genoemd. De klassieke versie ervan is vergelijkbaar met de logica van Aristoteles, hoewel men symbolen in plaats van natuurlijke taal gebruikt.

Terwijl tijdens de Griekse ontwikkeling van de logica grote waarde werd gehecht aan de argumentatieformuleringen, kan men de huidige wiskundige logica omschrijven als de studie van de inhoud door het leggen van combinaties. Daaronder vallen zowel de syntactische, het onderzoek van de formele tekenreeksen, als ook de semantische, het toewijzen van betekenis aan deze tekenreeksen, combinaties.

Historische publicaties van betekenis zijn het Begriffsschrift (Beschrijving der Begrippen) van Gottlob Frege, Studies in Logic (Studie in de Logica) van Charles Peirce, Principia Mathematica van Bertrand Russell en Alfred North Whitehead en Onvolledigheidsstellingen van Kurt Gödel. Voluit heet het werk van Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I.

Grondslagtheorie

Zie Grondslagen van de wiskunde voor het hoofdartikel over dit onderwerp.

De bezorgdheid dat er iets mis was met de basis waarop de wiskunde was gebaseerd was de aanleiding voor het ontwikkelen van axiomatische methoden met betrekking tot fundamentele onderdelen van de wiskunde zoals de rekenkunde, analyse en meetkunde.

In de logica verwijst rekenkunde naar de theorie van natuurlijke getallen. Los van Frege publiceerde Giuseppe Peano in 1888 zijn werk dat bekend is geworden onder de naam axioma's van Peano en een variatie op het logische systeem van Boole en Schröder maar met toevoeging van kwantoren bevatte. In hetzelfde jaar stelde Richard Dedekind een alternatieve karakterisering voor waarin de formeel-logische axioma's van Peano ontbraken. Dedekind toonde onder andere aan dat natuurlijke getallen alleen worden gekenmerkt door hun inductieve eigenschappen.

Met betrekking tot de meetkunde werden er in de 19e eeuw fouten in de postulaten van Euclides vastgesteld, zoals de in 1826 door Nikolaj Lobatsjevski vastgestelde onafhankelijkheid van het parallellenpostulaat. Ook werd vastgesteld dat bepaalde theorema's die door Euclides als vanzelfsprekend werden beschouwd niet met behulp van de axiomatische methode konden worden bewezen, bijvoorbeeld de stelling dat een lijn ten minste twee punten bevat. In 1899 publiceerde Hilbert op basis van de in 1882 gepubliceerde axioma's van Pasch een hele reeks nieuwe geometrische axioma's die bekendstaan als de axioma's van Hilbert. Aangemoedigd door het succes hiervan besloot Hilbert om ook op zoek te gaan naar methoden voor andere onderwerpen binnen de wiskunde, zoals de natuurlijke getallen en de reële lijn. In de eerste helft van de 20e eeuw was er nog veel belangstelling voor dit onderzoek.

In de 19e eeuw werd veel nieuws ontdekt op het gebied van analyse, zoals de Fourierreeksen. Karl Weierstrass stelde onder andere de analyse-aritmisering voor, met behulp waarvan analyses op basis van de eigenschappen van natuurlijke getallen moesten worden geanalyseerd, de verzamelingenleer is hiervan het belangrijkste resultaat. De moderne "ε-δ"-definitie voor limieten en continue functies werd tussen 1817 en 1823 ontwikkeld door Bernard Bolzano en Augustin Louis Cauchy. In 1858 stelde Dedekind aan de hand van zijn Dedekindsnede een definitie van reële getallen voor, die nog steeds wordt gebruikt.

Georg Cantor legde de basis voor de theorieën over oneindige verzamelingen en kardinaliteit en bewees dat natuurlijke getallen verschillende kardinaliteiten hebben. Gedurende de volgende twintig jaar ontwikkelde Cantor in een reeks publicaties een theorie met betrekking tot transfiniete getallen. In 1891 voerde hij met zijn diagonaalbewijs nieuw bewijs aan voor de ontelbaarheid van reële getallen. Deze methode gebruikte hij vervolgens om zijn stelling te onderbouwen.

20e eeuw

In 1900 presenteerde Hilbert zijn bekend geworden lijst met 23 problemen. In het eerste decennium van de 20e eeuw richtte de wiskundige logica zich verder vooral op de verzamelingenleer en de formele logica.

Verzamelingenleer en paradoxen

Doordat er in de informele verzamelingenleer tegenstrijdigheden waren geconstateerd, werd de consistentie van de wiskunde als zodanig in twijfel getrokken. In 1904 leverde Ernst Zermelo met zijn keuzeaxioma het bewijs dat elke reeks goed geordend kon zijn. In 1908 leverde hij de eerste reeks axioma's voor de verzamelingenleer. Samen met het door Abraham Fraenkel voorgestelde axioma-schema voor vervanging is dit bekend geworden als de Zermelo–Fraenkel verzamelingenleer (ZF).

In 1910 werd het eerste deel van de Principia Mathematica van Russell en Alfred North Whitehead gepubliceerd, waarin theorieën over functies en kardinaliteit werden ontwikkeld binnen het kader van de typentheorie. Hoewel dit werk op zich geldt als een van de invloedrijkste publicaties van de 20e eeuw, heeft de typentheorie het als theoretische grondslag voor de wiskunde niet gered.

In 1922 bewees Fraenkel dat het keuzeaxioma niet kan worden bewezen op basis van de overgebleven axioma's van Zermelo's verzamelingenleer met de oerelementen. In 1966 toonde de wiskundige Paul Cohen aan dat de toevoeging van oerelementen niet nodig is en het keuzeaxioma in de ZF-verzamelingenleer niet te bewijzen is. Dit bewijs gaf aanleiding tot het ontwikkelen van de forcing-methode, die nu als hulpmiddel dient bij het bepalen van onafhankelijkheidsresultaten.

Symbolische logica

Leopold Löwenheim en Thoralf Skolem presenteerden rond 1920 de stelling van Löwenheim-Skolem. In 1929 kwam Gödel met zijn volledigheidsstelling, waarin een overeenkomst tussen syntaxis en semantiek op grond van de predicatenlogica werd vastgesteld. Op basis van de volledigheidsstelling onderbouwde Gödel ook de compactheidsstelling en hij toonde de finitistische aard van logische consequenties van de eerste orde aan, die de predicatenlogica centraal in de wiskunde stelde. In 1931 publiceerde Gödel zijn werk Principia Mathematica waarin de onvolledigheid van alle theorieën van de eerste orde werd aangetoond. Dit werk leidde tot de onvolledigheidsstellingen van Gödel. De voornaamste conclusie van Gödels werk is dat van geen enkel axiomasysteem, hoe consistent ook, de consistentie van dit systeem met behulp van het systeem zelf kan worden aangetoond. In 1936 bewees Gerhard Gentzen de consistentie van de rekenkunde aan de hand van een finitistisch systeem en het principe van transfiniete inductie. Hiermee introduceerde Gentzen het idee van de hoofdzin en de ordinale analyse, die zeer belangrijk zijn geworden in de bewijstheorie.

Propositielogica

De propositielogica, sterkere vormen van klassieke logica zoals de tweede orde logica of de niet-klassieke logica zoals het intuïtionisme worden eveneens onderzocht. De basis voor het intuïtionisme is gelegd door Luitzen Egbertus Jan Brouwer, en hieruit vloeiden onder andere de wet van de uitgesloten derde en het door Arend Heyting ontwikkelde intuïtionisme voort. De filosofie van Brouwer was invloedrijk en zorgde voor menig verhit debat onder wiskundigen. Met behulp van de Brouwer-Heyting-Kolmogorovinterpretatie (BHK) en de Kripkemodellen werd het intuïtionisme weer met de klassieke wiskunde in overeenstemming gebracht.

Belangrijke resultaten

• De stelling van Löwenheim-Skolem (1919)
• De volledigheidsstelling (1929)
• De onvolledigheidsstelling (1931)
• De onmogelijkheid zeker te kunnen bepalen, dat van een algoritme de berekening eindigt, door Alan Turing en Alonzo Church in 1936 onafhankelijk van elkaar ontdekt.
• De onafhankelijkheid van de continuümhypothese van de Zermelo-Fraenkel-verzamelingenleer van Ernst Zermelo en Adolf Fraenkel; deze werd in 1963 door Paul Cohen bewezen.
• De algoritmische onoplosbaarheid van het 10e probleem van Hilbert werd in 1970 door Joeri Matijasevitsj aangetoond.

Literatuur

• (en) Barwise, K.J. (1977): Handbook of Mathematical Logic, ISBN 0-444-86388-5
• (en) Barwise, K.J. (1988): The Situation in Logic, ISBN 0-937073-32-6

Externe links

• (en) Wiskundige logica over de hele wereld, lijst met wiskundige logicalinken
• (en) Detlovs, Vilnis, en Podnieks, Karlis, Introduction to Mathematical Logic., e-book vanaf de Universiteit van Letland
• (en) Stewart Shapiro, Klassieke logica, Stanford filosofische encyclopedie
• (en) Wilfred Hodges Modeltheorie van de eerste orde, Stanford filosofische encyclopedie