Logique Intuitionniste

Kevin Quirin, avec Doc. Vítězslav Švejdar1

Été 2011

1. Université Charles, Faculté des Arts, Département de logique

Table des matières

1 Introduction 1

1.1 Prérequis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 La logique intuitionniste 3

2.1 Traduction de Godël et théorème de Glivenko . . . . . . . . . . . . . . . . . . . . . . . 6

3 Sémantique de Kripke 9

3.1 Théorème de complétude de Kripke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.2 Application : Définitions des connecteurs intuitionnistes . . . . . . . . . . . . . . . . . 19

4 Calcul des séquents en logique intuitionniste 22

4.1 Séquent à conclusion unique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.2 Séquent à conclusion multiple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Références 30

1 Introduction

Avant de parler de logique intuitionniste, il faut d’abord introduire le concept philo-sophique d’intuitionnisme, introduit par Luitzen Egbertus Jan Brouwer en 1907, s’opposantaux logicisme de Bertrand Russel, Georg Canter, etc. ; et au formalisme de David Hilbert. Ce

point de vue sur les mathématiques rejette deux concepts : le tiers-exclu et l’existentiel non constructif.Le premier est bien connu de tous, tellement qu’il peut être difficile d’imaginer qu’on puisse le rejeter.Aristote en parlait déjà dans Métaphysique :

« Il n’est pas possible qu’il y ait aucun intermédiaire entre les énoncés contradictoires : ilfaut nécessairement ou affirmer ou nier un seul prédicat, quel qu’il soit. »

David Hilbert dans Grundlagen der Mathematik ira jusqu’à dire :

« Enlever le principe du tiers-exclu aux mathématiciens serait la même chose, disons, qued’interdire le téléscope à l’astronome ou au boxeur l’usage de ses poings. »

Le second quand à lui, suppose de changer le sens habituel de « il existe » : cela implique dans notrecas de donner un procédé pour construire l’objet solution. La suppression de ces deux notions rendsévidemment les mathématiques plus compliquées, mais aussi plus proches de l’intuition.

Illustrons notre propos par un exemple de preuve utilisant le tiers-exclu :

Proposition 1.1

Il existe deux irrationnels a et b tels que ab soit rationnel.

Démonstration. On part du fait que 2 est rationnel, et que√

2 ne l’est pas. Deux cas se proposent :

– si√

2√

2est rationnel, on a le résulat ;

– sinon,(√

2√

2)

√2

est rationnel, puisqu’égal à 2. On a donc dans ce cas aussi une solution au

problème.

On part donc du principe, dans cette preuve, qu’on a√

2√

2est rationnel ou ne l’est pas, sans savoir

laquelle des deux assertions est vraie. Cela conduit à l’existence de notre couple (a, b), mais il estimpossible avec cette preuve de le construire. Il faut faire appel à un théorème beaucoup plus compliqué(le théorème de Gelfond-Schneider) pour avoir une preuve constructiviste du résultat : on déduit de

ce théorème que√

2√

2est bien irrationel, et donc que le couple

(√2

√2,√

2)

est solution de notre

problème.

Un autre exemple peut nous aider à sentir le côté « non-intuitionniste » du tiers-exclu :

Proposition 1.2 : Paradoxe des buveurs

Dans une pièce non vide, il existe une personne qui si elle boit, tout le monde boit.

1

Démonstration. Deux cas se présentent :– si tout le monde boit, alors comme la pièce est non vide on peut choisir n’importe qui ;– sinon, il existe une personne qui ne boit pas. En la choisissant, l’implication est vérifiée (car le faux

implique ce qu’on veut).

À ce stade, l’intuitionnisme n’est donc qu’un point de vue philosophique sur les mathématiques. Il fautattendre 1927 pour que la Dutch Mathematics Society en fasse un problème « officiel », et un an plustard, Arend Heyting gagne le prix. Dans son article, il a patiemment étudié les Principia Mathematica,pour n’en garder que les axiomes compatibles avec l’intuitionnisme. C’est une formalisation « à laHilbert », dans le sens ou Heyting donne une liste d’axiomes, et seulement deux règles de dérivation.

En 1935, Gehrard Gentzen découvre deux nouvelles façons de formaliser la logique : la déduction

naturelle et le calcul des séquents. En adaptant ces deux systèmes de déduction, on peut formaliserd’autres manières la logique intuitionniste.

1.1 Prérequis

Dans ce rapport, on suppose connu :– les bases de la logique propositionnelle ;– les bases de la logique des prédicats ;– la déduction naturelle ;– le calcul des séquents.Les règles des calculs des séquents pour la logique intuitionniste seront rappelées dans la section oùelles interviennent.

2

On rappelle les règles de la deduction naturelle :

Règles d’introduction Règles d’élimination

(∧I)ϕ ψ

ϕ ∧ ψ (∧E)ϕ ∧ ψϕ

,ϕ ∧ ψψ

(→I)

[ϕ]...ψ

ϕ→ ψ

(→E)ϕ ϕ→ ψ

ψ

(∨I)ϕ

ϕ ∨ ψ ,ψ

ϕ ∨ ψ (∨E)

[ϕ] [ψ]...

...ϕ ∨ ψ σ σ

σ

(∀I)ϕ(x)∀xϕ(x)

(∀E)∀xϕ(x)ϕ(t)

où x n’est pas libre dans les hypothèses où t est libre pour x

(∃I)ϕ(t)∃xϕ(x)

(∃E)

[ϕ]...

∃xϕ(x) ψ

ψoù t est libre pour x dans ϕ où x n’est pas libre pour ψ ni dans la sous-dérivation

On ajoute à ces règles la règle ex falso sequitur quodlibet :

(⊥)⊥ϕ

Dans le cas de la logique classique, on a aussi la règle reductio ad absurdum :

(RAA)

[¬ϕ]...⊥ϕ

2 La logique intuitionniste

En 1932, Andreï Kolmogorov résume comme suit :

« If a and b are two problems, then a∧ b designates the problem "to solve both problems aand b", while a ∨ b designates the problem "to solve at least one of the problems a and b".Furthermore, a→ b is the problem "to solve b provided that the solution for a is given" or,equivalently, "to reduce the solution of b to the solution of a" .¬a designates the problem "toobtain a contradiction provided that the solution of a is given". (x)a(x) stands in generalfor the problem "to give a general method for the solution of a(x) for every single value ofx". » (Kolmogorov 1932)

3

En effet, afin de « sentir » les bases de la logique intuitionniste, nous allons commencer par définirune preuve. Ce que nous appelons preuve ici, c’est une construction qui suit ces règles (nous fixons undomaine D pour les quantificateurs) :– a est une preuve de ϕ ∧ ψ si a est un couple (b, c) où b et c sont des preuves de ϕ et de ψ

respectivement ;– a est une preuve de ϕ∨ ψ si a est un couple (b, c) où b est 0 ou 1, et c est une preuve de ϕ si b = 0,

et de ψ sinon ;– a est une preuve de ϕ→ ψ si a est une construction qui transforme une preuve de ϕ en une preuve

de ψ ;Remarque – En logique intuitionniste, le connecteur→ est un connecteur à part entière, i.e ϕ→ ψn’est pas une abréviation pour ¬ϕ ∨ ψ. Regardons un exemple :Soit ϕn la proposition « Il y a une suite de n 1 dans le développement décimal de π ».Alors on a clairement ϕn → ϕn−1. Mais on ne sait pas choisir entre ¬ϕn et ϕn−1.

– a ne peut pas être une preuve de ⊥ ;– a est une preuve de ∀xϕ(x) si a est une construction qui transforme chaque x de D en une preuvea(x) de ϕ(x) ;

– a est une preuve de ∃xϕ(x) si a est un couple (x, c) où x est dans D, et c est une preuve de ϕ(x).On peut voir ici l’aspect constructiviste de la logique intuitionniste : la preuve d’un « ou » demandeun choix effectif entre les deux formules ; la preuve d’un « il existe » demander d’exhiber un élémentpour lequel la propriété est vraie.

Le tiers-exclu va donc poser problème : il est impossible en général de choisir entre une propriété etsa négation si on ne connait pas la preuve e l’un ou l’autre.

Avec le tiers-exclu vons disparaître un certain nombre de propriétés vraies en logique classique. Voiciquelques exemples :

Proposition 2.1

La propriété ϕ↔ ¬¬ϕ n’est pas vraie en logique intuitionniste (en fait, seul le sens direct est vrai).

La loi de Morgan (¬ϕ ∨ ¬ψ) ↔ ¬(ϕ ∧ ψ) n’est pas vraie en logique intuitionniste (seul le sens directest vrai).

Démonstration. Nous verrons des preuves formelles plus tard ; essayons juste de sentir pourquoi cesthéorèmes disparaissent.

Dans le premier cas, il faut commencer par revoir notre façon de voir le symbole ¬. Ici, on ne peutplus le lire « la propriété est fausse », plus plutot comme « on a une preuve que la propriété estcontradictoire ».

La double négation peut alors se lire « on a une preuve que la propriété n’est pas contradictoire ».

Le sens direct devient alors :

« si ϕ est vraie, alors ϕ n’est pas contradictoire »,

ce qui semble raisonnable.

En revanche, l’autre sens pose problème : savoir que ϕ n’est pas contradictoire ne nous permet pas de

4

construire une preuve que ϕ est vrai !

Dans le second cas, le problème vient du fait que la partie avec le ∨ est bien plus difficile à montrer, carelle demande un choix effectif, alors que la partie avec le ∧ ne demande que de montrer que quelquechose n’a pas de preuve.

Toutes ces transformations de preuves ne sont pas simples à utiliser : nous allons donc nous servirdans la suite de la déduction naturelle.

Dans les cas où il peut y avoir confusion, il convient de noter ⊢i une dérivation en logique intuitionniste,et ⊢c dans le cas classique. Un symbole ⊢ sans indice sera donné par le contexte.

Remarque – Si on rajoute le tiers-exclu à la logique intuitionniste, on retrouve la logique classique.Il est donc assez clair que Γ ⊢i ϕ⇒ Γ ⊢c ϕ.

Nous avons vu qu’une proposition n’est pas équivalente à sa double négation. Mais dans un certain cas,ce théorème est vrai. Pour le démontrer, commençons par voir une liste de théorèmes qu’on utiliseradans la suite :

Lemme 2.2

En logique intuitionniste, on a :

1. l’associativité et la commutativité de ∨ et ∧ sont des théorèmes

2. la distributivité de ∨ sur ∧ et de ∧ sur ∨ sont des théorèmes

3. ⊢ (ϕ→ (ψ → σ))↔ (ϕ ∧ ψ → σ)

4. ⊢ ϕ→ (ψ → ϕ)

5. ⊢ ϕ→ (¬ϕ→ ψ)

6. ⊢ ¬(ϕ ∨ ψ)↔ ¬ϕ ∧ ¬ψ7. ⊢ ¬ϕ ∨ ¬ψ → ¬(ϕ ∧ ψ)

8. ⊢ (¬ϕ ∧ ψ)→ (ϕ→ ψ)

9. ⊢ (ϕ→ ψ)→ (¬ψ → ¬ϕ)

10. ⊢ (ϕ→ ψ)→ ((ψ → σ)→ (ϕ→ σ))

11. ⊢ ⊥ ↔ (ϕ ∧ ¬ϕ)

12. ⊢ ∃x(ϕ(x) ∨ ψ(x))↔ ∃xϕ(x) ∨ ∃xψ(x)

13. ⊢ ∀x(ϕ(x) ∧ ψ(x))↔ ∀xϕ(x) ∧ ∀xψ(x)

14. ⊢ ¬∃xϕ(x)↔ ∀x¬ϕ(x)

15. ⊢ ∃x¬ϕ(x)→ ¬∀xϕ(x)

16. ⊢ ∀x(ϕ→ ψ(x))↔ (ϕ→ ∀xψ(x))

17. ⊢ ∃x(ϕ→ ψ(x))→ (ϕ→ ∃xψ(x))

18. ⊢ (ψ ∨ ∀xψ(x))→ ∀x(ϕ ∨ ψ(x)

19. ⊢ (ϕ ∧ ∃xψ(x))→ ∃x(ϕ ∧ ψ(x))

20. ⊢ ∃x(ϕ(x)→ ψ)→ (∀xϕ(x)→ ψ)

21. ⊢ ∀x(ϕ(x)→ ψ)↔ (∀xϕ(x)→ ψ)

5

22. ⊢ ϕ→ ¬¬ϕ23. ⊢ ¬ϕ↔ ¬¬¬ϕ24. ⊢ ¬¬(ϕ→ ψ)↔ (¬¬ϕ→ ¬¬ψ)

25. ⊢ ¬¬(ϕ ∧ ψ)↔ (¬¬ϕ ∧ ¬¬ψ)

26. ⊢ ¬¬∀xϕ(x)→ ∀x¬¬ϕ(x)

Démonstration. 1. à 21 sont des applications directes des règles.

22.[ϕ]1 [¬ϕ]2

¬¬ϕ⊥

2

ϕ→ ¬¬ϕ 1

23. Le sens direct est évident. Pour l’autre sens :

[ϕ]1 ϕ→ ¬¬ϕ¬¬ϕ [¬¬¬ϕ]2

⊥¬ϕ 1

¬¬¬ϕ→ ¬ϕ 2

24. , 25. et 26. sont laissés.

On peut maintenant énoncer le théorème :

Proposition 2.3

Si ϕ est une formule qui ne contient pas ∨ ou ∃, et que tous les atomes de ϕ (excepté ⊥) sont négatifs,alors on a ⊢i ϕ↔ ¬¬ϕ.

On remarque que la condition « enlève » le côté intuitionniste de la formule : c’est l’interprétation de∨ et ∃ qui change en passant à la logique intuitionniste.

Démonstration. On remarque que le sans ⊢ ϕ → ¬¬ϕ est toujours vrai. Montrons donc l’autre sens,par induction sur ϕ :– si ϕ est ¬p, on a le résultat car ⊢ ¬p↔ ¬¬¬p.– si ϕ est a ∧ b, a→ b ou ∀xa(x), alors le lemme 2.2 nous donne le résultat.

2.1 Traduction de Godël et théorème de Glivenko

Dans cette partie, nous allons essayer de relier les logiques intuitionnistes et classiques. Pour cela, latraduction de Godël permet de transformer les formules, afin de supprimer les connecteurs qui posentproblème : ∨ et ∃.

6

Définition 2.4

La traduction de Godël ϕo d’une formule ϕ est définie inductivement comme suit :– si p est un atome différent de ⊥, alors po := ¬¬p ;– on pose ⊥o := ⊥ ;– (ϕ ∧ ψ)o := ϕo ∧ ψo ;– (ϕ ∨ ψ)o := ¬(¬ϕo ∧ ¬ψo) ;– (ϕ→ ψ)o := ϕo → ψo ;– (∀xϕ(x))o := ∀xϕo(x) ;– (∃xϕ(x))o := ¬∀x¬ϕo(x).Si Γ est un ensemble de formules, on définit Γo comme l’ensemble des traductions de Godël des formulesde Γ :

Γo := {ϕo | ϕ ∈ Γ}.

On a alors le théorème suivant :

Théorème 2.5

Si Γ est un ensemble de formules, et ϕ une formule, alors :

Γ ⊢c ϕ⇔ Γo ⊢i ϕo.

Démonstration. Il est assez clair qu’en logique classique, ⊢c ϕo ↔ ϕ, et donc le sens réciproque est

évident.

Pour le sens direct, nous allons utiliser une induction sur la dérivation D de ϕ à partir de Γ.– Si ϕ ∈ Γ, alors ϕo ∈ Γo, et donc Γo ⊢i ϕ

o.– Si la dérivation D se termine par une règle d’introduction ou d’élimination propositionnelle :

(∧I) : ϕ est ψ ∧ σ. L’hypothèse d’induction est Γo ⊢i ψo et Γo ⊢i σ

o.On a alors Γo ⊢i ψ

o ∧ σo, et donc Γo ⊢i (ψ ∧ σ)o par définition de la traduction de Godël.(→I) : ϕ est ici ψ → σ. L’hypothèse d’induction est donc Γo, ψo ⊢i σ

o.On a alors Γo ⊢i ψ

o → σo, d’où le résultat.(∨I) : ϕ est de la forme ψ ∨ σ. L’hypothèse d’induction est (par exemple) Γo ⊢i ψ

o.Alors

Γo ⊢i ψo ∨ σo

⊢i ¬¬(ψo ∨ σo)

⊢i ¬(¬ψo ∧ ¬σo)

⊢i (ψ ∨ σ)o

(∧E) : Ce cas est évident.(→E) : Celui-là aussi.(∨E) : ϕ provient de ψ ∨ σ, et de dérivations de ψ et σ vers ϕ. L’hypothèse d’induction est donc

Γo ⊢i (ψ ∨ σ)o ie Γo ⊢i ¬(¬ψo ∧ ¬σo)

Γo, ψo ⊢i ϕo ie Γo ⊢i ψ

o → ϕo

7

Γo, σo ⊢i ϕo ie Γo ⊢i σ

o → ϕo

Alors on a une dérivation de ¬¬ϕo :

¬(¬ψo ∧ ¬σo)

[ψo]1 ψo → ϕo

ϕo [¬ϕo]3

⊥¬ψo

1

[σo]2 σo → ϕo

ϕo [¬ϕo]3

⊥¬σo

2

¬ψo ∧ ¬σo

⊥3

¬¬ϕo

Or la traduction de Godël nous place dans le cas de la proposition 2.3, et donc ¬¬ϕo ↔ ϕo. D’oùle résultat.

– Si la dernière règle de D est le ex falso sequitur quodlibet, alors l’hypothèse d’induction est Γo ⊢i ⊥o,et donc le résultat est évident car ⊥o = ⊥.

– Si la dernière règle de D est une règle d’introduction ou d’élimination d’un quantificateur :(∀I) : ϕ est de la forme ∀xψ(x), et l’hypothèse d’induction est Γo ⊢i ψ(x)o.

Alors on a Γo ⊢i ∀xψ(x)o, et donc Γo ⊢i ϕo.

(∃I) : ϕ est de la forme ∃xψ(x), et l’hypothèse d’induction est Γo ⊢i ψ(t)o.Alors il suit directement

Γo ⊢i ∃xψ(x)o

⊢i ¬¬(∃xψ(x)o)

⊢i ¬(∀x¬ψ(x)o)

⊢i (∃xψ(x))o

⊢i ϕ

(∀E) : Ce cas est évident.(∃E) : ϕ provient de ∃xψ(x) et d’une dérivation de ϕ à partir de ψ. L’hypothèse d’induction sera

Γo ⊢i (∃xψ(x))o ie Γo ⊢i ¬∀x¬ψ(x)o

Γo, ψ(x)o ⊢i ϕo ie Γo ⊢i ψ(x)o → ϕo.

Alors on peut déduire ¬¬ϕo par la dérivation suivante :

¬∀x¬ψ(x)o

[ψ(x)o]1 ψ(x)o → ϕo

ϕo [¬ϕo]2

⊥¬ψ(x)o

1

∀x¬ψ(x)o

⊥¬¬ϕo

2

Comme tout à l’heure, on est dans le cas de la proposition 2.3, et donc Γo ⊢i ϕo.

– Si la dernière règle de D est (RAA), alors notre hypothèse d’induction est Γo,¬ϕo ⊢i ⊥.Alors Γo ⊢i ¬¬ϕo. On est toujours dans le cas des hypothèses de la proposition 2.3, et donc on a lerésultat.

8

On a donc trouvé un lien entre les logiques classiques et intuitionnistes. Cepdenant, la traduction deGodël n’est pas très facile à manipuler. Le théorème de Glivenko nous donne un lien encore plus simpleentre les deux logiques, dans le cas de la logique propositionnelle :

Théorème 2.6 : de Glivenko

Si ϕ est une formule propositionnelle, alors

⊢c ϕ⇔⊢i ¬¬ϕ.

Démonstration. Commençons par montrer par induction que ⊢i ϕo ↔ ¬¬ϕ.

– Si ϕ est un atome, le résultat est vrai par définition de la traduction de Godël.– Si ϕ et ψ ∧ σ, ou ψ → σ, le résultat est évident.– Si ϕ est ψ ∨ σ, avec ⊢i ψ

o ↔ ¬¬ et ⊢i σo ↔ ¬¬σ.

Alors la suite d’équivalence est un théorème de la logique intuitionniste :

(ψ ∨ σ)o ↔ ¬(¬ψo ∧ ¬σo)

↔ ¬(¬¬¬ψ ∧ ¬¬¬σ)

↔ ¬(¬ψ ∧ ¬σ)

↔ ¬¬(ψ ∨ σ)

D’où le résultat attendu. Il suffit maintenant juste d’appliquer le théorème 2.5 pour avoir l’équivalence.

3 Sémantique de Kripke

Dans la section précédente, nous avons défini la syntaxe de la logique intuitionniste. Il convient main-tenant de donner des modèles où on pourra donner un théorème de complétude.

Nous étudierons ici les modèles de Kripke. Considérons un langage du premier ordre L, que noussupposons sans symbole de fonction.

Un modèle de Kripke K est un quadruplet < K,Σ, C,D >, où :– K est un ensemble non vide partiellement ordonné ;– C est une fonction définie sur l’ensemble des constantes de L ;– D est une fonction qui à chaque élément k ∈ K associe un ensemble non vide D(k) ;– Σ est une fonction sur K vérifiant Σ(k) ⊆ Atk, où Atk est l’ensemble des formules atomiques de L

avec pour constantes les éléments de D(k).On demande que les relations suivantes soient satisfaites :

(i) D et Σ sont croissantes, i.e

k 6 l ⇒ D(k) ⊆ D(l) and Σ(k) ⊆ Σ(l);

(ii) ⊥ 6∈ Σ(k)

9

(iii) C(c) ∈ D(k) pour tous c et k

Les éléments de K sont appelés les mondes, et leurs images par D sont appelées les domaines (onp eutvoir D(k) comme l’ensemble des objets disponibles dans le monde k). Σ(k) liste l’ensemble des faitsbasiques qui ont été établis dans le monde k.

La condition (i) assure qu’en passant d’un monde à un monde "plus grand", les objets disponibles, etles résutlats établis ne sont pas oubliés.

La conditions (ii) assure qu’il est impossible que l’absurde soit vrai.

On notera dans la suite k ϕ pour ϕ ∈ Σ(k). On dit que le monde k force ϕ.

On peut montrer qu’il est possible d’étendre la fonction Σ pour que Σ(k) ⊆ Sentk, l’ensemble desformules avec paramètres dans D(k), et que cette extension vérifie :

(i) k ϕ ∨ ψ ⇔ k ϕ ou k ψ

(ii) k ϕ ∧ ψ ⇔ k ϕ et k ψ

(iii) k ϕ→ ψ ⇔ k pour tout ℓ > k, (ℓ ϕ implique ℓ ψ)

(iv) k ∃xϕ(x)⇔ il exist a ∈ D(k) tel que k ϕ(a)

(v) k ∀xϕx⇔ pour tout ℓ > k, et tout a ∈ D(ℓ), ℓ ϕ(a)

La condition (iii) nous amène :

Lemme 3.1

vérifie :– k ¬ϕ⇔ pour tout ℓ > k, ℓ 6 ϕ– k ¬¬ϕ⇔ pour tout ℓ > k, il existe p > ℓ tel que p ϕ

Démonstration. On rappelle que ¬ϕ est une abréviation pour ϕ→ ⊥. On a :

k ¬ϕ⇔ k ϕ← ⊥⇔ pour tout ℓ > k, (ℓ ϕ implique ℓ ⊥)

Mais il est impossible que ℓ ⊥. Donc

k ¬ϕ⇔ pour tout ℓ > k, ℓ 6 ϕ.

En applicant deux fois le premier point, on obtient le second.

Remarque – On remarque ici que k ϕ et k ¬¬ϕ sont deux choses différentes.

Proposition 3.2

La condition de monotonie de pour les atomes reste vraie pour les formules en général, i.e :

Pour tous k, l ∈ K, si k 6 ℓ et k ϕ alors ℓ ϕ.

Démonstration. Nous prouvons cette proposition par induction sur la formule ϕ :

10

– Si ϕ est un atome, le resultat est vrai par définition de .– Si ϕ = ψ∧σ. Soient k 6 ℓ des mondes, et supposons que k ϕ. Alors k ψ et k σ. Par hypothèse

d’induction, ℓ ψ et l σ, etdonc ℓ ϕ.– Les autres cas (ϕ = ψ∨σ, ψ → σ, ∃xψ(x), ∀xψ(x)) se traitent de la même manière, avec l’hypothèse

de croissance des domaines.

Regardons maintenant quelques exemples de modèles de Kripke. On les représente sous forme d’arbres,la relation 6 s’exprimant sous la forme : k 6 ℓ si et seulement si il y a un chemin de k à ℓ et l est plushaut que k.

Les prochains exemples n’illustreront pas de formules avec quantificateurs. Les domaines n’ont doncpas d’importance, et on peut choisir ce qu’on veut (e.g D(k) = {0}).Exemple –

k1 ϕ

k0

Dans cet exemple, on a K = k0, k1 avec k0 6 k1. k0 ne force rien, et k1 force ϕ. On a donc :

k0 6 ϕ et k1 ϕ.

On a donc, par le lemme 3.1, k0 ¬¬ϕ, et donc il s’ensuit

k0 6 ¬¬ϕ→ ϕ.

De plus, on remarque que k1 ϕ, donc toujours par le lemme 3.1, k0 6 ¬ϕ. Finalement,

k0 6 ϕ ∨ ¬ϕ.

Exemple –

k1 ϕ k2 ψ

k0

Aucun ki ne force ϕ ∧ ψ, et donc par le lemme 3.1, k0 ¬(ϕ ∧ ψ).

Maintenant, k1 ϕ et donc k0 6 6 ϕ, et k2 ¬ψ et donc k0 6 ψ. Donc k0 6 ¬ϕ ∨ ¬ψ.

11

Finalement :k0 6 ¬(ϕ ∧ ψ)→ ¬ϕ ∨ ¬ψ.

Dans les deux précédents exemples, on a donc des modèles où il existe des mondes qui ne forcent pascertaines lois de la logique classique (ici, le tiers-exclu, et une loi de Morgan).

Nous allons maintenant voir deux exemples avec des quantificateurs. Le domaine de chaque mondesera représenté dans un cercle.

Exemple –

k1 0,1 ϕ

k0 0

On a ici k1 σ(1), et donc k1 ∃xσ(x), d’où k0 ϕ→ ∃xσ(x).

Mais le seul objet du monde k0 est 0, et donc, comme k0 6 ϕ→ σ(0), on a k0 6 ∃x(ϕ→ σ(x).

Finalement :k0 6 (ϕ→ ∃xσ(x))→ ∃x(ϕ→ σ(x)).

Remarque – La formule (ϕ → ∃xσ(x)) → ∃x(ϕ → σ(x)) s’appelle le principe d’indépendance des

prémisses.

Exemple –

...

k3 0,1,2,3 ϕ(0), ϕ(1), ϕ(2)

k2 0,1,2 ϕ(0), ϕ(1)

k1 0,1 ϕ(0)

k0 0

12

On prend ici K = (kn)n∈N, D(kn) = {0, . . . , n} et Σ(kn) = {ϕ(0), . . . , ϕ(n − 1)}.On a alors pour tout i, ki ¬¬ϕ(j) pour tout j 6 i, et donc k0 ∀x¬¬ϕ(x).

Mais aucun kj ne force ∀xϕ(x), et donc k0 6 ¬¬∀xϕ(x).

Finalement :k0 6 ∀x¬¬ϕ(x)→ ¬¬∀xϕ(x).

Remarque – Cette dernière formule s’appelle DNS (Double Negation Shift).

Ainsi, pour ces quelques formules non dérivables en logique intuitionniste, nous avons trouvé desmodèles de Kripke qui les contredisent. Le théorème de complétude semble donc cohérent.

Pour nous en convaincre un peu plus, regardons un exemple de formule dérivable, et montrons qu’elleest forcée dans tous les modèles de Krikpe.

Exemple – On considère la formule

¬¬∀xϕx→ ∀x¬¬ϕ(x);

montrons qu’elle est forcée par tout monde dans tout modèle de Kripke.

Soit donc K =< K,Σ, C,D >, et soit i0 ∈ K un monde fixé.

Montrons quei0 ¬¬∀xϕx→ ∀x¬¬ϕ(x).

Pour cela, soit donc j0 un monde tel que j0 > i0, et j0 ¬¬∀xϕ(x). On cherche à montrer quej0 ∀x¬¬ϕ(x).

Développons ces formules pour y voir plus clair :

j0 ¬¬∀xϕ(x)

⇔∀k > j0 ∃ℓ1 > k ∀m > ℓ1 ∀a ∈ D(m) m ϕ(a) (⋆)

j0 ∀x¬¬ϕ(x)

⇔∀k > j0 ∀a ∈ D(k) ∀ℓ > k ∃m > ℓ m ϕ(a)

On voit intuitivement que c’est la place du ∃ qui va nous permettre de conclure.

Soient donc k > j0, a ∈ D(k) et ℓ > k. On cherche un monde m qui force ϕ(a).

ℓ > j0 par transitivité, et donc on peut choisir m = ℓ1, où ℓ1 est défini comme dans (⋆).

Avant de passer au théorème de complétude, donnons trois définitions :

Définition 3.3

On dit que :

13

(i) un monde force une formule avec des variables libres si il force sa clôture universelle :

k ϕ si et seulement si k Cl(ϕ).

(ii) un modèle de Kripke force une formule si elle est forcée par tous les mondes du modèle :

K ϕ si ∀k ∈ K, k ϕ.

(iii) une formule est forcée si elle est forcée par tous les modèles de Kripke :

ϕ si ∀K , K ϕ.

(iv) un ensemble de formules Γ force une formule ϕ avec variables libres ~x = x0, x1, . . . si :

∀K ∀k ∈ K ∀~a ∈ D(k), ((∀ψ ∈ Γ k ψ(~a))⇒ ϕ(~a)) .

3.1 Théorème de complétude de Kripke

On peut maintenant démontrer ce qu’on avait conjecturé avec nos exemples : la complétude des modèlesde Kripke pour la logique intuitionniste.

Théorème 3.4 : de complétude de Kripke

Une proposition de la logique intuitionniste est démontrable si et seulement si elle est forcée dans toutmodèle de Kripke, i.e :

Γ ⊢ ϕ⇔ Γ ϕ.

Commençons par la correction :

Théorème 3.5 : de correction

Toute proposition de la logique intuitionniste démontrable est forcée dans tout modèle de Kripke, i.e :

si Γ ⊢ ϕ alors Γ ϕ.

Démonstration. Soit ϕ une formule démontrable de la logique intuitionniste, et soit D une dérivationde Γ ⊢ ϕ. On va montrer le résultat par induction sur D . On se donne un modèle de Kripke K .

1. La dérivation D ne contient que ϕ. Il n’y a rien à faire, le résultat est clair.

2. La dérivation D se termine avec une règle d’introduction ou d’élimination.(∧I) ϕ = ψ ∧ σ. L’hypothèse d’induction est

∀k ∈ K ∀~a ∈ D(k) (∀ζ ∈ Γ, k ζ(~a)⇒ k ψ(~a))

et

∀k ∈ K ∀~a ∈ D(k) (∀ζ ∈ Γ, k ζ(~a)⇒ k σ(~a))

Soient donc k ∈ K et ~a ∈ D(k) tels que ∀ζ ∈ Γ, k ζ(~a).Alors k ψ(~a) et k σ(~a), et donc

k ϕ(~a).

14

(∧E) L’hypothèse d’induction sera

∀k ∈ K ∀~a ∈ D(k) (∀ζ ∈ Γ, k ζ(~a)⇒ k (ψ ∧ ϕ)(~a)) ,

et le résultat est donc trivial.(∨I) Un raisonnement analogue à (∧I) donne le résultat.(∨E) L’hypothèse d’induction sera :

∀k ∈ K ∀~a ∈ D(k) (∀ζ ∈ Γ, k ζ(~a)⇒ k (ψ ∨ σ)(~a))

et

∀k ∈ K ∀~a ∈ D(k) (∀ζ ∈ Γ ∪ {ψ}, k ζ(~a)⇒ k ϕ(~a))

et

∀k ∈ K ∀~a ∈ D(k) (∀ζ ∈ Γ ∪ {σ}, k ζ(~a)⇒ k ϕ(~a)) .

Soient donc k ∈ K et ~a ∈ D(k) tels que ∀ζ ∈ Γ, k ζ(~a).On a alors par hypothèse k (ψ ∨ σ)(~a), et donc k ψ(~a) ou k σ(~a). Dans les deux cas,k ϕ(~a).

(→ I) L’hypothèse d’induction est :

∀k ∈ K ∀~a ∈ D(k) (∀ζ ∈ Γ ∪ {ψ}, k ζ(~a)⇒ k σ(~a)) .

Soient donc k ∈ K et ~a ∈ D(k) tels que ∀ζ ∈ Γ, k ζ(~a).On veut montrer k (ψ → σ)(~a). Soit ℓ > k tel que ℓ ψ(~a). Par la proposition 3.2, on a∀ζ ∈ Γ, ℓ ζ(~a), et par croissance de D, ~a ∈ D(ℓ).Par hypothèse d’induction, ℓ σ(~a), d’où le résultat.

(→ E) Le résultat découle directement de la définition.(⊥) L’hypothèse d’induction est :

∀k ∈ K ∀~a ∈ D(k) (∀ζ ∈ Γ, k ζ(~a)⇒ k ⊥) .

Aucun monde ne force ⊥, et donc il est impossible qu’un monde force ζ(~a) pour tout ζ ∈ Γ.Donc

∀k ∈ K ∀~a ∈ D(k) (∀ζ ∈ Γ, k ζ(~a)⇒ k ϕ) .

(∀I) On suppose ici que les variables libres dans Γ sont ~x, et on prend z une variable qui n’estpas dans ~x.L’hypothèse d’induction est :

∀k ∈ K ∀~a, b ∈ D(k) (∀ζ ∈ Γ, k ζ(~a)⇒ k ψ(~a, b)) .

Soient donc k ∈ K et ~a ∈ D(k) tels que ∀ζ ∈ Γ, k ζ(~a). On veut montrer k ∀zψ(~a, z).Soit ℓ > k, soit b ∈ D(ℓ). Par monotonie, ℓ ζ(~a) pour tout ζ ∈ Γ, et ~a ∈ D(ℓ). Par hypothèsed’induction, ℓ ψ(~a, b), d’où le résultat.

(∀E) Découle directement de la définition.(∃I) Découle directement de la définition.

15

(∃E) L’hypothèse d’induction est :

∀k ∈ K ∀~a ∈ D(k) (∀ζ ∈ Γ, k ζ(~a)⇒ k ∃zψ(~a, z))

et

∀k ∈ K ∀~a, b ∈ D(k) (∀ζ ∈ Γ, k ζ(~a) et k ψ(~a, b)⇒ k ϕ(~a)) .

où les variables de Γ et ϕ sont ~x, et z n’est pas dans ~x. Soient donc k ∈ K et ~a ∈ D(k) telsque ∀ζ ∈ Γ, k ζ(~a).Alors k ∃z, ψ(~a, z), donc pour un certain b ∈ D(k), k ψ(~a, b). Par hypothèse d’induction,on a le résultat.

Il n’y a qu’un nombre fini d’étapes dans la déduction naturelle, il était donc facile de prouver lacorrection. L’autre sens va être plus difficile. Introduisons la notion de théorie première.

Définition 3.6

Un ensemble Γ de formules est une théorie première par rapport à un langage L si :

(i) Γ est fermé pour ⊢, i.e :si Γ ⊢ ψ alors ψ ∈ Γ.

(ii) si ϕ ∨ ψ ∈ Γ alors ϕ ∈ Γ ou ψ ∈ Γ.

(iii) si ∃xϕ(x) ∈ Γ alors il y a une constante c de L telle que ϕ(c) ∈ Γ.

Nous allons devoir dans la suite travailler avec des théories premières, d’où le lemme :

Lemme 3.7

Soit Γ un ensemble de formule closes, et soit ϕ une formule close. Alors si Γ 6⊢ ϕ, il existe une théoriepremière Γ′ sur un langage L′ qui étend Γ telle que Γ′ 6⊢ ϕ.

Démonstration. Considérons une extension L′ du langage L en lui ajoutant un nombre dénombrablede constantes. Nous allons construire une suite (Γk) d’ensembles de formules par induction.

– On pose Γ0 = Γ.– On suppose avoir construit Γk tel que Γk 6⊢ ϕ et tel que Γk ne contient qu’un nombre fini de nouvelles

constantes. Pour traiter les cas de la disjonction et du quantificateur existentiel, on va séparer lescas k pair et k impair.k pair : Considérons une formule de L′ de la forme ∃xψ(x) telle que Γk ⊢ ∃xψ(x) qui n’a pas encore

été traitée. Soit c une nouvelle constante, qui n’est pas dans Γk. On pose alors Γk+1 = Γk ∪ {c}.k impair : Considérons une formule de L′ de la forme ψ ∨σ telle que Γk ⊢ ψ ∨σ qui n’a pas encore

été traitée.Il est impossible que Γk, ψ ⊢ ϕ et Γk, σ ⊢ ϕ soient toutes les deux vraies en même temps, sinonon aurait Γk ⊢ ϕ, ce qui est exclu.Posons donc Γk+1 = Γk ∪ {ψ} si Γk, ψ 6⊢ ϕ, et Γk+1 = Γk ∪ {σ} sinon.

16

Montrons que cette construction permet bien de définir les Γk. Il est évident que chaque Γk n’a qu’unnombre fini de nouvelles constantes, il suffit donc de montrer que Γk 6⊢ ϕ pour tout k. Étant donnéela construction, une preuve par induction s’impose.Initialisation : Γ0 6⊢ ϕ par hypothèse.Hérédité : Soit i ∈ N, supposons Γk 6⊢ ϕ. Si k est pair, la construction de Γk+1 donne directement le

résultat.Si k est impair, supposons Γk+1 ⊢ ϕ. Alors on a

Γi, ψ(c) ⊢ ϕ et Γi ⊢ ∃xψ(x).

Par la règle (∃E), on a donc Γi ⊢ ϕ, ce qui contredit l’hypothèse.Notre suite (Γk) étant bien définie, et croissante, on pose

Γ′ =⋃

k∈N

Γk.

La construction des Γk nous donne directement Γ′ 6⊢ ϕ.

Il nous reste donc à montrer que Γ′ est une théorie première.

(i) Soit ψ ∨ σ ∈ Γ′, et soit k le plus petit entier tel que Γk ⊢ ψ ∨ σ.Alors par construction de Γk+1, on a ψ ∈ Γk+1 ou σ ∈ Γk+1. Finalement, ψ ∈ Γ′ ou σ ∈ Γ′.

(ii) Soit ∃xψ(x) ∈ Γ′, et soit k le plus petit entier tel que Γk ⊢ ∃xψ(x).Alors par construction, ψ(c) ∈ Γk+1 pour un certain c, et donc ψ(c) ∈ Γ′.

(iii) Si Γ′ ⊢ ψ, alors Γ′ ⊢ ψ ∨ ψ et donc ψ ∈ Γ′ par (i).

Nous allons maintenant construire un modèle répondant à certains critères.

Lemme 3.8 : d’existence d’un modèle

Soient Γ un ensemble de formule et ϕ une formule. Si Γ 6⊢ ϕ, alors il existe un modèle de Kripke K

avec un nœud minimal qui force Γ mais pas ϕ.

Démonstration. Commençons par considérer une théorie première Γ′ sur un langage L′ qui étend Γ ettel que Γ′ 6⊢ ϕ (lemme 3.7). L’ensemble des constantes de L′ est C ′.

Considérons maintenant un ensemble de nouvelles constantes deux à deux distinctes {cim | i > 0, m >

0} (i.e disjoint de C ′).

Alors Ci := {cim | m > 0} définit une famille dénombrable d’ensembles de constantes dénombrables.

Construisons maintenant notre ensemble de Kripke.

L’ensemble des mondes K sera l’ensemble des suites finies de N, avec la relation d’ordre "est préfixede".

On pose C(〈〉) := C ′, et pour ~n de longueur k > 0, C(~n) := C(〈〉) ∪ C0 ∪ . . . ∪ Ck−1.

17

On appellera L(~n) l’extension de L en rajoutant les contantes de C(~n), et At(~n) l’ensemble des atomes.

On définit D(~n) = C(~n).

Définissons une suite de théories premières Γ(~n), par induction sur ~n.

On pose Γ(〈〉) = Γ′. Supposons que l’on a construit Γ(~n) pour un certain ~n. Soient maintenant 〈σ0, τ0〉,〈σ1, τ1〉, . . . l’énumération des couples de formules de L(~n) tels que Γ(~n), σi 6⊢ τi. Par le lemme 3.7appliqué à Γ(~n) ∪ {σi} et τi, on obtient une théorie première, soit Γ(~n, i), qui vérifie σi ∈ Γ(~n, i) etΓ(~n, i) 6⊢ τi.

On pose maintenant Σ(~n) = Γ(~n) ∩At(~n) pour tout monde ~n.

Par construction, il est assez clair que K ainsi défini est un modèle de Kripke.

Prouvons maintenant par induction sur ψ l’affirmation suivante :

~n ψ ⇔ Γ(~n) ⊢ ψ. (⋆)

– ψ est un atome : l’équivalence est immédiate par construction.– ψ = ψ1 ∧ ψ2 :

(⇒) Supposons ~n ψ1 ∧ ψ2.Alors ~n ψ1 et ~n ψ2. Par hypothèse d’induction, Γ(~n) ⊢ ψ1 et Γ(~n) ⊢ ψ2, et donc Γ(~n) ⊢ ψ1∧ψ2.(⇐) Supposons Γ(~n) ⊢ ψ1 ∧ ψ2. Alors par la règle (∧E), Γ(~n) ⊢ ψ1 et Γ(~n) ⊢ ψ2. Par hypothèsed’induction, on a le résultat.

– ψ = ψ1 ∨ ψ2 :(⇒) Supposons ~n ψ1 ∨ψ2. Alors ~n ψ1 ou ~n ψ2. Dans les deux cas, par hypothèse d’inductionet (∨I), Γ(~n) ⊢ ψ1 ∨ ψ2.(⇐) Supposons Γ(~n) ⊢ ψ1 ∨ ψ2. On a vu dans la construction que Γ(~n) était une théorie première,donc Γ(~n) ⊢ ψ1 ou Γ(~n) ⊢ ψ2. Par hypothèse d’induction, on a le résultat.

– ψ = ψ1 → ψ2 :(⇒) Supposons ~n ψ1 → ψ2, et que Γ(~n) 6⊢ ψ1 → ψ2, i.e Γ(~n), ψ1 6⊢ ψ2.Par construction des Γ(~m), il existe un ~m tel que Γ(~n) ∪ {ψ1} ⊆ Γ(~m), et Γ(~m) 6⊢ ψ2.On a en particulier Γ(~m) ⊢ ψ1, et donc par hypothèse d’induction :

~m ψ1 et ~m 6 ψ2,

ce qui est impossible.(⇐) Supposons Γ(~n) ⊢ ψ1 → ψ2. On veut montrer

∀~m > ~n, ~m ψ1 ⇒ ~m ψ2.

Soit donc ~m > ~n tel que ~m ψ1.On a alors Γ(~m) ⊢ ψ1 par hypothèse d’induction.Or Γ(~n) ⊆ Γ(~m), et Γ(~n) ⊢ ψ1 → ψ2, donc Γ(~m) ⊢ ψ1 → ψ2.Par modus ponens, Γ(~m) ⊢ ψ2. On conclut par hypothèse d’induction : ~m ψ2.

– ψ = ∀xψ1(x).(⇒) Supposons ~n ∀xψ1(x), et Γ(~n) 6⊢ ∀xψ1(x).Alors pour un certain i, Γ(~n, i) 6⊢ ∀xψ1(x).Soit c une constante dans L(~n, i)\Γ(~n, i).Alors Γ(~n, i) 6⊢ ψ1(c), et donc par hypothèse d’induction, (~n, i) 6 ψ1(c).

18

(⇐) Supposons Γ(~n) ⊢ ∀xψ1(x), et ~n 6 ∀xψ1(x).Alors il existe un monde ~m > ~n et une constante c ∈ D(~m).Donc Γ(~m) 6⊢ ψ1(x), d’où Γ(~m) 6⊢ ∀xψ1(x), et donc Γ(~n) 6⊢ ∀xψ1(x) car Γ(~n) ⊆ Γ(~m). On a doncune contradiction.

– ψ1 = ∃xψ1(x)(⇒) Supposons ~n ∃xψ1(x).Alors ∃c ∈ D(~n), ~n ψ1(c), donc ∃c ∈ L(~n), Γ(~n) ⊢ ψ1(c), et pour finir Γ(~n) ⊢ ∃cψ1(c).(⇐) Supposons Γ(~n) ⊢ ∃xψ1(x).Alors ∃c ∈ L(~n), Γ(~n) ⊢ ψ1(c), i.e ~n ψ1(x).

L’affirmation (⋆) est donc démontrée.

On a alors :〈〉 Γ car Γ(〈〉) ⊢ Γ

et

〈〉 6 ϕ car Γ′ 6⊢ ϕ.

On a maintenant tous les outils pour prouver le théorème de complétude de Kripke :

Théorème 3.9 : de complétude de Kripke

Pour Γ et ϕ fermés, on a :Γ ⊢i ϕ⇔ Γ ϕ.

Démonstration. On a déjà montré le sens direct (théorème 3.5). Pour le sens inverse, supposons Γ 6⊢i ϕ.En appliquant le lemme 3.8, on construit un modèle de Kripke ayant un monde k tel que k Γ etk 6 ϕ, d’où Γ 6 ϕ.

3.2 Application : Définitions des connecteurs intuitionnistes

Dans cette partie, nous allons montrer que contrairement à la logique classique, il est impossible enlogique intuitionniste d’exprimer les connecteurs en fonction des autres. Commençons par définir cettenotion de définition.

Définition 3.10

On dit qu’une formule ϕ définit un connecteur � avec les connecteurs △1, . . . ,△k si :

(i) ϕ ne contient que les atomes p et q, les connecteurs △1, . . . ,△k et ne contient par le connecteur�.

(ii) ⊢i p�q ↔ ϕ.

On dit qu’un connecteur � est défini par les connecteurs △1, . . . ,△k s’il existe une formule ϕ commeci-dessus.

19

On a alors des résultats pour la logique propositionnelle :

Proposition 3.11

On ne peut pas définir ∧ avec les connecteurs →,∨,⊥.

Démonstration. Supposons qu’il existe ϕ qui définit ∧ avec →,∨,⊥.

Considérons le modèle de Kripke suivant :

k3 p,q

k1 p k2 q

Montrons le résultat suivant par induction sur la formule F :

Soit F une formule ayant pour atomes p et q, et ne contenant pas le connecteur ∧. Alors on a soit⊢i F ↔ ⊥, soit k1 F ou k2 F .

– Si F est p,q ou ⊥, le résultat est évident.– Si F est ψ ∨ σ :

si ψ et σ sont équivalents à ⊥, alors F aussi ;sinon, l’un des deux est forcé par k1 ou k2, et donc F aussi.

– Si F est ψ → σ : il suffit de vérifier tous les cas :– si ψ est équivalent à ⊥, alors F est vérifiée partout ;– si ψ est forcée par k1 et σ est équivalent à ⊥, alors F est équivalent à ⊥ ;– si k1 force ψ et σ, alors k1 force ψ → σ car k3 > k1 et par monotonie de ;– si k1 force ψ et k2 force σ, alors k2 force ψ → σ.Les autres cas sont symétriques.

On a donc montré le résultat voulu. ϕ rentre dans ce cas, et on a donc ⊢i ϕ↔ ⊥ ou k1 ϕ ou k2 ϕ.

Si un des ki force ϕ, alors ki force p ∧ q ce qui est faux.

Si ϕ↔ ⊥, alors p ∧ q ↔ ⊥, ce qui est faux aussi.

Proposition 3.12

On ne peut pas définir → avec les connecteurs ∨,∧,⊥,¬.

Démonstration. Supposons qu’il existe ϕ qui définit → avec ∨,∧,¬,⊥.

Considérons le modèle de Kripke suivant :

k3 p,q

k1 p k2

20

Montrons par induction sur la formule F le résultat suivant :

Si F est une formule avec les atomes p et q, et ne contenant pas →, alors si k2 F alors k1 F .

– Si F est p,q ou ⊥ c’est évident.– Si F est ψ ∨ σ :

si k2 F , alors k2 ψ ou k2 σ, et donc on a le résultat par hypothèse d’induction sur ψ et σ.– Si F est ψ ∧ σ :

si k2 F , alors k2 ψ et k2 σ, et donc on a le résultat par hypothèse d’induction sur ψ et σ.– Si F est ¬ψ :

supposons k2 F , i.e k2 6 ψ et k3 6 ψ, et montrons que k1 F , i.e k1 6 ψ et k3 6 ψ.On a directement k3 6 ψ. Si on avait k1 ψ, alors par monotonie de , on aurait k3 ψ ce quicontredit l’hypothèse.

On a donc le résultat voulu. En l’appliquant à notre formule ϕ, comme k2 p → q, on auraitk1 p→ q et donc k1 q, ce qui est faux.

Proposition 3.13

On ne peut pas définir ∨ avec les connecteurs ∧,⊥,→.

Démonstration. Supposons qu’il existe ϕ qui définit ∨ avec ∧,⊥,→.

Considérons le modèle de Kripke suivant :

k1 p k2 q

k3

Montrons le résultat suivant par induction sur la formule F :

Si F est une formule avec les atomes p et q, et ne contenant pas ∨, alors k1 et k2 forcent F si etseulement si k3 force F .

Le sens réciproque est évident par monotonie de . regardons donc uniquement le sens direct.– Si F est p,q ou ⊥, le résultat est évident.– Si F est ψ ∧ σ :

Supposons k1 F et k2 F . Alors k1 et k2 forcent tous les deux ψ et σ, et donc k3 force ψ et σpar hypothèse d’induction.D’où le résultat.

– Si F est ψ → σ :Supposons k1 F et k2 F , et k3 6 F .Si ψ est forcé par k1 et k2, alors σ aussi, et donc par hypothèse d’induction, on a k3 ψ → σ.Si ψ n’est forcé que par un monde, par exemple k1, alors ψ n’est pas forcé par k3 par hypothèsed’induction, et σ est forcé par k1. On a donc k3 ψ → σ.Si ψ n’est forcé ni dans k1 ni dans k2, le résultat est évident.

21

On a donc le résultat voulu. En l’appliquant à notre formule ϕ, comme k1 p ∨ q et k2 p ∨ q, on ak3 p ∨ q, ce qui est faux.

4 Calcul des séquents en logique intuitionniste

On parlera dans cette section uniquement de logique intuitionniste propositionnelle, c’est-à-dire sansquantificateurs.

Les modèles de Kripke propositionnels sont plus simples : la notion de domaine d’un monde n’intervientpas.

Définition 4.1

Un modèle de Kripke K est dit contre-modèle du séquent 〈 Γ ⇒ ∆ 〉 s’il exsite un monde de K quisatisfait toutes les formules de Γ et aucune formule de ∆.

Un séquent 〈 Γ ⇒ ∆ 〉 est dit intuitionnistiquement tautologique s’il n’admet pas de contre-modèle.

Remarque – Si dans un modèle de Kripke, un monde r est plus petit que tous les autres, nousl’appellerons la racine du modèle.

Sans perte de généralité, si dans la suite on considère un contre-modèle, on pourra supposer que lemonde contredisant le séquent est la racine du modèle.

Nous essayerons dans cette section de trouver un algorithme qui décide si un séquent est intuitionnis-tiquement tautologique ou non.

Définition 4.2

Une règle de calcul des séquents est de la forme A,B / C (règle binaire) ou A / C (règle unaire), oùA,B et C sont des séquents.

Une règle binaire est dite correcte si :

Si A et B sont intuitionnistiquement tautologiques, alors C aussi.

Une règle binaire est dite inversible si :

A et B sont intuitionnistiquement tautologiques si et seulement si C l’est.

Les définitions de correction et d’inversibilité sont les même pour les règles unaires, en remplaçant Aet B par A.

Ce sont ces règles qui vont nous permettre de construire notre algorithme.

22

4.1 Séquent à conclusion unique

On ne s’intéresse dans cette partie qu’à des séquents de la forme 〈 Γ ⇒ G 〉 où Γ est un ensemble deformules, et G une formule.

Commençons par donner une liste de règles :

〈 Γ ⇒ G 〉 , 〈 Γ ⇒ F 〉 / 〈 Γ ⇒ E ∧ F 〉 (1)

〈 Γ, E, F ⇒ G 〉 / 〈 Γ, E ∧ F ⇒ G 〉 (2)

〈 Γ, E ⇒ G 〉 , 〈 Γ, F ⇒ G 〉 / 〈 Γ, E ∨ F ⇒ G 〉 (3)

〈 Γ, E ⇒ F 〉 / 〈 Γ ⇒ E → F 〉 (4)

〈 Γ, p,D ⇒ G 〉 / 〈 Γ, p, p→ D ⇒ G 〉 (5)

〈 Γ ⇒ E 〉 / 〈 Γ ⇒ E ∨ F 〉 (6)

〈 Γ ⇒ F 〉 / 〈 Γ ⇒ E ∨ F 〉 (6)

〈 Γ, C → D ⇒ C 〉 , 〈 Γ,D ⇒ G 〉 / 〈 Γ, C → D ⇒ G 〉 (7)

〈 Γ,D ⇒ G 〉 / 〈 Γ,D,C1 → (C2 → (· · · → (Ck → D) · · · ) ⇒ G 〉 (8)

〈 Γ, A→ (B → D) ⇒ G 〉 / 〈 Γ, (A ∧B)→ D ⇒ G 〉 (9)

〈 Γ, A→ D,B → D ⇒ G 〉 / 〈 Γ, (A ∨B)→ D ⇒ G 〉 (10)

〈 Γ, A,B → D ⇒ B 〉 / 〈 Γ, (A→ B)→ D ⇒ A→ B 〉 (11)

On a le résultat suivant :

Lemme 4.3

Les règles (1) à (5) sont correctes et inversibles.

Les règles (6) et (7) sont correctes.

Les règles (8) à (11) sont correctes et inversibles.

Démonstration. Les démonstrations se feront par contraposée.

(1) Supposons que 〈 Γ ⇒ E 〉 n’est pas intuitionnistiquement tautologique. Soit donc K un contre-modèle de Kripke.Alors K est aussi un contre-modèle pour 〈 Γ ⇒ E ∧ F 〉.Supposons maintenant que 〈 Γ ⇒ E ∧ F 〉 n’est pas intuitionnistiquement tautologique. Soit K

un contre-modèle de Kripke.Alors K est aussi un contre-modèle pour 〈 Γ ⇒ E 〉 ou pour 〈 Γ ⇒ F 〉.

(2) à (6) sont évidents en appliquant directement les définitions, comme pour (1).

(7) Supposons que 〈 Γ, C → D ⇒ G 〉 n’est pas intuitionnistiquement tautologique, et soit K uncontre-modèle de Kripke.Montrons que 〈 Γ, C → D ⇒ C 〉 ou 〈 Γ,D ⇒ G 〉 n’est pas intuitionnistiquement tautologique.On a une racine a de K telle que :– a Γ– a C → D

23

– a 6 GSi a force C, alors nécessairement a force aussi D, et donc K est un conttre-modèle pour〈 Γ,D ⇒ G 〉.Si a ne force pas C, alors c’est 〈 Γ, C → D ⇒ C 〉 qui n’est pas intuitionnistiquement tautolo-gique.

(8) La correction est évidente.Supposons donc que 〈 Γ,D ⇒ G 〉 n’est pas intuitionnistiquement tautologique, avec un contre-modèle K et une racine a qui falsifie le séquent.Construisons un monde b̂ de la façon suivante :– Si pour tout monde b > a on a b 6 C1, on pose b̂ = a ;

sinon, il existe un monde b1 > a qui force C1.– Si pour tout monde b > b1 on a b 6 C2, on pose b̂ = b1 ;

sinon, il existe un monde b2 > b1 qui force c2.

–...

– Si pour tout monde b > bk−1, on a b 6 Ck, on pose b̂ = bk−1 ;sinon, il existe bk > bk−1 qui force Ck. On pose alors b̂ = bk.

On a alors :– b̂ Γ, b̂ D et b̂ 6 G car b̂ > a.– b̂ C1 → (C2 → (· · · → (Ck → D) · · · ) par construction de b̂.

(9) à (11) sont évidents.

Nous avons maintenant toutes les règles qui nous permettront de construire notre procédure de déci-sion.

Commençons par regarder des séquents particuliers, les séquents irréductibles :

Définition 4.4

Un séquent 〈 Γ ⇒ G 〉 est dit irréductible si :– G est une disjonction, un atome qui n’est pas dans Γ ou l’absurde.– Γ ne contient ni disjonction, ni conjonction, ni l’absurde.– Γ ne contient pas de couples de formules de la forme p, p→ D où p est un atome.

On a alors, pour les séquents de ce type, une caractérisation :

Théorème 4.5

Soit 〈 Γ ⇒ G 〉 un séquent irréductible.

Alors il est intuitionnistiquement tautologique si et seulement si l’une des conditions suivantes estsatisfaite :

(i) G = E ∨ F et 〈 Γ ⇒ E 〉 ou 〈 Γ ⇒ F 〉 est intuitionnistiquement tautologique.

(ii) Il y a une implication C → D dans Γ, avec C composée ( i.e no un atome, ni l’absurde) telle que〈 Γ ⇒ C 〉 et 〈 Γ\{C → D},D ⇒ G 〉 soient tous les deux intuitionnistiquement tautologiques.

24

Démonstration. Le sens réciproque est évident en appliquant la règle (6) dans le cas (i), et la règle(7) dans le cas (ii).

Regardons donc le sens direct.

〈 Γ ⇒ G 〉 est irreductible, donc on peut supposer que G est de la forme E ∨ F (si G est un atomeou l’absurde, la démonstration est similaire).

Commençons par faire la liste de toutes les implications Ci → Di dans Γ, 1 6 i 6 m, avec les Ci

composées.

Supposons que 〈 Γ ⇒ E 〉 et 〈 Γ ⇒ F 〉 ne sont pas intuitionnistiquement tautologiques, et quepour tout i, un des deux 〈 Γ\{Ci → Di ⇒ G 〉 n’est pas intuitionnistiquement tautologique.

Dans le cas où 〈 Γ\{Ci → Di},Di ⇒ G 〉 n’est pas intuitionnistiquement tautologique, le contre-modèle pour ce séquent sera aussi un contre-modèle pour 〈 Γ ⇒ G 〉.En effet, si K est le contre-modèle considéré, avec une racine a, deux cas se présentent :– si Ci n’est forcé dans aucun monde, alors a Ci → Di, et donc a Γ.– sinon, il existe un monde b qui force Ci, et Di par monotonie, et donc b Ci → Di, i.e b Γ.On peut donc maintenant supposer que c’est 〈 Γ ⇒ Ci 〉 qui n’est pas intuitionnistiquement tauto-logique.

On considère les contre-modèles suivants :– pour tout i, Ki est un contre-modèle de 〈 Γ ⇒ Ci 〉 avec une racine ai ;– Km+1 est un contre-modèle de 〈 Γ ⇒ E 〉 avec une racine am+1 ;– Km+2 est un contre-modèle de 〈 Γ ⇒ F 〉 avec une racine am+2 ;On considère alors le modèle de Kripke K construit comme sur le dessin suivant :

K1 K2 Km+1 Km+2

a1 a2 am+1 am+2

a

b b b

où la racine du modèle a force les atomes dans Γ, et ne force pas les autres.

On a alors ai 6 Ci, et donc par monotonie de , a 6 Ci non plus. De la même façon, on montre quea 6 E et a 6 F .

25

Il reste maintenant à montrer que les formules de Γ sont forcées par le monde a.

〈 Γ ⇒ G 〉 est irréductible, et donc Γ ne contient que des atomes et des implications.

Les atomes de Γ sont forcés par a par définition du modèle K .

Pour les implications, il suffit de remarquer que pour tout monde k de K , excepté a, k force toutesles formules de Γ. Il nous reste donc seulement à montrer que a force les implications de Γ.

Comme a ne force pas les Ci, a force bien les implications Ci → Di. De la même façon, si p → Dest dans Γ, avec p un atome, alors p n’est pas dans Γ par définition d’irréductibilité, et donc a forcep→ D car a ne force pas p.

Il est maintenant temps de donner l’algorithme de décision ; il commence par transformer le séquenten un séquent irréductible, afin d’y appliquer le théorème 4.5. On construit donc une fonction S quiprend un séquent 〈 Γ ⇒ G 〉 en paramètre et qui renvoie true ou false. Celle fonction (récursive)fonctionne comme suit :

(a) Si G est E ∧ F , alors S(〈 Γ ⇒ G 〉) renvoie true si S(〈 Γ ⇒ E 〉) et S(〈 Γ ⇒ F 〉) renvoienttous les deux true, et false sinon. (On utilise ici la règle (1).)Si G est E → F , alors S(〈 Γ ⇒ G 〉) renvoie la même chose que S(〈 Γ, E ⇒ F 〉) (règle (4)).So Γ contient des formules du type E ∧ F , E ∨ F , (A ∧B)→ D ou (A ∨B)→ D, alors on utiliserespectivement les règles (2),(3),(9) et (10). Par exemple, dans le premier cas, S(〈 Γ ⇒ G 〉)renvoie la même chose que S(〈 Γ\{E ∧ F}, E, F ⇒ G 〉).

(b) Si Γ contient une paire p, p → D où p est un atome, alors dans Γ on remplace p → D par D(règle (5)), on enlève toutes les formules du type C1 → (· · · → (Ck → D) · · · ) (règle (8) autant defois que nécessaire), et alors S(〈 Γ ⇒ G 〉) renvoie la même chose que l’appel de S sur le séquentainsi construit.

(c) Si Γ contient l’absurde, ou si G est un atome de Γ, alors S(〈 Γ ⇒ G 〉) renvoie true.

(d) Si G est E∨F , alors S(〈 Γ ⇒ G 〉) renvoie true si l’un des deux S(〈 Γ ⇒ E 〉) ou S(〈 Γ ⇒ F 〉)renvoie true, et false si les deux renvoient false.

(e) On liste toutes les implications de Γ qui ont un prémisse composé : (A1 → B1)→ D1, . . . , (Am →Bm)→ Dm. On pose

Γi := Γ\{(Ai → Bi)→ Di}et

Γ−i := Γi\{C1 → (· · · → (Ck → Di) · · · ) | k}.

Pour tout i entre 1 et m, on appelle S(〈 Γi, Ai, Bi → Di ⇒ Bi 〉) et S(⟨

Γ−i ,Di ⇒ G

⟩)

. Sipour un certain i les deux renvoient true, alors S(〈 Γ ⇒ G 〉) renvoie true, et sinon S(〈 Γ ⇒ G 〉)renvoie false.

On a alors le théorème :

Théorème 4.6

L’algorithme expliqué précédemment décide si un séquent est intuitionnistiquement tautologique, entemps polynomial.

26

Démonstration. La preuve est longue et technique. L’idée générale consiste à associer à chaque séquentun poids, puis de construire l’arbre de séquents de l’algorithme.

On montre que le poids décroit, et ainsi les branches de l’arbre auront une taille finie (polynomialeen le poids du séquent de départ), ce qui prouve que l’algorithme termine correctement, en tempspolynomial.

Pour les détails, on pourra lire [6].

Remarque – J. Hudelmaier a construit un algorithme plus performant que celui-ci dans AnO(n log n)-space decision procedure for intuitionistic propositional logic.

4.2 Séquent à conclusion multiple

Dans la partie précédente, nous n’avons regardé que les séquents dont la conclusion était une formule.Nous allons regarder ici les séquents dont la conclusion est un ensemble de formules, appelés séquents

à conclusion multiple.

Nous appellerons séquents initiaux les séquents 〈 Γ, p ⇒ ∆, p 〉 et 〈 Γ,⊥ ⇒ ∆ 〉 où p est un atome,et nous utiliserons les règles suivantes :

〈 Γ ⇒ ∆, A ∧B,A 〉 , 〈 Γ ⇒ ∆, A ∧B,B 〉 / 〈 Γ ⇒ ∆, A ∧B 〉 (12)

〈 Γ ⇒ ∆, A ∨B,A,B 〉 / 〈 Γ ⇒ ∆, A ∨B 〉 (13)

〈 Γ, A ⇒ B 〉 / 〈 Γ ⇒ ∆, A→ B 〉 (14)

〈 Γ ⇒ ∆, A→ B,B 〉 / 〈 Γ ⇒ ∆, A→ B 〉 (15)

〈 Γ, A ∧B,A,B ⇒ ∆ 〉 / 〈 Γ, A ∧B ⇒ ∆ 〉 (16)

〈 Γ, A ∨B,A ⇒ ∆ 〉 , 〈 Γ, A ∨B,B ⇒ ∆ 〉 / 〈 Γ, A ∨B ⇒ ∆ 〉 (17)

〈 Γ, A→ B ⇒ ∆, A 〉 , 〈 Γ, A→ B,B ⇒ ∆ 〉 / 〈 Γ, A→ B ⇒ ∆ 〉 (18)

Lemme 4.7

Les règles (12) à (18) sont correctes et inversibles, sauf la règle (14) qui est correcte mais pas inversible.

Démonstration. Comme dans le lemme 4.3, les preuves se font aisément, par contraposée.

Définition 4.8

Un séquent 〈 Γ ⇒ ∆ 〉 est saturé si les conditions suivantes sont satisfaites :– Si A ∧B ∈ Γ (resp. A ∨B ∈ ∆), alors les deux formules A et B sont dans Γ (resp. dans ∆).– Si A ∨B ∈ Γ (resp. A ∧B ∈ ∆), alors l’une des deux formules A et B est dans Γ (resp. dans ∆).– Si A→ B ∈ Γ, alors A ∈ ∆ ou B ∈ Γ.– Si A→ B ∈ ∆, alors B ∈ ∆.

On a alors une caractérisation des séquents saturés intuitionnistiquement tautologiques :

27

Théorème 4.9

Un séquent saturé 〈 Γ ⇒ ∆ 〉 est intuitionnistiquement tautologique si et seulement s’il est initial,ou s’il existe une formule A → B ∈ ∆ telle que A 6∈ Γ et 〈 Γ, A ⇒ B 〉 soit intuitionnistiquementtautologique.

Démonstration. Le sens réciproque est évident avec la règle (14).

Soit donc 〈 Γ ⇒ ∆ 〉 un séquent saturé intuitionnistiquement tautologique, non initial.

On considère la liste A1 → B1, . . . , Am → Bm des implications de ∆ telles que Ai 6∈ Γ, et on supposequ’aucun des séquents 〈 Γ, Ai ⇒ Bi 〉 n’est intuitionnistiquement tautologique.

Soient K1, . . . ,Km des contre-modèles pour les 〈 Γ, Ai ⇒ Bi 〉, avec des racines respectives ai.

Soit K le modèle de Kripke construit à partir des K1, . . . ,Km comme dans le théorème 4.5, avec pourracine a, où a force uniquement les atomes de Γ.

Montrons par induction sur une formule D que :

Si D ∈ Γ alors a D, et si D ∈ ∆ alors a 6 D.

– Si D est un atome de Γ, alors a D par définition de a.Si D est un atome de ∆, alors comme 〈 Γ ⇒ ∆ 〉 n’est pas initial, D n’est pas dans Γ, et donca 6 D.Si D est ⊥, le résultat est évident.

– Si D ∈ ∆ est A ∧B, alors A ∈ ∆ ou B ∈ ∆.Par hypothèse d’induction, a 6 A ou a 6 B, et donc a 6 A ∧B.

– Si D ∈ Γ est A ∨B, alors A ∈ ∆ et B ∈ ∆, et donc a 6 A ∨B par hypothèse d’induction.– Si D ∈ ∆ est A→ B, deux cas se présentent :

– si A→ B est Ai → Bi, alors ai A et ai 6 B, et donc a 6 A→ B.– si A → B n’est aucun des Ai → Bi, alors A ∈ Γ. Comme 〈 Γ ⇒ ∆ 〉 est saturé, on a aussiB ∈ ∆.Par hypothèse d’induction, on a alors a A et a 6 B, et donc a 6 A→ B.

– Si D ∈ Γ est A ∨B, alors A ∈ Γ ou B ∈ Γ, et donc a A ∨B par hypothèse d’induction.– Si D ∈ Γ est A ∧B, alors A ∈ Γ et B ∈ Γ, et donc a A ∧B par hypothèse d’induction.– Si D ∈ Γ et A→ B, il faut montrer que pour tout b > a, si b A alors b B. Si b est différent dea, alors e résultat est évident car les ai forcent toutes les formules de Γ, donc D en particulier.Sinon, l’hypothèse de saturation nous donne A ∈ ∆ ou B ∈ Γ, c’est-à-dire a 6 A ou a B parhypothèse d’induction, et donc on a le résultat.

On peut maintenant décrire l’algorithme M :

(a) Si ∆ contient une formule du type A ∧ B avec A,B 6∈ ∆, alors M(〈 Γ ⇒ ∆ 〉) renvoie true siM(〈 Γ ⇒ ∆, A 〉) et M(〈 Γ ⇒ ∆, B 〉) renvoient tous les deux true, et false sinon.Appliquer les règles (13),(15),(16),(17) et (18) autant que possible, tant que les sous-appels de Mont des paramètres différents de 〈 Γ ⇒ ∆ 〉.

28

(b) Quand (a) n’est plus applicable, le séquent 〈 Γ ⇒ ∆ 〉 est saturé. Alors M(〈 Γ ⇒ ∆ 〉) renvoietrue si ⊥ ∈ Γ ou si Γ et ∆ ont un atome en commun, et passe à (c) sinon.

(c) Si ni (a) ni (b) ne sont applicables, alors on crée la liste des implications Ai → Bi dans ∆ avecAi 6∈ Γ. On calcule les M(〈 Γ, Ai ⇒ Bi 〉) et on renvoie true si l’un des appels renvoie true, etfalse sinon.

Théorème 4.10

l’algorithme détaillé ci-dessus décide si un séquent est intuitionnistiquement tautologique, avec unecomplexité en O(n2), où n est le nombres de connecteurs logiques du séquent.

Démonstration. De même que pour les séquents à conclusion unique, la preuve est technique. On peutla trouver dans [6].

29

Références

[1] Anne Sjerp Toelstra : History of construtivism in the Twentieth Century. 1991.

[2] Dirk Van Dalen : Intuitionistic Logic. In The Blackwell guide to philosophical logic, chapitre 11.2001.

[3] Dirk Van Dalen : Intuitionistic Logic. In Handbook of philosophical logic, volume 5, chapitre 1.2nd édition, 2002.

[4] Dirk Van Dalen : Logic and structures. 4th édition, 2004.

[5] Joseph Vidal-Rosset : L’argument de Russel-Tennant. 2005.

[6] Vítěslav Švejdar : On Sequent Calculi for Intuitionistic Propositional Logic. 2005.

30