Matemaattinen logiikka

Matemaattinen logiikka viittaa kahteen erilliseen tutkimusalueeseen: toisaalta formaalisen logiikan menetelmien soveltamiseen matematiikkaan ja matemaattiseen päättelyyn, ja toisaalta matemaattisten menetelmien soveltamiseen formaalisen logiikan esittämisessä ja analysoinnissa.

Varhaisin matematiikan ja geometrian käyttö logiikassa ja filosofiassa löytyy jo antiikin Kreikasta Eukleideelta, Platonilta ja Aristoteleelta. Rohkein yritys soveltaa logiikkaa matematiikkaan on epäilemättä ollut filosofi-loogikoiden Gottlob Frege ja Bertrand Russell logisismi. Heidän ajatuksensa oli, että matemaattiset teoriat olivat loogisia tautologioita, ja he pyrkivät osoittamaan tämän palauttamalla matematiikan logiikkaan. Tämä kuitenkin epäonnistui, mistä esimerkkinä Fregen ohjelman lamaannuttanut Russellin paradoksi ja Hilbertin ohjelman romuttanut Gödelin epätäydellisyyslause.

Sekä Hilbertin ohjelma että Gödelin vastine siihen olivat riippuvaisia toisesta matemaattisen logiikan osa-alueesta, matematiikan soveltamisesta logiikkaan todistusteorian muodossa. Vaikka epätäydellisyysteoreema oli luonteeltaan negatiivinen, Gödelin täydellisyyslause oli malliteorian tulos ja osoittaa, kuinka lähellä logisismi oli osoittautua todeksi: jokainen täsmällisesti määritelty matemaattinen teoria voidaan esittää ensimmäisen kertaluvun logiikan teorialla; Fregen todistuskalkyyli pystyi kuvaamaan koko matematiikan, vaikka ei vastaakaan sitä. Näin matemaattisen logiikan kaksi osa-aluetta osoittautuvat toisiaan täydentäviksi.

Jos todistusteoria ja malliteoria ovatkin olleet matemaattisen logiikan perusta, ne ovat muodostaneet vasta kaksi sen neljästä tukipilarista. Joukko-oppi sai alkunsa Georg Cantorin äärettömyyden tutkimuksista ja se on tuottanut monet matemaattisen logiikan haastavimmista ja merkittävimmistä ongelmista (kuten Cantorin lause, valinta-aksiooma ja kontinuumihypoteesi). Rekursioteoria kuvaa laskentaa logiikan ja aritmetiikan avulla. Sen klassisimpia saavutuksia ovat Alan Turingin Entscheidungsproblemin osoittaminen ratkaisemattomaksi sekä Churchin-Turingin teesi. Nykyisin rekursioteoria tutkii ennen kaikkea monimutkaisuuksia ja ongelmien (tehokasta) ratkeavuutta.