Vollständigkeit (Logik)
Für andere Wortbedeutungen siehe die Begriffsklärungsseite Vollständigkeit oder speziell Vollständigkeit (Analysis).
Vollständigkeit ist eine Eigenschaft formaler Systeme bzw. Kalküle. Man unterscheidet semantische Vollständigkeit ("Alles, was wahr ist, ist beweisbar."), klassische Vollständigkeit ("Eine der zwei Aussagen und ist stets beweisbar.") und syntaktische Vollständigkeit ("Wird eine nicht beweisbare Aussage als Axiom verwendet, so ist die Widerspruchsfreiheit verletzt, d.h. alles wird beweisbar.").
Vollständigkeit ist das Pendant zur Korrektheit, in dem Sinn, dass ein Kalkül korrekt ist, wenn jede in ihm beweisbare (ableitbare) Aussage gilt ("Alles, was beweisbar ist, ist wahr.") Wenn ein Kalkül korrekt und vollständig ist und terminiert, können in ihm genau alle wahren Aussagen abgeleitet werden. Ein korrekter Kalkül ist insbesondere widerspruchsfrei, denn in einem Kalkül, der nicht widerspruchsfrei ist, d. h. in dem ein Widerspruch beweisbar ist, ist insbesondere alles, was falsch ist, beweisbar.
Kurt Gödel bewies, dass die Prädikatenlogik erster Stufe nicht nur korrekt, sondern auch vollständig ist (Gödelscher Vollständigkeitssatz). Er bewies weiter, dass alle Systeme, die so mächtig sind wie die Arithmetik, nicht vollständig (oder nicht Widerspruchsfrei) sind (siehe Gödelscher Unvollständigkeitssatz). Dasselbe folgt aus der von Alan Turing bewiesenen Unlösbarkeit des Halteproblems.