Théorème de complétude (calcul des propositions)

On peut montrer que les systèmes de déduction cités en préambule permettent en particulier d'effectuer les déductions suivantes :

${\displaystyle \vdash P\to P}$ (identité), ${\displaystyle \vdash \lnot P\lor P}$ (principe du tiers exclu), ${\displaystyle \vdash P\to \lnot \lnot P}$ et ${\displaystyle \vdash \lnot \lnot P\to P}$ (simplification de la double négation ou raisonnement par l'absurde).

si ${\displaystyle \vdash P\to Q}$ et ${\displaystyle \vdash P\to R}$, alors ${\displaystyle \vdash P\to Q\land R}$.

${\displaystyle \vdash \lnot R\to \lnot (R\land Q)}$

si ${\displaystyle \vdash P\to R}$ et ${\displaystyle \vdash Q\to R}$, alors ${\displaystyle \vdash P\lor Q\to R}$ (disjonction des hypothèses).

si ${\displaystyle \vdash P}$ et ${\displaystyle \vdash P\to Q}$, alors ${\displaystyle \vdash Q}$ (modus ponens).

Nous allons maintenant démontrer que, dans ces systèmes :

Il suffit de montrer le théorème pour des modèles finis. En effet, ordonnons linéairement les propositions atomiques, nous obtenons la suite ${\displaystyle p_{1}}$, ${\displaystyle p_{2}}$, ${\displaystyle p_{3}}$... Un modèle initial ou bien valide ${\displaystyle p_{i}}$ ou bien ne valide pas ${\displaystyle p_{i}}$, mais ne fait pas les deux. Comme une proposition ${\displaystyle P}$ ne contient qu’un nombre fini de propositions atomiques, notons ${\displaystyle n}$ le plus grand indice parmi ceux des propositions ${\displaystyle p_{n}}$ qui ont une occurrence dans ${\displaystyle P}$. Si ${\displaystyle P}$ est vraie dans tous les modèles initiaux de longueur ${\displaystyle n}$, alors elle est vraie dans tous les modèles, puisque les propositions ${\displaystyle p_{m}}$ n'ont pas d'occurrence dans ${\displaystyle P}$ quand ${\displaystyle m>n}$, donc la valeur de vérité de ces propositions atomiques n'a aucune incidence sur la véracité de ${\displaystyle P}$.

Pour démontrer (i), on va d’abord démontrer (ii) et (iii) ci-dessous. Soit ${\displaystyle P}$ une formule propositionnelle, et ${\displaystyle {\mathcal {M}}}$ un modèle. Notons ${\displaystyle h({\mathcal {M}})}$ la conjonction de toutes les formules atomiques ${\displaystyle p_{n}}$ telle que ${\displaystyle p_{n}=V}$ est dans ${\displaystyle {\mathcal {M}}}$ et de toutes les négations des formules atomiques ${\displaystyle p_{n}}$ telles que ${\displaystyle p_{n}=F}$ est dans ${\displaystyle {\mathcal {M}}}$.

On va démontrer (ii) par induction sur la complexité des formules. Celle-ci est mesurée par le nombre maximal d’opérateurs emboités. Par exemple dans ${\displaystyle (\lnot p)\lor (q\land r)}$ , le ou et le non sont emboités l’un dans l’autre. Mais le non et le et ne le sont pas. Cette proposition est de complexité 2 parce qu’elle a au maximum deux opérateurs emboités.

Soit ${\displaystyle p_{i}}$ une proposition de complexité 0, c’est-à-dire une proposition atomique. La formule ${\displaystyle p_{i}\to p_{i}}$ est dérivable, de même que toute formule du type ${\displaystyle H\to p_{i}}$, où ${\displaystyle H}$ est n’importe quelle conjonction de propositions atomiques ou de leurs négations qui contient ${\displaystyle p_{i}}$ parmi elles. Si ${\displaystyle p_{i}}$ est vraie dans le modèle ${\displaystyle {\mathcal {M}}}$, ${\displaystyle h({\mathcal {M}})}$ contient ${\displaystyle p_{i}}$. (ii) est donc démontrée pour les propositions de complexité 0. La démonstration de (iii) est identique.

Supposons que (ii) et (iii) soient vraies pour toutes les propositions de complexité au plus égale à ${\displaystyle n}$. Soit ${\displaystyle P}$ une proposition de complexité ${\displaystyle n+1}$. Deux cas sont possibles.

a) il y a un ${\displaystyle Q}$ tel que ${\displaystyle P=\lnot Q}$

• Si ${\displaystyle P}$ est vraie dans le modèle ${\displaystyle {\mathcal {M}}}$ alors ${\displaystyle Q}$ est fausse dans ${\displaystyle {\mathcal {M}}}$. Comme ${\displaystyle Q}$ est de complexité ${\displaystyle n}$, l’hypothèse d’induction donne, ${\displaystyle \vdash h({\mathcal {M}})\to \lnot Q}$. (ii) est donc démontrée pour ${\displaystyle P}$ dans ce cas.
• Si ${\displaystyle P}$ est fausse dans le modèle ${\displaystyle {\mathcal {M}}}$ alors ${\displaystyle Q}$ est vraie dans ${\displaystyle {\mathcal {M}}}$. On a donc par induction ${\displaystyle \vdash h({\mathcal {M}})\to Q}$. Par ailleurs, on sait que ${\displaystyle \vdash Q\to \lnot \lnot Q}$. On peut alors déduire que ${\displaystyle \vdash h({\mathcal {M}})\to \lnot \lnot Q}$. (iii) est donc démontrée pour ${\displaystyle P}$ dans ce cas.

b) il y a ${\displaystyle R}$ et ${\displaystyle S}$ tels que ${\displaystyle P=R\land S}$

• Si ${\displaystyle P}$ est vraie dans le modèle ${\displaystyle {\mathcal {M}}}$ alors ${\displaystyle R}$ et ${\displaystyle S}$ sont toutes les deux vraies dans ${\displaystyle {\mathcal {M}}}$. On a alors par induction ${\displaystyle \vdash h({\mathcal {M}})\to R}$ et ${\displaystyle \vdash h({\mathcal {M}})\to S}$. On en déduit que ${\displaystyle \vdash h({\mathcal {M}})\to R\land S}$. (ii) est donc démontrée pour ${\displaystyle P}$ dans ce cas.
• Si ${\displaystyle P}$ est fausse dans le modèle ${\displaystyle {\mathcal {M}}}$ alors l’une au moins de ${\displaystyle R}$ ou de ${\displaystyle S}$ est fausse dans ${\displaystyle {\mathcal {M}}}$. Supposons que ce soit ${\displaystyle R}$. On a alors par induction ${\displaystyle \vdash h({\mathcal {M}})\to \lnot R}$. Or, de ${\displaystyle \lnot R}$, on peut déduire ${\displaystyle \lnot (R\land S)}$. (iii) est donc démontrée pour ${\displaystyle P}$ dans ce cas.

Cela termine cette démonstration de (ii) et (iii).

Prouvons maintenant (i), le théorème de complétude, par induction sur la longueur des modèles. Soit ${\displaystyle I_{n}}$ l’énoncé : Si ${\displaystyle P}$ est vraie dans tous les modèles de longueur ${\displaystyle n}$ alors ${\displaystyle P}$ est dérivable. Démontrons par récurrence les énoncés ${\displaystyle I_{n}}$.

Prouvons d’abord ${\displaystyle I_{1}}$. Supposons que ${\displaystyle P}$ est vraie dans tous les modèles de longueur 1, c’est-à-dire les deux modèles ${\displaystyle p_{1}=V}$ et ${\displaystyle p_{1}=F}$. On a alors, d'après (ii) ${\displaystyle \vdash p_{1}\to P}$ et ${\displaystyle \vdash \lnot p_{1}\to P}$. Par la règle de disjonction des hypothèses, on en déduit que ${\displaystyle \vdash (p_{1}\lor \lnot p_{1})\to P}$ mais ${\displaystyle p_{1}\lor \lnot p_{1}}$ est elle-même une formule dérivable : c’est le principe du tiers-exclu. La règle du modus ponens suffit alors pour démontrer que ${\displaystyle \vdash P}$.

Supposons que ${\displaystyle I_{n}}$ soit vrai. Soit ${\displaystyle P}$ une proposition vraie dans tous les modèles de longueur ${\displaystyle n+1}$. Soit ${\displaystyle {\mathcal {M}}}$ un modèle de longueur ${\displaystyle n}$. ${\displaystyle P}$ est vraie dans ${\displaystyle ({\mathcal {M}},p_{n+1}=V)}$ et dans ${\displaystyle ({\mathcal {M}},p_{n+1}=F)}$. D'après (ii), on a alors ${\displaystyle \vdash (h({\mathcal {M}})\land p_{n+1})\to P}$ et ${\displaystyle \vdash (h({\mathcal {M}})\land \lnot p_{n+1})\to P}$. Comme ci-dessus, on en déduit que ${\displaystyle \vdash h({\mathcal {M}})\to P}$. Comme ${\displaystyle {\mathcal {M}}}$ un modèle quelconque de longueur ${\displaystyle n}$, l'hypothèse de récurrence ${\displaystyle I_{n}}$ permet de conclure que ${\displaystyle \vdash P}$. ${\displaystyle I_{n+1}}$ est donc vérifiée.

Cela termine cette démonstration du théorème de complétude du calcul des propositions.