Negationstreu (engl.: negation complete) ist eine Eigenschaft von Folgen ${\displaystyle \Phi }$ von prädikatenlogischen Ausdrücken. Diese Eigenschaft wird – in Verwechslungsgefahr zu andersgemeinten Begriffen der Vollständigkeit – auch syntaktisch vollständig (in der englischsprachigen Literatur auch syntactically complete, deductively complete or maximally complete) genannt.

Definition: Eine Menge ${\displaystyle \Phi }$ von prädikatenlogischen Ausdrücken heißt negationstreu, wenn für jeden beliebigen Ausdruck ${\displaystyle \phi }$ gilt:

${\displaystyle \Phi \vdash \phi }$ oder ${\displaystyle \Phi \vdash \neg \phi }$ .

Man kann es auch anders ausdrücken: Ein formales System, gegeben durch die Axiomenmenge ${\displaystyle \Phi }$, ist negationstreu oder syntaktisch vollständig, wenn jedes weitere Axiom, das nicht selbst schon aus ${\displaystyle \Phi }$ ableitbar ist, zu einem Widerspruch führt.

Bedeutung

Die Bedeutung des Begriffs negationstreu liegt in seiner Rolle als Beweishilfsmittel für den Satz von Henkin, der seinerseits als Hilfsmittel für einen alternativen Beweis von Gödels Vollständigkeitssatz der Prädikatenlogik erster Stufe ist.

Literatur

Hans Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. Spektrum Akademischer Verlag, Heidelberg 2007, ISBN 3-8274-1691-4.