Logique prédicative

(version chantier)

Marc SAGE
avril 2015

Table des matières

1 Logique prédicative (ou calcul des prédicats) 2
1.1 Langage : symboles d’objet (singulier, générique et invocable), de composition et de relation . . . 3
1.2 Formules & énoncés : relation entre termes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Quanti…cation, symboles d’objet génériques libres, formules closes, prédicats, conventions . . . . 5
1.4 Invocation : « …xer une variable » . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Axiomes de la logique prédicative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 Règles de la logique prédicative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.7 Preuves, h-théorème de la déduction, ajout de symboles d’objet singulier . . . . . . . . . . . . . . 8
1.8 Théorie, schéma d’axiomes, théorème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.9 Égalité, indistinguabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.10 Contradictions, (in)consistance, indécidabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.11 Complétude (syntaxique), existence explicite, rajout de symbole d’objet singulier . . . . . . . . . 12

2 Sémantique des énoncés prédicatifs 13

2.1 Structures et modèles : interprétation du langage . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Cohérence & complétude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Compacité1 et entiers non standards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Incomplétude (et récursivité) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5 Le problème de l’objet / la réalité mathématique . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 Logiques d’ordre supérieur 17

3.1 Langages et énoncés d’ordres supérieurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Pouvoir et limites du deuxième ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4 Logique séquentielle 19

5 Logique prop & préd à la fois 19

6 Exos 20
6.1 Sur trois règles de la logique prédicative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.2 Ajout de symbole d’objet singulier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.3 l’indistingabilité est une relations d’équivalence compatibible avec les lois et relations . . . . . . . 20
6.4 Variations sur l’indistingabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6.5 Cohérence de la logique prédicative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
6.6 la logique prédicative n’exprime pas la …nitude . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1 En topologie, ce terme est associé de près à la …nitude.

1
 Ce cours vise à décrire la logique des prédicats, dont l’énoncé des axiomes présuppose la logique des propo-
sitions.

1 Logique prédicative (ou calcul des prédicats)

Rq Russell (Introduction to Mathematical Philosophy) :

(172) The proposition « Socrates is a man » is no doubt equivalent to « Socrates is human » , but it is not
the very same proposition. The is of « Socrates is human » expresses the relation of subject and predicate ; the
is of « Socrates is a man » expresses identity. It is a disgrace to the human race that it has chosen to employ
the same word « is » for these two entirely di¤ erent ideas – a disgrace which a symbolic language of course
remedies.
Frege en dit pas mal aussi :-)

cf. TLF
un attribut : Tout caractère en tant qu’il est a¢ rmé (ou nié) d’un sujet
EG : tuquoise, mortel, petit...
un prédicat : Qualité, propriété en tant qu’elle est a¢ rmée ou niée d’un sujet.
EG : être homme, satisfaire le thérème de complétude, marcher sur trois membres,

chaque attribut "A" donne lieu au prédicat "posséder l’attribut A"

chaque prédicat "P" donne lieu à l’attribut "véri…ant le prédicat P"

l’attribution : Action d’attribuer quelque chose (à qqn) et résultat de cette action.

la prédication : Action, fait d’a¢ rmer ou de nier un prédicat d’un sujet
(6=prédiction !)

d’où les jugements prédicatif et attributif

On retiendra l’intérêt des prédicats : : POssibilité de dire si le sujet se soumet ou non à une
condition

prédicat singulaire, binaire, tertiaire, quaternaire...

prédicat monadique, dyadique, triadique, tétradique...

Alain Michel, thèses d’exitence et travail mathématique (dirigé par M. Serfait, De la méthode)
Comme l’a expliqué le premier Frege, du moins avec autant de clarté, dire qu’un certains être (par exemple
Dieu) existe, c’est moins dire qu’un objet (à savoir Dieu), qu’il existe –ici, c’est seulement le langage qui nous
trombe –, que dire d’un concept, donc d’un prédicat (être Dieu), qu’il est pas vide, et qu’il est rempli par au
moins un individu : qu’un individu au moins tombe sous le concept de Dieu, et donc que le nombre appartient
au concept en question. Ainsi, comme le nombre, l’existence est un concept de second ordre, qui ne
peut se dire d’un objet ou d’un individu, mais seulement d’un concept.

(Gilles Dowek, Les métamorphoses du calcul, p. 119-120)

La dernière étape pour réconcilier les mathématiques constructives et non constructives consistait à proposer
une variante de la logique des prédicats qui comprenne deux locutions « il existe » et des règles de déduction
qui expriment la signi…cation de ces deux locutions. Une telle logique a été proposée par Gödel, en 1933, sous
le nom de « traduction négative » . Les détails de cette logique sont moins importants que le fait qu’elle montre
que les mathématiques constructives et non constructives peuvent coexister paci…quement, contrairement à ce
que pensaient aussi bien Brouwer que Hilbert.

Albert Lautman (le congrès international de philosophie des sciences (du 15 au 23 septmebre 1935)
ce scandale logique qu’est le double sens du verbe être en grec, qui sert à la fois à lier l’attribut au sujet et
à a¢ rmer l’existnece substantielle de ce même sujet

2
1.1 Langage : symboles d’objet (singulier, générique et invocable), de composition
et de relation

On se donne un h-nombre arbitrairmet grand de symboles dits « d’objets » (anciennement symbole de

variables, même si on devrait dire variable tout court, même …xable et mieux incarnable) (chacun en attente
qu’on lui assigne un objet spécial) regroupés :
1. d’une part en symboles d’objet générique (sur lesquelles on va quanti…er)
2. d’autre par en symboles d’objet invocable (que nous invoquerons localement dans une preuve), égale-
ment appelées symboles d’objet localement singulier (car il joueront, le temps de l’invocation, le rôle
d’un symbole d’objet singulier / d’individu) ou symboles d’invidu local.
Lorsque a ou " ou • désigne un symbole d’objet générique, il est coutume de comprendre le symbole pointé
a0 ou "0 ou •0 comme désignant un symbole d’objet invocable, comme une "…xation de la variable" (aussi
absurde soit cette expression). On pourra visualiser le point 0 comme la marque d’une ‡échette qui "imoblise
le truc qui bouge/varie".
Cependant, a…n d’éviter d’alourdir avec des indices, on préférea utiliser les lettres de …n de l’alphabet
comme génériques et celle du début comme invocables (par exemple, x; y; z et a; b; c). Cette convention n’est
pas systématique mais suit un certain usage : il sera sans doute confusant de noter x; y; z des invocables à côté
de génériques a; b; c.

Un langage va être ce qui permet d’énoncer... : pas de modalité / temporalité.

h-Dé…nition. Un langage est la donnée de trois h-séries (éventuellement in…nement longues) de sym-
boles (distingables) :
1. ceux dits d’objets singuliers2 ou d’invidus ;
2. ceux dit de composition ou de loi ou d’opération ;
3. ceux dit de relation ou de correspondance.
Les symboles de composition et relation possède une arité qui est un h-nombre non nul.

RQ : on pourrait tout à fait dé…nir un symbole d’objet singulier comme un symbole de loi d’arité nulle, mais
cela ne sera pas pratique pour les dé…nitions car les objet singulier s’apparrentent bien plus aux objets qu’aux
lois.
RQ : usuellement les h-suites sont …nies. Cepedannt nous aurons besoin d’un h-nombre aussi grand que
souhité de symboles d’objet singulier pour compléter une théorie (et uniquement pour cela : montrer la h-
complétude).

EG en pensant :
au entiers, on a un langage formé des symboles d’objet singulier 0, lois (binaire, ternaire, ou plus) +; et
de relation ; j; =1 .
à la géométriqe (points droites plans), on a des lois binaires \, milieu, et des relations k; ?; 2, être point,
être droite
aux ensembles, objets singulier ;, lois \ [ P, relation 2, ;être disjoint (pour chaque h-nombre ),
aux groupes : un obejt singluier (le neute), une loi binaire, une loi uniair (liverse), , un relation ternaire
(valoir le composé),
aux ev (vecteurs & saclaires) obj sing vecteur nul & scalaire nul & scalire 1, lois scalaire et linaires, des
relations unaire (être sclaire/vectuer, être le vectuer nul), une relation ternaire « être dans le plan engendré
par »
à la logique propo : des symboles d’objet singulier (V & F), des lois (les connecteurs logiques), des relations
« prouve » et « est conséquence logique de » , une relation binaire « avoir même vérité » ,

Dans tous ceseemples, les symboles sont des dessins, graphèmes, dénué de sens (surtout celui qu’on aimerat
spontannément leur attribuer !) On pourrait donctrès bien dé…nir pour les entiers des lois | k et des relation
.
2 La tradition parle de symboles de constante, ce qui fait sens uniquement par opposition aux symboles de variable, terminologie

dont nous avons su¢ samment expliqué le caractère immensément confusogène.

3
 Mettre ces symboles bout à bout permet de construie les termes du lanages, à savoir ce sur quoi il sera
légimim de porterun discours, ce dernier se trasuaitn essentiellement par des relations entre termes.
RQ : si le langage ne possède pas de symbole de relation, on ne pourra rien « énoncer » . IL restera toujours
possible de considérer ses termes (c’est ce que l’on a fait avec la logique propositionnelle).

1.2 Formules & énoncés : relation entre termes

h-Dé…nition. Un terme (prédicatif ) est

1. ou bien un symbole d’objet (terme atomiqe)
2. ou bien un symbole de loi s’appliquant à des termes
(attention, on suppose que cette dé…nition récursive termine : pas de terme de longueur in…nie !)

Rq Version algo : un terme s’obtient à partir de termes atomiques en utilsiant un h-nombre de fois des
symboles de loi –> rsptation arboalire
RQ Version ensemble : les termes forment le plu petit sensemble stable par lois et contenant le termes
primitifs

EG (x + u) z + t exp 2(penser à (x + 1) 0 + 32 ) ou (P (A) \ E) n(X [ V ) ou une formule en logique propo-

sitionnelle.
En arbre, ça donne
+ n
exp \ [
et
+ z t 2 P A X V
x u A
rappel (occurence) : lorsqu’un même symbole apparaît plusieurs fois dans une h-suite de symboles, chacune
de ses apparitions sera appelée une occurence de ce symbole.

h-Dé…nition. Une formule (prédicative) est

1. (atomique/relationnelle) ou bien un symbole de relation reliant des termes
2. (propositionnelle) ou bien un connecteur logique connectant une ou des formules
3. (quanti…ante) pour x symbole d’objet générique (dont l’occurence après le quanti…cateur est alors dite
quanti…ée)
(a) ou bien 9x; F (existentielle)
(b) ou bien 8x; F (universelle)
dans les deux cas, F est une formule dont aucune des occurences de x n’est quanti…ée.
(attention, on suppose que cette dé…nition récursive termine : pas de formule de longueur in…nie !)

Rq VErsion algo : on part de formules atomique et l’on quanti…e / connecte un h-nombre …ni de fois
(en …sant ga¤e aux isntances) — > arbre
RQ Version ensembliste : les formules forment le plus petit ensemble contenat les formules atomique et
stable par connexion et quantifcation (respectant les symboles d’objet).
RQ Pour les connecteurs logiques, on peut se resreindre à un seul connectuer universel (ce qui évite de
distinguer tous les cas dans d’éventuelles preuves)

RQ : si le langage n’a pas de symbole de relation, il n’y a pas de formule prédicative !

Q
Rq histoique : 8 était notéQ (eg chez Cavaillès) sous forme d’un produit , analogue de la conjonction,
2
de l’intersection, par exemple Qx2R xP 0 ; de même, 9 (anaogue d’une disjonction, d’une réunion) était noté
avec une somme, par exemple n2N a;b;c;s2N n = a2 + b2 + c2 + d2 .
Dans les texte qui n’écrivait pas ces symboles (whatever reason), 8x devenait (x) et 9x devenait Ex (eg
Russell dans ses écrits non mathématiques, ou TLP de Wittgenstein)

RQ (parenthèsages / priorité) : les formules atomiques sont prioritaire sur connectuer/quantif mais
ambiguité de =) sur quantif –> dans le doute parenthéser

4
 EG : 8a; 9b; P (a) ^ Q (b) =) 8c; R (a; b; c) pourrait signiier

8a; 9b; ([P (a) ^ Q (b)] =) [8c; R (a; b; c)])

8a; [(9b; [P (a) ^ Q (b)]) =) [8c; R (a; b; c)]]
[8a; 9b; (P (a) ^ Q (b))] =) [8c; R (a; b; c)]

EG 8x; P (x) =) 9y; Q (y) signi…e souvent [8x; P (x)] =) [9y; Q (y)]. On parserait sinon 8x; [P (x) =) 9y; Q (y)].

rQ : la dernière condition est pour éviter d’écrire 8x; 9y; x 6= y en remplaçant y par x (ce qui changerait la
valeur de véritié)

EG de formule prédicative
x + 0 3a ^ x j a^ =3 (t) x générique/invocable
8p8q; [(ppt) ^ (qpt)] =) [9D; (Ddte) ^ (p 2 D) ^ (q 2 D)]
: (A = ;) =) 9a; a 2 A A générique/invocable
8x; 9y; 0 = 1
8 8 8v; ( scal ^ scal ^ vvect) =) ( ( v) = ( ) v)
9z; ( scal
h =) :z = z) générique/invocable
i
connec loi
8P; Q; (P ` Q) () ` P =) Q clos
on voit que les relaion unaire permettrent de di¤érencier des types d’objets. Attentinoau denier énoncé, on
mélange les symbole de loi du langage avec les connecturs logiques (ciment des énoncé)

EXO : montrer que les formules sont énumérables

Idée : h-suite …nie de symboles, chacun étant élément d’une h-liste éventuelement in…ne (mais énumérable) :
symboles d’objet/loi/relatin, connecteurs logiques, quantif, virgules. Une fois choisie pour chacune des h-listes
une numérotation de ses h-éléments, on dit que la formules de numéros a; b; c; :::z a pour numéro 2a 3b 5c où
le produit court sur les premiers.

1.3 Quanti…cation, symboles d’objet génériques libres, formules closes, prédicats,

conventions

quantif universel : Frege dans sa Begri¤sschrift 1879

h-Dé…nition. Une occurence non quanti…ée (d’un symbole d’objet générique) dans une formule est dite
libre dans cette formule.
Un symbole d’objet générique est dit libre dans une formule si toutes ses occurences y sont libres.
Une formule prédicative est dite ouverte si l’un de ses symboles d’objet générique possède une occurence
libre.
La forme est sinon dite close ou fermée. (il n’y aura pas besin de déterminatation extérieur pour les
interpréter). On parle aussi

d’allégation d’a¢ rmation d’assertion

d’énoncé de proposition de thèse.

(on réservera le terme de jugement pour le métacadre. Parler d’axiomes ou de postulats sous-entend que l’on fonde une
théorie, un théorème sera un énoncé prouvable à partir des axiomes)
Lorsque des symboles d’objet générique sont libres, mettons en h-nombre n, on parle de prédicat à n géné-
riques libres, d’arité n ou plus simpleemnt de n-prédicat.
RQ un n-prédicat peut devenir un symbole de relation d’arité n, par exemple l’inclusion est un 2-prédicat
Attention : la formulle peut être close sans que tous ses symboles d’objet soient quanti…és (penser aux
symboles d’objet singulier et invocable !), eg a2 + 1 2a
Attention : une formule ouverte peut ne pas être un prédicat, EG x = 0 ^ 8x; x 6= 1 (le symbole x a une
occurence libre et une autre liée) ; on préférera éviter ces situations au vu de la convention ci-dessous et changer
de générique (qui jouent des rôles di¤érents), eg y = 0 ^ 8x; x 6= 1

EG :
EG de formule prédicative

5
 (x + 0 3a ) ^ (x j a) ^ =3 (t) est un 1prédicat en x
8p8q; (ppt) ^ (qpt) =) [9D; (Ddte) ^ (p 2 D) ^ (q 2 D)] est une assertition
: (A = ;) =) 9a; a 2 A est un 1-prédicat en A
8 8 8v; ( scal ^ scal ^ vvect) =) ( ( v) = ( ) v) est un énoncé
9z; ( scal
h =) :z = z) pas clos si générique
i
connec loi
8P; Q; (P ` Q) () ` P =) Q est un a¢ rmation (exprime le théoème de la déduction)

Sous-entendu de la quanti…cation universelle dans un énoncé.

La quanti…action universelle sera toujours sous entendue sur un symbole d’objet générique libre.
Cette convention est justi…ée par deux règles (à venir) : pour chaque 1-prédicat P :
1. si on dispose d’un énoncé 8x; P (x) (où x symbole d’objet générique), on peut en déduire P (t) pour chaque
terme du langage, en particulier un symbole d’objet invocable ;
2. si l’on considère un symbole d’objet invocable a puis que l’on montre P (a), alors on peut en déduire
8x; P (x).
Bien sûr, pas de sens pour un prédicat pas clos (car on peut vouloir garder un symbole d’objet libre)

Convention. Comem on dit en frçais « qq soient a; :::z en relation..., on a P (a; :::z) » ou « il y a des
schblurb en relation » , on abrégera
8R (a; :::; z) ; pour 8a; 8b; :::; 8z; R (a; :::; z) =)
9R (a; :::; z) pour 9a; 9b; :::9z; R (a; :::; z)
On peut éventuelmnt mettre un exmposant après le quantif pour précise le nombre de symboles d’objet. EG :
8A ;; : (9a 2 A)
82 x y; 9"; y = x + "2
8Ddte, 94 p; q; r; spoints, (p 2 D) ^ (q 2 D) ^ (r 2 D) ^ (s 2 D)
82 D ? ; 9ppoint, p 2 D \ .

Tous les (exemples d’)écnonsé ci-dessusont une interprétaion « naturelle » dans le contexte arithémeique,
ensembleiste, géométique (j’avoue mon secret de fabricaion !). Mais on pourait très bien en inventer des appara-
memnt snas queu ni tete que l’on serait bieen pein d’interpreter. Libre à eux d’exister, c’es le role du matheux
de démeler dans le fatras d’énoncé exprimables ceux qui lui parlent (puis de recouper avec les prouvables)

1.4 Invocation : « …xer une variable »

Dans un démo, on est amené à « …xer des varaibles » pour raisonner dessus, du type
1. soit " > 0
2. considérons un réel non algbérique zéro de la foction f
3. prenons trois matrices 2 2 inverisble que l’on notera M; N; O
4. Fixons par la suite un sous-groupe H distingué dans G
5. Donnons-nous un complexe C de K-ev de dimension n2 ainsi qu’un enmorphime de ce complexe.

h-Dé…nition Une invocation est une suite de symbole de la forme

# a; E (lire « Soit a tel que E » )
où a est un symbole d’objet invocable (dit alors invoqué) et où E est un énoncé.
La ‡èche vers le bas pourra être interprétée comme « nous avons invoqué l’objet a, il tombe alors du ciel, il
est là, il ne changera plus, il est …xé » . Tout autre symbole avec une meilleure visualisation est le bienvenu.

On pourra utilsier les mêmes abus de notation que pour les énoncé quanti…ant, eg :
1. # " > 0
2. # 2 R; f ( ) = 0
3. #3 M; N; O 2 GL2
4. # H C G
2
5. #2 C 2 Comp K n ; ' 2 End C

6
1.5 Axiomes de la logique prédicative

on aimerait bien pouvoir utiliser les tautologies du calcul propositinnel, d’où axiomes 1 2 (en fait 9 est
super‡u)
on aimreait que les énoncés universel puissent s’appliquer à chaque situtaion (d’où 3) et que la donnée d’un
objet invoqué (ou d’un complexe de tels objets) fasse o¢ ce d’existence (axiome 4). Ainsi, 3&4 sont lien entre
termes sans symboles d’objet générique et quanti…cateurs.
la quantif universel 8x; P (x) n’est qu’une conjonction in…nie ^x P (x), de même pour 9 et disjoinction. On
aimeriat donc pouvoir utiliser les loi de De Morgan : (A _ B) :
A ^ : B (qu’on laisse sous cette forme pour
évier TE) (d’où axime 5) ainsi que les règle de substitution

[(A () A0 ) ^ (B () B 0 )] =) [A B () A0 B 0 ]

pour chaque connecteur dont on n’ulisera qu’une forme a¤aiblie (cf axiome 6)
En…n des axiomes sont censés avoir une valeur de vérité (le vrai !), ce qui rend légitime de les instancier dans
chaque V d’une tautologie (cf axiomes 7)

h-Dé…nition. Les axiomes de la logique prédicative sont les sept suivants. Dans ce qui suit :
t va être un terme sans symbole d’objet générique, i. e. ne contenant que des symboles d’objet (localement)
singulier
x symbole d’objet générique
P et Q des 1-prédicats ou des énoncés

1. (tautologie) chaque tautologie T (p1 ; :::; pn ) instanciée en énoncés

2. (tautologie et quanti…cateurs) 8x; T et 9x; T où T est une tautologie T (p1 ; :::; pn ) instanciée en formules
du type P (x)
3. (spécialsation) [8x; P (x)] =) P (t)
4. (du fait à l’existence) P (t) =) [9x; P (x)]
:
5. (loi de De Morgan) (9x; P (x)) () (8x;: P (x))
6. (distributivité de 8 sur =) ) [8x; P (x) =) Q (x)] =) [(8x; P (x)) =) (8x; Q (x))].
7. (vérité des axiomes précédents) chaque tautologie T (p1 ; :::; pn ; V; V; V; :::; V) instanciée où les V sont rem-
placés par les axiomes ci-dessus.

Rq : si on apppliqe l’axiome 7 à lui-même, cela reste stable : c’est dire qu’une tautologie où l’on remplace
les V par une tautologie est encore une tautologie.

RQ : si le lange n’a pas de symbole de relatin, il n’y pas de prédicat, donc pas d’axiomes !

1.6 Règles de la logique prédicative

On garde évidemment le modus ponens, d’où plein de règles corollaire des axiomes.
Voyons le role des invocations : pour invoquer, il nous su¢ ra d’une existence. On veut pouvoir utiliser les
propriétés de l’objet invoqué. En…n, pour prouver un énoncé universel, on « …xe un objet et on montre l’énoncé
sur cet objet » .

h-Dé…nition. Les règles de la logiques prédicative sont les quatre suivantes. Comem pour les axiomes
x va désigner un symbole d’objet générique
P et Q des énoncés ou des 1-prédicats
a va être un symbole d’objet invocable.

1. ( modus ponens) de A et A =) B déduire B (si A et B sont énoncé)

2. ( l’invocation provient de lexistence) de 9x; P (x) déduire # a; P (a)
3. (e¤ectivité de l’invocation) de # a; E déduire E

7
 4. (généralisation) de # a; P (a) et Q (a) déduire 8x; P (x) =) Q (x)

h-Corollaire (exo). Les trois règles suivantes sont valides (s’il y a un symbole de relation)
( modus ponens quanti…é) de 8x; P (x) =) Q (x) et 98x; P (x) déduire 98x; P (x)
( invocation ex nihilo) invoquer un a tel que "une tautologie instanciée"
( généralisation) pour montrer 8x; P (x), on invoque un a ex nihilo et on montre P (a)

Rq : pour montrer 8x; P (x) =) Q (x), on peut toujours invoquer # a; P (a) via 9x; P (x), sinon 8x; : P (x),
or on a la tautotlogie : p =) (p =) q), d’où l’axiome 8x; : P (x) =) (P (x) =) Q (x)) puis subtitation.
ARNAQUE : ce n’est pas parce de P on peut déduire une contradiction que l’on peut déduire : P ! ce
deveidnra vrai avec théorème de déduction.

1.7 Preuves, h-théorème de la déduction, ajout de symboles d’objet singulier

h-Dé…nition. Une preuve d’un énoncé (appelé thèse)à partir de propositions A; B; C:::; Z (éventuellement
aucune, appelées hypothèses) est une h-suite …nie de propositions ou d’invocations …nissant par telle que
chacune est
1. ou bien une hypothèse
2. ou bien un axiome
3. ou bien déduite des précédentes par une règle.
On impose en outre que
1. la première occurence d’un symbole d’objet invocable est son invocation (les objets invoqués sont nouveaux)
2. aucun symbole d’objet invocable de n’est invoqué dans la preuve (les objets invoqués dans l’ont été
avant la preuve)
On note alors
A; B; C:::; Z `
et on dit que les propositions A; B; C:::; Z prouvent .
Lorsque la thèse peut être déduite uniquement à l’aide des axiomes et des règles, i. e. quand

` ,

on dit que est un théorème (prédicatif)

RQ VErsion ensembliste : les théorèmes prédicatifs forment la plus petit famille d’énoncés/invocations
contenant les axiomes qiu soit stable par preuve prédicative et dont on a ensuite retiré chaques les invocations
(à cause des invciations, preuve et théorème ont version algo crades)

EG : montrons qu’une somme de suites complexe de limites nulles converge vers 0.

Le lange est celui des suites complexe ou entiers (qui appariesnen dans déf limite), loi +, loi bianire "le
n-ième terme de", relation "être une suite/entier", relation <
Traduisons : 8 (usuite ! 0) ; 8 (vsuite ! 0) ; (u + v ! 0) où l’on a abrégé

a ! 0 pour 8" > 0; 9N entier; 8nentier > N; jan j < ".

On commencer par invoquer # u; (u suite)^(u ! 0), puis # (v suite)^(v ! 0) puis # " > 0. Par e¤ectiivté
del’invcocation, on a u ! 0, d’où en spécialisant en le terme 2" la prop 9N entier,8nentier> N; jun j < 2" . On
invoque alors # U0 entier, 8nentier> U0 ; jun j < 2" . Idem pour v avec un V0 . Montrons alors 8nentier> U0 + V0 ,
jun + vn j < ", ce qui donnera par existence 9N; 8nentier> N ,jun + vn j < " et conclura.
On invoque # n entier> U0 + V0 . On utiliser n > U0 + V0 , d’où n > U0 , d’où (spécialiation) jun j < 2" et de
mêm jvn j < 2" . En spécialiant le théorme 8a; bcomplexes,ja + bj jaj + jbj il vient jun + vn j jun j + jvn j, puis
en spéclianst l’adidtion des inégalit ainsi que sa transitivité on obtient jun + vn j 2" + 2" = ", cqfd.

Il est immédait par modus ponens que si ` A =) E alors A ` E. Il est remarquable d’avoir la réciproque.
En d’autres termes, une preuve relative (de E à partir de A) revient toujours à une preuve absolue (de A =) E),
i.e. à un théorème.

8
 h-Théorème de la déduction. Si A ` E, alors A =) E est un théorème.
Il su¢ t de le faire pour E une contradiction •(instanciée en des énoncés) : en e¤et, il su¢ ra alors de
montrer : A =) E ` • pour conclure ` :: A =) E et A =) E par TE, et l’on prouve à partir de
:
A =) E ` A ^ : E d’une part : E, d’autre part A ` E d’où la contradiction.
Il su¢ t de montrer A =) • car on utilise la contraposée : • =) : A et la tautologie (V =) p) =) p
:
instanciée en Vp a
:• .

Si • est un axiome, on obtient un axiome en instanciant la tautologie p =) V en Vp A

• , d’où
A =) •, cqfd
Par réc sur longueur de la preuve.
l=2:
Si • est A, on instancie la tautologie p =) p en p A, d’où A =) •, cqfd.
Si • est un axiome, déjà fait.
Si • est déduite par une règle, ce n’est pas par invocation (• n’est pas une invocation), ce n’est ni le
modus ponens ni la généralsation (faute de longueur) ni l’e¤evtivité de l’invocation (A n’est pas une invocation),
d’où absudité.
l 3:
si • axiome, déjà fait. Sinon • est déduit par une règle. Or • n’est ni une invocation ni un énoncé
existentiel (car c’est une instancation d’un terme propositionel) il reste :
Si modus ponens, on a une preuve A1 ; :::; Ak ; :::; Ak =) •; :::•, d’où par rec A =) Ak ; or on a aussi
| {z }
Ak =) •, d’où par modus ponens A =) •.
Si • vient d’invocation # a; • (où l’symbole d’objet invocable a n’appaarit pas dans•) l’invocation vient
de 9x; •. Par rec, on a A =) (9x; •), d’où (modus tollens) (8x; : •) =) : A. Or, : • est une tautolgie
instanciée blabla, donc (8x; : •) est un axiome. D’où : A par modus ponens.

RQ : ce h-théorème utilise encore le h-principe d’induction. La h-démontration ci-dessus est cependant

constructive et devient e¤ective pour n’importe quelle preuve de longueur un h-nombre.

EXO mq 8x; E =) P (x) prouve E =) (8x; P (x))

h-Dem. (on utilise TE à souhait) Partons de la négation (9x; : P (x)) ^ E. On en tire # a; : P (a) puis
:
P (a). De l’hypothèse 8x; E =) P (x) on spécialise E =) P (a), d’où de E on tire P (a). Par conjoncion
on obtient • = P (a) ^ : P (a)
On a donc mq : (8x; P (x)) ` •, d’où ` :: (8x; P (x)) et ` 8x; P (x).

h-Cor. Soient x un symbole d’objet générique, a un symbole d’objet invocable et P 1-prédicat. On a

alors l’équivalence
[8x; P (x)] () P (a)
Voici donc la justi…cation de la convention de sous-entendre la quantifcation universelle.

1.8 Théorie, schéma d’axiomes, théorème

On …xe un langage
h-Dé…nition (cloture déductive, théorie, axiomatisabilité). Soit E un h-ensemble de formule
(descriptible). La cloture déductive de E est le plus petit ensemble E ` contennat E et stable par `. Lorsque
E ` = E, on dit que E est une théorie. Lorsque E est engendré par un (nombre …ni d’)énoncé(s), on dit que
E est …niment axiomatisable.
En pratique, on ne pourra décrire une théorie que par une base axiomatique. Par abus de langage, on
identi…era une théorie à une telle base.
h-Dé…nition (théorie bis) Une théorie est la donnée d’une famille d’énoncés close par déduction.
Une théorie est la donnée d’une certaine h-famille d’énoncés, appelés axiomes ou postulats (anciennement
demandes)
Lorsque la famille suit un certain « pattern » , un certain schéma, on parle alors souvent d’un schéma
(d’axiomes)
Un théorème dans une théorie est
1. ou bien un axiome de la théorie

9
 2. ou bien un énoncé prouvé à partir de théorème et des règles/axiomes de la logique prédicative

RQ. En termes ensemblistes, les théorèmes d’une théorie forment la plus petit famille d’énoncés conte-
nant les axiomes et stable par preuve prédicative.

EG : groupes, anneaux, ev, entiers, ensembles.

Arithmétique de Robinson P A : deux axiomes sur le succeseurs (qui traduisent que l’incrémentaion induit
une bijection de N sur N ), axiomes sur role de 0 et S pour calculer + et
n 6= 0 =) 9m; n = s (m)
a 6 = b =) s (a) 6= s (b)
n+0 = n a + s (b) = s (a + b)
n 0 = 0 a s (b) = a b + a
(su¢ sant pour montrer Godel)
Arithmétique de Peano P A1 : on rajoute l’axiome d’induction pur chaque 1-prédicat P
(P (0) ^ [8n; P (n) =) P (s (n))]) =) [8n; P (n)] .
Si préférèe écrire au second ordre P A2 , on mettre un 8P devant.

RQ : commer coller deux théories ? avec une agra¤e m’a-t-on balancé un jour :-( Plus sérieusment : on
rajoute deux symbole de relations pour typer les symboles d’objet, puis on écrit les deux théories en rajoutant
le bon typages.

En puissance, une théorie contient chq énocé qu’elle prouve (comme les règles de grammaire française contient
en puissance tous les textes littéraires jamais écrits). En pratique, il faut faire le tri dans ce qui nous intéresse.
CITER triangle de pensées page 16 Alain Connes :
Si l’on devait utiliser une machine logico-déductive quelle qu’elle soit, produisant mécaniquement des as-
sertions démontrables dans un système logico-déductif donné, toute la di¢ culté serait de déterminer parmi les
myriades de propositions ainsi produites celles qui ont du sens et de les distinguer de celles qui sont insigni…antes.
C’est un problème que l’on ne peut pas éluder.

1.9 Égalité, indistinguabilité

introduction of the notation “ = “ by Robert Recorde in 1557 (source https ://[Link]/12184900/PREPRINT_Th

Grounded-Interaction_to_its_Written_Expression)

(résutlat needed que pour th complétude, mais concept intéressant à traiter –>EXO)

Rant sur l’égalité comme "sélection" de ce que l’on souhaite retenir : tous les objets équivalents / indistin-
guables pour nos critères seront dits égaux.
Citer Bergson dans le rire (eg des moutons) et Frege (151 abstraire, c’est oublier ) Faire abstraction
de quelque chose, ce n’est rien d’autre que ne pas y prêter une attention particulière. Le cœur de l’a¤ aire est
évidemment dans le mot « particulière » . L’inattention est une lessive très mordante, elle ne doit pas être
employée avec une concentration trop forte si on ne veut pas qu’elle dissolve tout ; mais elle ne doit pas non
plus avoir une concentration trop faible si on veut qu’elle produise une altération su¢ sante. Tout repose donc
sur le juste degré de la solution, et il n’est pas facile de tomber juste.

Pour les preuves, il est naturel de dire que deux termes sont insitinguales si remplacer l’un par l’autre prouve
les même énoncés (Leibniz : critère salva veritae). IL serait souhaitable que cette notion soit RST et stable par
création de termes, ce qui est renvoyé en exo.

CRITIQUE : l’indistinguabilité pourrait ne pas être transitive, comme les points du continu (Poincaré)...

Autre vision : égalité de subsitution. On en a besoin simplement pour mener un calcul (cas des permutations
où pas de relation dans le langage).

Possibilité : toujours ajouter = comme symbole de relation et demander principes :

10
 1. (salva veritate) a = b =) P (a) () P (b)
2. RST (çàd = est rel d’eq la plus …ne : chq classe est un singleton)

! ! ! ! ! Le principe 1 est une dé…niton au 2e ordre.

h-Dé…nition. On dit que deux termes d’une théorie t et t0 sont indistinguables pour la théorie si cette
dernière prouve P (t) () P (t0 ) pour chaque 1-prédicatP . On note alors t t0 . (c’est un symbole du h-langage
au même titre que `)

h-Propriété. Pour chaques termes a; b; c, chaque théorie prouve

1. ré‡exivité a a
2. symétrie si a b, alors b a
3. transitivité si a b et b c, alors a c

h-Propriété (compatibilité avec les lois et relations). On se donne des termes a; b; :::; z; a0 ; b0 ; :::; z 0
tels que a a0 et b b0 et ... et z z 0 . Alors
1. pour chaque symboel de relation R (d’arité n), la théorie prouve R (a; b; c; :::; z) () R (a0 ; b0 ; c0 ; :::; z 0 )
2. pour symbole O d’opération (d’arité n) les termes O (a; b; c; :::; z) et O (a0 ; b0 ; c0 ; :::; z 0 ) sont indistinguables.

1.10 Contradictions, (in)consistance, indécidabilité

Appeleons contradiction chaque instance (en énoncés) d’une anti-tautolgie (eg la négation d’une tautologie,
eg : p ^ p).

h-lemme. Si une théorie prouve une contradiction, alors elle prouve chaque énoncé.
h-dem Soit C une contradicion et P n’importe quelle proposition. Alors : C est une tautologie instanciée,
donc un axiome prédicatif . De même pour la tautologie : C =) (C =) P ) En copuant avec : C, on obtien
C =) P , d’où P en coupant cette fois avec C.

Ce h-lemme motive la dé…nition suivante.

h-Dé…nition. Une théorie est dite :

1. inconsistante : si elle montre une contradiction (eg A et : A). Alors tout est prouvable, il n’y a aucun
relief entre énoncés (non-)prouvables, aucune formen, aucune consitance ;
2. consistante : pas de contradiction (pas automatique si axiomes contienent un énoncé et sa négation),
elle se « tient » .

RQ. Vu le h-lemme, une théorie inconsistante prouvera chaque énoncé, donc n’importe qeulle contradic-
tion. On peut donc remplacer dans la def ci-dessus "une contradtion" par une contradiction de notre choix, par
exemple "un énoncé et sa négation".

Lorsqu’on étudie une théorie, on doit toujours être persuadé de sa consistance, que ce soit par un acte de foi
ou par des arguments détourné. Le rêve de D. Hilbert de montrer la consistance des maths à l’aide des maths
s’est e¤ondré depuis Gödel qui a construit un énoncé indéciable (et vrai) en arithémtique.

h-dé…nitiion. Un énoncé est dit indécidable (par une théorie) si cette théorie ne prouve ni cet énoncé
ni sa négation
h-prop (élargissement des axiomes). Rajouter un indécidable préserve la consistance.
h-dém. SOit T théorie et I indécidable tels que T; I poruvent une contradiction C. Par le h-th de
déduction, T ` (I =) C), d’où par moduls tollens T ` (:C =) :I) ; or :C est un axiome préicatif, d’où par
modus ponens T ` :I, contredisant l’indécidabilité.
Réciproqueent, il est immédiat que si T; I consistane, alors d’une apart T est conssitante, d’autre part ou
bien I est indéciabel ou bien T; I a même force que T (ie T ` I).

11
 La consistance est donc intimement reliée à l’indécibailité.

Une première approche pour obtenir une consistance est de dire : si je peut interpréter mon langager de
manière univoque dans la « réalité » , alors il ne peut contenir de contradiction (sinon une telle contradiction
s’interpréterait de manière unique dans la réalité, ce qui nous couterait très cher). Cette approche est fructueuse,
et pose la question de l’interprétation, de quelle réalité. Elle peut se réduire à celle d’une interprétaion primitive
(celle des ensembles), laquelle reste problèmatique.

1.11 Complétude (syntaxique), existence explicite, rajout de symbole d’objet sin-

gulier

Vers le théorème de complétude, on aura besoin de deux notions.

h-Dé…nition Une théorie est dite

1. (syntaxiquement) complète3 : si elle prove chaque énoncé ou sa négation (a une opinion "prouvabili-
tative" sur chaque énoncé) ;
2. explicite : si (pour chaque 1-prédicat P ) dès qu’elle prouve 9x; P (x) elle prouve P (c) pour un symbole
d’objet singulier

Une théorie inconsistante est toujours complète. Une théorie consistante prouve chaque énoncé ou bien sa
négation. Une théorie est incomplète ssi elle possède un énoncé indécidable.
Une théorie explicite lève le problème de "il en existe, mais donnez-en moi un !"
On va montrer que chaque théorie peut se compléter en une théorie complète explicite (on rajoute un témoin
pour chaque énoncé existentiel), à condition d’autoriser une h-liste in…nie de symbole d’objet singulier.

h-théorème (Henkin). Soit T une théorie consistante écrite dans un langage L. Alors il existe une
théorie T T complète consistante explcite4 écrite dans le langage L enrichi d’une in…nité énumérable de symboles
d’objet singulier.

h-démonstration. Le point fondamental est de pouvoir énumérer les énoncés d’un langage (cf. h-énoncé
de l’avertissemnt). On forme un langae LL en rajoutant à L une liste aribirairemen grande d’objets singuliers
c1 ; c2 ; ::: et on en énumère les énoncés E1 ; E2 ; E3 ; :::. On construit alors une suite de théorie consistantes et une
suite de langages par h-récurrence.
On part de T0 := T et L0 := L. Supossons construites Tn 1 et Ln 1 pour un h-entier n non nul. Si Tn est
inconsitante avec En , on rajoute :En ; sinon on rajoute En . La consitance est préservée dans le même langage
par le h-thoérème de déduction. Dans le dernier cas où de plus En est existentiel, disons 9x; P (x), on rajoute
en plus l’énoncé P (c) où c est un symbole de la liste qui n’a pas encore été utilisée et que l’on rajoute pour
former Ln . La consistance doit être véri…ée, ce qui fait l’objet du point 3 d’un h-lemme rejété en …n de preuve
(cf exo).
On considère la théorie "limite" T T réunion des Tn et concluons.
Considérons un énoncé de LL. C’est donc un En qui est par constrcution décidé par Tn , aforiotir par T T .
DOnc cette dernière est complète.
Si T T était inconstant, une sous-théorie …nie serait inconsitaten dans LL : une preuve met en jeu des
hypohtèses d’une T et les symboles d’un langage L , et l’on peut supposer = quitte à augmenter l’un vers
l’autre. Mais alors T , ce qui n’est pas.
En…n, si T T prouve 9x; P (x), un sous-théorie …nie le prouve, ie un Tn , mais alors on a rajouté un P (c),
donc T T explicite.

Le h-lemme suivant (preuve en exo) nous dit qu’un symbole d’objet localement singulier peut être vu comme
symbole d’objet singulier dans un autre langage –plus grand.
h-lemme (ajout de symboles d’objet singulier). On se donne une théorie T et un 1-prédicat P
écrits dans un langage L. On enrichit L en un langage LL en raojoutant un symbole d’objet singulier c.
3 Certains auteurs rajoutent la consistance.
4 on parfois explicitement complète pour explite et complète

12
 1. Si T prouve P (c) dans LL, alors T prouve 8x; P (x) (dans L)
2. Si T prouve (énoncé sans c) dans LL, alors T prouve aussi dans L.
3. Si la théorie T à laquelle on rajoute l’énoncé 9x; P (x) est consistance (dans L), alors il en est de même
(dans LL) en remplaçant 9x; P (x) par P (c)

2 Sémantique des énoncés prédicatifs

Grande question de l’interprétaio d’un langage. Pour les formules de la logique propositionnel, c’était facile
via les tables de vérité. Mais que dire des autres symbole d’objet singulier / lois / relation ?
Idée expliuuant le symbolisme :
un d’objet singulier -> un objet concret
une loi –> une loi concrete pour composer des objet entre eux
une relation -> une mise en relation concrete (vrai ou faux).
On pourra alors interpréter récrusement chaque terme et chaque énoncé.

eg : langage sans d’objet singulier ni lois, avec une relation unaire C une relation binaire

structures : ... .. et
.
..
.
..
.
..
. C signi…e

"être un carré ", signi…e "être relié en pointillé".

2 axiomes 8C (x) ; 9y; :C (y) ^ x y et 82 x y; C (x) () :C (y)
strucutures 1 et 2 satisfont deux axiomes, structure 3 satifsait premier axiome mais pas second, structure 4
satisfait aucun axiome.

Rq : Les conj ou disj peuvent porter sur tous les objets, donc induisent potentiellement de l’in…ni, donc
recours à théorie de l’in…ni semble inévitable, ce qui mène à la théorie des ensembles.

2.1 Structures et modèles : interprétation du langage

h-Dé…nition. On …xe un langage L.

Une L-structure est un h-ensemble S où l’on peut interpréter le langage, à savori la donnée :
1. des h-éléments pour les symboles de cstes ;
2. des h-lois de composition entre h-éléments de S pour les symboles de loi ;
3. des h-relations entre h-éléments de S pour les symboles de relation.
On …xe une L-structure S. L’interprétation d’un terme (resp. énoncé prédicatif ) de L sont dé…nis comme
le h-élément de S (resp. la valeur vrai/faux) comme suit :
1. d’un terme atomique : le h-élément de S correposndant au symbole d’objet singulier
2. d’un terme : récurivement à l’aide des h-loi de composition
3. d’un énoncé atomique : à l’aide de la h-reltion correspodante (vrai ou faux)
4. d’un énoncé propositiionne : comme en logique propositionelle
5. d’un énoncé unviersel : vrai ssi tous les quan…és sont vraie
6. d’un énoncé existeniel : vrai s’il y existe un h-éléemnt de S satisfait le quan…é.
Lorsque l’interprétation d’un énoncé E est "vrai" dans S, on dit que S satisfait ou valide ou véri…e E
ou plus simplement que E est vrai dans S et on note

S j= E.

Un modèle d’une théorie est une structure où axiomes vrais (donc cohérence !).
Une tautologie (prédicative) est un énoncé vrai dans chaque structure (donc qq soit manière de l’inter-
préter). On parle égalemnt d’énoncé valide (en un sens absolu, indépednamment de toute strucutre).

13
 Exemples.
chaque L-structure est un modèle de la théorie vide sur L.
chaque tautologie (propositionnelle) instanciée en énoncés prédicatifs est une tautologie prédicative.
PLus géénrelament (exo), les axiomes de la logique prédicative sont tautologiques !
on se donne une structure S et on consièdre tous les énoncés prédicatifs satisfait par S. C’est la théorie du
prmier ordre T h1 (S) satisfaite par S. Par dé…nitino, S en est un modèle. Par ailleurs, T h1 (S) est complète
puisqu’un énoncé a toujours une interprétation (vrai ou faux) dans S.

Se reposent alors les questions de cohérence et (surtout) de complétude : une tautolgoie est-elle prouvable ?
La validité d’une formule dépend a priori de l’interprétation des termes, il n’y en avait qu’une en logique
propositionnelle (vrai ou faux)

2.2 Cohérence & complétude

h-th (cohérence) les énoncés prouvés par une théorie sont vrai dans chaque modèle de cette théorie
ie un moèdle d’une théorie satisfait tous les énoncés prouvés par cette théorie

en particulier, les théorème prédicatif sont tauologiques — > cf. exo

h-th complétude (Gödel - Henkin, 1929) :

Une théorie complète consistante & explicte admet une structure où vérité et prouvabilité coincident.
chaque théorie consistante a un modèle dont les symboles d’objet singulier sont énumérables

h-Preuve.
D’apèrs le h-théorème de henkin, le second point résulte du premier (chaque modèle est modèle de chaque
sous-théorie).
On construit alors un modèle M en considérant les termes du langages modulo indistingabilité. On inter-
prète :
1. t comme sa classe de t
2. O (t) comme sa classe (ok par h-lemme de compatibilité)
3. R (t) comme "T prouve R (t)" (ok par h-lemme de compatibilité)
On montre que les énoncés de T sont vrai dans M, par rec sur leur complexité (avec : et ^). Hic : la récu
peut fair sortir de T , donc on récurre sur les énoncé prouvés par T . SEcond hic : pour utiliser la complétude de
T , on aura besoin d’augmenter la taille avec : au sein de la récurre, on va donc montrer par rec qu’un énoncé
est vrai dans M si et seulement si il prouvé par T (ca fait chier car on n’en besoin que pour les énoncés négatifs
et il faudra se farcir l’autre sens pour les autres ; mais le vrai=prouvable vaut le détour)
Par construction, T prouve chaque énoncé atomique ssi M véri…e ceux-là (en ce sens, si l’on cherchait un
modèle avec vrai=pble, on devait considérer ce modèle)
Soit E énoncé de la forme :A. Si prouvé par T , alors (consit) A faux dans M (sinon par rec T prouveA),
donc :A vrai. Récpqt, si vrai dans M, alors A faux, donc (rec) T ne prouve pas A, donc (compéltude) T prouve
:A.
Soit E énoncé de la forme A ^ B. Si prouvé par T , par consistance, T ne peut pas prouver ni :A ni :B,
donc (par complétude) T prouve A et B, donc (rec) A et B sont vrais dans M, donc A ^ B aussi. Récip clair :
si A ^ B vrai, alors A et B vrais, donc (rec) T prouve A et B, a fortiori A ^ B.
Soit Eénoncé de la forme 8x; P (x). Si T le prouve, pour t terme, on a une preuve de P t , donc (rec) P t
est vrai, d’où (fasiant varier t) la vérité de E. Sinon, par complétude T montre 9x; :P (x), donc montre un
:P (c), d’où (rec & consit) P (c) faux, a fortior 8x; P (x).
Soit Eénoncé de la forme 9x; P (x). Si T le prouve, alors T prouve un certain P (c), donc (rec) P (c) vrai,
tout comme 9x; P (x). Rec, si vrai, alors il ya un objet o tel que P (o), ie un terme t tel que P (t) vrai, d’où
(rec) T prouve P (t) et par axiome 9x; P (x).

Variante. Fixons théore T . Un énoncé est

vrai dans chaque modèle de T ssi théorème de T

14
 Cor (cf complétude LP). (T vide) Un énoncé prédicatif est

valide ssi théorème prédicatf

en d’autres temres : les tautologies sont les théorèmes

En revanche, on verra que (incomplétude)

vrai dans un modèle de T n’implqiue pas (toujours) théorème de T

2.3 Compacité5 et entiers non standards

h-théorème de compacité.
T a un modèle ssi chaque sous-théorie …nie a un modèle
DEm : <=> consistante <=> chaque sous théorie est consistante

Application 1 : vers les entiers non standard

Applciation 2 : limites du pouvoir d’expression de la logique prédicative

cor il y a des modèle de Peano pas comme les h-entiers.

dem on rajoute un symbmole de ! et les axiome ! > 0; ! > 1; ! > 2; :::. Alors chaque sous théorie …nie
contient un n max tq ! > n et il su¢ t d’interpréter ! en n + 1.

Mieux : il y a beaucoup de moèlde de Peano pas standards

Dem : on ra…ne : pour A partie de h-entiers, on rajoute un symboles de cste ! et les axiomes "les divseurs
de ! sont exactement les entiers de A". chaque sous-ens …ni a clairemet un modèle , donc TA a un modèle MA .
Pour A 6= B, il y a un h-entier a 2 AnB, donc a j ! sera vrai dans MA et pas dans MB , donc ils ne sont pas
isomorphes.

Vers Lowenheim-Skolem : en rajoutant des symboles d’objet singulier, on peut faire croître la taille des
modèles comme on veut (cela donne même lieu à un théorème
EXO : Pour chaque langage L, il n’y a pas de théorie écrites dans L dont les modèles sont les structures
…nies (de L).
Rq :(On the ontological signi…cance of the LS theorem, by John R. Myhill)
there is an elementary mathematical notion which escapes formalism within the …rst order functional calculus.
(Notice that the sense of ‘escapes formalization’ is here much more far-reaching than that in which, according
to Gödel’s theorem, the arithmetic of natural numbers escapes formalization. For here we place no restrictions
on the system from the point of view of axiomatizability or recursive enumerability.)
[. . . ] a formalism [. . . ] cannot force the interpretation of any of its predicate-letters as a relation with a
non-denumerable …eld.

Curioisité :
Soit 8n; P (n) indécidable. On dé…nit an = 1 si A (0) ; A (1) ; :::; A (n) et 0 si 9m < n; nonP (m). Alors an
stationne mais impossible de prouver vers quoi.

2.4 Incomplétude (et récursivité)

Suivant Henkin, vrai=proubal sous de fortes conditions. MAis faux dans N

idée de base : Codage des preuves par les entiers –> chaque énoncé de preuve est arhitmétique (sans
récurrence).
Ainsi, chaque
l m théorie contenant 0; s; +; et les aximes de P A pourra dire des choses de ses preuves.
Oo note E le numéro de l’énoncé E
5 En topologie, ce terme est associé de près à la …nitude.

15
 on regarde les énoncés construits de mannièr "récursvie", çàd "calculables" (au sesn de la thèse de Church)

h-def. les énoncs 1 sont engendré d’une part par les formules sans quantif, d’autre part par conj, dijs,
quantif exitentielle et quantif universelle bornée.
Par exeleple,
9a; 9b; 9c; (8x 42; x = a + bc)
complétude 1
chaque énoncé 1 vrai dans N est prouvable par P A .

Codage d’une relation (sémantique) par un prédicat (syntaxique).

On dit qu’un prédicat P représente dans une théorie T une relation R de N si
1. T prouve P (!a ) qd R (!
a ) vrai
2. T prouve :P (!
a ) qd R (!
a )fausse

Représentabilité (récursif -> sigma 1).

chaque relation récursive sur N est représentable dans P A par un prédicat 1.

Exemples (preuve et consistance)

Pour T P A récursive, la relation "la formule de numéro p est une preuve de la formuel de numéro a" est
représentable par une formule 1 , mettons preuveT (a; p)et on note

Pr (n) pour 9p; preuveT (n; p) .

T

ON dé…nit une relation binaire sur N par "être les numéros d’un énoncé et de sa négation", on la représente
dans une théorie T par un formule ContradT (a; b) de ciompelxité 1 , puis on dé…nit l’noncé
h i
Cons par : 9a; 9b; Pr (a) ^ Pr (b) ^ Contrad (a; b) .
T T T T

Remarque : on a dit plkus haut que chaque énoncé E 1 vrai dans N était prouvable dans P A , d’où la
véracité de PrP A (dEe) On en déduit que N véri…e

E =) Pr (dEe)
T

indécidabilité
L’ensemble des formules prouvable par une théorie T P A n’est jamais récurif.

non dé…nissabilité de la vértié (Tarski).

il n’y a pas d’énoncés V (n) codant la vérité, au sens où pour chaque énoncé E on aurait
l m
N j= E ssi N j= V E .

Ier théorème d’incmplétude

Soit T récursive telle que P A T T h1 (N). Alors il y a un énoncé vrai dans N non prouvalble par T .
(rq : prednre T = T h1 (N) serait contrcitoire, donc T h1 (N) n’esr pas récursive !)

idée de preuve (beacoup de détails sous silence) : "je ne suis pas prouvable". C’est vrai, car si faux serait (in-
terprétation de l’énoncé) prouvale donc vrai par cohrénce. C’est pas prouvable sinon vrai et donc (interprétation
de l’énonce) prouvable.
interprétation : P A n’est pas su¢ sante pour atteindre la vérité des enteirs -> mais même en rajoutant
un énoncé mauqnat, on passera à côté d’autres.
EG concret (pas comme le "je mens" dans la preuve), th Kirby & Paris (1981) convergence des suites
de Goldsein est vraie dans N mais non prouvable dans P A1 .

2d téorèm d’incomplétude.

16
 l m
Soit T P A pourvant pour chaque énoncé E de compelxité 1 les implication E =) PrT E . Alors
T ne prouve pas sa consistance.
INterpréstiaon : on peut agrandir T pour montrer la consistance (par exemple ZF montre N), mais cette
opération est sans …ni –> pas de recherche des fondemnts noncontradiction au sein des maths

Soit T une théorie consistante codant l’arithmétique. Le second théorème d’incomplétude de GÖDEL nous
dit que sa consistance C (qui est un énoncé de T ) n’est pas prouvable. On peut donc rajouter sa négation et
obtenir une théorie T 0 := T [f: Cg qui reste consistante (lemme classique et facile). Par complètude de la logique
prédicative, cette théorie T 0 admet un modèle. Considérons alors les entiers de ce modèle et supposons qu’ils
soient « standards » . L’énoncé : C étant vrai dans ce modèle (c’est un axiome de T 0 ), son interprétation fournit
une preuve d’une contradiction à partir de T , a fortiori à partir de T 0 , ce qui montre que T 0 est inconsistante.
Contradiction !

2.5 Le problème de l’objet / la réalité mathématique

Changeux - Connes, page 40, Alain Connes

« Rien ne prouve, dis-tu, la réalité de ces objets en dehors de notre cerveau » . Comparons la réalité mathé-
matique au monde matériel qui nous entoure. Qu’est-ce qui prouve la réalité de ce monde matériel en dehors de
la perception que notre cerveau en a ? Principalement, la cohérence de nos perceptions, et leur permanence.
Plus précisément, la cohérence du toucher et de la vue pour un seul et même individu. Et la cohérence entre la
perception de plusieurs individus. La réalité mathématique est de même nature. Un calcul e¤ ectué de plusieurs
manières di¤ érentes donne le même résultat, qu’il soit fait par un seul individu ou par plusieurs. [...] On a
commencé par explorer la réalité mathématique dans des zones où l’imagerie mentale liée au réel est très simple.
C’est le cas pour la géométrie euclidienne. Ensuite, grâce aux procédés axiomatiques ou aux problèmes concrets
posés par la théorie des nombres, on a pu accéder à des régions beaucoup plus éloignées de la réalité matérielle.
Il n’empêche que la réalité à laquelle on est alors confronté est tout aussi solide que la réalité quoti-
dienne. La frustration éprouvée par un mathématicien qui ne parvient pas à voir ce qui se passe
dans cette réalité est tout à fait comparable à celle d’un aveugle qui cherche son chemin.

page 49, Alain Connes

Je crois qu’il faut se garder de confondre la réalité mathématique et son illustration possible dans des phé-
nomènes naturels. Quand je parle de l’existence indépendante de la réalité mathématique, je ne la localise
absolument pas dans la réalité physique. Un certain nombre de modèles physiques, utilisent, il est vrai, les ma-
thématiques pour décrire des phénomènes naturels, mais ce serait une grave erreur de réduire les mathématiques
à ces phénomènes. Je pense que le mathématicien développe un « sens » , irréductible à la vue, à l’ouïe et au tou-
cher, qui lui permet de percevoir une réalité tout aussi contraignante mais beaucoup plus stable que la réalité
physique, car non localisée dans l’espace-temps. Lorsqu’il se déplace dans la géographie des mathématiques, le
mathématicien perçoit peu à peu les contours et la structure incroyablement riche du monde mathématique. Il
développe progressivement une sensibilité à la notion de simplicité qui lui donne accès à de nouvelles régions
du paysage mathématique.

3 Logiques d’ordre supérieur

EG égalité
déf
a = b () 8P; P (a) () P (b)
EG induction
8F; [F (0) ^ (8n; F (n) =) F (n + 1))] =) [8n; F (n)]
EG séparation
8'; 8A; 9A0 ; (a 2 A0 () [(a 2 A) ^ ' (a)])

17
 EG remplacement

8'; [8x; y; y 0 ; ' (x; y) = ' (x; y 0 ) =) y = y 0 ]

=) 8A; 9B; (b 2 B () 9a; [(a 2 A) ^ ' (a; b)])

Comment formaliser ? que dire des modèles ? complétude ? compacité ? ...

3.1 Langages et énoncés d’ordres supérieurs

On se donne des symboles d’objet d’ordre k pour chaque k 1 miunité d’une arité pour k > 1.

Intuivment, on a la correspondance :
objets d’ordre 1 : objets usuel
objets d’ordre 2 : formules sur les objets
objets d’ordre 3 : les formules sur les formules
objets d’ordre 4 : les formules sur les formules sur les formules....
Une formule d’ordre k est une formue qui parle de termes d’ordre k. Par exemples, les formules prédicatives
sont d’odre 1, les formules de formules sont d’ordre 2, etc... Les objets peuvent être vu comme formule d’ordre
0.

h-Dé…nition Un langage d’ordre supérieur est la donnée pour chaque h-entier k 1 de

1. symboles d’objet singulier
2. symboles de loi
3. symbole de relation

Très souvent, à l’ordre >1, il n’y a aucun symbole ! On pourrait également imaginer des symboles de loi /
relation mélageant les arité (pas seulement k et k + 1).
On dé…nit toujours les termes atomiques et les termes, en leur collant le su¢ xe d’ordre 1
Soit k 2.
Une terme d’ordre k (ou formule d’ordre k 1) est
1. (atomique) ou bien un symbole d’objet d’ordre k
2. (moléculaire) ou bien un symbole de loi d’ordre k s’appliquant à des termes atomiques d’ordre k
3. (relationnel) ou bien un symbole de relation d’ordre k 1 reliant des termes d’ordre k 1
4. (propositionnel) ou bien un connecteur logique connectant un ou des termes d’ordre k
5. (quanti…ant) pour x isntance générique d’ordre k 1 (dite alors quanti…ée)
(a) ou bien 9x; F (existentiel)
(b) ou bien 8x; F (universel)
dans les deux cas, F est un terme d’ordre k 1 qui ne contient pas de terme quanti…é sur x.

proposer quantif générélisé : Qx;;y;z::: P où le domaine indexant fx; y; z:::g peut être vide (cas des connec-
teurs singulaire :)

On voit ci-dessus qu’on peut toujours connecter à n’iporte quel ordre. C’est dire que la logique propositionnel
ne voit pas l’odre (si a; b sont des termes, alors a^b est encore un terme etc...). On dit parfois qu’elle est agnostique
en l’ordre (on devrait dire athée)

Les axiome sont les mêmes que ceux de la logique prédicative en …sant attention à l’ordre pour qu’ils fassent
sens.

18
3.2 Pouvoir et limites du deuxième ordre

Au second ordre :
Peano est catégorique
les modèles de ZFC sont les cardinaux inaccesibles (ie les "gros" ensembles limite)
la …nitude et l’au-plus-dénombrabilité est exprimable.

Mais on perd la compacité –et, partant, la complétude.

manifeste de Shapiro pour LSO ? (foundationalism without foundations)

h-PROP : il y a deux énoncés du duexième ordre dont les modèles sont les structures …nies et au plus
dénombrables
Idée : en présence de ACdén, un ensemble est …ni ssi chaque injection est surjective, ce qui donnt l’énoncé au
second ordre (la quantif sur les injectinos fait apparaitre le second ordre). De même, être au plus dénombrables
équivant à admettre un ordre dont chaque segment initial (strict) est …ni

h-COR : dès le second ordre, pas de compacité, pas de complétude.

DEM : si compacité, on montrerait comme pour le premier ordre qu’aucune téhroe ne code les structures
…nies.

Rigolo (cf girard point avugle 1) : en logique propositionnelle, tout dé…nir au second ordre à l’aide de =)
et de 8 :

A^B : = 8X; ((A =) (B =) X)) =) X)

A_B : = 8X; ([A =) X] =) [(B =) X) =) X])
F : = 8X; X
9X; A : = 8Y; (8X; (A =) Y ) =) Y )

4 Logique séquentielle

leçon de JY Girard, vers page 60

séquents de Gentzen : préciser un contexte (porquoi ? pour que commutent les règles d’introduction de ^ et
de coupure, cf haut page 63)
Haupsatz : élimination des coupures ! ! ! ! ! ! ! ! ! ! ! (alog en complexité tour d’exponentielle)
la règle contraction est seule coupabable –> vers le décompte des utiisation d’une hypothèse –> logique
linéaire
code l’intuitionisme (p. 70)

5 Logique prop & préd à la fois

ON peut englober les deux. On se donne un ensembe in…ni de symbole de "générique". Un langage est la
donnée de :
symboles de relations :
toute ou aucune variable
arité 0 sont les variables prop
symboles de connecteurs
symboles de fonctions :
avec ensemble de variables : (8x est un connecteur singulaire)
arité 0 sont les constantes
arité 0 sont les constantes logiques (V, T)
Si pas de symboles de relations d’airté >0, alors (inutile d’avoir fonctions et) on a obtient la LOG PROP

19
6 Exos

6.1 Sur trois règles de la logique prédicative

Validité de trois règles supplémentaires

subt dans 9 :
9x; P (x)
# a; P (a) 8x; P (x) =) Q (x)
P (a) P (a) =) Q (a)
Q (a)
8x; P (x) =) Q (x)
substi dans 8 : axiome avec deux coupure.
invocation ex nihilo : soit R un symbole de relation et n son arité, on peut former le 1-prédicat P (x) dé…ni
par R (x; :::; x) et la tautologie instanciée (x) dé…nie par P (x) =) P (x). On a alors l’axiome 9x; (x), d’où
l’on infère # a; (a).
généralisatino. Soit a tq (a). Par e¤ectitvité, ona (a). Supposonat montré P (a). On en déduite (par
généralition) 8x; (x) =) P (x). Or, (t =) p) =) p est une tautologie, on l’instancie en t (x) et
p P (x), d’où axiome 8x; ( (x) =) P (x)) =) P (x), puis substitution conclut.

6.2 Ajout de symbole d’objet singulier

1. Ecrivons une preuve de P (c) dans LL. On remplace l’symbole d’objet invocable c par un symbole
d’objet a invocable qui n’apparaît pas dans la preuve (donc pas dans P ). On rajoute au début une
invocation # a ex nihilo et à la …n l’énoncé 8x; P (x). Montrons qu’on obtient ainsi une preuve de ce
dernier.
Les hypothèse restent des énoncé de T . Dans les axiomes utilisés, l’objet singulier c n’apparaît plus,
donc on a bien des axiome écrit dans L (les symboles d’objet sont les mêmes). Pour les mêmes raison, si
une règle a été appliquée, son application est conservée. Il reste à controler les invocations # x0 ; E.
Elles utilisent des symboles x0 d’objets invocables de LL, qui sont les même que ceux de L, et qui
n’apparaisent pas dans P (c) –a fortiori pas dans 8x; P (x). Les énoncé E sont écrits dans LL, donc dans
L sauf si c apparaît – or l’on remplacé ce dernier par a. En…n, vu la construction, a a été invoqué avant
toutes ses appariations et n’apparait pas dans P (donc non plus dans 8x; P (x)).
2. On procède exactemetn de même, d’où une preuve de 8x; , d’où en spécialisant .
3. Supposons que T et P (c) montrent une contradiction. Par déduction, T prouve :P (c) dans LL, donc
(par les points 1&2) prouve 8x; :P (x) dans L, à savoir : (9x; P (x)), donc (par déduction) T et 9x; P (x)
mènemnt à une contradiction dans L, ce quiest contraire aux hypothèses

6.3 l’indistingabilité est une relations d’équivalence compatibible avec les lois et
relations

relations d’équivalence. On …xe une formule F (x).

1. On a un axiome 8x; F (x) () F (x), que l’on spécialise en a
2. On invoque la tautologie (p () q) =) (q () p)
3. On invoque la tautologie [(p () q) ^ (q () r)] =) (p () r).

compatibible avec les lois et relations

20
 1. On considère les formules obtenues à partir de R (a; b; c; :::; z) en primant des symboles d’objet singulier
et en remplaçant l’un des symboles d’objet singulier par un symbole d’objet. On obtient ainsi que T prouve
a a0
R (a; b; c; :::; z) () R (a0 ; b; c; :::; z) ,
b b0
R (a0 ; b; c; :::; z) () R (a0 ; b0 ; c; :::; z) ,
0
c c
R (a0 ; b0 ; c; :::; z) () R (a0 ; b0 ; c0 ; d; :::; z) ,

z z0
R (a0 ; b0 ; :::; y 0 ; z) () R (a0 ; b0 ; :::; y 0 ; z 0 ) .

On conclut en invoquant la transitivité de l’équivalence (tautologie instancité en les énoncés ci-dessus)

2. On montre de proche en proche O (a; b; c; :::; z) O (a0 ; b; c; :::; z) O (a0 ; b0 ; c; :::; z) O (a0 ; b0 ; c0 ; :::; z 0 ).
Soit P un 1-prédicat On raisonne comme au point 1. en remplant la relation R ( ) par P (O ( )).
L’indiscernabilité permet alors de dire que T rprouve
a a0
P (O (a; b; c; :::; z)) () P (O (a0 ; b; c; :::; z)) , d’où O (a; b; c; :::; z) O (a0 ; b; c; :::; z) ,
b b0
P (O (a0 ; b; c; :::; z)) () P (O (a0 ; b0 ; c; :::; z)) , d’où O (a0 ; b; c; :::; z) O (a0 ; b0 ; c; :::; z) ,
c c0
P (O (a0 ; b0 ; c; :::; z)) () P (O (a0 ; b0 ; c0 ; d; :::; z)) , d’où O (a0 ; b0 ; c; :::; z) O (a0 ; b0 ; c0 ; d; :::; z) ,

z z0
P (O (a0 ; b0 ; :::; y 0 ; z)) () P (O (a0 ; b0 ; :::; y 0 ; z 0 )) , d’où O (a0 ; b0 ; :::; y 0 ; z) O (a0 ; b0 ; :::; y 0 ; z 0 ) .

On conclut alors par transitivité de .

6.4 Variations sur l’indistingabilité

Soit un langage muni d’une relation binaire P. Soien a et b deux objets. Alors il revient au mêm de dire :
1. P code l’indistibgabiltié (çàd a et b sont indistingles sii a P b)
2. P compatible avec les loi et les relations.
et, dans ce cas, la rleation P est RST.
RQ : l’indistaigabilité est RST, donc chaque relation traduiasant cela doit être RST.
(cp : magmas : une seule loi. Alors la comptabilité s’écrit a P b =) aIdIda P bIdIdb )

Mq si [ t P t0 implique que t et t0 sont ind.], alors P est compatble avec lois et relations.
déjà fait pour (cf ci-dessus).

Mq t et t0 sont ind. ssi ils véri…ent les mêmes 1prédicats relationnels.

<= Soit P (x) un 1 prédicat. Montrrons P (t) =) P (t0 ) (d’où ()par sym) par réc sur longueur.
Si P (x) est une relation, terminé.
Si P (x) est qqti…é, mettons P (x) ets 8y; Q (x; y). Supp P (t). Soit y0 : on a Q (t; y0 ), d’où (par réc) Q (t0 ; y0 ),
ce qui montre P (t0 ).
Si P (x) est une connexion logique Q (x) R (x). Supposon Q (t) R (t). Sa table de vérité ne dépend que
des valeurs de vérité de Q (t) et R (t), qui sont les mêmes que celles de Q (t0 ) et R (t0 ), d’où Q (t0 ) R (t0 )

Mq [si t P t0 implique que t et t0 sont ind. par rapport aux termes et si P compatble avec les relations], alors
[ t P t0 implique que t et t0 sont ind. par rapport aux relations]
Soit P (x) une relation R ( 1 (x) ; 2 (x) ; :::; n (x)) où i (x) sont des termes. Mq P (t) =) P (t0 ). Posons

Rk (x) :<=> R ( 1 (t) ; :::; k 1 (t) ; k (x) ; k+1 (t0 ) ; :::; n (t0 )) .
def ind def def
Alors R (t) () Rn (t) () Rn (t0 ) () Rn 1 (t) () () R1 (t0 ) () R (t0 ).

Mq [si P cmpatbiel par rapport aux lois] alors [ t P t0 implique que t et t0 sont ind. par rapport aux termes]
Un terme (x) est de la forme a (x) ou x (x) (ou autre sens) avec a singulier. Puisque t P t0 , on a
(t) P (t0 ), d’où (en faisant le produit avec a P a ou avec t P t) (t) P (t0 ).

21
 (anecdotique) Mq deu objets ind. sont relié par chaque relation ré‡exive.
SOit t et t0 ind. Soit R relation ré‡. Le 1-prédicat xRt (où x est générique) est véri…é par t, donc par t0 ,
d’où t0 Rt. De même, considérer le 1prdéaicat xRt0 montrerait tRt

Mq si P impùlique ind, mq Psym et trans.

Supp a P b et b P c. Alors a P x véri…é par b donc par c
Suppo a P b : alors a P x est véri…é par b donc par a, donc x P a véri…é par a donc par b.

6.5 Cohérence de la logique prédicative

par réc sur longueur preuve (uniforme en les langages, théorie & modèles).
Si énoncé est axiome prédicatif, on sait qu’il sont vrai.
Si axiome de la théorie, c’est def d’un modèle
Si énoncé déduit par modus ponens de A et A =) B, ces deux dernies sont prouvés, donc (par rec) vrais,
donc B vrai.
Si énoncé déduit par e¤ectivité de l’invocation, l’énoncé E (…n de preuve !) ne dépend pas de l’symbole
d’objet invocable, donc l’invcation vient d’un 9x; E ; étant prouvé ce dernier est vrai, donc on peut trouver un
objet véri…ant E
Si énoncé déduit par génrésaltin 8x; P (x) =) Q (x), il provient d’une # a; P (a) et d’un Q (a). Rajoutons
a comme symsbole d’objet singulier : remplaçant l’invocation par P (a) donne une preuve de Q (a) à aprtir de
T etP (a) (seul chgt : P (a) est bien un axiome de T etP (a), et la seul conséquence tirable de # a; P (a) est P (a)
qui peut pour les meme raisons rester tout seul). COnsidérons un objet o de notre modèle satisfaisant P (o).
ON agrandit le modèle en interprétant a comme o. On a donc un modèle de T etP (a), d’où par rec la vérité de
Q (a), ie celle de Q (o). On a donc montré la vérité de P (o) =) Q (o) pour chaque objet o, d’où la vérité de
l’énoncé universel.

6.6 la logique prédicative n’exprime pas la …nitude

Supposons que T admette des modèles de chaque cardinal …ni. Montrons alors qu’elle en admet des in…nis,
ce qui fera contrdiction.
On rajoute au langage L une suite énumérable de symboles d’objet singulier cn et l’on étend T en une théorie
T T en rajoutant les énoncés ci 6= cj pour chaques h-entiers i 6= j. Alors chaque sous-théorie …nie de T T admet
un modèle (on prend un modèle de cardinal >le nombre d’indices des ci de la sous-théorie …nie et on interpréter
les symboles d’objet singulier par autant d’élément distincts), donc T T admet unmodèle, qui est un modèle
in…ni de T , CQDF.

22