axiomatiseerbaar

Axiomatiseerbaar (axiomatizable) is een eigenschap van een theorie T in een formele taal L. Een theorie is axiomatiseerbaar als er een verzameling zinnen A bestaat waarvan de deductieve sluiting gelijk is aan T, oftewel T is precies de verzameling van alle zinnen die volgt uit A via de formele regels van gevolgtrekking. In de praktijk spreekt men ook van recursief axiomatiseerbaar wanneer de axioma’s A op een computabele (recursief opsombare) manier kunnen worden opgesomd. Dan volgt uit A een effectieve procedure om alle gevolgen van A te généreren.

Een theorie kan eindig axiomatiseerbaar zijn als er een eindige verzameling axioma’s is die dezelfde theorema’s oplevert. Veel klassieke theorieën zijn recursief axiomatiseerbaar; bijvoorbeeld ZFC en Peano-aartikel (PA) zijn via een oneindig axioma-schema axiomatiseerbaar, waardoor ze recursief axiomatiseerbaar maar niet finitely axiomatiseerbaar zijn. Een theorie zoals de theorie van densely ordered sets zonder boven- of ondergrenzen (DLO) is in zekere zin finitely axiomatiseerbaar in een geschikt taalmet betrekking tot de orde.

Het begrip axiomatiseerbaar is niet altijd van toepassing op elke theorie. De verzameling van alle ware zinnen over de natuurlijke getallen (“ware rekenkunde”) is bijvoorbeeld niet recursief op te sommen en daarom niet recursief axiomatiseerbaar. Gödel’s onvolledigheidsstellingen laten zien dat een consistente, voldoende sterke, recursief axiomatiseerbare theorie niet volledig kan zijn: er bestaan ware beweringen die niet binnen de theorie proefbaar zijn.

Samengevat verwijst axiomatiseerbaar naar het bestaan van een axiomasysteem waarvan delogische consequenties precies het bedoelde theoretische systeem vormen; recursieve axiomatiseerbaarheid voegt daar een effectieve opsombaarheid aan toe.