Propriété d'un système déductif ou d'une théorie affirmant que pour toute formule φ du langage, soit φ est démontrable à partir du système (ou de la théorie), soit sa négation ¬φ est démontrable ; en d'autres termes, la théorie est maximalement consistante par rapport aux formules du langage.

Principe

La règle organisatrice est que la relation de preuve décide chaque assertion du langage : la dérivabilité partitionne l'ensemble des formules en démontrables et réfutables, sans laisser de formule indépendante.

Démonstration

Exemple : une théorie du premier ordre complète telle que la théorie des corps algébriquement clos d'une caractéristique fixée est syntactiquement complète parce que pour chaque phrase la théorie la prouve ou en prouve la négation ; en revanche, l'arithmétique de Peano est syntactiquement incomplète car il existe des phrases arithmétiques indépendantes de ses axiomes.

Mauvaise application

Confondre la complétude syntaxique avec la complétude sémantique (le théorème de complétude qui identifie conséquence sémantique et démontrabilité) ou avec la décidabilité ; la complétude syntaxique n'implique pas en soi l'existence d'une procédure effective décidant laquelle de φ ou ¬φ est démontrable.

Conséquence

Lorsqu'une théorie est syntactiquement complète, elle est maximalement informative : chaque phrase a un statut de preuve défini relativement à la théorie, ce qui implique que la théorie détermine un seul diagramme élémentaire complet à équivalence logique près et permet une analyse modèle-théorique plus catégorique.

Inversion

La négation est l'incomplétude syntaxique : il existe des phrases ni démontrables ni réfutables, ce qui entraîne la présence d'énoncés indépendants et de plusieurs complétions non équivalentes de la théorie.

Limite

S'applique à un système déductif donné ou à une théorie spécifique dans un langage fixé ; cela ne concerne pas les notions sémantiques de validité sur tous les modèles, ni la décidabilité au méta-niveau, ni les systèmes de preuve partiels qui ne sont pas clos par la négation.

Tension sémantique

Il y a une tension entre complétude syntaxique et décidabilité effective, et entre complétude syntaxique et expressivité sémantique : une théorie peut être syntactiquement complète tout en étant indécidable, ou l'ajout de pouvoir expressif peut détruire la complétude.

Synthèse

La complétude syntaxique caractérise les théories dont le système de preuve ne laisse aucune formule indéterminée : elle relie la détermination syntaxique maximale (toute formule ou sa négation est dérivable) à l'unicité sémantique des valeurs de vérité au sein de la théorie, tout en restant distincte de la complétude sémantique et de la décidabilité algorithmique.