Fullständighet (logik)

Ett axiomatiskt uppbyggt system eller ett formellt system är fullständigt, om allt det, som man önskar skall vara ett teorem i systemet också är ett teorem. Mer precist uttryckt är ett formellt system S, med språket L, fullständigt om och endast om varje tautologi i L är ett teorem i S. Man skiljer på semantiskt fullständiga system och syntaktiska sådana.

Semantisk fullständighet

Det satslogiska systemet PS med språket P är semantiskt fullständigt. Således är varje tautologi A i språket P ett teorem i systemet PS, vilket symboliskt kan uttryckas enligt följande: Om ${\displaystyle \models _{P}A}$ så ${\displaystyle \vdash _{PS}A}$.

Det finns på området ingen överenskommen terminologi, och uttrycket semantisk fullständighet behöver inte nödvändigtvis tolkas på samma sätt i varje sammanhang. Många skriver endast fullständighet och låter betydelsen bero av sammanhanget. Det finns i litteraturen ett antal olika bevis för formella systems semantiska fullständighet. Ett av de kortare och allra första är konstruerat av logikern Emil L. Post 1920 och ett annat av W. Quine 1937. Ett fundamentalt metateorem i logiken av Kurt Gödel, säger att det finns ett fullständigt härledningssystem för första ordningens logik.

Syntaktisk fullständighet

Det finns ett flertal formuleringar av syntaktisk fullständighet. En av dem är följande: Ett formellt system är syntaktiskt fullständigt om och endast om för varje formel A i systemets språk, antingen A eller icke-A är ett teorem i systemet. Det satslogiska systemet PS är inte fullständigt i denna mening.

Med hjälp av symboler kan definitionen för syntaktiskt fullständighet för ett formellt system formuleras enligt följande: Systemet är syntaktiskt fullständigt om det för varje formel ${\displaystyle \varphi \!\,}$ gäller att antingen ${\displaystyle \vdash _{S}\varphi }$ eller ${\displaystyle \vdash _{S}\neg \varphi }$ är sant. I systemet S är alltså antingen ${\displaystyle \varphi \!\,}$ eller dess negation ${\displaystyle \neg \varphi }$ härledbar, det vill säga för alla uttryck ${\displaystyle \varphi \!\,}$ som kan uttryckas i systemets språk L.

För första ordningens logik har ett metateorem formulerats av den polske logikern och matematikern Adolf Lindenbaum: Alla konsistenta uttrycksmängder i predikatlogik kan förlängas till fullständiga uttrycksmängder.

Se även

• Första ordningens logik
• Gödels ofullständighetsteorem

Källor

• Rebecca Newberger Goldstein, The Proof and Paradox of Kurt Gödel, William Warder Norton, 2005.
• Geoffrey Hunter, Metalogic. An Introduction to the Metatheory of Standard First-Order Logic, MacMillan London 1971.