Une théorie du premier ordre T dans un langage L est complète si, pour toute phrase φ en L, soit T ⊢ φ soit T ⊢ ¬φ ; équivalemment, deux modèles quelconques de T sont élémentairement équivalents (T décide toute phrase du langage).

Principe

La complétude signifie que la théorie attribue une valeur de vérité première-ordonnée définie à chaque phrase du langage, de sorte que la déduction syntaxique et la vérité sémantique coïncident au niveau des phrases pour cette théorie.

Démonstration

La théorie des ordres linéaires denses sans extrémités (DLO) est complète : toute phrase dans le langage des ordres linéaires est soit démontrable à partir de DLO soit sa négation l'est, et tous les ordres denses dénombrables sans extrémités sont isomorphes à (Q,<), si bien que DLO décide les phrases de premier ordre relatives à la densité et aux extrémités.

Mauvaise application

Confondre complétude et décidabilité (une théorie complète peut être indécidable) ou avec la modèle-complétude (une théorie complète n'est pas nécessairement modèle-complète) ; supposer à tort que la complétude se conserve sous extension du langage sans précaution.

Conséquence

Une théorie complète fixe le profil des phrases de premier ordre vérifiées par ses modèles : les types sur l'ensemble vide sont déterminés, et deux modèles satisfont exactement les mêmes phrases, ce qui facilite la classification et le transfert de propriétés entre modèles.

Inversion

Une théorie incomplète laisse des phrases indépendantes (ni démontrables ni réfutables), autorisant plusieurs modèles non élémentairement équivalents et une incertitude réelle sur les vérités du premier ordre du langage.

Limite

La complétude dépend du langage choisi : l'ajout de symboles peut rompre la complétude ; la complétude n'implique pas des propriétés méta-théoriques plus fortes comme la décidabilité ou la catégoricité sans hypothèses supplémentaires.

Tension sémantique

Tension avec la modèle-complétude et la décidabilité : la modèle-complétude concerne le comportement des plongements entre modèles tandis que la décidabilité porte sur la détermination effective de la démontrabilité, notion distincte de la complétude syntaxique.

Synthèse

Une théorie complète est une théorie du premier ordre qui décide chaque phrase de son langage, donnant un profil sémantique déterminé à ses modèles sans pour autant garantir la décidabilité algorithmique ou l'unicité des modèles en chaque cardinalité.