Volledigheidsstelling van Gödel

De volledigheidsstelling van Gödel is een fundamentele stelling in de wiskundige logica, die zegt dat elke semantische geldige uitspraak in de eerste-orde logica ook bewijsbaar is. De stelling werd in 1929 voor het eerst bewezen door Kurt Gödel. Samen met gezondheid van een bewijssysteem (die veel makkelijker te bewijzen is) toont de stelling aan dat geldigheid en bewijsbaarheid overeenkomen.

De Volledigheidsstelling van Gödel moet niet worden verward met de Onvolledigheidsstelling van Gödel, waar naar een andere notie van volledigheid verwezen wordt.

Achtergrond

Een uitspraak in de eerste-orde logica is geldig, als ze waar is in elke voor de taal van de logica geschikte structuur (model). Dat betekent, dat welke interpretatie we ook aan de constanten en predikaatsymbolen toekennen, de formule altijd waar is. Aan de andere kant bestaan er verschillende syntactische afleidingssystemen voor de eerste-orde logica, zoals natuurlijke deductie. Een uitspraak is bewijsbaar, als er een eindig bewijs bestaat dat de uitspraak als conclusie heeft. Een bewijssysteem is gezond, als alle bewijsbare uitspraken ook geldig zijn, en volledig, als alle geldige uitspraken bewijsbaar zijn. In feite bestaan er dus gezondheids- en volledigheidsstellingen voor elk afleidingssysteem.

De stelling

De Volledigheidsstelling van Gödel zegt dat alle geldige beweringen in eerste-orde logica ook bewijsbaar zijn. De gezondheid van een bewijssysteem is veel makkelijker te bewijzen, en samen daarmee volgt uit de Volledigheidsstelling dat geldigheid en bewijsbaarheid overeenkomen.

Een belangrijk gevolg van de stelling is dat de verzameling van geldige beweringen semi-beslisbaar is. Dat wil zeggen, dat er een algoritme bestaat, dat, voor een geldig bewering, in eindige tijd de geldigheid ervan beslist, ofwel voor een ongeldige bewering eventueel oneindig lang doorgaat.

Externe links

• (en) Juliette Kennedy, Kurt Gödel in de Stanford Encyclopedia of Philosophy
• (en) Kurt Gödel op MacTutor

Zie ook

• Onvolledigheidsstelling van Gödel