CONSIDERATIONS HEURISTIQUES SUR LES MÉTHODESDE DÉDUCTION PAR SÉQUENCES

E. W. BETH

1. L' int roduc t ion des systèmes L j et LK n'est justif iée chez Gentzenque par les applicat ions importantes qu' ils permettent. Ce n'est querécemment que des recherches, notamment de Hint ik k a et de l 'Au-teur, ont donné une explicat ion de la curieuse structure de ces systè-mes. Cependant, cet te explicat ion n'es t pas complète étant donnéque, pour la logique intuit ioniste, la méthode des tableaux sémant i-ques du présent auteur donne lieu à un système formel Fo q u i n e r é -pond pas exactement au système I J de Gentzen (bien qu' i l l u i soitéquivalent).

Dans cette note, je veux présenter quelques considérations heuris-tiques qui, me semble-t-il, pourront contribuer à rendre plus compré-hensible la curieuse structure des systèmes L.1 et LK de Gentzen. I ls'agira notamment d'éluc ider les deux points suivants:

1'. L' int roduct ion de séquences dont le conséquent f ait intervenirplusieurs formules;

2'. Le fait qu'un calcul intuit ionis te est obtenu dès que le nombredes formules dans le conséquent est l imit é à (zéro ou) un.

2. 11 ne sera pas nécessaire de sort ir du cadre restreint de la logi-que de l' implicat ion. Comme formules nous admettons tous les ato-mes A , B, C, e t , s i U et V sont des formules, également I J —I V . S iK = f Ul, U 2 , 141 et L = {V1, V2, Va} sont des ensembles

quelconques de formules, alors K/L, ou:U,„ Um)/(V1, V2, —, ,

sera une séquence avec l'antécédent K et le conséquent L.

3. No u s considérons d'abord des séquences K / Z dont l e consé-quent se constitue d'une seule f ormule Z. D'une manière f ort natu-relle une telle séquence peut être interprétée comme expression d'uncertain problème de déduction:

en partant des prémisses K , déduire la conclusion Z

Le calcul de séquences se constituera de règles permettant la réduc-t ion d'un tel problème à des problèmes plus s imples ou la c lôtured'une suite de réduct ions successives lorsqu'elle résulte dans la dé-duction proposée. Le but de notre discussion sera d'établir des règles

153

motivées au préalable par des considérat ions aussi plaus ibles quepossible. Not re princ ipale source d' inspirat ion sera le modus ponens.

4. C e mot i f peut êt re appliqué «à rebours» lorsqu' i l s 'agit d ' unproblème de type K / U —> V. Si ce problème était résolu, alors noussaurions également résoudre le problème (K , LI )/V A l o r s i l paraitraisonnable de permet t re la réduct ion du premier problème au se-cond, ce qui s 'exprime par le schéma de réduction:

154

(in

Prémisses

Cela revient , en somme, à supposer que la f ormule U •--> , unefois qu'elle sera établie, ne pourra servir à rien excepté à une appli-cation du modus ponens.

5. S i nous nous t rouvons devant u n problème ( K , U V ) / Z , i lsera raisonnable d'essayer de prof iter de la prémisse U —› V e n ap-pliquant le modus ponens aux deux formules U e t U ---> V , ce quiexige pourtant de déduire d'abord la formule U . Cela rev ient à uneréduction du problème original aux deux problèmes suivants:

(i) e n partant de (K, U —› V) , déduire U [et ensuite V] ;(ij) en partant de (K, U --->V, V) , déduire Z

ou, sous forme d'un schéma de réduction:

Prémisses

—) V

6. L e schéma de clôture:

(i)

Prémisses

n'a pas besoin d'être expliqué.

Conclusions

Conclusions

U —› V

(ID

Conclusions

7. Malheureusement , les schémas ( i ) , ( i jaI ) e t ( i jb) n e suff isentpas pour effectuer toutes les déductions qui, au point de vue de lalogique classique, sont acceptables et même indispensables. A t it red'exemple, i l convient de discuter le problème représenté par la sé-quence 0/ [ (A -4B) -4 Al —9A V o i c i le tableau déduct if qui lu i corres-pond:

(1) (A B ) -+ A [prémisse](2) A -› B [supposée déduct ible](3)

A [modus ponensl(4) B [modus ponension

( ip)(ijal)

(i)

Prémisses

(A--->B) -> A

A

Conclusions

[...] - AA

(I)A -+ B

Le problème original se réduit donc aux deux problèmes:

(i) ( A- B ) - › A/A —9 13, et (ij) (A--->B) -9 A, A/A

Or, supposons que le problème ( i ) admet une solut ion générale.Alors nous pourrons effectuer la déduct ion suivante:

Substituons, pour A , la f ormule B-313 A l o r s la f ormule (1) de-vient:

[(B -> 13) -9 B] - + ( 1 1 - 13 ) ,

et cette formule est déductible en partant de l'ensemble v ide o P a rconséquent, une formule B quelconque serait déductible de l'ensem-ble v ide 0 Ma i s cela n'est pas admissible; i l en résulte que, en géné-ral, le problème (i) ne doit pas admettre une solution.

8. U n e procédure tendant à combler cette lacune est suggérée parla considérat ion suivante. Supposons que nous n e réusissons pas,comme i l était exigé en Section 5, sub (i), de déduire U en partant de(K, U-9V) , mais que nous tombons immédiatement s ur Z . A lorsnous aurons résolu le problème original sans avoir recours à la rédu-t ion (ijaI). I l sera donc plus sage de f ormuler la réduct ion de la ma-nière suivante:

155

Par conséquent, s i nous int roduisons u n problème de déduct ionqui correspond a une séquence ( K , U—>V)/(U, Z) , le problème inso-luble tout a l'heure se résout sans aucune dif f iculté.

9. No u s ment ionnons deux méthodes (d'ai l leurs équivalentes)pour effectuer l'amplif icat ion q u i s'impose. L a première consistereformuler les schémas de telle façon que dorénavant i ls t iennentcompte du cas d'un conséquent ( V I , V2, \ Tr i) , n > 1 L ' a m p l i f i c a -

t ion du schéma (ijal) présuppose un appel tacite au princ ipe du t iersexclu:

156

(i) e n partant de (K, U-->V), déduire soit U [et ensuite VI soit Z;(ij) en partant de (K, V ) , déduire Z.

(ijaC)

Prémisses

[U]

U—>V

(ii)[UI

Conclusions

et cette démarche n'est donc pas admiss ible d ' un point de v ue in -tuitioniste. L'adéquat ion des schémas de réduct ion et de clôture ains iamplif iés résulte immédiatement de robservat ion qu' ils sont ent ière-ment conformes aux règles de construction et de c lôture pour les ta-bleaux sémantiques dans le cas classique.

Notons en passant que si, au contraire, on s'en t ient aux schémas(i), (ijaI ) et (ijb) sous leur f orme init iale, on a une méthode de dé-duction qui est adéquate pour la logique intuitioniste de l'implica-tion.

10. L a deuxième méthode consiste à retenir les schémas (i), (tiaT)et (i jb) sous leur f orme init iale, mais à permettre, chaque fois quepour une séquence (K, U-4V)/Z o n aurait recours au schéma (ijaC),l'adjonct ion à l'antécédent (K , U--->V) d ' une prémisse:

[(Z U )

Alors l'appel au schéma (ijaC) devient inut ile et peut être remplacépar une suite d'applicat ions des schémas (i), (ijaI ) et (ijb) sous leurforme originale:

(i)

[ -*1_1) Z ] -> Z( i ja ) (f )

Prémisses

X

X --0 Y

Prémisses

Y

(i)

(in

X

(III) [ ( Z - ) Z ] ---> Z ,

Conclusions

11. S i , dans une colonne gauche, nous t rouvons deux prémissesX e t X-->Y , alors l'applicat ion du schéma (ija) pourra se présentercomme une s imple applicat ion du modus ponens:

Conclusions P r é m i s s e s

X

X -4 Y

Y

(I)

(I l) [ V -4 (X -4 Y)] —› [ (V -+ - - - > Y ) ] ,

Conclusions

12. P o u r terminer, j e veux démont rer que, pour l a logique i n -tuitioniste de l' implicat ion, les axiome-schémas:

constituent une base adéquate et que l'adjonct ion de l'axiome-sché-ma :

157

suffit pour obtenir une base adéquate pour la logique classique del' implicat ion, le modus ponens constituant dans les deux cas le seulschéma d'inférence.

Il suf f it de comparer deux tableaux déductifs:

158

Prémisses

[ : :

iK Uk

V

XX-->Y

Y

Conclusions

W

Nous avons posé, comme abréviat ion:

: V ---> ( ( v -V ) - 0 ,

V 2 : V - > ( V - › ,

Prémisses

U k

uk uk)

V - * U k

V 1

V 2

- ) V2 - - ) (V -> V)}

V -. /

V -OCV Y )

[V ( X -4 Y)I-->--»[(V -OC) ( V -) Y)]

V --) Y

Conclusions

en sorte que VI e t V2 s o n t d es a p p li c a ti o n s de l ' ax i om e -s c hé m a (I).

tandis que l a f ormule VI - - > V2 - * ( V - › V )} e s t u n e a p p l ic a t i on de

l'axiome-schéma (I I ). Uk es t une formule quelconque dans K . Nousavons représenté dans le tableau à gauche l a dernière applicat iondu schéma de réduct ion (ijb). Pour toute f ormule Y q u i se présentedans le tableau à gauche, nous trouvons dans le tableau à droite laformule V -4 Y ; or, s i le tableau à gauche est clôturé, le tableaudroite l e sera également. I l en résulte que l a dernière applicat ion

(donc toutes les applicat ions) peut êt re remplacée par l'adjonc t iond'applications appropriées des axiome-schémas (I ) et (I I ).

Or, supposons que le tableau déduct if pour la séquence K/ Z cons-truit, conformément au point de vue intuit ioniste, d'après les sché-mas de réduct ion ( i j ) sous leur f orme originale, soit c lôturé. L'ad-jonct ion d'applicat ions appropriées des axiome-schémas ( I ) e t ( I I )produit un tableau déduct if pour une séquence K* / Z , construit d'a-près le seul schéma (ijaI ) et clôturé. Cela veut dire que Z résult ede K * p a r l'applicat ion du modus ponens.

Le cas d ' un t ableau classique s e ramène, d'après l'observat ionfaite dans la Section 10, au cas précédent par l'adjonct ion d'applica-tions appropriées de l'axiome-schéma (I I I ).

Pour terminer, notons que, pour t enir compte de l a négat ion, i lsuffit, t ant pour le cas classique que pour le cas intuit ioniste, d ' in-troduire les axiome-schémas f i ' -0 (II -*Z) e t (Z—>Z)--->2

E. W. BETH, Quelques remarques s ur la sémantique (Revue philos , d e Lou-vain, 54 (1956), pp. 607-625).

E. W. BETH, La crise de la raison et la logique (Collec t ion de logique mathé-matique, Série A , Fasc. XII), Paris -Louvain, 1957.

A. CHURCH, Int roduc t ion t o Mathemat ical Logic , v ol. 1, P r i n c e t o n , N . J . , 1 9 5 6

[pp. 115 (exercise 19.6), 140, 142, 159, 161, 1641.G. GENTZEN, Recherches sur la déduction logique, trad. et comm. par R. FEYS

CI J. LADRIkRE, Paris, 1955.A. N. PRIOR, Format Logic , Ox ford, 1955 [pp. 48-641.

Amsterdam, le 9 mai 1959

BIBLIOGRAPHIE SUCCINTE

Instituut v oor Grondslagenonderzoek e nPhilosophie der Exacte Wetenschappen,

Universiteit v an Ams terdam

159