Propriété d'un système déductif selon laquelle toute formule sémantiquement valide (vraie dans tous les modèles de la sémantique du système) est démontrable au sein du calcul de preuves du système.

Principe

La complétude sémantique exige l'alignement entre la conséquence du point de vue des modèles et la dérivabilité syntaxique : si une phrase tient dans tous les modèles, les règles formelles du système peuvent la dériver ; la complétude se prouve souvent en construisant un modèle canonique à partir d'ensembles consistants ou par des théorèmes de complétude.

Démonstration

Le calcul du premier ordre est sémantiquement complet au sens du théorème de complétude de Gödel : toute formule vraie dans tous les modèles d'une théorie du premier ordre est dérivable à partir des axiomes de la théorie par les règles du premier ordre.

Mauvaise application

Confondre la complétude sémantique avec la complétude syntaxique (ou la complétude au sens de négation) d'une théorie (chaque phrase ou sa négation étant démontrable), ou interpréter à tort les théorèmes d'incomplétude de Gödel comme une contradiction au théorème de complétude pour le premier ordre.

Conséquence

Un système sémantiquement complet garantit que la recherche de preuves est adéquate pour capturer toutes les vérités sémantiques du langage : si une formule est valide, il existe une preuve finie dans le système (même si elle peut être difficile à trouver).

Inversion

Incomplétude sémantique : il existe des formules sémantiquement valides qui ne sont pas démontrables dans le système ; la complétude syntaxique est orthogonale et concerne la démontrabilité de chaque assertion ou de sa négation.

Limite

S'applique à un langage et un cadre sémantique spécifiés ; la complétude n'implique pas la décidabilité, ni l'existence de procédures effectives de recherche de preuves pour des théories arbitraires formulées dans ce langage.

Tension sémantique

Tension entre complétude sémantique et décidabilité ou complétude syntaxique : un système peut être sémantiquement complet mais indécidable, et la complétude n'implique pas que chaque énoncé soit décidable à l'intérieur de la théorie.

Synthèse

La complétude sémantique relie la vérité dans tous les modèles à la démontrabilité : lorsqu'un système déductif est sémantiquement complet, validité model-théorique et dérivabilité syntaxique coïncident, permettant aux preuves de capturer toutes les conséquences sémantiques universelles.