Achtergrond
We hebben in Semantiek en Correctheid en al eerder in dit college de begrippen "Soundness" en "Completeness" leten kennen. Deze leggen een 1-op-1 verband tussen afleidbaarheid en waarheid in modellen. Een andere vorm van volledigheid, ook wel bekend als syntactische volledigheid, is gedefinieerd voor een theorie: een verzameling gesloten formules T. We noemen T volledig als voor iedere gesloten formule A geldt dat A uit T afleidbaar is of ~A.
De vraag of theorieen volledig zijn speelde een belangrijke rol in de grondslagen kwesties die speelden in de 20ste eeuw. De wiskundige Hilbert stelde zich ten doel om de volledige wiskunde te formaliseren binnen een theorie en daarvan dan de consistentie, de volledigheid en de beslisbaarheid te bewijzen. Dit is niet gelukt en kan ook niet lukken, zoals bewezen is door de logicus Goedel, door middel van zijn bekende onvolledigheidsstelling
In dit college behandelen we de onvolledigheidsstelling van Goedel, zonder de volledige details te geven, maar we bespreken wel de context en de verdere implicaties.
Leerdoel
Na het voltooien van deze taak kunt u
Instructie
Product
Reflectie