Cours de logique mathematique

Martin Hils

15 janvier 2013

Table des matieres

1 Compter a l’infini 31.1 Le Theoreme de Cantor et le Theoreme de Cantor-Bernstein . . . 41.2 Notions d’ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Operations sur les ordres . . . . . . . . . . . . . . . . . . . . . . . 51.4 Ordinaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.5 Arithmetique ordinale . . . . . . . . . . . . . . . . . . . . . . . . 101.6 Axiome du choix . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.7 Cardinaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.8 Operations sur les cardinaux . . . . . . . . . . . . . . . . . . . . 141.9 Cofinalite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 Calcul des predicats 192.1 Langages et structures . . . . . . . . . . . . . . . . . . . . . . . . 192.2 Termes et formules . . . . . . . . . . . . . . . . . . . . . . . . . . 202.3 Semantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.4 Substitution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.5 Formules universellement valides . . . . . . . . . . . . . . . . . . 262.6 Demonstrations formelles et theoreme de completude de Godel . 29

3 Premiers pas en theorie des modeles 363.1 Quelques theoremes fondamentaux . . . . . . . . . . . . . . . . . 363.2 La methode des diagrammes . . . . . . . . . . . . . . . . . . . . . 393.3 Expansions par definitions . . . . . . . . . . . . . . . . . . . . . . 403.4 Elimination des quanteurs . . . . . . . . . . . . . . . . . . . . . . 423.5 Corps algebriquement clos . . . . . . . . . . . . . . . . . . . . . . 453.6 Le theoreme d’Ax . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4 Recursivite 494.1 Fonctions primitives recursives . . . . . . . . . . . . . . . . . . . 494.2 La fonction d’Ackermann . . . . . . . . . . . . . . . . . . . . . . 524.3 Fonctions partielles recursives . . . . . . . . . . . . . . . . . . . . 544.4 Fonctions calculables par machine de Turing . . . . . . . . . . . . 544.5 Fonctions universelles . . . . . . . . . . . . . . . . . . . . . . . . 614.6 Ensembles recursivement enumerables . . . . . . . . . . . . . . . 62

1

4.7 Elimination de la recurrence . . . . . . . . . . . . . . . . . . . . . 64

5 Modeles de l’arithmetique et theoremes de limitation 675.1 Codage des formules et des preuves . . . . . . . . . . . . . . . . . 675.2 Theories decidables . . . . . . . . . . . . . . . . . . . . . . . . . . 695.3 Arithmetique de Peano . . . . . . . . . . . . . . . . . . . . . . . . 705.4 Les theoremes de Tarski et de Church . . . . . . . . . . . . . . . 755.5 Les theoremes d’incompletude de Godel . . . . . . . . . . . . . . 76

6 Theorie axiomatique des ensembles 796.1 Les axiomes de Zermelo-Fraenkel . . . . . . . . . . . . . . . . . . 796.2 Axiome du choix . . . . . . . . . . . . . . . . . . . . . . . . . . . 846.3 La hierarchie de von Neumann et l’axiome de fondation . . . . . 866.4 Quelques resultats d’incompletude, d’independance et de consis-

tance relative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

2

Chapitre 1

Compter a l’infini

Dans ce premier chapitre, les notions d’ensemble et d’entier sont prises dansleur sens naıf. La theorie des ordinaux et cardinaux, due a Cantor (fin du 19e

siecle) sera developpee du point de vue naıf.Voici les deux principes de la Theorie des ensembles naıve :– Extensionalite : Deux ensembles contenant les memes elements sont egaux.– Comprehension (globale) : Pour toute propriete (raisonnable) P , la collec-

tion {a | a verifie P} est donnee par un ensemble.C’est le second principe qui est problematique.

Antinomie de Russell. Soit a = {x | x 6∈ x}. Alors a ∈ a ssi a 6∈ a.

Grace a cette antinomie montrant que la Theorie des ensembles naıve estcontradictoire, des fondements rigoureuses de la Theorie des ensembles (et parconsequent de la mathematique en generale) etaient devenues necessaires.

Dans le dernier chapitre de ce cours nous traitons le systeme d’axiomesZFC (axiomes de Zermelo-Fraenkel plus l’axiome du choix ) ; la plupart de cesaxiomes consisteront en une forme restreinte du principe de comprehension.Nous y verrons que les notions et resultats de ce premier chapitre restent validesen Theorie axiomatique des ensembles, en n’utilisant que le systeme d’axiomesZFC.

Notation. Si A,B sont des ensembles, A∪B, A∩B et A\B designent la reunion,l’intersection et la difference d’ensembles, respectivement. Si (Ai)i∈I est unefamille d’ensembles, on note sa reunion par

⋃i∈I Ai = {x | x ∈ Ai pour un i ∈

I}, et son intersection par⋂i∈I Ai.

Nous ecrivons A ⊆ B si A est une partie de B, et A ⊂ B si A est une partiepropre de B. L’ensemble des parties de A est note P(A).

3

1.1 Le Theoreme de Cantor et le Theoreme deCantor-Bernstein

L’existence d’une fonction injective / surjective / bijective entre deux en-sembles sera utilisee comme moyen pour comparer leur « taille ». Nous com-mencons avec deux premiers resultats qui vont dans ce sens.

Theoreme 1.1.1 (Cantor). Soit A un ensemble. Il n’existe pas de surjectionde A sur P(A).

Demonstration. Soit f : A→ P(A) une appliction. On considere l’ensemble

B = {x ∈ A | x 6∈ f(x)}.

Pour tout x ∈ A avec f(x) = B, on a x ∈ B si et seulement si x 6∈ B. Donc Bn’est pas dans l’image de f .

Theoreme 1.1.2 (Cantor-Bernstein). Soient A et B deux ensembles, f : A→B et g : B → A deux injections. Alors il existe une bijection h : B → A.

Demonstration. On peut supposer que A est une partie de B et que l’applicationf est donnee par l’inclusion. (Il suffit de remplacer g par f ◦ g et A par f(A).)Soit C = {gn(x) | n ∈ N, x ∈ B \ A}. On pose h(c) = g(c) pour c ∈ C eth(x) = x pour x ∈ B \ C.

Definition. Soient X et Y deux ensembles. On dit que X et Y sont equipotents,note X ∼ Y , s’il existe une bijection entre X et Y ; on dit que X est subpotenta Y , note X 4 Y , s’il existe une injection de X dans Y .

Dans cette terminologie, le theoreme de Cantor-Bernstein dit que si X 4 Yet Y 4 X, alors X ∼ Y .

Exercice 1.1.3. Montrer qu’il existe une bijection entre R et P(N).

1.2 Notions d’ordre

Definition. Un ordre partiel < sur un ensemble X est une relation binaire (c.-a-d. donnee par une partie de X ×X) qui est transitive (si x < y et y < z alorsx < z) et antireflexive (x 6< x). Si de plus < est une relation connexe (pour toutx, y ∈ X on a x < y, x = y ou y < x) on dit que < est un ordre total.

On note x ≤ y pour x < y ou x = y, puis x > y pour y < x, et x ≥ y poury ≤ x.

Si Y ⊆ X, y ∈ Y est un plus petit element si pour tout y′ dans Y , y ≤ y′.C’est un element minimal si pour tout y′ dans Y , y′ 6< y. On definit de meme unplus grand element et un element maximal. Un minorant de Y est un elementde X qui est ≤ a tous les elements de Y . Une borne inferieure de Y est un plus

4

grand element parmi les minorants. On definit de meme la notion de majorantet de borne superieure.

Noter que, dans un order partiel, a ≤ b et b ≤ a entraıne a = b. Un plus petit(grand) element est donc necessairement unique, ce qui n’est pas le cas pour unelement minimal (maximal) en general.

Remarque 1.2.1. Si < est un ordre partiel alors ≤ est une relation reflexive(x ≤ x pour tout x ∈ X), transitive et faiblement antisymetrique (x ≤ y ety ≤ x entraıne x = y).

Reciproquement, si ≤ est une relation reflexive, transitive et faiblement an-tisymetrique, la relation < definie par x < y :⇔ (x ≤ y et x 6= y) est un ordrepartiel.

Demonstration. Exercice.

Definition. – Soit < un ordre partiel sur X. On dit que < est bien-fondesi toute partie non vide de X contient un element minimal.

– Un bon ordre est un ordre total bien-fonde.

Exemples 1.2.2. 1. L’ordre usuel < sur N est un bon ordre, tandis qu’ildefinit un ordre total non bien-fonde sur Z.

2. Pour tout ensemble X, la relation ⊂ est un ordre partiel sur P(X) qui estbien-fonde si et seulement si X est fini1.

3. La restriction d’un ordre partiel (total, bien-fonde) sur X a une partieY ⊆ X est un ordre partiel (total, bien-fonde) sur Y .

Remarque 1.2.3. Soit < un ordre partiel sur X.

1. L’application a 7→ X≤a = {x ∈ X | x ≤ a} identifie (X,<) a une partieY de P(X) avec l’ordre partiel sur Y induit par ⊂.

2. < est bien-fonde si et seulement s’il n’existe pas de suite infinie strictementdecroissante dans X.

3. < est un bon ordre si et seulement si toute partie non vide de X contientun plus petit element.

Demonstration. Les preuves de (1) et (3) sont laissees en exercice.Montrons (2). Si (X,<) n’est pas bien-fonde, il existe une partie ∅ 6= Y ⊆ X

sans element minimal. Par induction on peut donc choisir des elements yn ∈Y tels que yn+1 < yn. Reciproquement, si (yn)n∈N est une suite strictementdecroissante, il est clair que Y = {yn | n ∈ N} ne contient pas d’elementminimal.

1.3 Operations sur les ordres

Definition. Soient X et Y deux ensembles partiellement ordonnes.1Par un ensemble fini nous entendons un ensemble dans lequel on ne peut pas injecter N.

5

– La somme ordonnee de X et Y , notee X+Y , est l’ensemble ordonne formedes paires (x, 0) avec x ∈ X et (y, 1) avec y ∈ Y et ou l’ordre est definiainsi : (a, i) < (b, j) si i < j ou si i = j et a < b.

– Le produit lexicographique de X et Y est obtenu en munissant le produitcartesien X × Y de l’ordre suivant : (x, y) < (x′, y′) si y < y′ ou si y = y′

et x < x′. On le note egalement X × Y .

Lemme 1.3.1. 1. La somme ordonnee d’ordres totaux (resp. bien-fondes)est un ordre total (resp. bien-fonde).

2. Le produit lexicographique d’ordres totaux (resp. bien-fondes) est un ordretotal (resp. bien-fonde).

3. Soient X, Y et Z des ensembles partiellement ordonnes. On a les isomor-phismes suivants d’ensembles ordonnes.

(a) (X + Y ) + Z ∼= X + (Y + Z)

(b) (X × Y )× Z ∼= X × (Y × Z)

(c) X × (Y + Z) ∼= (X × Y ) + (X × Z)

Demonstration. Le seul point non trivial est de montrer que si deux ordres sontbien-fondes, alors leur produit lexicographique l’est aussi. Soient donc X et Ydes ensembles ordonnes bien-fondes. Soit Z un sous-ensemble non vide de X×Y .On denote π : X × Y → Y la projection sur la deuxieme coordonnee. Commel’ordre sur Y est bien-fonde, il existe un element minimal y0 dans π(Z) ⊆ Y .Comme l’ordre sur X est bien-fonde, il existe x0 minimal dans Zy0 = {x ∈ X |(x, y0) ∈ Z}. Il est clair que (x0, y0) est minimal dans Z.

Definition. Soient X et Y des ensembles totalement ordonnes. On supposeque X possede un plus petit element 0. On definit l’exponentiation, notee X(Y ),comme suit. Comme ensemble, il s’agit des suites a support fini, c’est-a-dire lesous-ensemble de XY forme des applications f : Y → X avec supp(f) = {y ∈Y | f(y) 6= 0} fini. On pose f < g s’il existe y ∈ Y tel que f(y) < g(y) etf(y′) = g(y′) pour tout y′ > y.

Proposition 1.3.2. 1. La relation < definit un ordre total sur X(Y ) qui estbien-fonde si les ordres sur X et Y le sont.

2. On a les isomorphismes X(Y+Z) ∼= X(Y ) ×X(Z) et X(Y×Z) ∼=(X(Y )

)(Z).

Demonstration. L’enonce sur les isomorphismes est une consequence directe desdefinitions. Il est egalement facile a voir qu’il s’agit d’un ordre total.

Supposons que les ordres sur X et Y soient bien-fondes (ce sont donc desbons ordres). Soit Z une partie non vide de X(Y ). Il faut montrer que Z contientun plus petit element. Si la fonction constante a 0 est dans Z, il n’y a riena montrer. On peut donc supposer que supp(f) 6= ∅ pour tout f ∈ Z. SoitY1 = {s1(f) | f ∈ Z}, ou s1(f) = max(supp(f)). Soit y1 le plus petit elementde Y1, et Z ′1 = {f ∈ Z | s1(f) = y1}. L’ensemble Z ′1 est un segment initial deZ, c’est-a-dire f < g pour tout f ∈ Z ′1 et g ∈ Z \ Z ′1.

6

Soit x1 le plus petit element de {f(y1) | f ∈ Z ′1}. On pose

Z1 = {f ∈ Z ′1 | f(y1) = x1}.

L’ensemble Z1 est un segment initial de Z ′1. Si Z1 contient la fonction qui estconstante 0 en dehors de y1, on a termine. Sinon, supp(f) \ {y1} 6= ∅ pour toutf ∈ Z1. Soit Y2 = {s2(f) | f ∈ Z1}, ou s2(f) = max(supp(f) \ {y1}). Soit y2 leplus petit element de Y2, puis x2 le plus petit element de {f(y2) | f ∈ Z1 et y2 =s2(f)}. On pose Z2 = {f ∈ Z1 | s2(f) = y2 et f(y2) = x2}. C’est un segmentinitial de Z1. Si Z2 contient la fonction qui est constante 0 en dehors de {y1, y2},on a termine, sinon on continue de la meme facon, construisant Y3, y3, Z

′3, x3, Z3

et ainsi de suite. Comme la suite des yi est strictement decroissante dans Y , ceprocede s’arrete apres un nombre fini d’etapes.

1.4 Ordinaux

Un ensemble X est transitif si pour tout x ∈ X et y ∈ x on a y ∈ X. (C’estequivalent a x ∈ X ⇒ x ⊆ X.

Definition. Un ensemble X est un ordinal s’il est transitif et si ∈�X×X definitun bon ordre sur X.

Proposition 1.4.1. Soient α et β des ordinaux.

1. ∅ est un ordinal.

2. Si α 6= ∅, alors ∅ ∈ α.

3. α 6∈ α4. Si x ∈ α, alors x = S<x := {y ∈ α | y < x}.5. Si x ∈ α, alors x est un ordinal.

6. β ⊆ α si et seulement si β ∈ α ou β = α.

7. x := α ∪ {α} est un ordinal. On le note α+.

Demonstration. (1) est clair. Quant a (2), on considere x ∈ α minimal. S’ilexistait y ∈ x, alors y ∈ α par transitivite de α, et x ne serait donc pas minimal.Dans (3), par antireflexivite, on a x 6∈ x pour tout x ∈ α. Donc α ∈ α entraıneα 6∈ α. (4) suit du fait que < est donne par ∈. Pour montrer (5), notons que ∈se restreint en un bon ordre sur x, car x ⊆ α. De plus, x = S<x est un ensembletransitif, car z ∈ y ∈ x⇒ z < x⇒ z ∈ S<x.

Pour montrer le sens direct dans (6), supposons que β ⊂ α. Soit x minimaldans α\β. Clairement β ⊇ S<x par minimalite. Reciproquement, si y ∈ β, alorsy ∈ x car sinon x ∈ y et x ∈ β. Donc β = S<x = x ∈ α. L’autre sens dans (6)est trivial, et (7) se verifie immediatement.

Proposition 1.4.2. Soit X un ensemble non vide d’ordinaux. Alors⋂α∈X α

est un plus petit element de X.

7

Demonstration. L’intersection d’ensembles transitifs est transitive, et l’ordre in-duit sur un sous-ensemble d’un bon ordre est un bon ordre. Donc β =

⋂α∈X α

est un ordinal. On a β ⊆ α pour tout α ∈ X. Si β 6∈ X, alors β ∈ α pour toutα ∈ X, par Proposition 1.4.1(6). D’ou β ∈ β, absurde.

Theoreme 1.4.3. Soient α et β deux ordinaux. Une et une seule des troisproprietes suivantes est verifiee :

(1) α ∈ β , (2) α = β , (3) β ∈ α.

Demonstration. On poseX = {α, β}, et on applique Proposition 1.4.2. Si α∩β =α, alors α ⊆ β, d’ou α = β ou α ∈ β par Proposition 1.4.1(6). De meme, siα ∩ β = β, alors α = β ou β ∈ α. L’exclusivite de ces proprietes est claire.

Notation. Dans la suite, nous ecrivons α < β pour α ∈ β, et α ≤ β pourα ⊆ β, quand α et β sont des ordinaux.

Proposition 1.4.4. Soit X un ensemble d’ordinaux. Alors b =⋃α∈X α est

un ordinal. De plus, si γ < b, il existe α ∈ X tel que γ ∈ α. On ecrira aussib = supα∈X α.

Demonstration. Comme b est reunion d’ensembles transitifs, il est transitif. Deplus, b ne contient que des ordinaux. Par le Theoreme 1.4.3, ∈ induit un ordretotal sur b. Si ∅ 6= Z ⊆ b, alors

⋂α∈Z α est un plus petit element de Z par 1.4.2.

Cela montre que cet ordre est bien-fonde.

Un ordinal de la forme α+ est appele ordinal successeur. Il est clair que α+

est le plus petit ordinal > α, autrement dit le successeur de α.

Definition. Un ordinal limite est un ordinal non vide qui n’est pas successeur.

Proposition 1.4.5. Pour un ordinal λ 6= ∅, sont equivalents :

1. λ est limite ;

2. λ =⋃α<λ α.

Demonstration. (1)⇒(2). Soit β =⋃α<λ α et λ limite. Il est clair que β ⊆ λ.

Reciproquement, supposons α < λ. Donc α+ ≤ λ et alors α+ < λ car λ estlimite. On conclut, puisque α ∈ α+ ⊆ β.

(2)⇒(1). Si λ = γ+, alors⋃α<λ α =

⋃α≤γ α = γ < λ.

Exemples 1.4.6. 1. On peut retrouver les entiers comme ordinaux de lafacon suivante. On pose 0 := ∅, puis inductivement n+ 1 := n+ pourn ∈ N. On a par exemple 1 = {∅}, 2 = {0, 1} = {∅, {∅}}, 3 = {0, 1, 2} ={∅, {∅}, {∅, {∅}}}.On montre par induction que n est un ordinal pour tout entier n. Dans lasuite, on identifiera souvent n et n.

2. On note ω :=⋃n∈N n. C’est un ordinal par 1.4.4.

Definition. On dit qu’un ordinal est fini si ni lui-meme ni aucun de ses elementsn’est limite.

8

Proposition 1.4.7. 1. ω est l’ensemble des ordinaux finis.2. ω est le plus petit ordinal limite.

Demonstration. On montre d’abord, par induction sur n ∈ N, que tous leselements de ω sont des ordinaux finis. De plus, α < ω entraıne α+ < ω. Celamontre (2). Si α 6∈ ω, alors ω ≤ α, donc ou bien α = ω ou bien ω ∈ α. Dans lesdeux cas, α n’est pas fini. Cela montre (1).

Theoreme 1.4.8 (Classification des bons ordres par les ordinaux).Tout ensemble bien-ordonne X est isomorphe, comme ensemble ordonne, a unordinal. De plus, l’ordinal et l’isomorphisme en question sont uniques.

Pour demontrer le theoreme, nous avons besoin d’un lemme.

Lemme 1.4.9. Soit f : α → α′ une application strictement croissante entredeux ordinaux. Alors f(β) ≥ β pour tout β ∈ α. En particulier, on a α ≤ α′, etsi f est un isomorphisme, alors α = α′ et f est egale a l’identite.

Demonstration. S’il existe β ∈ α avec f(β) < β, on choisit β0 minimal aveccette propriete. Comme f est strictement croissante, on a f(f(β0)) < f(β0), cequi contredit la minimalite.

Demonstration du Theoreme 1.4.8. L’unicite est une consequence du lemme.Quant a l’existence, notons d’abord que pour tout x ∈ X, tout isomorphismeentre S<x et un ordinal α s’etend en un isomorphisme entre S≤x = S<x ∪ {x}et α+. Soit

Y = {y ∈ X | il existe f : S≤y ∼= α pour un ordinal α}.

Par unicite, pour y ∈ Y , l’ordinal α = α(y) et l’isomorphisme f = fy sontuniques. Nous allons montrer que Y = X. Sinon, il existe x ∈ X minimal dansX \ Y . Pour y < x on a fy : S≤y ∼= α(y). De plus, il s’agit d’un systemecoherent d’isomorphismes, c’est-a-dire pour tout y′ < y < x on a fy �S≤y′ = fy′ .(Remarquons pour cela qu’un segment initial d’un ordinal est un ordinal.) Onpose

α = supy<x

α(y) et f : S<x → α, f(y) := fy(y).

Il est clair que f est bien definie et induit un isomorphisme d’ensembles ordonnesentre S<x et α. Par ce qui etait dit au debut, f s’etend en un ismorphisme entreS≤x et α+. Contradiction. On a donc bien Y = X. Pour conclure, il suffitd’employer un argument du meme type, en posant α(X) := supx∈X α(x) etf : X ∼= α(X), x 7→ fx(x).

Remarque 1.4.10 (Induction transfinie).Soit P une propriete qui porte sur les ordinaux. On suppose :

– ∅ verifie P ;– pour tout ordinal α : si α verifie P , alors α+ verifie P ;– pour tout ordinal limite λ : si tout α < λ verifie P , alors λ verifie P .

Alors tout ordinal verifie P .

9

1.5 Arithmetique ordinale

Si α et β sont des ordinaux, on note α + β l’unique ordinal isomorphe a lasomme ordonnee de α et β (qui existe par le Theoreme 1.4.8). On definit dememe αβ comme l’unique ordinal isomorphe au produit lexicographique α× βet αβ comme l’unique ordinal isomorphe a l’ensemble ordonne α(β). Notons que0β n’est pas encore defini. On pose 00 := 1, puis 0β := 0 pour tout β > 0.

Proposition 1.5.1 (Addition ordinale). 1. α+ 0 = 0 + α = α

2. α+ 1 = α+

3. α+ (β + γ) = (α+ β) + γ, en particulier α+ β+ = (α+ β)+

4. α < β si et seulement s’il existe γ > 0 tel que β = α+ γ

5. Si β < β′, alors α + β < α + β′ pour tout α. En particulier, on peutsimplifier a gauche : α+ β = α+ β′ ⇒ β = β′.

6. Si λ est limite, alors α+ λ = supβ<λ(α+ β) (continuite).7. 1 + α = α+ 1 si α est fini, 1 + α = α sinon.

Demonstration. (1)–(3) sont clairs. Dans le sens non trivial de (4), on verifiesans peine que l’ordinal γ isomorphe a l’ensemble bien-ordonne β \ α marche.

(5) Si β < β′, on utilise (2) et (4) pour obtenir β′ = β + γ et donc α+ β′ =(α+ β) + γ pour un γ > 0.

(6) α + λ ≥ supβ<λ(α + β) suit de (5). Reciproquement, si α ≤ µ < α + λ,alors µ = α + δ pour un δ avec 0 ≤ δ < λ. Comme λ est limite, on a δ+ < λ,d’ou µ < α+ δ+ ≤ supβ<λ(α+ β).

(7) On montre par induction sur n ∈ N que 1+n = n+1. Puis, on a 1+ω = ωpar (6). Enfin, α ≥ ω s’ecrit α = ω+β, d’ou 1 +α = 1 +ω+β = ω+β = α.

Dans ce qui suit, nous omettons quelques parentheses, en suivant la conven-tion que l’exponentiation lie plus fortement que la multiplication et que la mul-tiplication lie plus fortement que l’addition. Ainsi, il faudra par exemple lireαβ + γ comme (αβ) + γ, et γαβ comme γ

(αβ).

Proposition 1.5.2 (Multiplication ordinale). 1. α0 = 0α = 02. α1 = 1α = α

3. α(βγ) = (αβ)γ4. α(β + γ) = αβ + αγ, en particulier αβ+ = αβ + α

5. 2ω = ω < ω2 = ω + ω

6. On suppose α 6= 0. Si β < β′, alors αβ < αβ′. En particulier, on peutsimplifier a gauche : αβ = αβ′ ⇒ β = β′.

7. Si λ est limite, alors αλ = supβ<λ αβ (continuite).

Demonstration. (1) et (2) sont clairs, (3) et (4) sont consequences du Lemme1.3.1. Dans (5), 2ω = ω suit de (7), les autres parties de (5) sont simples. Quanta (6), il suffit de noter que si β < β′ alors β′ = β + γ pour un γ > 0, d’ouαβ′ = αβ + αγ par (4) et alors αβ′ > αβ.

10

(7) On peut supposer α 6= 0. Soit λ un ordinal limite. L’inegalite αλ ≥supβ<λ αβ =: δ est clair par (6). Reciproquement, on se donne γ < αλ. La divi-sion euclidienne, demontree dans le lemme suivant, fournit une paire d’ordinaux(ρ, µ) telle que γ = αµ + ρ, avec ρ < α. Comme µ < λ (par (6)), on a µ+ < λcar λ est limite, d’ou γ = αµ+ ρ < αµ+ α = αµ+ ≤ δ.

Lemme 1.5.3 (Division euclidienne). Soient α et β des ordinaux, avec α 6= 0.Alors il existe une unique paire d’ordinaux (ρ, µ) telle que ρ < α et β = αµ+ ρ.

Demonstration. Unicite : Supposons que αµ + ρ = αµ′ + ρ′ avec ρ, ρ′ < α. Siµ < µ′, alors αµ+ ρ < αµ+ ≤ αµ′ ≤ αµ′ + ρ′, ce qui est absurde. Donc µ = µ′

par symetrie, et on obtient egalement ρ = ρ′ en simplifiant.Existence : Si β = 0 il n’y a rien a montrer. Soit donc β 6= 0. L’application

f0 : β → α × β, x 7→ (0, x) est strictement croissante, d’ou β ≤ αβ par 1.4.9.Si β = αβ, on pose µ = β et ρ = 0. Sinon, on a β ∈ αβ. Soit f l’isomorphismed’ensembles ordonnes entre αβ et α × β. On pose (ρ, µ) = f(β). On verfie queβ = αµ+ ρ (exercice).

Exercice 1.5.4. 1. Montrer que α est limite si et seulement s’il existe β 6= 0tel que α = ωβ.

2. Montrer que ω2 = ωω n’est pas de la forme δ + ω.

Proposition 1.5.5 (Exponentiation ordinale).

1. Pour tout α on a α0 = 1, α1 = α et 1α = 1. Si α 6= 0, alors 0α = 0.

2. αβ+γ = αβαγ , en particulier αβ+

= αβα.

3.(αβ)γ = αβγ

4. Si α > 1, alors β < β′ ⇒ αβ < αβ′.

5. Si λ est limite et α 6= 0, alors αλ = supβ<λ αβ (continuite).

Demonstration. (1) se verifie directement, et (2) ainsi que (3) suivent de 1.3.2.(4) β < β′ ⇒ β′ = β + ρ pour un ρ > 0. Donc αβ

′= αβ+ρ = αβαρ. Or

αρ > 1 est clair (l’ensemble α(ρ) contient au moins 2 elements), d’ou αβ′> αβ

par 1.5.2(6).Montrons l’inegalite non triviale dans (5). On se donne f ∈ α(λ). On peut

supposer que f n’est pas la fonction constante 0. Alors s1(f) < λ, d’ou β =s1(f)+ < λ, ce qui montre que S≤f admet une application strictement croissantedans α(β). On conclut par le Lemme 1.4.9.

Exercice 1.5.6. Soit α > 1.

1. Montrer que αγ ≥ γ pour tout γ. (Est-ce qu’il y a des exemples avecαγ = γ ?)

2. Soit β > 0. Montrer qu’il existe γ tel que αγ ≤ β < αγ+

.

11

3. En deduire que tout ordinal β admet un developpement en base α : ilexiste une suite finie d’ordinaux β1 > . . . > βn ≥ 0 et des ordinaux ki telsavec 0 < ki < alpha tels que

β = αβ1k1 + . . .+ αβnkn.

De plus, l’entier n ainsi que les suites (βi) et (ki) sont uniques.

On appelle le developpement en base ω la forme normale de Cantor.

Remarque 1.5.7. Les formules suivantes permettraient de donner une autredefinition (par recurrence transfinie) de l’addition, de la multiplication ainsi quede l’exponentiation ordinale :

– α+ 0 = α, α+β+ = (α+β)+, puis α+λ = supβ<λ(α+β) pour λ limite.– α0 = 0, αβ+ = αβ + α, puis αλ = supβ<λ(αβ) pour λ limite.– (α 6= 0.) α0 = 1, αβ

+= αβα, puis αλ = supβ<λ

(αβ)

pour λ limite.

Exercice 1.5.8 (Topologie de l’ordre). Dans tout ordre total X, on peut definirune topologie, appele topologie de l’ordre, dont une base d’ouverts est donneepar les intervalles ouverts, c’est-a-dire par les ensembles de la forme (−∞, b) ={x ∈ X | x < b}, (a, b) = {x ∈ X | a < x < b} ou (a,∞), pour a, b ∈ X.

1. Montrer que pour X quelconque, cette topologie est separee.

2. Soit maintenant α un ordinal muni de la topologie de l’ordre. Montrer :

(a) La topologie sur α est discrete si et seulement si α ≤ ω.

(b) α est compact si et seulement s’il n’est pas limite.

(c) Une application f : α→ β entre deux ordinaux et qui est faiblementcroissante (x ≤ y ⇒ f(x) ≤ f(y)) est continue si et seulement si,pour tout λ ∈ α limite, on a f(λ) = supγ<λ f(γ).

1.6 Axiome du choix

Pour une famille d’ensembles (Xi)i∈I on pose∏i∈I

Xi = {f : I →⋃i∈I

Xi | f(i) ∈ Xi pour tout i ∈ I},

appele le produit de la famille.

Definition. L’Axiome du choix (AC) dit que le produit d’une famille d’en-sembles non vides est non vide, c’est-a-dire que si Xi 6= ∅ pour tout i ∈ I, alors∏i∈I Xi 6= ∅.

Dans le systeme d’axiomes de Zermelo-Fraenkel (ZF), (AC) est equivalentau Lemme de Zorn ainsi qu’au Theoreme de Zermelo. Nous le demontrons audernier chapitre du cours et l’admettons comme resultat pour l’instant.

12

Definition. Un ensemble partiellement ordonne X est inductif si toute partieY ⊆ X totalement ordonne possede un majorant (dans X). En particulier, untel X n’est pas vide.

Lemme de Zorn. Tout ensemble partiellement ordonne inductif possede unelement maximal.

Theoreme de Zermelo (Wohlordnungssatz). Tout ensemble X admet un bonordre.

1.7 Cardinaux

On suppose jusqu’a la fin de l’avant-dernier chapitre que l’axiome du choixest verifie.

Definition. On appelle cardinal tout ordinal qui n’est pas equipotent a unordinal plus petit.

Exemples 1.7.1. 1. Tout ordinal fini et un cardinal.

2. L’ordinal ω est un cardinal. Il sera note ℵ0.

3. Si α est infini, alors α+ n’est pas un cardinal. (α+ et α sont equipotents.)

Proposition 1.7.2. Tout ensemble X est equipotent a un unique cardinal, notecard(X).

Demonstration. Par le Theoreme de Zermelo et 1.4.8, X est equipotent a unordinal α. Soit β ≤ α minimal tel que β soit equipotent a α. Alors β est uncardinal et en bijection avec X. L’unicite est claire.

Proposition 1.7.3. Soient X et Y deux ensembles avec X non vide. Sontequivalents :

1. card(X) ≤ card(Y )

2. Il existe une injection de X dans Y .

3. Il existe une surjection de Y sur X.

Demonstration. (1)⇒(2) est facile.(2)⇒(3) : Soit f : X → Y une injection. On choisit x0 ∈ X et on obtient

une surjection g : Y → X, en posant g(y) := x0 si y 6∈ im(f) = {f(x) | x ∈ X},et g(y) := f−1(y) sinon.

(3)⇒(1) : S’il existe une surjection de Y sur X, alors il existe une surjectiong : λ = card(Y ) → κ = card(X). L’application f qui a α ∈ κ associe l’elementminimal β dans λ avec g(β) = α definit une injection de κ dans λ. En particulier,κ est en bijection avec un ordinal γ ≤ λ. (On prend γ l’unique ordinal qui estisomorphe au bon ordre induit sur im(f).)

Definition. On appelle un ensemble X denombrable si card(X) ≤ ℵ0, et fini sicard(X) < ℵ0.

13

Dans la suite, κ, λ etc. denoteront des cardinaux.

Proposition 1.7.4. Soit X un ensemble de cardinaux. Alors λ = supκ∈X κ estun cardinal.

Demonstration. Si α < λ, alors α < κ pour un κ ∈ X. Comme κ est un cardinal,on a κ = card(κ) ≤ card(λ), d’ou α < card(λ). Cela montre que λ n’est pasequipotent avec un ordinal plus petit.

Il n’y a pas de plus grand cardinal. En effet, si κ est un cardinal, alorsλ := card(P(κ)) > κ par le theoreme de Cantor. L’ensemble des cardinaux ≤ λqui sont > κ est donc non vide. On note κ+ son plus petit element, appelesuccesseur cardinal de κ. Pour eviter des confusions, le successeur ordinal de αsera note α+ 1 dans la suite.

Definition. La hierarchie des ℵ est l’application des ordinaux dans les cardi-naux qui est definie comme suit :

– ℵ0 := ω– ℵα+1 := ℵ+

α

– ℵα := supβ<α ℵβ , si α est un ordinal limite.

Par induction transfinie, on montre que α < β ⇒ ℵα < ℵβ . En combinai-son avec le resultat suivant, on en deduit que la hierarchie des ℵ etablit uneenumeration strictement croissante des cardinaux infinis par les ordinaux.

Proposition 1.7.5. Tout cardinal infini est de la forme ℵα.

Demonstration. Soit κ un cardinal infini. La fonction β 7→ ℵβ est strictementcroissante sur κ + 1 (et a valeurs dans ℵκ+1). Donc ℵκ ≥ κ par 1.4.9, d’ouℵκ+1 > κ. Soit α ≤ κ + 1 minimal avec ℵα > κ. Comme κ ≥ ℵ0, on a α > 0.Si α etait limite, par definition on aurait κ ∈

⋃β<α ℵβ et alors κ ∈ ℵβ pour un

β < α, ce qui contredirait la minimalite de α. Donc α = β + 1 et alors ℵβ ≤κ < ℵβ+1 = ℵ+

β . Comme ℵ+β est le successeur cardinal de ℵβ , necessairement

ℵβ = κ.

1.8 Operations sur les cardinaux

Si X et Y sont des ensembles, on note X + Y leur reunion disjointe, X × Yleur produit cartesien et XY l’ensemble des applications de Y dans X. Si κ etλ sont deux cardinaux, on note κ + λ le cardinal de leur reunion disjointe, κλle cardinal de leur produit cartesien et κλ le cardinal de l’ensemble des applica-tions de λ dans κ. Ces operations sont appelees addition (resp. multiplication,exponentiation) cardinale. Il ne faut pas confondre ces operations avec les ope-rations ordinales correspondantes. Ainsi, on a par exemple 2ω = ω = ℵ0 < 2ℵ0 ,ou encore ℵ02 = ℵ0, mais ω < ω2. Il est clair que ces operations coıncident avecles operations arithmetiques usuelles sur les cardinaux finis.

On notera aussi que card(X + Y ) = card(X) + card(Y ), card(X × Y ) =card(X)card(Y ) et card(XY ) = card(X)card(Y ).

La preuve des resultats suivants est immediate.

14

Proposition 1.8.1. 1. L’addition et la multiplication cardinale sont com-mutatives et associatives, la multiplication est distributive par rapport al’addition, κλ+µ = κλκµ, (κλ)µ = κλµ et (κλ)µ = κµλµ.

2. Si κ ≤ κ′, alors κ+ λ ≤ κ′ + λ, κλ ≤ κ′λ et κλ ≤ κ′λ (si κ > 0) ainsi queλκ ≤ λκ′ (si λ > 0).

Proposition 1.8.2. On a card(R) = 2ℵ0 .

Demonstration. Cela reprend l’exercice 1.1.3, compte tenu de la bijection cano-nique entre P(N) et 2ℵ0 .

On a une injection h : 2ℵ0 → R qui a une suite (ai)i∈N de 0 et de 1 associe∑i ai2

−i si le support de la suite est infini, et 2 +∑i ai2

−i sinon. Cela montre2ℵ0 ≤ card(R). D’autre part l’image de h contient l’intervalle ]0, 1[ qui est equi-potent a R (par exemple via x 7→ 1/π arctan(x) + 1/2), d’ou card(R) ≤ 2ℵ0 .

Proposition 1.8.3 (Theoreme de Hesseberg).Pour tout cardinal infini κ on a κκ = κ.

Demonstration. Par induction sur α, on montrera que ℵαℵα = ℵα. Pour α = 0c’est clair. (L’application α2 : N2 → N, α2(m,n) := 1/2(m+ n+ 1)(m+ n) + nest bijective.) On suppose que ℵβℵβ = ℵβ pour tout β < α, et on munit ℵα×ℵαde l’ordre suivant :(β, γ) < (β′, γ′) si max(β, γ) < max(β′, γ′) ou si max(β, γ) = max(β′, γ′) etβ < β′ ou si max(β, γ) = max(β′, γ′) et β = β′ et γ < γ′.

On verifie qu’il s’agit d’un bon ordre.De plus, pour tout δ < ℵα, la partie δ × δ est un segment initial pour

<. Soit f : ε → ℵα × ℵα l’unique isomorphisme d’ensembles ordonnes avec εun ordinal. Si ε > ℵα, alors ℵα ∈ ε et f(ℵα) = (β0, γ0) ∈ ℵα × ℵα. Posonsδ0 := max(β0, γ0) + 1. Comme aucun ordinal successeur infini n’est un cardinal(par 1.7.1), on a δ0 < ℵα et f restreinte a ℵα definit une injection de ℵαdans δ0 × δ0, un ensemble de cardinal card(δ0 × δ0) = card(δ0) ≤ δ0 < ℵα parhypothese d’induction. Contradiction. Donc ℵαℵα ≤ ℵα. L’inegalite dans l’autresens est claire.

Exemple 1.8.4. Soit T = {X ⊆ R | X est un ouvert}. Alors card(T ) = 2ℵ0 .

Demonstration. L’application qui a r ∈ R associe l’intervalle (r,+∞) definitune injection de R dans T , ce qui montre que card(T ) ≥ 2ℵ0 .

Reciproquement, notons que tout ouvert de R s’ecrit comme reunion surdes intervalles de la forme =(q, q + q′), avec q ∈ Q et q′ ∈ Q>0. L’applicationqui a Y ⊆ Q × Q>0 associe

⋃(q,q′)∈Y (q, q + q′) definit donc une surjection

de P(Q × Q>0) sur T . Comme Q × Q>0 est denombrable, on obtient 2ℵ0 ≥card(T ).

Proposition 1.8.5. 1. Si X et Y sont des ensembles non vides dont l’un aumoins est infini, alors

card(X ∪ Y ) = card(X × Y ) = max(card(X), card(Y )).

15

2. Soit κ ≥ ℵ0 et λ > 0 des cardinaux. Alors κ+ λ = κλ = max(κ, λ).

3. Soit (Xi)i∈I une famille d’ensembles avec au moins un Xi infini. Alors

card

(⋃i∈I

Xi

)≤ sup ({card(Xi) | i ∈ I} ∪ {card(I)}) . (1.1)

(En particulier, une reunion denombrable d’ensembles denombrables estdenombrable.) Si de plus les Xi sont tous non vides et 2 a 2 disjoints,alors on a egalite dans (1.1).

Demonstration. (1) Soit κ = max(card(X), card(Y )). On a κ ≤ card(X ∪ Y ) ≤κ+ κ = 2κ ≤ κκ ainsi que κ ≤ card(X × Y ) ≤ κκ. On conclut par le theoremede Hesseberg. (2) est un cas particulier de (1).

(3) Soit X = {(xi, i) | xi ∈ Xi pour un i ∈ I} la reunion disjointe des Xi.On a une surjection canonique de X sur

⋃i∈I Xi et il suffit donc de montrer que

card(X) ≤ sup ({card(Xi) | i ∈ I} ∪ {card(I)}). Soit κ = sup(card(Xi)), et soitYi l’ensemble des applications injectives de Xi dans κ. Comme les Yi sont tousnon vides, par l’axiome du choix il existe f = (fi)i∈I ∈

∏i∈I Yi. La fonction

g : X → κ× I, g((xi, i)) := (fi(xi), i) est injective, d’ou card(X) ≤ κ card(I) =max(κ, card(I)). L’enonce sur l’egalite est clair.

La proposition precedente montre que l’addition cardinale et la multiplica-tion cardinale deviennent triviaux pour des cardinaux infinis. C’est tout a fait lecontraire pour l’exponentiation cardinale. Notons que le systeme d’axiomes ZFCne determine pas completement l’exponentiation cardinale. Ainsi, il ne permetpar exemple pas de trancher sur l’hypothese du continu.

Definition. – L’Hypothese du continu (CH) est l’enonce 2ℵ0 = ℵ1.– L’Hypothese du continu generalisee (GCH) dit que 2κ = κ+ pour tout

cardinal infini κ.

Si (κi)i∈I est une famille de cardinaux, on note∑i∈I κi le cardinal de la

reunion disjointe des κi, et∏i∈I κi le cardinal du produit de la famille.

Theoreme 1.8.6 (Theoreme de Konig). Soient (κi)i∈I et (λi)i∈I deux famillesde cardinaux dont on suppose que κi < λi pour tout i. Alors

∑i∈I κi <

∏i∈I λi.

Demonstration. Soit f :∑i∈I κi →

∏i∈I λi. Pour chaque i, f induit une ap-

plication fi : κi → λi donnee par la i-eme composante de la restriction de f aκi. Comme κi < λi, l’ensemble Bi := λi \ im(fi) est non vide pour tout i. Parl’axiome du choix il existe b ∈

∏i∈I Bi ⊆

∏i∈I λi. Clairement b 6∈ im(f).

1.9 Cofinalite

Afin de pouvoir demontrer des enonces du type 2ℵ0 6= ℵω, nous aurons besoinde la notion de cofinalite.

16

Definition. – SoitX un ensemble totalement ordonne. On dit qu’une partieY ⊆ X est cofinale dans X si Y n’est pas borne dans X, c’est-a-dire sipour tout x ∈ X il existe y ∈ Y tel que x ≤ y.

– Soit f : β → α une application entre ordinaux. On dit que f est cofinalesi im(f) est cofinale dans α.

– La cofinalite de α, notee cof(α), est le plus petit ordinal β tel qu’il existeune fonction f : β → α qui est cofinale.

Exemples 1.9.1. 1. cof(0) = 02. cof(α+ 1) = 1 pour tout α3. cof(ω) = ω

Proposition 1.9.2. 1. cof(α) ≤ α2. cof(α) est un cardinal.3. cof(α) est egal au plus petit ordinal β tel qu’il existe une application cofi-

nale et (strictement) croissante f : β → α.4. cof(cof(α)) = cof(α)

Demonstration. (1) est clair, et (2) suit du fait que tout ordinal β est en bijectionavec card(β) ≤ β.

(3) Il suffit de construire β ≤ cof(α) et une application f : β → α quisoit strictement croissante et cofinale. Par hypothese il existe h : cof(α) → αcofinale. On definit

X = {x ∈ cof(α) | h(y) < h(x) pour tout y < x}.

L’ensemble h(X) = {h(x) | x ∈ X} est une partie cofinale de α. En effet,soit γ < α donne. Par cofinalite de h, il existe y ∈ cof(α) tel que h(y) ≥ γ. Si yest minimal avec cette propriete, on a y ∈ X.

Comme (X,<) ∼= (β,∈) pour un β ≤ cof(α), on a donc termine, car hrestreinte a X est strictement croissante et cofinale.

(4) cof(cof(α)) ≤ cof(α) suit de (1). Pour l’autre sens, on choisit deuxfonctions croissantes et cofinales f : cof(cof(α)) → cof(α) et g : cof(α) → αce qui est possible par (3). Alors g ◦ f : cof(cof(α)) → α est cofinale, d’oucof(α) ≤ cof(cof(α)).

On dit qu’un cardinal infini κ est regulier si cof(κ) = κ, et singulier sicof(κ) < κ.

Proposition 1.9.3. Tout cardinal infini successeur est regulier. En particulier,ℵ1 est regulier.

Demonstration. Soit κ = ℵβ+1 = ℵ+β . Notons que pour un ordinal limite α, une

partie X ⊆ α est cofinale si et seulement si α =⋃γ∈X γ. (C’est une consequence

de 1.4.5.) On considere f : λ → κ pour un cardinal λ < κ. Alors λ ≤ ℵβet 1.8.5(3) entraıne que card

(⋃β<λ f(β)

)≤ sup ({f(β) | β < λ} ∪ {λ}) ≤ ℵβ .

Donc f n’est pas cofinale.

17

Proposition 1.9.4. Si λ est un ordinal limite, alors cof(ℵλ) = cof(λ).

Demonstration. Si f : α → λ est cofinale, alors il est clair que f : α → ℵλ,β 7→ ℵf(β), est cofinale aussi, car ℵλ =

⋃γ<λ ℵγ par definition. Cela montre

cof(ℵλ) ≤ cof(λ). Reciproquement, soit g : α→ ℵλ cofinale. On definit g : α→λ, g(β) = 0 si g(β) est fini, et g(β) = γ si card(g(β)) = ℵγ . Clairement, g estcofinale.

Proposition 1.9.5. Si κ ≥ 2 et λ ≥ ℵ0 sont deux cardinaux, alors cof(κλ)> λ.

Demonstration. Soit f : α→ κλ une application, avec α un ordinal ≤ λ. Commef(β) < κλ pour tout β < α, le theoreme de Konig donne

card

⋃β<α

f(β)

≤∑β<α

card(f(β)) <∏β<α

(κλ)

=(κλ)card(α)

= κλ·card(α) ≤ κλ.

Donc f n’est pas cofinale.

Corollaire 1.9.6. On a 2ℵ0 6= ℵω.

Demonstration. On a cof(ℵω) = cof(ω) = ω = ℵ0 < cof(2ℵ0).

18

Chapitre 2

Calcul des predicats

2.1 Langages et structures

Les enonces du calcul des predicats sont des chaınes de symboles qui de-crivent des proprietes de structures. L’enonce

ϕ = ∀x(x > 0→ ∃y y · y=x)

par exemple est satisfait dans un corps ordonne si et seulement si tout ele-ment positif est un carre. Il est vrai dans le corps ordonne des reels R =〈R; 0, 1,+,−, <〉 et faux dans le corps ordonne des rationnels.

On verra que l’enonce ϕ s’exprime dans le cadre que nous allons etudier, c’est-a-dire dans la logique du premier ordre. Par contre, nous verrons que d’autresproprietes de corps ordonnes comme le fait d’etre archimedien (pour tout x > 0il existe n ∈ N tel que nx > 1) ou complet (toute partie bornee non vide admetun supremum) ne s’expriment pas par des enonces du premier ordre.

Definition. Un langage (du premier ordre) est un ensemble de symboles L quise compose de deux parties :

1. La premiere partie (commune a tous les langages) consiste en les symbolesauxiliaires « ( » et « ) » ainsi qu’en les symboles logiques suivants :

l’ensemble des variables V = {vn | n ∈ N}le symbole de l’egalite = (« egal »)les connecteurs ¬(negation, « non ») , ∧(conjonction, « et »)le quanteur existentiel ∃ (« il existe »)

2. La deuxieme partie, appelee la signature de L et notee σL, consiste en lessymboles non logiques de L. Elle est formee– d’un ensemble de symboles de constante CL ;– d’une suite d’ensembles FLn , n ∈ N∗, ou les elements de FLn sont appeles

symboles de fonction n-aires ;– d’une suite d’ensembles RLn , n ∈ N∗, ou les elements de RLn sont appeles

symboles de relation (ou predicat) n-aires.

19

Le langage L est donne par la reunion (disjointe) de ces ensembles desymboles.

On observe que tout langage est infini. Comme la premiere partie est com-mune a tous les langages, nous identifions souvent L et σL, par un abus denotation.

Exemples 2.1.1.L∅ = ∅ Le langage vide.Lan = {0, 1,+,−, ·} Le langage des anneaux (avec 1).Lord = {<} Le langage des ordres.Lc.ord = Lan ∪ Lord Le langage des corps ordonnes.Lar = {0, S,+, ·, <} Le langage de l’arithmetique.Lens = {∈} Le langage de la theorie des ensembles.

Dans ces exemples, 0 et 1 sont des symboles de constantes, − et S dessymboles de fonction unaires, + et · des symboles de fonction binaires, et <ainsi que ∈ des symboles de relation binaires.

Definition. Soit L un langage. Une L-structure A est la donnee d’un ensemblenon vide A (appele l’ensemble de base de A) muni d’un element cA ∈ A pourchaque c ∈ CL, d’une fonction fA : An → A pour chaque f ∈ FLn et d’une partieRA ⊆ An pour chaque R ∈ RLn . On l’ecrit A = 〈A; (ZA)Z∈σL〉.

ZA est une interpretation du symbole Z ∈ σL.

Exemples 2.1.2. 1. N = 〈N; 0, S,+, ·, <〉 est une Lar-structure, avec S l’ap-plication successeur qui a x associe x+ 1.

2. C = 〈C; 0, 1,+,−, ·〉, le corps des complexes, est une Lan-structure.3. R = 〈R; 0, 1,+,−, ·, <〉, le corps ordonne des reels, est une Lc.ord-structure.

Definition. On dit que deux L-structures A et B sont isomorphes, A ∼= B, s’ilexiste un isomorphisme F : A ∼= B, une bijection F : A→ B qui commute avecles interpretations des symboles dans σL, c’est-a-dire

– F (cA) = cB pour tout c ∈ CL,– F (fA(a1, . . . , an)) = fB(F (a1), . . . , F (an)) pour tout f ∈ FLn et tout uple

(a1, . . . , an) ∈ An,– (a1, . . . , an) ∈ RA ⇐⇒ (F (a1), . . . , F (an)) ∈ RB pour tout R ∈ RLn et

tout uple (a1, . . . , an) ∈ An.

2.2 Termes et formules

Un mot sur un ensemble (alphabet) E est une chaıne finie m = a0a1 · · · ak−1

avec ai ∈ E pour tout i. On appelle k la longueur de m, et on note E∗ l’ensembledes mots sur E.

Definition. Soit L un langage. L’ensemble T L des L-termes est le plus petitsous-ensemble de L∗ qui contient les variables et les symboles de constante ettel que si f ∈ FLn et t1, . . . , tn ∈ T L, alors ft1 · · · tn ∈ T L.

20

On a T L =⋃n∈N T Ln , ou on definit T L0 = CL ∪ VL, puis inductivement

T Ln+1 = T Ln ∪ {ft1 · · · tk | f ∈ FLk et t1, . . . , tk ∈ T Ln }.

Proposition 2.2.1 (Lecture unique des termes). Tout terme t ∈ T L verifieune et une seule des trois possibilites suivantes :

1. t est une variable,

2. t est un symbole de constante,

3. il existe un unique entier n ≥ 1, un unique symbole de fonction n-aire fet une unique suite (t1, . . . , tn) de termes tels que t = ft1 · · · tn.

Demonstration. Exercice. (On montrera d’abord, par induction sur la longueurdes termes, qu’aucun segment initial propre d’un terme n’est un terme.)

Notation. Pour faciliter la lecture des termes, on ecrira dorenavant f(t1, . . . , tn)pour ft1 · · · tn. Si f est binaire, on ecrira parfois aussi t1ft2 au lieu de ft1t2.Par exemple, (x+ y) · z signifie ·+ xyz.

Si t est un terme, son hauteur ht(t) est defini comme le plus petit entier ktel que t ∈ T Lk . Il suit de la propriete de lecture unique pour les termes queht(ft1 · · · tn) = 1 + max(ht(ti)).

Definition. 1. Une L-formule atomique est– soit un mot de la forme t1=t2, ou t1 et t2 sont des L-termes,– soit un mot de la forme Rt1 · · · tn, ou R ∈ RLn et tous les ti sont desL-termes.

2. L’ensemble FmlL des L-formules est le plus petit sous-ensemble de L∗ quicontient les formules atomiques et tel que si ϕ,ψ ∈ FmlL et x ∈ V, alors¬ϕ, (ϕ ∧ ψ) et ∃xϕ sont des elements de FmlL.

On a FmlL =⋃n∈N Fml

Ln , ou FmlL0 est definit comme l’ensemble des for-

mules atomiques, puis inductivementFmlLn+1 = FmlLn ∪ {¬ϕ | ϕ ∈ FmlLn} ∪ {(ϕ ∧ ψ) | ϕ,ψ ∈ FmlLn}

∪ {∃xϕ | x ∈ V et ϕ ∈ FmlLn}.

Proposition 2.2.2 (Lecture unique des formules).Toute formule ϕ ∈ FmlL verifie une et une seule des possibilites suivantes :

1. ϕ est une formule atomique, soit de la forme Rt1 · · · tn pour R et t1, . . . , tnuniques, soit de la forme t1=t2 pour t1, t2 uniques ;

2. ϕ = ¬ψ pour une unique L-formule ψ ;

3. ϕ = (ψ ∧ χ) pour des uniques L-formules ψ et χ ;

4. ϕ = ∃xψ pour une unique variable x et une unique L-formule ψ.

Demonstration. Exercice. (On montrera d’abord qu’aucun segment initial propred’une formule n’est une formule.)

21

Si ϕ est une formule, son hauteur ht(ϕ) est definie comme le plus petit entierk tel que ϕ ∈ FmlLk . Il suit de la propriete de lecture unique pour les formulesque ht(∃xϕ) = ht(¬ϕ) = 1 + ht(ϕ) et ht((ϕ∧ψ)) = 1 + max(ht(ϕ),ht(ψ)). Celanous permet de donner des definitions par induction sur la hauteur des formules.

Definition. 1. Soit vk une variable. On definit, par induction sur la hauteurde ϕ, la notion d’occurrence libre de vk dans ϕ :– Si ϕ est atomique, toutes les occurrences de vk dans ϕ sont libres.– Les occurrences libres de vk dans ϕ = ¬ψ sont celles dans ψ.– Les occurrences libres de vk dans ϕ = (ψ∧χ) sont celles dans ψ et celles

dans χ.– Si l 6= k, les occurrences libres de vk dans ϕ = ∃vlψ sont celles de ψ.– Aucune occurrence de vk dans ϕ = ∃vkψ n’est libre.Les occurrences non libres d’une variable sont dites liees.

2. Les variables libres de ϕ sont celles qui admettent au moins une occurrencelibre dans ϕ. On note Lib(ϕ) l’ensemble des variables libres de ϕ.

3. Un enonce est une fomule sans variable libre.

Exemple. Dans ϕ = (∃v0 v0 < v1 ∧ v0=v1), les deux premieres occurrences dev0 sont liees, tandis que la troisieme est libre. Toutes les occurrences de v1 dansϕ sont libres, d’ou Lib(ϕ) = {v0, v1}.

Notation. On utilisera les abbreviations suivantes :

(ϕ ∨ ψ) = ¬(¬ϕ ∧ ¬ψ) (disjonction, « ou »)(ϕ→ ψ) = ¬(ϕ ∧ ¬ψ) (implication, « implique »)(ϕ↔ ψ) = ((ϕ→ ψ) ∧ (ψ → ϕ)) (equivalence, « si et seulement si »)∀xϕ = ¬∃x¬ϕ (quanteur universel, « pour tout »)

On ecrira ∃x1, . . . , xn au lieu de ∃x1 · · · ∃xn (de meme pour le quanteuruniversel), R(t1, . . . , tn) au lieu de Rt1 · · · tn, et parfois t1Rt2 au lieu de Rt1t2.

On notera (ϕ0∧· · ·∧ϕn) au lieu de (· · · ((ϕ0∧ϕ1)∧ϕ2)∧ . . .∧ϕn), de memepour ∨ a la place de ∧.

Enfin, pour faciliter la lecture des formules, on ajoutera parfois des paren-theses, ou on les omettra. Dans ce cas, on lira les formules selon l’affinite dessymboles logiques :

Affinite maximale : ¬ ∃ ∀∧∨

Affinite minimale : → ↔

Ainsi, ∀xϕ ∧ ψ → χ voudra dire ((∀xϕ ∧ ψ) → χ) = ¬((∀xϕ ∧ ψ) ∧ ¬χ) =¬((¬∃x¬ϕ ∧ ψ) ∧ ¬χ).

Exemple. Voici la liste des axiomes de corps dans Lan.

1. ∀xx+ 0=x

2. ∀x, y x+ y=y + x

22

3. ∀x (−x) + x = 04. ∀x, y, z (x+ y) + z=x+ (y + z)5. ∀xx · 1=x6. ∀x, y x · y=y · x7. ∀x, y, z (x · y) · z=x · (y · z)8. ∀x, y, z x · (y + z)=(x · y) + (x · z)9. ∀x (¬x=0→ ∃y x · y=1)

10. ¬0=1

2.3 Semantique

Dans ce paragraphe, nous donnons un sens aux formules.

Definition. 1. Soit A une L-structure. Une affectation est une fonction α :V → A de l’ensemble des variables dans l’ensemble de base de A.

2. Si α est une affectation, A une L-structure et t un L-terme, on definittA[α], par induction sur ht(t), de la maniere suivante :

– vAi [α] = α(vi) (pour vi ∈ V) et cA[α] = cA (pour c ∈ CL),

– f(t1, . . . , tn)A[α] = fA(tA1 [α], . . . , tAn [α]).

La preuve du lemme suivant est claire.

Lemme 2.3.1. Si les affectations α et β coıncident sur toutes les variables quiont une occurrence dans t, alors tA[α] = tA[β].

Notation. Si t est un terme, on ecrira t = t(x1, . . . , xn) si les variables xi sontdistinctes et si toutes les variables ayant au moins une occurrence dans t figurentparmi les xi.

Si t = t(x1, . . . , xn) et a1, . . . , an ∈ A, on definit tA[a1, . . . , an] par tA[α] ou αest une affectation avec α(xi) = ai pour tout i. (C’est bien defini par le lemme.)

Definition (Satisfaction d’une fomule). Soit A une L-structure. On definit pourtoutes les affectations α et toutes les formules la relation A |= ϕ[α] qu’on lit « ϕest satisfait dans A par α » :

A |= t1=t2[α] :⇐⇒ tA1 [α] = tA2 [α]A |= Rt1 · · · tn[α] :⇐⇒ (tA1 [α], . . . , tAn [α]) ∈ RA

A |= ¬ψ[α] :⇐⇒ A 6|= ψ[α]A |= (ψ ∧ χ)[α] :⇐⇒ A |= ψ[α] et A |= χ[α]A |= ∃xψ[α] :⇐⇒ il existe a ∈ A tel que A |= ψ[αa/x]

Ici, αa/x(y) :=

{α(y), si y 6= x,

a, si y = x.

Proposition 2.3.2. Si les affectations α et β coıncident sur Lib(ϕ), alors ona A |= ϕ[α] ⇐⇒ A |= ϕ[β].

23

Demonstration. Par induction sur ht(ϕ). Le cas des formules atomiques suit dulemme. Dans l’etape d’induction, seul le cas ϕ = ∃xψ merite un argument. SiA |= ϕ[α], il existe a ∈ A tel que A |= ψ[αa/x]. Toute variable y 6= x qui est libredans ψ est aussi libre dans ϕ. Donc A |= ψ[βa/x] par l’hypothese d’induction,d’ou A |= ϕ[β].

Notation. Si ϕ est une formule, on ecrira ϕ = ϕ(x1, . . . , xn) si les variables xisont distinctes et si toutes les variables libres dans ϕ figurent parmi les xi.

Si ϕ = ϕ(x1, . . . , xn) et a1, . . . , an ∈ A, on definit A |= ϕ[a1, . . . , an] parA |= ϕ[α], ou α est une affectation avec α(xi) = ai. (C’est bien defini par laproposition.)

Ainsi, la formule ϕ(x1, . . . , xn) definit une relation n-aire dans la structureA, donnee par {(a1, . . . , an) ∈ An | A |= ϕ[a1, . . . , an]}.

En particulier, si ϕ est un enonce, on peut definir le symbole

A |= ϕ,

lu comme « ϕ est satisfait (ou vrai) dans A » ou bien « A est modele de ϕ ».

Exemple. Une Lan-structure 〈K; 0, 1,+,−, ·〉 est un corps si et seulement sielle satisfait aux axiomes de corps (1)–(10) donnes auparavant.

Exercice 2.3.3. 1. Soit A une L-structure et B une partie non vide de Aqui contient les interpretations cA de toutes les constantes de L et quiest close sous toutes les operations fA. En restreignant les interpretationsdes symboles de A a B on obtient alors une L-structure B, appelee sous-structure de A. Nous ecrivons B ⊆ A si B est une sous-structure de A.Montrer que l’intersection d’une famille de sous-structures de A est unesous-structure ou vide. En deduire que toute partie non vide X de Aest contenue dans une plus petite sous-structure de A, appelee la sous-structure engendree par X et notee 〈X〉A. Montrer que l’ensemble de basede 〈X〉A est donne par {tA[α] | t ∈ T L et α : V → X}.

2. Soit A = 〈A; 0, 1,+,−, ·〉 une Lan-structure. On suppose que A est unanneau. Montrer que la sous-structure engendree par une partie X de Aest donnee par le sous-anneau engendre par X.

2.4 Substitution

Le but de ce paragraphe est de donner une bonne definition de la substitution(dans une formule ϕ) d’une variable x par un terme s, d’une telle maniere queles proprietes semantiques qu’on attend (voir 2.4.2) soient satisfaites.

On pourrait tout simplement remplacer toute occurrence libre de x dans ϕpar s, mais alors il se peut qu’une variable de s est liee, dans la formule ainsiobtenue, par un quanteur. Cela peut avoir des effets semantiques indesirables,comme par exemple pour ϕ(v0) = ∃v1¬v1=v0, x = v0 et s = v1. On obtiendrait

24

l’enonce ψ = ∃v1¬v1=v1 satisfait par aucune structure, tandis que si A contientau moins deux elements, alors A |= ϕ[a] pour tout a ∈ A.

La definition suivante, un peu plus compliquee, remedie a ce probleme.

Definition. Soient x0, . . . , xr des variables distinctes et s0, . . . , sr des termes.On definit la substitution simultanee des xi par les si comme suit.

1. Soit t un terme. Alors ts0/x0,...,sr/xr = ts/x est le mot obtenu en « rempla-cant simultanement toutes les occurrences de xi dans t par si », c’est-a-dire(par induction sur la hauteur de t)

– xs/x =

{x, si x 6= x0, . . . , x 6= xr

si, si x = xi– cs/x = c– [ft1 · · · tn]s/x = ft1s/x · · · t

ns/x.

2. Par induction sur la hauteur d’une formule, on definit

– [t=t′]s/x = ts/x=t′s/x ainsi que [Rt1 · · · tn]s/x = Rt1s/x · · · tns/x.

– [¬ψ]s/x = ¬ψs/x.– (ψ ∧ χ)s/x = (ψs/x ∧ χs/x).– Soient xi1 , . . . xik (i1 < . . . < ik) les variables parmi x0, . . . , xr qui sont

libres dans ∃xψ. (En particulier on a x 6= xi1 , . . . , x 6= xik .)– Si x n’a pas d’occurrence dans si1 , . . . , sik , on pose

[∃xψ]s/x = ∃xψsi1/xi1 ,...,sik/xik ;

– si x a une d’occurrence dans si1 , . . . , sik , on pose

[∃xψ]s/x = ∃uψsi1/xi1 ,...,sik/xik ,u/x, (2.1)

ou u est la premiere variable dans l’enumeration v0, v1, v2, . . . qui n’apas d’occurrence dans les mots ∃xψ, si1 , . . . , sik .

Exercice 2.4.1. Montrer (par induction sur la hauteur) :

1. Si t est un terme, alors ts/x est un terme.

2. Si ϕ est une formule, alors ϕs/x est une formule et on a ht(ϕs/x) = ht(ϕ).

Soient x0, . . . , xr des variables distinctes, α une affection a valeurs dans Aet a0, . . . , ar des elements de A. On definit l’affectation αa0/x0,...,ar/xr = αa/xcomme αa/x(xi) = ai et αa/x(y) = α(y) si y 6= xi pour tout i.

Proposition 2.4.2 (Lemme de substitution). Soient x0, . . . , xr des variablesdistinctes, s0, . . . , sr des termes et α une affectation a valeurs dans A.

1. Pour tout terme t on a tAs/x[α] = tA[αsA

0 [α]/x0,...,sAr [α]/xr

].

2. Pour toute formule ϕ on a

A |= ϕs/x[α] ⇐⇒ A |= ϕ[αsA

0 [α]/x0,...,sAr [α]/xr

].

25

Demonstration. (1) est facile. On montre (2) par induction sur la hauteur deϕ, le seul cas non evident etant ϕ = ∃xψ. Soient, comme dans la definitionde [∃xψ]s/x, les variables xi1 , . . . , xik exactement celles parmi les xi qui sontlibres dans ∃xψ. Le cas ou x n’a pas d’occurrence dans si1 , . . . , sik est facile etlaisse en exercice. Supposons donc que x a une occurrence dans l’un des termessi1 , . . . , sik , et soit u la variable choisie comme dans (2.1). On a alors

A |= [∃xψ]s/x[α] ⇐⇒ A |= ∃uψsi1/xi1 ,...,sik/xik ,u/x[α]⇐⇒ il existe a ∈ A tel que A |= ψsi1/xi1 ,...,sik/xik ,u/x[αa/u]⇐⇒ il existe a ∈ A tel que A |= ψ[αsA

i1[αa/u]/xi1 ,...,s

Aik

[αa/u]/xik ,uA[αa/u]/x]

(par hypothese d’induction)⇐⇒ il existe a ∈ A tel que A |= ψ[αsA

i1[α]/xi1 ,...,s

Aik

[α]/xik ,a/x]

(par 2.3.1, comme u est different de tous les xij )⇐⇒ A |= ∃xψ[αsA

i1[α]/xi1 ,...,s

Aik

[α]/xik]

⇐⇒ A |= ∃xψ[αsA0 [α]/x0,...,sA

r [α]/xr ]

La derniere equivalence suit de 2.3.2, car les affectations αsAi1

[α]/xi1 ,...,sAik

[α]/xik

et αsA0 [α]/x0,...,sA

r [α]/xr coıncident sur l’ensemble Lib(∃xψ).

Exemples 2.4.3. 1. Soit ϕ = ϕ(v0) = ∃v1¬v1=v0 et s = v1. Alors ϕs/v0 =∃v2[¬v1=v0]v1/v0,v2/v1 = ∃v2¬v2=v1.

2. Soient ϕ une formule et x1, . . . , xn des variables distinctes. On supposeque s1, . . . , sn ne contiennent pas de variables ayant une occurrence dansϕ. Alors ϕs/x est le mot obtenu en remplacant toute occurrence libre dexi par si. (Preuve par induction sur ht(ϕ), laissee en exercice.)

Lemme 2.4.4. Soit y une variable sans occurrence dans ϕ. Alors(ϕy/x

)x/y

=ϕ.

Demonstration. On fait une induction sur la hauteur de ϕ, le seul cas non trivialetant ϕ = ∃zψ. Si z = x, alors ni x ni y n’est libre dans ϕ = ∃xψ, d’ou(ϕy/x)x/y = ϕx/y = ϕ. Sinon, on a z 6= x et z 6= y, et alors ([∃zψ]y/x)x/y =(∃zψy/x)x/y = ∃z(ψy/x)x/y. Or (ψy/x)x/y = ψ par hypothese d’induction.

Notation. Soient s1, . . . , sn des termes. Si t(x1, . . . , xn) est un terme, nousecrivons souvent t(s1, . . . , sn) pour ts1/x1,...,sn/xn , et ϕ(s1, . . . , sn) au lieu deϕs1/x1,...,sn/xn si ϕ = ϕ(x1, . . . , xn) est une formule.

2.5 Formules universellement valides

Definition. Une L-formule ϕ est dite universellement valide, note |= ϕ, si elleest satisfaite par toute L-structure A et toute affectation α a valeurs dans A,c’est-a-dire si A |= ϕ[α] pour tout A et tout α.

Remarque 2.5.1. La formule ϕ = ϕ(x1, . . . , xn) est universellement valide siet seulement si l’enonce ∀x1, . . . , xnϕ est universellement valide.

On appelle ∀x1, . . . , xnϕ une cloture universelle de ϕ.

26

Exemples. 1. ∃xx=x est universellement valide. (Par definition, une struc-ture est non vide !)

2. Soient ϕ et ψ des L-formules quelconques. Alors (ϕ → (ψ → ϕ)) estuniversellement valide.

Le lemme suivant justifie que nous ne faisons pas reference au langage Ldans la notation |= ϕ.

Lemme 2.5.2. Soit ϕ une L-formule et L′ ⊇ L. Alors ϕ est universellementvalide en tant que L-formule si et seulement si elle l’est en tant que L′-formule.

Demonstration. Si A′ = 〈A; (ZA′)Z∈σL′ 〉 est une L′-structure, on pose A :=A′ �L := 〈A; (ZA′)Z∈σL〉, le reduit de A′ a L ⊆ L′ (la structure A′ est appeleeexpansion de A a L′).

On peut identifier les affectations a valeurs dans A et celles a valeurs dansA′, et on a A′ |= ϕ[α] ⇐⇒ A |= ϕ[α] pour toute affectation α.

Il suffit donc de montrer que toute L-structure A admet une expansion a uneL′-structure. Ceci est clair.

Afin de preciser un cadre pour les formules de la forme (ϕ → (ψ → ϕ))qui sont toujours verifiees independemment des valeurs de verite de ϕ et ψ, onintroduira les formules du calcul propositionnel.

On fixe un ensemble P = {pi | i ∈ N}, ou les pi sont des variables proposi-tionnelles (elles prennent comme valeurs « vrai » ou « faux »).

Les formules du calcul propositionnel sont des mots sur l’alphabet P ∪{¬,∧, (, )}, formes selon les regles suivantes :

– pi est une formule pour tout i ;– si F et G sont des formules, alors ¬F et (F ∧G) aussi.Soit FmlP l’ensemble des formules du calcul propositionnel. Comme avant

on introduit ∨,→ et ↔ comme abbreviations. On identifie Z/2 = {0, 1} avec{ « faux », « vrai »}, en associant 0 a « faux » et 1 a « vrai ». Une affectation(ou distribution de valeurs de verite) est une application δ : P → {0, 1}.

Toute affectation δ induit une fonction δ∗ : FmlP → {0, 1} donnee (inducti-vement) par δ∗(pi) = δ(pi), δ∗(¬F ) = 1− δ∗(F ) et δ∗((F ∧G)) = δ∗(F ) · δ∗(G).

On ecrit F = F (q1, . . . , qn) si les qi sont des variables distinctes et si toutesles variables ayant une occurrence dans F figurent parmi les qi.

Exercice 2.5.3. Pour toute fonction g : {0, 1}n → {0, 1} il existe une formuleF (p1, . . . , pn) telle que pour toute affectation δ on ait δ∗(F ) = g(δ(p1), . . . , δ(pn)).

Definition. 1. Une tautologie du calcul propositionnel est une formule F ∈FmlP telle que δ∗(F ) = 1 pour toute distribution de valeurs de verite δ.(Autrement dit, si F = F (q1, . . . , qn), alors F est vraie quelle que soientles valeurs de verite des qi.)

2. La L-formule ϕ est une tautologie du calcul des predicats s’il existe unetautologie F = F (q1, . . . , qn) du calcul propositionnel et des L-formulesψ1, . . . , ψn telles que ϕ = Fψ1/q1,...,ψn/qn (le mot obtenu en substituant lesψi aux variables qi).

27

Lemme 2.5.4. Les tautologies (du calcul des predicats) sont des formules uni-versellement valides.

Demonstration. Clair.

Lemme 2.5.5 (Axiomes de l’egalite).Les enonces suivants sont universellement valides :

– ∀xx=x (reflexivite)– ∀x, y (x=y → y=x) (symetrie)– ∀x, y, z ((x=y ∧ y=z)→ x=z) (transitivite)– ∀x1, . . . , xn, y1, . . . , yn (x1=y1 ∧ . . . ∧ xn=yn → fx1 · · ·xn=fy1 · · · yn)

pour tout f ∈ FLn (congruence 1)– ∀x1, . . . , xn, y1, . . . , yn (x1=y1 ∧ . . . ∧ xn=yn ∧Rx1 · · ·xn → Ry1 · · · yn)

pour tout R ∈ RLn (congruence 2)

Remarque. Ces enonces expriment que = est une relation de congruence,c’est-a-dire une relation d’equivalence qui est compatible avec les fonctions etles relations du langage.

Lemme 2.5.6 (Axiomes du quanteur existentiel). Soient ϕ une L-formule, tun L-terme et x une variable. Alors la formule ϕt/x → ∃xϕ est universellementvalide.

Demonstration. On pose ψ = ϕt/x → ∃xϕ. Soit α une affectation a valeurs dansA. Par le lemme de substitution, on a

A |= ϕt/x[α]⇒ A |= ϕ[αtA[α]/x

]⇒ A |= ∃xϕ[α].

On en deduit que A |= ψ[α].

Lemme 2.5.7 (Modus ponens). Si ϕ et (ϕ→ ψ) sont universellement valides,alors ψ aussi.

Lemme 2.5.8 (∃-introduction). On suppose que x n’est pas libre dans ψ. Alorssi ϕ→ ψ est universellement valide, ∃xϕ→ ψ l’est aussi.

Demonstration. Si A |= ∃xϕ[α], il existe a ∈ A tel que A |= ϕ[αa/x].Si |= ϕ→ ψ, on a donc A |= ψ[αa/x]. On en deduit A |= ψ[α] par Proposition

2.3.2, puisque x n’est pas libre dans ψ. Cela etablit A |= (∃xϕ→ ψ)[α].

Exemple. La restriction sur la variable x dans le lemme est necessaire, comele montre l’exemple suivant. Soient ϕ = ψ = x=c. On a |= ϕ → ψ, mais6|= (∃xx=c→ x=c).

Definition. Une L-theorie est un ensemble de L-enonces. Soit T une L-theorie.– Une L-structure A est modele de T , notee A |= T , si A |= ϕ pour toutϕ ∈ T .

– L’enonce ϕ est consequence logique de T si pour toute L-structure A quiest modele de T on a A |= ϕ. On le note T |= ϕ.

La preuve du lemme 2.5.2 montre que T |= ϕ ne depend pas du langage L.

28

2.6 Demonstrations formelles et theoreme de com-pletude de Godel

On va formaliser la notion de preuve.

Axiomes logiques :– les tautologies ;– les axiomes de l’egalite ;– (∃-ax) les axiomes du quanteur existentiel.

Regles de deduction :– (MP) A partir de ϕ et ϕ→ ψ, on peut deduire ψ.– (∃-intro) Supposons x non libre dans ψ. A partir de ϕ → ψ, on peut

deduire ∃xϕ→ ψ.

Definition. Soit ϕ une L-formule et T une L-theorie. Une preuve formelle deϕ dans T est une suite finie de L-formules (ϕ0, . . . , ϕn) avec ϕn = ϕ et telle que,pour chaque i ≤ n, soit ϕi ∈ T , soit ϕi est un axiome logique, soit il s’obtientpar (MP) a partir de ϕj et ϕk avec j, k < i, soit il s’obtient par (∃-intro) a partird’une formule ϕj avec j < i.

On dit que ϕ est prouvable dans T , notee T `L ϕ, s’il existe une preuveformelle de ϕ dans T .

A priori, `L depend du langage L dans lequel la formule ϕ et la theorie Tsont considerees, car si L′ ⊇ L, il y a plus de L′-preuves que de L-preuves.Nous verrons plus tard que T |= ϕ si et seulement si T `L ϕ, ce qui montrera enparticulier que la prouvabilite d’une formule est une notion qui est independantedu langage.

Dans la suite, on donnera aussi des preuves (ϕ0, . . . , ϕn) dans lesquelles desformules ϕi dont la prouvabilite a deja ete etablie anterieurement seront utiliseescomme axiomes. On pourra toujours transformer une telle preuve en une preuveformelle — il suffit de remplacer ϕi par une preuve formelle de ϕi.

On utilisera parfois l’axiome (derive) et les regles (derivees) qui sont donnesdans le lemme suivant.

Lemme 2.6.1.

1. (MPGen) Si T `L ϕi pour i = 1, . . . , n et T `L ϕ1 ∧ . . . ∧ ϕn → ψ, alorsT `L ψ.

2. (∀-ax) On a `L ∀xϕ → ϕt/x pour toute L-formule ϕ, tout L-terme t ettoute variable x.

3. (∀-intro) Si x n’est pas libre dans ϕ et si T `L ϕ → ψ, alors T `L ϕ →∀xψ.

4. (Generalisation) Si T `L ψ, alors T `L ∀xψ.

29

Demonstration. (1) La formule suivante est une tautologie :

((ϕ1 ∧ . . . ∧ ϕn → ψ)→ (ϕ1 → (ϕ2 → . . .→ (ϕn → ψ) · · · ).

On applique (MP) n+ 1 fois pour obtenir T `L ψ.(2) Soient ϕ, t et x donnes. Voici une preuve formelle de ∀xϕ→ ϕt/x (rap-

pelons que ∀xϕ = ¬∃x¬ϕ par definition) :ϕ0 = (¬ϕt/x → ∃x¬ϕ) (∃-ax)ϕ1 = (¬ϕt/x → ∃x¬ϕ)→ (¬∃x¬ϕ→ ϕt/x) (tautologie)ϕ2 = ∀xϕ→ ϕt/x ((MP) sur ϕ0 et ϕ1)

(3) La preuve de (∀-intro) est similaire que celle de (∀-ax). On l’obtient parcontraposition a partir de (∃-intro).

(4) On suppose T `L ψ. On choisit un enonce prouvable ϕ.ϕ0 = ϕ (prouvable par notre choix)ϕ1 = ψ (prouvable dans T par hypothese)ϕ2 = ψ → (ϕ→ ψ) (tautologie)ϕ3 = ϕ→ ψ ((MP) sur ϕ1 et ϕ2)ϕ4 = ϕ→ ∀xψ ((∀-intro) appliquee a ϕ3)ϕ5 = ∀xψ ((MP) sur ϕ0 et ϕ4)

Lemme 2.6.2 (Lemme de deduction). Soit χ un L-enonce, T une L-theorie etϕ une L-formule.

1. T ∪ {χ} `L ϕ ssi T `L χ→ ϕ.

2. T `L ϕ ssi il existe ψ1, . . . , ψn ∈ T tels que `L (ψ1 ∧ · · · ∧ ψn)→ ϕ.

Demonstration. (1) Il est clair que T `L χ → ϕ entraıne T ∪ {χ} `L ϕ. Reci-proquement, soit (ϕ0, . . . , ϕn) une preuve formelle de ϕ = ϕn dans T ∪{χ}. Parinduction sur i, on montrera que T `L (χ → ϕi). Si ϕi = χ, c’est clair, et siT `L ϕi, cela suit de (MP) et du fait que (ϕi → (χ → ϕi)) est une tautologie.Cela montre T `L (χ → ϕi) dans les cas ou ϕi est un axiome logique ou unelement de T .

Si ϕi s’obtient par (MP) a partir de ϕj et ϕk = (ϕj → ϕi) pour j, k < i, ilsuffit d’utiliser (MP) et le fait que ((χ → ϕj) ∧ (χ → (ϕj → ϕi)) → (χ → ϕi))est une tautologie.

Enfin, si ϕi = (∃xψ → ϕ) s’obtient par (∃-intro) a partir de ϕj = (ψ → ϕ)pour j < i (donc x n’est pas libre dans ϕ), on utilise la tautologie (F → (G→H)) → (G → (F → H)) deux fois et le fait que x n’est pas libre dans (χ → ϕ)pour conclure :

T `L χ→ (ψ → ϕ) ⇒ T `L ψ → (χ→ ϕ)(par ∃-intro) ⇒ T `L ∃xψ → (χ→ ϕ)

⇒ T `L χ→ (∃xψ → ϕ)

La partie (2) se deduit facilement de (1).

30

Lemme 2.6.3 (Simulation des constantes par des variables). Soit ψ une L-formule, T une L-theorie, et C un ensemble de constantes tel que L ∩ C = ∅.

(a) Soit x une variable et c ∈ C. Les proprietes suivantes sont equivalentes :

(1) T `L ψ(2) T `L∪{c} ψc/x(3) T `L∪{c} ψ

(b) On a T `L ψ si et seulement si T `L∪C ψ.

Demonstration. On supposera dans la preuve que T = ∅. La preuve du casgeneral est la meme. Montrons d’abord la partie (a).

(1)⇒(3) est triviale. (Toute L-preuve est une L ∪ {c}-preuve.)(3)⇒(2). Si `L∪{c} ψ, alors `L∪{c} ∀xψ par generalisation. En utilisant (∀-

ax) et (MP), on obtient `L∪{c} ψc/x.(2)⇒(1). Pour ϕ une L∪{c}-formule et y une variable sans occurrence dans

ϕ, on notera ϕ = ϕy/c le mot obtenu en substituant toute occurrence de c dansϕ par y.

Soient ϕ, ψ et χ des L ∪ {c}-formules sans occurrences de y. Alors on a lesproprietes suivantes :

(i) ϕ est une L-formule.(ii) ϕc/y = ϕ.(iii) Si ϕ est un axiome d’egalite (respectivement une tautologie ou un ∃-

axiome), alors ϕ aussi.(iv) Si ϕ s’obtient par (MP) a partir de ψ et χ, alors ϕ s’obtient par (MP)

a partir de ψ et χ.(v) Si ϕ s’obtient par (∃-intro) a partir de ψ, alors ϕ s’obtient par (∃-intro)

a partir de ψ.On peut montrer (i) par induction sur la hauteur de ϕ, et (ii) est une conse-

quence de l’exemple 2.4.3(2). Les proprietes (iv) et (v) sont immediates, dememe les cas d’un axiome d’egalite ou d’une tautologie dans (iii). Reste a ve-rifier le cas d’un (∃-ax) dans (iii) : Si ϕ = (δt/x → ∃xδ), il faut monter queϕ = ([δt/x]y/c → ∃x[δ]y/c) est un axiome de quanteur existentiel. Ceci est uneconsequence de l’identite

[δt/x]y/c = [δy/c]ty/c/x

dont la preuve se fait par induction et est laissee en exercice.Maintenant, soit (ϕ0, . . . , ϕm) une L∪{c}-preuve formelle de ψc/x. On choisit

une variable y sans occurrence dans ϕ0, . . . , ϕm et telle que y 6= x.On deduit des proprietes (i)-(v) que (ϕ0, . . . , ϕm) est une L-preuve formelle

de ϕm = (ψc/x)y/c = ψy/x. (On utilise 2.4.3(2) pour etablir cette egalite.) Engeneralisant on obtient `L ∀yψy/x.

On utilise (∀-ax) et (MP) pour montrer `L (ψy/x)x/y. Or, le lemme 2.4.4montre que

(ψy/x

)x/y

= ψ, ce qui termine la preuve de (2)⇒(1).

31

La partie (b) est une consequence immediate de (a). En effet, comme touteL ∪ C-preuve n’utilise qu’un nombre fini de constantes de C, on peut supposerque C est fini. On termine donc par une induction sur le cardinal de C, enutilisant (1)⇔(3).

Definition. Soit T une L-theorie.– T est contradictoire s’il existe un enonce ϕ tel que T `L ϕ et T `L ¬ϕ.– T est coherente si elle est non contradictoire.– T est complete si elle est coherente et pour tout L-enonce ϕ on a soitT `L ϕ, soit T `L ¬ϕ.

Remarque 2.6.4. Pour une L-theorie T , sont equivalents :1. T est contradictoire ;2. T `L ϕ pour tout L-enonce ϕ ;3. il existe ψ1, . . . , ψn ∈ T tels que `L ¬(ψ1 ∧ · · · ∧ ψn).

Demonstration. Exercice.

Lemme 2.6.5. Soit T une L-theorie.1. Soit ψ un L-enonce. Alors T `L ψ ssi T ∪ {¬ψ} est contradictoire.2. Soit ϕ(x) une L-formule et c ∈ L une constante qui n’a pas d’occurrence

dans T ∪ {ϕ(x)}. On suppose que T est coherente. Alors la theorie T ∪{∃xϕ→ ϕc/x} est une L-theorie coherente.

Demonstration. (1) Le sens direct est clair. Reciproquement, si T ∪ {¬ψ} estcontradictoire, par le lemme de deduction, il existe un L-enonce ϕ tel que T `Lψ → ϕ et T `L ψ → ¬ϕ. On utilise la tautologie ((ψ → ϕ) → (ψ → ¬ϕ)) → ψet (MP) pour conclure.

(2) Si la conclusion etait fausse, on aurait T `L ∃xϕ∧¬ϕc/x par la premierepartie du lemme. Par le lemme de deduction il existerait donc ψ1, . . . , ψn ∈ Ttels que `L (ψ1 ∧ . . . ∧ ψn)→ (∃xϕ ∧ ¬ϕc/x).

Nous allons montrer que si `L ψ → (∃xϕ ∧ ¬ϕc/x) pour un L-enonce ψqui ne contient pas c, alors `L ¬ψ. En effet, on a clairement `L ¬∃xϕ → ¬ψet `L ϕc/x → ¬ψ. Le dernier donne `L ϕ → ¬ψ par le Lemme 2.6.3(a), puis`L ∃xϕ → ¬ψ par (∃-intro). En utilisant des tautologies convenables et (MP),on obtient `L ¬ψ.

Exemples 2.6.6. 1. Soit A une L-structure. Alors Th(A) := {ϕ L-enonce |A |= ϕ} est une theorie, appelee la theorie de A. C’est une theorie com-plete. (Sa coherence sera une consequence de la direction facile du theo-reme de completude.)

2. La theorie des corps algebriquement clos est la Lan-theorie CAC qui outreles axiomes de corps contient un enonce χn pour tout n ≥ 1 exprimantque tout polynome de degre n a une racine.[χn = ∀z0, . . . , zn−1∃x(xn+zn−1x

n−1 + . . .+z0=0) marche ; cette formulepeut etre reecrite dans Lan.]

32

Theoreme 2.6.7 (Theoreme de completude de Godel). Soit T une L-theorieet ϕ un L-enonce. Alors T |= ϕ si et seulement si T `L ϕ.

Remarque. Comme |= ne depend pas du langage considere, a postiori `L n’endepend pas non plus. Une fois le theoreme de completude etabli, nous ecrivonsdonc ` au lieu de `L.

Demonstration. T `L ϕ ⇒ T |= ϕ. Ce sens facile exprime que notre calcul depreuves formelles est correct. En effet, `L ϕ ⇒ |= ϕ est une consequence deslemmes 2.5.4–2.5.8. Si T `L ϕ, il existe ψ1, . . . , ψn ∈ T tels que `L (ψ1 ∧ . . . ∧ψn) → ϕ. Donc |= (ψ1 ∧ . . . ∧ ψn) → ϕ et alors pour tout A |= T on a A |= ϕ(car A |= ψ1 ∧ . . . ∧ ψn).

T |= ϕ ⇒ T `L ϕ. C’est le sens non trivial. Il sera consequence du theoremed’existence de modele suivant. En fait, comme

T 6|= ϕ ⇐⇒ T ∪ {¬ϕ} a un modele (par definition), etT 6`L ϕ ⇐⇒ T ∪ {¬ϕ} est coherente (Lemme 2.6.5(1)),

ce theoreme est equivalent au theoreme de completude.

Theoreme 2.6.8. Une theorie a un modele si et seulement si elle est coherente.

Demonstration. La direction facile a deja ete montree. Pour montrer que toutetheorie coherente T a un modele, l’idee est de construire une expansion T+

de T dans un langage L+ ⊇ L qui ressemble au « diagramme complet d’unestructure ». Nous avons besoin d’une definition.

Definition. Soit L un langage et C un ensemble de constantes avec L∩C = ∅.On dit qu’une L ∪ C-theorie T+ admet des temoins de Henkin dans C si pourtoute L ∪ C-formule ϕ = ϕ(x) il existe c ∈ C tel que ∃xϕ→ ϕc/x ∈ T+.

Si A est une L-structure et A = {ac | c ∈ C} une enumeration (non necessai-rement injective) de son ensemble de base par C, on note A+ la L∪C-structureobtenue a partir de A en interpretant c par ac. Alors Th(A+) est une theo-rie complete qui admet des temoins de Henkin dans C. En fait, toute theoriecomplete qui admet des temoins de Henkin dans C est de cette forme :

Proposition 2.6.9. Toute L ∪ C-theorie complete T+ qui admet des temoinsde Henkin dans C a un modele A+ forme de constantes de C, c’est-a-dire dontl’ensemble de base est de la forme A+ = {cA+ | c ∈ C}.

Demonstration de 2.6.9. Quitte a remplacer T+ par {ϕ L ∪ C-enonce | T+ `L∪Cϕ}, on peut supposer que T+ est deductivement close (T `L∪C ϕ ssi ϕ ∈ T+).

Sur C, la relation c ∼ d :⇐⇒ c=d ∈ T+ est une relation d’equivalence. Eneffet, cela decoule des axiomes de l’egalite. On pose ac := c/∼ et A+ := {ac |c ∈ C}. Evidemment, on a A+ 6= ∅. On definit une L ∪ C-structure A+ sur A+

comme suit :

33

– Pour d une constante, on pose dA+:= ac si c=d ∈ T+. Pour montrer

qu’un tel c existe, on raisonne ainsi : d=d → ∃xx=d ∈ T+ (par (∃-ax)),donc ∃xx=d ∈ T+ par (MP) ; comme T+ admet des temoins de Henkin,il existe c ∈ C tel que ∃xx=d→ c=d ∈ T+, d’ou c=d ∈ T+ par (MP).C’est bien defini par les axiomes de l’egalite.

– R ∈ RLn . On definit (ac1 , . . . , acn) ∈ RA+:⇐⇒ Rc1 · · · cn ∈ T+.

C’est bien defini par les axiomes de l’egalite (congruence 2).

– f ∈ FLn . On definit fA+(ac1 , . . . , acn) = ac0 :⇐⇒ fc1 · · · cn=c0 ∈ T+.

On montre sans probleme en utilisant les axiomes de l’egalite (congruence1) que c’est bien defini. Un argument similaire a celui donne pour lesconstantes montre que fA+

est une fonction qui est definie partout.

(I) Si t est un L ∪ C-terme sans variable, alors tA+

= ac ⇐⇒ t=c ∈ T+.

(II) Soit ψ un L ∪ C-enonce. Alors A+ |= ψ ⇐⇒ ψ ∈ T+.

On demontre (I) par induction sur ht(t), en utilisant les axiomes de l’egalite.Quant a (II), on raisonne par induction sur ht(ψ), ou ψ est un L∪C-enonce.

Rappelons que ht(ϕ) = ht(ϕs/x) (voir l’exercice 2.4.1).Si ψ = t1=t2, alors (II) suit de (I).Si ψ = Rt1 · · · tn, on choisit ci ∈ C tel que tA

+

i = aci . Comme ti=ci ∈ T+,on a A+ |= ψ ⇐⇒ Rc1 · · · cn ∈ T+ ⇐⇒ ψ ∈ T+. La premiere equivalence suitde la definition de A+, la seconde suit de la congruence 2.

Le cas ψ = (ϕ1 ∧ ϕ2) est facile.Si ψ = ¬ϕ, on a A+ |= ψ ⇐⇒ A+ 6|= ϕ ⇐⇒ ϕ 6∈ T+ ⇐⇒ ψ ∈ T+,

puisque T+ est complete par hypothese.Finalement, soit ψ = ∃xϕ. On montre d’abord que ψ ∈ T+ ⇐⇒ il existe

c ∈ C tel que ϕc/x ∈ T+. En effet, comme T+ admet des temoins de Henkindans C, on a le sens direct. Pour le sens indirect, il suffit d’appliquer (∃-ax),(MP) et utiliser que T+ est deductivement close.

On obtient les equivalences A+ |= ψ ⇐⇒ A+ |= ϕ[ac] pour un c ∈ C(Lemme de substitution) ⇐⇒ A+ |= ϕc/x pour un c ∈ C(Hypothese d’induction) ⇐⇒ ϕc/x ∈ T+ pour un c ∈ C

⇐⇒ ψ ∈ T+

A+ est donc un modele de T+ qui est forme de constantes de C.

Le lemme suivant terminera la preuve du theoreme 2.6.8, car si A+ est unmodele de la L+ = L ∪ C-theorie T+ avec T+ ⊇ T , alors le reduit de A+ aulangage L est un modele de T .

Lemme 2.6.10. Soit T une L-theorie coherente. Alors il existe une L ∪ C-theorie complete T+ contenant T qui admet des temoins de Henkin dans C.

Demonstration. Pour toute L-formule a une variable libre ϕ = ϕ(x) on introduitune nouvelle constante cϕ. Soit C1 l’ensemble des cϕ. On pose L1 = L ∪ C1 etT1 := T := T ∪{∃xϕ→ ϕcϕ/x | ϕ = ϕ(x)}. Montrons que T1 est une L1-theoriecoherente. Comme une theorie est coherente si et seulement si toute partie finie

34

est coherente, il suffit evidemment de montrer que la theorie T ′ = T ∪{∃xiϕi →ϕicϕi/xi

} est coherente pour tout ensemble fini {ϕ1, . . . , ϕn} de formules. CommeT est coherente en tant que L1-theorie par 2.6.3, c’est une consequence du lemme2.6.5(2), quitte a raisonner par induction sur n.

On repete cette construction, avec C2 un ensemble de nouvelles constantes,L2 := L1 ∪ C2 et la L2-theorie T2 := T1. On montre qu’il s’agit d’une theoriecoherente. Si Tn est construite, on trouve Tn+1 := Tn, une theorie coherentedans le langage Ln+1 = Ln ∪ Cn+1. Posons C :=

⋃n∈N Cn et L+ := L ∪ C.

Alors (Tn)n∈N est une suite croissante de L+-theories coherentes. La L+-theorieT ′ :=

⋃n∈N Tn est alors coherente. Par construction, elle admet des temoins de

Henkin dans C.Comme toute L+-theorie S′ contenant T ′ admet des temoins de Henkin

dans C, il reste a montrer que toute L+-theorie coherente est contenue dansune L+-theorie complete. C’est une consequence du Lemme de Zorn. En effet,l’ensemble S = {S′ ⊇ T ′ | S′ et une L+-theorie coherente} est non vide etordonne partiellement par inclusion. Comme la reunion d’une chaıne de theoriescoherentes est coherente, cet ordre est inductif. Par le lemme de Zorn, il existe unelement maximal dans S, autrement dit il existe une L+-theorie T+ ⊇ T ′ qui estmaximale coherente. Soit ϕ un L+-enonce. Si T 6`L+ ϕ, la L+-theorie T+∪{¬ϕ}est coherente par 2.6.5(1). On en deduit que ¬ϕ ∈ T+ par maximalite, ce quimontre que T+ est complete et termine la preuve.

Si L est denombrable, le lemme admet une preuve par une construction plusdirecte. Nous allons l’esquisser maintenant. On choisit un ensemble C = {cn |n ∈ N} de nouvelles constantes et on enumere l’ensemble des L∪C-enonces viaϕ1, ϕ2, . . .. Par induction, on construit une suite croissante de L ∪ C-theoriescoherentes ayant les proprietes suivantes :

– T0 = T , et Tn \ T est fini pour tout n ∈ N ;– ϕn ∈ Tn+1 ou ¬ϕn ∈ Tn+1 ;– si ϕn = ∃xψ, alors il existe c ∈ C tel que ψc/x ∈ Tn+1.

Une fois la suite des Tn construite, il suffit de poser T+ :=⋃n∈N Tn. C’est une

theorie complete par construction, et elle admet des temoins de Henkin dans C.En effet, soit ψ(x) donnee. Alors il existe n ∈ N tel que ∃xψ = ϕn. Si ϕn ∈ T+,alors par construction ψc/x ∈ T+ pour un c ∈ C, donc ∃xψ → ψc/x ∈ T+.Sinon, on a ¬∃xψ ∈ T+, d’ou trivialement ∃xψ → ψc/x ∈ T+ pour tout c.

Supposons Tn construite. Si Tn ∪ {ϕn} est coherente, on pose ψn = ϕn.Sinon, ψn = ¬ϕn. Dans les deux cas, Tn ∪ {ψn} est coherente. Si ψn n’est pasde la forme ∃xχ, on pose Tn+1 := Tn ∪ {ψn}. Sinon, soit m minimal tel que cmn’a pas d’occurrence dans Tn (il existe car Tn \ T est fini). On pose Tn+1 :=Tn ∪ {ψn, χcm/x}. La theorie Tn+1 est coherente par le lemme 2.6.5(2).

35

Chapitre 3

Premiers pas en theorie desmodeles

3.1 Quelques theoremes fondamentaux

Theoreme 3.1.1 (Theoreme de compacite). Soit T une theorie dont toutepartie finie a un modele. Alors T a un modele.

Demonstration. La theorie T est coherente si et seulement si toute partie finiede T est coherente. Le resultat suit du theoreme 2.6.8.

Exercice. Soit X l’ensemble des L-theories T completes et closes par deduction.Sur X, on definit une topologie de la maniere suivante. Pour ϕ un L-enonce, onnote 〈ϕ〉 := {T ∈ X | ϕ ∈ T}, et on prend la collection des 〈ϕ〉 comme based’ouverts d’une topologie. Montrer :

1. 〈ϕ∧ψ〉 = 〈ϕ〉 ∩ 〈ψ〉 et 〈¬ϕ〉 = X \ 〈ϕ〉. En particulier, les 〈ϕ〉 forment unebase d’ouverts-fermes.

2. Cette topologie est compacte et separee.

Definition. Soient M et N des L-structures.

1. On dit que M et N sont elementairement equivalentes, si Th(M) = Th(N),c’est-a-dire si elles satisfont les memes enonces. On le note M ≡ N.

2. Soit M une sous-structure de N (ce que l’on note M ⊆ N). On dit quec’est une sous-structure elementaire (et N est appelee extension elemen-taire de M) si pour toute L-formule ϕ = ϕ(x1, . . . , xn) et tout upleta = (a1, . . . , an) ∈ Mn on a M |= ϕ[a] si et seulement si N |= ϕ[a].On le note M 4 N.

Remarque. 1. Si M 4 N, alors M ≡ N.

2. Si M et N sont isomorphes, alors M ≡ N.

36

L’exemple suivant montre que M ⊆ N et M ≡ N n’entraıne pas toujoursM 4 N.

Exemple. Dans le langage L<, on considere N := 〈N;<〉 et M := 〈N∗;<〉, ouN∗ := N \ {0}.

On a M ⊆ N et M ∼= N, en particulier M ≡ N. Or, l’extension M ⊆ N n’estpas elementaire, puisque M |= ¬∃xx < 1 et N |= ∃xx < 1.

Theoreme 3.1.2 (Test de Tarski-Vaught). Soient M ⊆ N deux L-structures.On suppose que pour toute L-formule ϕ(x0, . . . , xn) et tout uplet (a1, . . . , an) ∈Mn, s’il existe b0 ∈ N tel que N |= ϕ[b0, a1, . . . , an], alors il existe a0 ∈ M telque N |= ϕ[a0, a1, . . . , an]. Alors M 4 N.

Demonstration. Par induction sur ht(ϕ(x1, . . . , xn)) on montre : pour tout a ∈Mn on a M |= ϕ[a] ⇐⇒ N |= ϕ[a].

Si ϕ est une formule atomique, c’est vrai car M est une sous-structure de N.Le cas des connecteurs logiques est clair.Soit donc ϕ = ϕ(x1, . . . , xn) = ∃x0ψ(x0, . . . , xn). (Comme x0 n’est pas libre

dans ϕ, on peut supposer que x0 6= xi pour i = 1, . . . , n.) Soit (a1, . . . , an) ∈Mn.On a M |= ϕ[a1, . . . , an] ⇐⇒ il existe a0 ∈M tel que M |= ψ[a0, . . . , an](hypothese d’induction) ⇐⇒ il existe a0 ∈M tel que N |= ψ[a0, . . . , an]

(hypothese du theoreme) ⇐⇒ il existe b0 ∈ N tel que N |= ψ[b0, . . . , an]⇐⇒ N |= ϕ[a1, . . . , an].

Notons que pour tout langage L on a card(L) = card(FmlL) ≥ card(T L).(Exercice.)

Theoreme 3.1.3 (Theoreme de Lowenheim-Skolem descendant). Soit M uneL-structure et A ⊆ M une partie de l’ensemble de base de M. On suppose quecard(M) ≥ card(L). Alors il existe une sous-structure elementaire M0 de Mcontenant A et de cardinalite sup(card(A), card(L)).

Demonstration. Quitte a agrandir A on peut supposer que card(A) ≥ card(L).Dans cette preuve, si ∅ 6= B ⊆ M , nous notons B ⊆ M l’ensemble de

base de 〈B〉M (la sous-structure engendree par B). On a B = {tM[b1, . . . , bn] |t = t(x1, . . . , xn) ∈ T L, b1, . . . , bn ∈ B} (Exercice 2.3.3). En particulier, sicard(B) ≥ card(L), alors card(B) = card(B), puisqu’il existe une surjection deT L ×

⋃n∈N B

n sur B.Soit A0 := 〈A〉M et A0 := A. Etant defini Ai ⊆M , on construit Ai+1 comme

suit. Pour toute L-formule ϕ(x0, . . . , xn) et tout n-uplet a ∈ Ani , si M |= ϕ[b0, a]pour un b0 ∈ M , on choisit c(ϕ, a) ∈ M tel que M |= ϕ[c(ϕ, a), a]. On poseBi+1 := Ai ∪ {c(ϕ, a) | ϕ = ϕ(x0, . . . , xn) ∈ FmlL, a1, . . . , an ∈ Ai}, puisAi+1 := Bi+1, l’ensemble de base de Ai+1 = 〈Bi+1〉M.

Soit M0 :=⋃i∈N Ai. Alors M0 contient cM pour tout c ∈ CL et est clos par

fM pour tout f ∈ FL. C’est donc l’ensemble de base d’une sous-structure M0

de M.

37

Soit ϕ = ϕ(x0, . . . , xn) une formule, a ∈Mn0 et b0 ∈M tel que M |= ϕ[b0, a].

Il existe N ∈ N tel que a1, . . . , an ∈ AN . Par construction de AN+1 il existec0 ∈ AN+1 ⊆ M0 tel que M |= ϕ[c0, a]. Donc M0 4 M par le test de Tarski-Vaught. Le fait que card(M0) = card(A) est clair.

Exemples 3.1.4. Soit R = 〈R; +,−, 0, 1, ·, <〉 le corps ordonne des reels.

1. Il existe R′ ≡ R avec R′ non archimedien, c’est-a-dire contenant un ele-ment ε > 0 tel que n · ε = ε+ . . .+ ε︸ ︷︷ ︸

n fois

< 1 pour tout n ∈ N. Un tel ε est

appele infinitesimal.

2. Il existe R′ 4 R tel que R′ ne soit pas complet.

Demonstration. (1) Soit c une nouvelle constante et L := Lc.ord ∪ {c}. Onconsidere la L-theorie T := Th(R) ∪ {0 < c} ∪ {ϕn = c+ . . .+ c︸ ︷︷ ︸

n fois

< 1 | n ∈ N}.

Soit T0 ⊆ T une partie finie. Alors il existe N ∈ N tel que ϕm 6∈ T0 pour toutm ≥ N . L’expansion de R a L obtenue en interpretant c par 1/N ∈ R est doncun modele de T0. Par compacite, T a un modele R′. L’element ε = cR

′montre

que R′ n’est pas archimedien.(2) Par le theoreme de Lowenheim-Skolem descendant (pour A = ∅), il existe

R′ 4 R avec R′ denombrable. On a Q ⊆ R′, car R′ est un corps. On choisitr ∈ R \R′. Alors la partie {r′ ∈ R′ | r′ < r} n’a pas de supremum dans R′, carR′ est dense dans R.

Remarque. On peut montrer que Ralg 4 R, ou Ralg = 〈Ralg; +,−, 0, 1, ·, <〉et Ralg = {r ∈ R | il existe 0 6= p(X) ∈ Q[X] tel que p(r) = 0}.

Definition. Soit P une propriete que chaque L-structure est susceptible deverifier ou non.

On dit que P est axiomatisable (resp. finiment axiomatisable) s’il existeune L-theorie T (resp. un L-enonce ϕ) telle que pour toute L-structure M, lapropriete P est satisfaite par M si et seulement si M |= T (resp. M |= ϕ).

Dans ce cas, on dit que T (resp. ϕ) axiomatise la propriete P.

Proposition 3.1.5. Soit P une propriete que chaque L-structure est susceptiblede verifier ou non. Alors P est finiment axiomatisable si et seulement si et P etla negation de P sont axiomatisables.

Demonstration. Si ϕ axiomatise P, alors ¬ϕ axiomatise la negation de P. Re-ciproquement, on suppose que T axiomatise P et que T ′ axiomatise la nega-tion de P. La theorie T ∪ T ′ est contradictoire. Il existe donc ϕ1, . . . , ϕn ∈ T ,ϕ′1, . . . , ϕ

′m ∈ T ′ tels que {ϕ1, . . . , ϕn, ϕ

′1, . . . , ϕ

′m} soit contradictoire. On a

M |= T ⇒M |=n∧i=1

ϕi ⇒M 6|=m∧i=1

ϕ′i ⇒M 6|= T ′ ⇒M |= T.

Cela montre que ϕ =∧ni=1 ϕi est une axiomatisation finie de P.

38

Exemples 3.1.6. 1. Soit p un nombre premier. Alors les corps de caracte-ristique p sont finiment axiomatisables (dans le langage Lan).

2. Les corps de caracteristique 0 sont axiomatisables dans Lan, mais pasfiniment. (En effet, si l’enonce ϕ0 etait une axiomatisation finie, il seraitconsequence de ϕcorps ∪ {¬ 1 + . . .+ 1︸ ︷︷ ︸

p fois

=0 | p premier}, et on aurait alors

ϕcorps ∪ {¬ 1 + . . .+ 1︸ ︷︷ ︸p fois

=0 | p premier et p < N} ` ϕ0 pour un N ∈ N.

Contradiction, puisqu’il existe des corps de caracteristique p > N .)3. Les corps ordonnes archimediens ne sont pas axiomatisables (cf. 3.1.4(1)).4. Les corps ordonnes complets ne sont pas axiomatisables (cf. 3.1.4(2)).

On observe que les deux derniers exemples precisent ce que nous avons ditau debut du chapitre 2.

3.2 La methode des diagrammes

Soit M une L-structure. On considere le langage LM obtenu en rajoutanta L une constante nouvelle cm pour chaque element m de M . La structure Madmet une expansion naturelle au langage LM , en interpretant cm par m. Onnote M∗ la LM -structure ainsi obtenue.

Par abus de notation, on identifiera parfois m et cm dans la suite. Cela nepose pas de vrai probleme, a cause du lemme de substitution.

Definition. 1. Le diagramme complet de M, note D(M), est defini commeTh(M∗). Il est donc forme des ϕ(cm1 , . . . , cmn), ou ϕ = ϕ(x1, . . . , xn) estune L-formule et m ∈Mn tel que M |= ϕ[m1, . . . ,mn].

2. Le diagramme simple de M, note ∆(M), est forme des ϕ(cm1 , . . . , cmn), ouϕ est une L-formule sans quanteur et m ∈Mn tel que M |= ϕ[m1, . . . ,mn].

Proposition 3.2.1. Les reduits au langage L des modeles de D(M) corres-pondent, a L-isomorphisme pres, aux extensions elementaires de M.

Demonstration. Soit N∗ |= D(M) et N := N∗ � L son L-reduit. L’applicationm 7→ cNm definit un isomorphisme entre M et une sous-structure elementaire deN (exercice facile).

Reciproquement, si M 4 N, il suffit de considerer la LM -expansion N∗ deN obtenue en interpretant cm par m. On a alors N∗ |= D(M). En effet, soitϕ(cm1 , . . . , cmn) ∈ D(M). Alors M |= ϕ[m1, . . . ,mn] ⇒ N |= ϕ[m1, . . . ,mn] ⇒N∗ |= ϕ(cm1 , . . . , cmn), par elementarite et le lemme de substitution.

Proposition 3.2.2. Les reduits au langage L des modeles de ∆(M) corres-pondent, a L-isomorphisme pres, aux extensions de M.

Demonstration. Similaire a la preuve precedente.

Exercice 3.2.3.

39

1. Soient M1 et M2 deux L-structures. Montrer que M1 ≡M2 si et seulements’il existe N1,N2 et P telles que Mi

∼= Ni et Ni 4 P pour i = 1, 2.(Indication : On pourra montrer que D(M1) ∪ D(M2) est une theoriecoherente, ou les deux ensembles de constantes sont choisis disjoints.)

2. Soit T = Th(N), ou N est la Lar-structure 〈N;S, 0,+, ·, <〉. Montrer qu’ilexiste N′ |= T tel que N ′ contienne un nombre premier non standardp′ (par cela, on entend que N′ |= ∀x(∃y x · y=p′ → (x=1 ∨ x=p′)) etN′ |= (S · · ·S︸ ︷︷ ︸

n fois

0) < p′ pour tout n ∈ N).

Theoreme 3.2.4 (Theoreme de Lowenheim-Skolem ascendant). Soit M uneL-structure infinie et κ un cardinal tel que κ ≥ sup(card(M), card(L)). Alors ilexiste une extension elementaire de M qui est de cardinalite κ.

Corollaire 3.2.5. Soit T une theorie ayant un modele infini. Alors T a unmodele en tout cardinal ≥ card(L).

Demonstration du theoreme 3.2.4. Il suffit de construire une extension elemen-taire N de M qui est de cardinalite ≥ κ, puis d’appliquer le theoreme deLowenheim-Skolem descendant a un ensemble A ⊆ N de cardinalite κ et conte-nant M .

Pour chaque i ∈ κ, soit ci une nouvelle constante. Soit L := LM∪{ci | i ∈ κ},et soit T := D(M) ∪ {¬ci=cj | i < j < κ}. C’est une L-theorie qui est finimentsatisfaisable. En effet, si T0 est une partie finie de T , il suffit d’interpreter lessymboles de constantes ci1 , . . . , cin qui apparaissent dans T0 par des elementsdistincts de M pour construire une expansion de M∗ qui est modele de T0.Comme M est infini, c’est possible. Par compacite, on trouve alors N |= Tdont le L-reduit N est une extension elementaire de M (par 3.2.1) qui est decardinalite ≥ κ, puisqu’il contient les κ elements 2 a 2 distincts cNi , i ∈ κ.

Exercice 3.2.6. Soit L un langage fini (c’est-a-dire dont la signature σL estfinie), et soit M une L-structure finie.

1. Montrer qu’il existe un LM -enonce ϕ ∈ ∆(M) tel que ` ϕ→ ϕ′ pour toutϕ′ ∈ ∆(M).

2. En deduire que si N ≡M, alors N ∼= M.3. (Plus difficile.) Soit M′ une L′-structure finie, avec L′ non necessairement

fini. Montrer que N′ ≡M′ ⇒ N ∼= M.

3.3 Expansions par definitions

Soit T une L-theorie et ϕ = ϕ(x1, . . . , xn) une L-formule. On peut intro-duire un nouveau symbole de relation (n-aire) R et definir la L′ = L ∪ {R}-theorie T ∪ {∀x1, . . . , xn(ϕ(x1, . . . , xn)↔ Rx1 · · ·xn)}. Alors T ′ est une expan-sion conservatrice de T , c’est-a-dire : pour tout L-enonce ψ on a T |= ψ si etseulement si T ′ |= ψ. C’est clair, car tout modele de T admet une L′-expansion(meme unique) en un modele de T ′.

40

On dit que deux formules ϕ1(x1, . . . , xn) et ϕ2(x1, . . . , xn) sont equivalentesdans la theorie T si T |= ∀x1, . . . , xn(ϕ1 ↔ ϕ2).

Par induction, on montre que toute L′-formule est equivalente, dans T ′, aune L-formule.

Notation. ∃!xψ (« il existe un et un seul x tel que ψ ») est une abbreviationpour ∃x(ψ ∧ ∀x′(ψx′/x → x = x′)), ou x′ est une variable distincte de x.

Si l’on rajoute un symbole de fonction (resp. symbole de constante) pour unefonction (resp. constante) definissable, l’expansion T ′ ainsi construite satisfaittoujours les memes proprietes (Proposition 3.3.2).

Lemme 3.3.1. Toute formule est logiquement equivalente a une formule danslaquelle ne figurent que des termes de hauteur ≤ 1.

Demonstration. Pour ϕ une formule, soit M(ϕ) la hauteur maximale d’un termedans ϕ. On fait une preuve par induction sur (M(ϕ),ht(ϕ)) ordonne lexicogra-phiquement. Le seul cas non trivial est le cas d’une formule atomique ϕ, disonsϕ = Rt1 · · · tn. Pour simplifier les notations, nous supposons que ht(ti) > 1pour i = 1, . . . ,m et ht(ti) ≤ 1 pour i > m. Pour i = 1, . . . ,m, soit ti =fi(si,1, . . . , si,ki). Pour i = 1, . . . ,m on choisit des nouvelles variables yi,j pour1 ≤ j ≤ ki. Si yi := (yi,1, . . . , yi,ki), alors ϕ est equivalente a

ψ = ∃y1, . . . , ym

Rf1(y1) · · · fm(ym)tm+1 · · · tn ∧∧i,j

yi,j=si,j

et on a M(ψ) < M(ϕ). Le cas ϕ = t1=t2 est similaire.

Proposition 3.3.2 (Fonctions definissables). Soit ϕ(x0, . . . , xn) une L-formule.On suppose que T |= ∀x1, . . . , xn∃!x0 ϕ, c’est-a-dire que dans tout modele de T ,ϕ definit le graphe d’une fonction n-aire.

– Si n > 0, soit f un nouveau symbole de fonction n-aire, L′ = L ∪ {f} etsoit T ′ = T ∪ {∀x1, . . . , xn ϕ(f(x1, . . . , xn), x1, . . . , xn)}.

– Si n = 0, soit c un nouveau symbole de constante, L′ = L ∪ {c} et soitT ′ = T ∪ {ϕ(c)}.

Alors T ′ est une expansion conservatrice de T . De plus, toute L′-formule ψest equivalente dans T ′ a une L-formule ψ∗.

Demonstration. Nous donnons l’argument dans le cas n > 0, le cas n = 0 etantsimilaire.

Tout modele M de T admet une L′-expansion (meme unique) en un modeleM′ de T ′. En effet, il faut et il suffit de definir fM′(a1, . . . , an) = a0 si M |=ϕ[a0, a1, . . . , an]. Donc T ′ ⊇ T est conservatrice.

Soit d’abord ψ une L′-formule atomique ne contenant que des termes dehauteur ≤ 1, disons ψ = Rt1 · · · tm. On suppose que pour i = 1, . . . , k on aitti = f(si1, . . . , s

in) et que f n’apparaisse pas dans ti pour i > k. Les sij sont

41

des termes de hauteur 0, donc en particulier des L-termes. Soient z1, . . . , zk desnouvelles variables. Alors la L-formule

ψ∗ := ∃z1, . . . , zk

(Rz1 · · · zktk+1 · · · tm ∧

m∧i=1

ϕ(zi, si1, . . . , sin)

)

est equivalente (modulo T ′) a ψ. Si ψ = t1=t2, l’argument est le meme.Soit maintenant ψ une L′-formule arbitraire. Par le lemme, on peut sup-

poser que tous les termes figurant dans ψ sont de hauteurs au plus 1. Pourtoute sous-formule atomique ϕ de ψ, on choisit une L-formule equivalente ϕ∗.(On vient de construire une telle formule.) On definit ψ∗ comme la L-formuleobtenue en remplacant toute sous-formule atomique ϕ de ψ par la formule ϕ∗

correspondante.C’est un fait general que si on remplace des sous-formules par des sous-

formules equivalentes, on obtient une formule equivalente. (Exercice.)

Une expansion par des relations, fonctions et constantes definissables estappelee une expansion par definition.

Exemples 3.3.3. 1. Soit T ′ = Th(R) la theorie du corps ordonne des reels,et soit T la theorie du (pur) corps des reels. Comme dans R on a r < s siet seulement s’il existe t 6= 0 tel que t2 = s− r, T ′ est une expansion pardefinition de T .

2. Soit T = Th(〈ℵ1;<〉). Alors ω est une constante definissable dans T ,c’est-a-dire il existe une formule ϕ(x0) telle que T |= ∃!x0ϕ et 〈ℵ1;<〉 |=ϕ[ω]. En effet, l’ensemble des ordinaux limites est defini par la formuleLim(x) = ∃yy < x ∧ ∀y∃z(y < x → y < z ∧ z < x), et il suffit de poserϕ(x0) = Lim(x0) ∧ ∀y(Lim(y)→ ¬y < x0)

3.4 Elimination des quanteurs

Par induction sur la hauteur, il est facile de montrer que toute formule ϕ estlogiquement equivalente a une formule ψ qui est sous forme prenexe, c’est-a-direde la forme Q1x1 · · ·Qnxnχ, avec χ sans quanteur et Qi ∈ {∃,∀} pour tout i.En general, le nombre d’alternances des quanteurs ∃ et ∀ fournit une bonneindication pour la complexite de la formule ϕ (ainsi que de l’ensemble defini parϕ dans une structure donnee). Souvent, on comprend assez bien les ensemblesqui sont definissables a l’aide d’une formule sans quanteur.

Nous commencons par un resultat technique important et dont la preuve estun peu longue.

Theoreme 3.4.1. Soit T une L-theorie, n ≥ 1 un entier et ϕ = ϕ(x1, . . . , xn)une L-formule. Sont equivalents :

1. Il existe une L-formule sans quanteur ψ(x1, . . . , xn) qui est equivalente aϕ dans T .

42

2. Soient M et N deux modeles de T et A une sous-structure commune deM et de N. Alors pour tout a ∈ An on a M |= ϕ[a] ⇐⇒ N |= ϕ[a].

Remarque 3.4.2. Le theoreme s’applique aussi dans le cas ou ϕ est un enonce.Il suffit de considerer ϕ comme ϕ(x) pour trouver une formule ψ(x) sans quan-teurs et equivalente a ϕ dans T . Ainsi, un theoreme de T , par exemple ∃yy=yest equivalent dans T a la formule x=x. Si le langage L ne contient pas de sym-bole de constante, il n’y a pas de L-enonce sans quanteur et on ne peut doncpas faire mieux.

Une autre maniere de traiter ce probleme serait d’introduire une constantepropositionnelle > pour un enonce toujours vrai.

Demonstration du theoreme 3.4.1. (1)⇒(2). On note d’abord que si A ⊆ B, laformule ψ(x1, . . . , xn) est sans quanteur et a ∈ An, alors A |= ψ[a] ⇐⇒ B |=ψ[a].

Si M et N sont des modeles de T ayant A comme sous-structure et si ϕ =ϕ(x1, . . . , xn) est equivalente dans T a la formule ψ(x1, . . . , xn) sans quanteur,alors pour a ∈ An on a donc

M |= ϕ[a] ⇐⇒ M |= ψ[a] ⇐⇒ A |= ψ[a] ⇐⇒ N |= ψ[a] ⇐⇒ N |= ϕ[a].

(2)⇒(1). On considere l’ensemble de formules

Γ(x) := {χ(x1, . . . , xn) sans quanteur | T |= ∀x1, . . . , xn(ϕ→ χ)}.

On choisit c1, . . . , cn des nouvelles constantes 2 a 2 distinctes et on considerela theorie Γ(c) := {χ(c1, . . . , cn) | χ ∈ Γ(x)}. Soit L′ = L ∪ {c1, . . . , cn}. Nousallons montrer :

T ∪ Γ(c) |= ϕ(c) (3.1)

Si (3.1) etait faux, on pourrait trouver M′ |= T ∪ Γ(c) ∪ ¬ϕ(c). Soit A′ :=〈cM′1 , . . . , cM

′

n 〉M′ = 〈A; . . .〉 la sous-structure engendree par les cM′

i dans M′.On observe que Γ(c) ⊆ ∆(A′). Montrons que

Σ := T ∪∆(A′) ∪ {ϕ(c)}

a un modele.Sinon, on aurait T ∪ ∆(A′) |= ¬ϕ(c), d’ou T ∪ ∆(A′) ` ¬ϕ(c). Comme

tout element de A s’ecrit comme un L′-terme, si on note ∆c(A′) l’ensembledes L′-enonces sans quanteurs dans ∆(A′), alors T ∪ ∆(A′) est une expansionconservatrice de T ∪∆c(A′) par la proposition 3.3.2. En particulier, on a

T ∪∆c(A′) ` ¬ϕ(c).

Il existe alors des L-formules sans quanteur ξ1(x), . . . , ξk(x) telles que

T `k∧i=1

ξi(c)→ ¬ϕ(c) et ∆(A′) `k∧i=1

ξi(c) =: ξ(c).

43

Comme les ci n’apparaissent ni dans T ni dans ϕ(x), ξ(x), on en deduit (parexemple par 2.6.3) que T ` ∀x(ξ(x) → ¬ϕ(x)) et alors T ` ∀x(ϕ(x) → ¬ξ(x)).Mais alors ¬ξ(x) ∈ Γ(x) par definition, et ¬ξ(c) ∈ Γ(c), d’ou ¬ξ(c) ∈ ∆(A′).Contradiction.

Donc Σ a un modele N∗, et le L-reduit N de N∗ contient une copie isomorpheB′ de A′ comme sous-structure par la proposition 3.2.2. Quitte a identifier B′

et A′, on a donc construit deux modeles M = M′ �L et N de T contenant unesous-structure commune A = A′ �L tels que si l’on pose ai = cM

′

i alors N |= ϕ[a]et M |= ¬ϕ[a], ce qui contredit la condition (2). On a donc demontre (3.1).

Par compacite il existe ζ1(c), . . . , ζm(c) ∈ Γ(c) tels que T |=∧mi=1 ζi(c) →

ϕ(c), ce qui entraıne comme avant T |= ∀x (∧mi=1 ζi(x)→ ϕ(x)). Mais alors,

comme T |= ∀x(ϕ → ζi) pour tout i, on obtient T |= ∀x (∧mi=1 ζi(x)↔ ϕ(x)),

avec∧mi=1 ζi(x) sans quanteur.

Definition. Soit T une L-theorie. On dit que T admet l’elimination des quan-teurs (dans le langage L) si toute L-formule ϕ est equivalente dans T a uneL-formule sans quanteur.

Lemme 3.4.3. Si pour toute formule sans quanteur ϕ et toute variable x ilexiste une formule sans quanteur ψ telle que ∃xϕ et ψ soient equivalentes dansT , alors T admet l’elimination des quanteurs.

Demonstration. Soient ψ et ψ′ deux formules qui sont equivalentes dans T ,note ψ ∼T ψ′. Alors ¬ψ ∼T ¬ψ′, ∃xψ ∼T ∃xψ′ et χ ∧ ψ ∼T χ ∧ ψ′ pour touteformule χ. On peut donc raisonner par induction sur la hauteur de la formule,et la preuve est claire.

Theoreme 3.4.4. Soit T une L-theorie. On suppose que pour toute paire demodeles M et N de T , pour toute sous-structure commune A de M et de N ettoute formule sans quanteur ϕ(x0, . . . , xn), s’il existe a ∈ An et b0 ∈M tels queM |= ϕ[b0, a], alors il existe c0 ∈ N tel que N |= ϕ[c0, a].

Alors T admet l’elimination des quanteurs.

Remarque. La reciproque de ce resultat est claire : toute theorie avec l’elimi-nation des quanteurs satisfait a l’hypothese du theoreme.

Demonstration. Soient A ⊆M,N donnees, avec M,N |= T . Quitte a symetriserl’hypothese du theoreme, elle exprime que si ϕ est sans quanteur et χ = ∃x0ϕ,alors M |= χ[a] ⇐⇒ N |= χ[a] pour tout a ∈ An. Par le theoreme 3.4.1, χ estequivalente dans T a une formule sans quanteur. Par le lemme, cela suffit.

Proposition 3.4.5. Soit T une theorie qui admet l’elimination des quanteurs.

1. Soient M et N deux modeles de T ayant une sous-structure commune.Alors M ≡ N.

2. Si M ⊆ N, ou M et N sont deux modeles de T , alors M 4 N.

44

Demonstration. (1) Il s’agit d’un cas particulier de la direction facile du theo-reme 3.4.1. En effet, tout enonce ϕ est equivalent dans T a une formule ψ(x)sans quanteur. Pour a ∈ A arbitraire, ou A est une sous-structure commune deM et de N, on a donc

M |= ϕ ⇐⇒ M |= ψ[a] ⇐⇒ A |= ψ[a] ⇐⇒ N |= ψ[a] ⇐⇒ N |= ϕ.

(2) Clair.

Exercice 3.4.6. Toute theorie T admet une expansion par definition qui admetl’elimination des quanteurs.

3.5 Corps algebriquement clos

On considere la Lan-theorie CAC des corps algebriquement clos (voir 2.6.6).On utilisera des notions et resultats qui seront vus en Algebre 1.

Soit A un sous-anneau d’un corps K. Un element de K est appele algebriquesur A s’il est racine d’un polynome non nul a coefficients dans A.

Soit A un anneau integre. Une cloture algebrique de A est un corps algebri-quement clos contenant A et dont tout element est algebrique sur A.

Fait 3.5.1. Soit A un anneau integre.

1. A admet une cloture algebrique.

2. Si K et K ′ sont deux clotures algebriques de A, alors il existe un isomor-phisme f : K ∼= K ′ tel que f �A = idA.

3. Soit A ⊆ L, ou L est un corps algebriquement clos. Alors le sous-corpsAalgL = {b ∈ L | b est algebrique sur A} est une cloture algebrique de A.

4. Soit Falgp une cloture algebrique du corps a p elements Fp. Alors Falgp estune reunion croissante de sous-corps finis FN , N ∈ N. Plus precisement,pour tout entier k ≥ 1, l’ensemble des racines du polynome Xpk −X estun sous-corps Fpk (a pk elements), et

⋃k∈N Fpk = Falgp . Comme de plus

Fpk ⊆ Fpl si k | l (car alors Xpl −X est divisible par Xpk −X), il suffitde poser FN := FpN! .

5. Tout corps algebriquement clos est infini.

6. Soit K ⊆ L une extension de corps avec K algebriquement clos, et soitb ∈ L \K. Alors b n’est pas algebrique sur K.

Theoreme 3.5.2. La theorie CAC admet l’elimination des quanteurs.

Demonstration. On observe qu’une sous-structure d’un corps dans Lan n’estrien d’autre qu’un sous-anneau. Par le theoreme 3.4.4 il suffit donc de montrerque si K et L sont algebriquement clos, A est un sous-anneau commun et ϕ =ϕ(x0, . . . , xn) une formule sans quanteur, alors pour tout a ∈ An il existe b ∈ Ltel que L |= ϕ[b, a] si et seulement s’il existe c ∈ K tel que K |= ϕ[c, a].

45

Par le fait, K et L contiennent des clotures algebriques FK et FL de A quisont isomorphes au-dessus de A. Quitte a agrandir A, on peut donc supposerque A est algebriquement clos. On peut alors meme supposer que A = K ⊆ L.Dans cette situation, il faut montrer que s’il existe b ∈ L tel que L |= ϕ[b, a],alors il existe c ∈ K tel que K |= ϕ[c, a].

La formule ϕ est logiquement equivalente a une formule de la forme∨i

∧χi,j ,

avec χi,j = χi,j(x0, . . . , xn) atomique ou negation d’atomique. Si L |= ϕ[b, a],il existe i tel que L |=

∧j χi,j [b, a]. Il suffit donc de traiter le cas ou ϕ est une

conjonction de formules atomiques ou negations d’atomiques. Dans la theoriedes corps, toute formule atomique est equivalente a P (x)=0 pour un polynomeP (x) a coefficients entiers. Alors on peut supposer que

ϕ(x) =n∧i=1

Pi(x)=0 ∧m∧i=1

¬Qi(x)=0.

Si l’un des Pi(x0, a1, . . . , an) ∈ K[x0] est un polynome non nul, alors b estalgebrique sur K, d’ou b ∈ K et on a termine.

On peut donc supposer que ϕ =∧mi=1 ¬Qi(x)=0. Comme chaque Qi(x0, a) ∈

K[x0] est different du polynome nul (sinon, b ne pourrait pas exister), il n’a qu’unnombre fini de racines. On en deduit qu’il existe c ∈ K tel que K |= ϕ[c, a], carK est un corps infini (il est algebriquement clos).

Pour p un nombre premier ou p = 0 on note CACp la theorie des corpsalgebriquement clos de caracteristique p.

Theoreme 3.5.3. Les theories CACp sont completes (p premier ou p = 0).

Demonstration. Tout corps de caracteristique p > 0 contient Fp comme sous-corps. Si K et L sont algebriquement clos de caracteristique p, alors K ≡ Lpar le theoreme 3.5.2 et la proposition 3.4.5(1), ce qui montre que CACp estcomplete.

Pour CAC0, on fait le meme argument, en remplacant Fp par Q.

Theoreme 3.5.4 (Principe de Lefschetz). Soit ϕ un Lan-enonce. Les proprietessuivantes sont equivalentes :

1. C |= ϕ.2. Il existe un corps algebriquement clos de caracteristique 0 qui verifie ϕ.3. Tout corps algebriquement clos de caracteristique 0 verifie ϕ.4. Il existe N ∈ N tel que ϕ est verife dans tout corps algebriquement clos de

caracteristique p > N .5. Il existe un ensemble infini de nombres premiers P tel que pour tout p ∈ P

il existe Kp |= CACp verifiant ϕ.

Demonstration. (1)⇐⇒ (2)⇐⇒ (3) suit de 3.5.3.(3)⇒(4). Notons que CAC0 est donnee par CAC ∪ {χp | p premier}, ou χp

exprime que p = 1 + · · · + 1 est different de 0. Si CAC |= ϕ, par compacite il

46

existe une partie finie ∆ de CAC0 telle que ∆ |= ϕ. Or ∆ ne contient qu’unnombre fini d’axiomes de la formes χp. En particulier il existe N ∈ N tel queK |= ∆ pour tout corps algebriquement clos de caracteristique p > N .

(4)⇒(5) est trivial.(5)⇒(3). Pour p ∈ P, soit Kp |= CACp tel que Kp |= ϕ. Si CAC0 6|= ϕ, alors

CAC0 |= ¬ϕ par completude. Par (3)⇒(4) il existe N ∈ N tel que ¬ϕ soit verifiedans tout corps algebriquement clos de caracteristique p > N . En particulier Pest fini.

Theoreme 3.5.5 (Theoreme des zeros (Nullstellensatz) de Hilbert).Soient K un corps algebriquement clos et P1(X), . . . , Pm(X) ∈ K[X1, . . . , Xn].Si le systeme d’equations polynomiales P1(X) = P2(X) = . . . = Pm(X) = 0 aune solution dans un corps L ⊇ K, alors il a une solution dans K.

Demonstration. Soient L ⊇ K et a ∈ Ln tel que P1(a) = . . . = Pm(a) = 0.Quitte a agrandir L, on peut supposer que L est algebriquement clos. CommeCAC admet l’elimination des quanteurs, on a K 4 L par 3.4.5.

On choisit des Lan-termes Fi(X,Zi) et des uplets bi extraits de K tels quePi(X) = Fi(X, bi).

Alors L |= ∃x∧Fi(x, bi)=0, d’ou K |= ∃x

∧Fi(x, bi)=0, comme K 4 L.

3.6 Le theoreme d’Ax

Une chaıne de L-structures est une suite (Mi)i∈N de L-structures telle queMi ⊆Mi+1 pour tout i.

Si (Mi)i∈N est une telle chaıne, il existe une et une seule L-structure M avecensemble de base M =

⋃i∈N Mi telle que Mi ⊆ M pour tout i. En effet, il

faut et il suffit d’interpreter les symboles du langage comme suit : cM = cM0 ,fM =

⋃i∈N f

Mi et RM =⋃i∈N R

Mi . Il est facile a voir que c’est bien defini.La L-structure M ainsi obtenue est notee

⋃i∈N Mi.

Definition. Une formule ∀∃ est une formule de la forme ∀x1, . . . , xn∃y1, . . . , ymϕ,ou ϕ est sans quanteur et m,n ≥ 0.

Lemme 3.6.1 (Preservation des enonces ∀∃ par union de chaıne).Soit ψ un L-enonce ∀∃ et (Mi)i∈N une chaıne de L-structures avec Mi |= ψpour tout i. Alors M =

⋃i∈N Mi |= ψ.

Demonstration. Soit ψ = ∀x1, . . . , xn∃y1, . . . , ymϕ(x, y) avec ϕ sans quanteur. Ilfaut montrer que M |= ∃y1, . . . , ymϕ[a, y] pour tout a ∈Mn. Comme Mi est unesuite croissante, il existe k ∈ N tel que a ∈ Mn

k . Il existe donc b1, . . . , bm ∈ Mk

tels que Mk |= ϕ[a, b], car M |= ψ. On en deduit que M |= ϕ[a, b], car ϕ est sansquanteur et Mk est une sous-structure de M.

Remarque. On peut montrer qu’un enonce est preserve par union de chaınesi et seulement s’il est logiquement equivalent a un enonce ∀∃.

47

Proposition 3.6.2. Soit ϕ un Lan-enonce ∀∃ vrai dans tout corps fini. AlorsCAC |= ϕ. En particulier il est vrai dans C.

Demonstration. Par le fait 3.5.1(4), Falgp est reunion croissante de sous-corpsfinis. Donc Falgp |= ϕ par le lemme, pour tout p premier. On en deduit le resultatpar le principe de Lefschetz.

Theoreme 3.6.3 (Theoreme d’Ax). Soit f : Cn → Cn une application po-lynomiale, c’est-a-dire de la forme f = (f1, . . . , fn) pour des polynomes fi ∈C[x1, . . . , xn]. Si f est injective, alors f est surjective.

Demonstration. Il existe des Lan-termes — ce sont en particulier des polynomesa coefficients entiers — Pn,d(z, x) tels que pour tout corps K, tout polynomef(x) ∈ K[x1, . . . , xn] de degre ≤ d s’ecrit comme Pn,d(a, x) pour un uplet ad’elements de K. L’enonce suivant ψn,d est ∀∃ et il exprime que toute fonctionpolynomiale et injective f : Kn → Kn, definie a l’aide de polynomes fi de degreau plus d, est surjective :ψn,d = ∀z1, . . . , zn∀u∃x∃x′∃y

[(∧ni=1 Pn,d(zi, x)=Pn,d(zi, x′) ∧ ¬

∧ni=1 xi=x

′i) ∨ (

∧ni=1 Pn,d(zi, y)=ui)]

Evidemment, ψn,d est vrai dans tout corps fini, donc CAC |= ψd,n par laproposition 3.6.2, et en particulier C |= ψd,n.

48

Chapitre 4

Recursivite

Dans ce chapitre, nous developpons la theorie des fonctions et ensemblesd’entiers qui sont « calculables ». Nous donnons deux precisions de la notionintuitive d’une fonction calculable — la notion de fonction recursive, et la notionde fonction calculable par une machine de Turing — et nous montrons que cesdeux notions coıncident.

Pour n ∈ N, on note Fn := {f : Nn → N} et F :=⋃n∈N Fn.

Notation. Soit f la fonction qui a (x1, . . . , xn) associe f(x1, . . . , xn) ∈ N. Onnotera parfois f = λx1 · · ·xn.f(x1, . . . , xn).

4.1 Fonctions primitives recursives

Definition. L’ensemble des fonctions primitives recursives est le plus petitsous-ensemble E de F verifiant les conditions suivantes :

(R0) E contient les fonctions de base suivantes :– S = λx.x+ 1 (la fonction successeur) ;– la fonction 0-aire constante a 0, notee C0

0 ;– pour tout n ≥ 1 et tout 1 ≤ i ≤ n la projection Pni sur la iecoordonnee,

c’est-a-dire Pni = λx1 · · ·xn.xi.(R1) E est clos par composition : si f1, . . . , fn ∈ Fp ∩E et si h ∈ Fn ∩E, alors

g = h(f1, . . . , fn) ∈ E.

(R2) E est clos par recurrence : pour tout entier n, si g ∈ Fn∩E et h ∈ Fn+2∩E,alors la fonction f definie par

f(x1, . . . , xn, 0) := g(x1, . . . , xn),f(x1, . . . , xn, y + 1) := h(x1, . . . , xn, y, f(x1, . . . , xn, y))

est dans E aussi.

Observons que toutes les fonctions constantes Cnk = λx1 · · ·xn.k sont primi-tives recursives pour tout k, n ∈ N. (La fonction C1

0 est obtenue par recurrencea partir de g = C0

0 et h = P 22 .)

49

Si X ⊆ Nn, on notera 1X la fonction caracteristique de X, c’est-a-dire

1X(x1, . . . , xn) =

{1, si (x1, . . . , xn) ∈ X;0, sinon.

Lemme 4.1.1. Les fonctions λxy.x + y, λxy.x · y, λxy.xy, λx.x!, λxy.x−y et

sg = 1N∗ sont primitives recursives, ou x−y :=

{x− y, si x ≥ y ;0, sinon.

.

Demonstration. L’addition f = λxy.x + y est obtenue par recurrence a partirde g = P 1

1 et h = S ◦ P 33 , comme x+ 0 = x et x+ (y + 1) = S(x+ y).

Il est egalement facile d’obtenir les autres fonctions. Donnons juste l’argu-ment pour λxy.x−y et sg. On construit d’abord λy.y−1 par recurrence, via0−1 = 0, (y + 1)−1 = y. Puis, on peut definir x−0 = x, x−(y + 1) = (x−y)−1.Enfin, on a sg(x) = 1−(1−x).

Definition. Une partie X ⊆ Nn est primitive recursive si sa fonction caracte-ristique 1X l’est.

Lemme 4.1.2. 1. L’ensemble des fonctions primitives recursives est clospar permutation des variables.[Clair]

2. Si X ⊆ Nn est primitif recursif et si f1, . . . , fn ∈ Fp sont primitivesrecursives, alors Y = {(x1, . . . , xp) ∈ Np | (f1(x), . . . , fn(x)) ∈ X} estprimitif recursif.[On a 1Y = 1X(f1, . . . , fn).]

3. L’ensemble des parties primitives recursives de Nn contient ∅ et Nn, et ilest stable par ∪, ∩ et par passage au complement (donc par combinaisonsbooleennes).[On a 1Nn\X = 1−1X et 1X∩Y = 1X · 1Y .]

4. L’ensemble {(x, y) | x < y} ⊆ N2 est primitif recursif.[On a 1<(x, y) = sg(y−x).]

5. (Definition par cas.) Soit Nn = A1∪ . . . ∪Ak une partition de Nn en unnombre fini de parties primitives recursives Ai, et soient f1, . . . , fk ∈Fn primitives recursives. Alors la fonction f , definie par f(x) = fi(x)si x ∈ Ai, est primitive recursive aussi. En particulier, les fonctionsλx1 · · ·xn.max(xi) et λx1 · · ·xn.min(xi) sont primitives recursives.[En effet, on a f = 1A1f1 + . . .+ 1Akfk.]

6. (Sommes et produits limites.) Si f ∈ Fn+1 est primitive recursive, alorsles fonctions suivantes aussi :

λx1 · · ·xny.y∑t=0

f(x, t) et λx1 · · ·xny.y∏t=0

f(x, t)

[Par recurrence.]

50

7. (Schema µ borne.) Soit X ⊆ Nn+1 primitif recursif. Alors la fonctionf ∈ Fn+1, f(x, z) = (µt ≤ z) ((x, t) ∈ X), definie par

f(x, z) :=

{0, s’il n’existe pas de t ≤ z tel que (x, t) ∈ X;t0, si t0 est le plus petit entier t ≤ z tel que (x, t) ∈ X

est primitive recursive.

[On a f(x, 0) = 0, f(x, z + 1) =

f(x, z), si

∑zt=0 1X(x, t) ≥ 1 ;

z + 1, sinon et si (x, z + 1) ∈ X;0, sinon.

Donc f est primitive recursive (recurrence et definition par cas).]8. (Quantification bornee.) Si X ⊆ Nn+1 est primitif recursif, alors aussi

Xe = {(x1, . . . , xn, z) ∈ Nn+1 | (∃t ≤ z) (x, t) ∈ X} ainsi queXa = {(x1, . . . , xn, z) ∈ Nn+1 | (∀t ≤ z) (x, t) ∈ X}.

[Comme on peut passer au complementaire, il suffit de traiter le premiercas. On a 1Xe(x, z) = 1 si

∑zt=0 1X(x, t) ≥ 1, et 1Xe(x, z) = 0 sinon.]

Exemples 4.1.3. 1. Soit q : N2 → N la fonction qui a (x, y) associe la partieentiere de x/y si y 6= 0, et 0 sinon. Alors q est primitive recursive.[On a q(x, y) = (µt ≤ x) ((t+ 1) · y > x).]

2. {(x, y) ∈ N2 : y | x} est un ensemble primitif recurisf.[On a y | x ⇐⇒ ∃zz · y = x ⇐⇒ x = q(x, y) · y.]

3. L’ensemble P des nombres premiers est primitif recursif.[On a x ∈ P ⇐⇒ x ≥ 2 ∧ (∀y ≤ x) (y | x→ (y = 1 ∨ y = x)). Par lesproprietes de cloture du lemme precedent, P est donc primitif recursif.]

4. Soit π la fonction qui a x associe le (x+ 1)e nombre premier. Alors π estprimitive recursive.[On a π(0) = 2, π(x+ 1) = (µz ≤ π(x)! + 1) (z > π(n) et z ∈ P ).]

5. Une bijection primitive recursive entre N2 et N est donnee par la fonctionα2 = λxy. 12 (x+y+1)(x+y)+x. On a α2(β2

1 , β22) = idN pour des fonctions

primitives recursives β21 , β

22 ∈ F1. En effet, comme α2(x, y) ≥ min(x, y),

on a β21(x) = (µz ≤ x)(∃t ≤ x(α2(z, t) = x)), de meme pour β2

2 .Par induction sur p ≥ 2, on definit une bijection primitive recursive αp :Np → N avec composantes de l’inverse βp1 , . . . , β

pp primitives recursives. Il

suffit de poser αp+1(x1, . . . , xp+1) = αp(x1, . . . , xp−1, α2(xp, xp+1)).

Lemme 4.1.4. 〈x0, . . . , xn−1〉 := π(0)x0 · . . . · π(n− 2)xn−2 · π(n− 1)xn−1+1 − 1definit une bijection 〈 〉 : N∗ → N, ou N∗ denote l’ensemble des suites finiesd’entiers. Elle satisfait aux proprietes suivantes :

1. La fonction composante a deux places (x)i, definie par

(〈x0, . . . , xn−1〉)i =

{xi, si i < n ;0, sinon

51

est primitve recursive.

2. La fonction longueur, lg(〈x0, . . . , xn−1〉) = n, est primitive recursive.

3. Pour tout n ∈ N, 〈 〉�Nn : Nn → N est primitive recursive.

4. On a lg(x) ≤ x pour tout x, et si x > 0, alors (x)i < x pour tout i.

On appelle 〈x0, . . . , xn−1〉 le nombre de Godel de la suite d’entiers (x0, . . . , xn−1).

Demonstration. (4) est clair, et (3) suit de 4.1.3.

(2) On a lg(x) =

{0, si x = 0 ;(µy ≤ x) [(∀z ≤ x) (y ≤ z → π(z) - (x+ 1))] , sinon.

(1) On a (x)i =

0, si i ≥ lg(x) ;(µy ≤ x)

(π(i)y+2 - (x+ 1)

), si i+ 1 = lg(x) ;

(µy ≤ x)(π(i)y+1 - (x+ 1)

), si i+ 1 < lg(x).

4.2 La fonction d’Ackermann

Voici une fonction qui est calculable au sens intuitif, la fonction d’Ackermannξ ∈ F2 definie ainsi :

– ξ(0, x) := 2x

– ξ(y, 0) := 1– ξ(y + 1, x+ 1) := ξ(y, ξ(y + 1, x))

Cette fonction est bien definie et se calcule en un nombre fini d’etapes (exercice ;il suffit de considerer l’ordre lexicographique sur N2).

On ecrit aussi ξn(x) pour ξ(n, x), et ξkn pour

k fois︷ ︸︸ ︷ξn ◦ . . . ◦ ξn.

Lemme 4.2.1. 1. ξn(x) > x pour tout n, x ∈ N.

2. ξn est strictement croissante pour tout n ∈ N.

3. ξn+1(x) ≥ ξn(x) pour tout n, x ∈ N.

4. ξkn est strictement croissante pour tout k, n ∈ N.

5. ξkn(x) < ξk+1n (x) pour tout k, n, x ∈ N.

6. ξkm(x) ≤ ξkn(x) pour tout k,m, n, x ∈ N avec m ≤ n.

7. ξkn(x) ≤ ξn+1(x+ k) pour tout k, n, x ∈ N.

Demonstration. (1) On fait une induction sur n, le cas n = 0 etant clair. On aξn+1(x+ 1) = ξn(ξn+1(x)) > ξn+1(x) > x.

(2) C’est clair pour n = 0, et on vient de voir que ξn+1(x+ 1) > ξn+1(x).(3) ξn+1(0) = ξn(0), ξn+1(x+ 1) = ξn(ξn+1(x)︸ ︷︷ ︸

≥x+1

) ≥ ξn(x+ 1) par (2).

(4), (5) et (6) sont clairs.(7) On fait une recurrence sur k, le cas k = 0 etant clair. On a ξk+1

n (x) =ξn(ξkn(x)) ≤ ξn(ξn+1(x+ k)) = ξn+1(x+ k + 1).

52

Definition. On dit que la fonction f ∈ F1 domine la fonction g ∈ Fn s’il existeun entier N tel que pour tout x ∈ Nn on ait g(x) ≤ f (max(xi, N)).

Notons que si f est strictement croissante, alors f domine g si et seulementsi g(x) ≤ f(max(xi)) sauf pour un ensemble fini de n-uplets.

On note Cn l’ensemble des fonctions dans F qui sont dominees par au moinsune des fonctions ξkn, pour k ∈ N.

Lemme 4.2.2. 1. Cn ⊆ Cm pour tout n ≤ m.

2. C0 contient les fonctions de base ainsi que les fonctions λxy.x+y, λx.k ·x(pour k fixe) et λx1 . . . xn.max(xi).

3. Cn est stable par composition.

4. Si g ∈ Fp ∩ Cn et h ∈ Fp+2 ∩ Cn, alors f definie par recurrence a partirde g et h est dans Cn+1.

En conclusion, C =⋃n∈N Cn contient l’ensemble des fonctions primitives

recursives.

Demonstration. (1) et (2) sont clairs. Quant a (3), on se donne f1, . . . , fm ∈Fp∩Cn et g ∈ Fm∩Cn. Il existe des entiers N,N1, . . . , Nm, k, k1, . . . , km tels queg(y) ≤ ξkn(max(yj , N)) pour tout y ∈ Nm et fi(x) ≤ ξkin (max(xj , Ni)) pour toutx ∈ Np. Posons M = max(N,N1, . . . , Nm) et l = max(k1, . . . , km). Pour toutx ∈ Np on a g(f1(x), . . . , fm(x)) ≤ ξkn(ξln(max(xj ,M))) = ξk+l

n (max(xj ,M)).(4) On a f(x, 0) = g(x) et f(x, y+1) = h(x, y, f(x, y)). Il existe k1, N1, k2, N2

tels que g(x) ≤ ξk1n (max(xj , N1)) et h(x, y, t) ≤ ξk2n (max(xj , y, t,N2)). Par re-currence sur y, on montre sans probleme que

f(x, y) ≤ ξk1+yk2n (max(xj , y,N1, N2)). (4.1)

Par le lemme 4.2.1(7), on deduit de (4.1) que

f(x, y) ≤ ξn+1(max(xj , y,N1, N2) + k1 + k2y︸ ︷︷ ︸composee de fonctions dans Cn+1

),

d’ou le resultat par la partie (3).

Theoreme 4.2.3. La fonction d’Ackermann n’est pas primitive recursive.

Remarque. Par contre, une induction sur n montre que toutes les fonctionsξn sont primitives recursives.

Demonstration du theoreme 4.2.3. Par l’absurde. On suppose donc que ξ estprimitive recursive. Alors λx.ξ(x, 2x) l’est aussi, et il existe k, n,N ∈ N tels queξ(x, 2x) ≤ ξkn(x) pour tout x > N . Par 4.2.1(7) on a donc ξx(2x) ≤ ξn+1(x+ k)pour tout x > N . Pour x > max(k, n+ 1), c’est absurde.

53

4.3 Fonctions partielles recursives

Compte tenu de l’existence de la fonction d’Ackermann — calculable au sensintuitif et non primitive recursive — nous allons elargir la classe des fonctionsque nous considerons. Pour des raisons techniques, il convient egalement depasser aux fonctions partielles.

Une fonction partielle de Nn dans N est la donnee d’un couple (A, f) avecA ⊆ Nn et f : A → N. L’ensemble A est le domaine de definition de f , notedom(f). On note F∗n l’ensemble de ces couples et F∗ =

⋃n∈N F∗n.

Definition. L’ensemble des fonctions partielles recursives est le plus petit sous-ensemble E de F∗ verifiant les proprietes (R0)∗ − (R3)∗ suivantes :

(R0)∗ E contient les fonctions de base (C00 , S et Pni pour n ≥ 1 et 1 ≤ i ≤ n).

(R1)∗ E est clos par composition (de fonctions partielles) : si f1, . . . , fn ∈ F∗m ∩E et h ∈ F∗n ∩ E, alors g = h(f1, . . . , fn) ∈ E, ou g est la fonctionpartielle qui a x associe h(f1(x), . . . , fn(x)) si x ∈ dom(fi) pour tout i et(f1(x), . . . , fn(x)) ∈ dom(h). Sinon, g n’est pas definie en x.

(R2)∗ E est clos par recurrence (de fonctions partielles) : si g ∈ F∗p ∩ E eth ∈ F∗p+2 ∩ E, alors f ∈ E, ou– f(x, 0) = g(x) si x ∈ dom(g), et sinon f n’est pas definie en (x, 0) ;– f(x, y + 1) = h(x, y, f(x, y)) si f est definie en (x, y) (relation definie

en meme temps par recurrence sur y) et si (x, y, f(x, y)) ∈ dom(h), etsinon f n’est pas definie en (x, y + 1).

(R3)∗ E est clos par schema µ : soit f ∈ F∗n+1∩E. Alors g ∈ E, ou g ∈ F∗n, g(x) =µy (f(x, y) = 0) est definie ainsi :– s’il existe z tel que f(x, z) = 0 et (x, z′) ∈ dom(f) pour tout z′ ≤ z,

alors g(x) est le plus petit tel z ;– sinon, g n’est pas definie en x.

Une fonction partielle f ∈ F∗n est totale si dom(f) = Nn. On appelle fonctionrecursive totale toute fonction totale qui est recursive partielle.

L’operation suivante est reservee pour les fonctions totales.Soit f une fonction totale a n+1 arguments telle que ∀x1, . . . , xn∃y f(x, y) =

0. Alors on dit que la fonction (totale) g, g(x) = µy (f(x, y) = 0) est obtenuepar schema µ total a partir de f .

La propriete (R3) exprime qu’un ensemble de fonctions totales est clos parschema µ total.

Exercice 4.3.1. Montrer que la fonction d’Ackermann est recursive totale.(Voir Proposition 4.5.4.)

4.4 Fonctions calculables par machine de Turing

Les machines de Turing fournissent une precision de la notion de « calcula-bilite par une machine ».

54

Definition. Une machine de Turing M est la donnee– d’un nombre fini (≥ 1) de bandes B1, B2, . . . placees horizontalement,

toutes bornees a gauche et non bornees a droite ; chaque bande est di-visee en cases, numerotees par N∗ de gauche a droite. Les bandes sontarrangees de sorte que les cases du meme numero se trouvent sur unememe verticale.

– d’une tete de lecture qui peut lire, effacer et ecrire des symboles sur lescases (un symbole par case). Cette tete se deplace horizontalement et estplacee a chaque instant sur une verticale et manipule toutes les cases decette verticale d’un coup.L’ensemble de symboles est donne par S = {d, |, b}, d comme « debut debande », | comme « baton » et b comme « blanc ».

Voici les donnees qui sont specifiques a M :– n = n(M) ∈ N∗ (le nombre de bandes)– Un ensemble fini d’etats E. Il y a deux etats specifiques appartenant a E :ei (l’etat initial) et ef (l’etat final).

– Une fonction M : Sn×E → Sn×E×{−1, 0, 1}, appelee table de transitionde M.

Fonctionnement de la machine :– A chaque instant t ∈ N, M se trouve dans un etat donne (de E).– M fonctionne en changeant d’etat, en effacant et ecrivant des symboles

sur les bandes et en deplacant sa tete a chaque instant.

Le fonctionnement est sujet aux regles suivantes :1. A l’instant t = 0,M se trouve dans l’etat initial et sa tete se trouve devant

les cases no 1.2. A chaque instant t, M lit les symboles (s1, . . . , sn) ∈ Sn ecrits devant sa

tete, et la table M decrit alors ce que M est censee faire. Si M est dansl’etat e et lit (s1, . . . , sn), alors, soit M(s, e) = (s′, e′, ε). La tete efface s,ecrit s′, se deplace par ε horizontalement etM se met dans l’etat e′, puispasse a l’instant t+ 1.

3. M s’arrete quand elle atteint l’etat final.Entree correcte :– A l’instant t = 0, d est inscrit dans les cases no 1 et uniquement la.– Toutes les cases sont remplies, et il y a un nombre fini de batons.(Cela reste vrai tout au long du calcul, vu les contraintes qui suivront).

Contraintes :– Pour tout s ∈ Sn on a M(s, ef ) = (s, ef , 0).– La tete ne peut ni ecrire ni effacer le symbole de debut de bande :

– Pour tout e ∈ E, on a M((d, . . . , d), e) = ((d, . . . , d), e′, ε) pour unε ∈ {0, 1} ;

– si s 6= (d, . . . , d), alors M(s, e) = (s′, e′, ε) avec s′i 6= d pour tout i.

Remarque. Il s’agit d’une machine deterministe, c’est-a-dire on peut prevoirpour tout instant t la position de la tete, l’etat de la machine et le remplissagedes bandes.

55

Definition. 1. Une bande represente (a un instant donne) l’entier m si labande remplie est egale a (d, |, . . . , |︸ ︷︷ ︸

m fois

, b, . . . , b, . . .).

2. Une machine de TuringM calcule f ∈ F∗p si n(M) ≥ p+ 1 et si pour toutm ∈ Np, quand on fait fonctionner M sur l’entree ou, pour i = 1, . . . , p,la bande Bi represente mi et, pour i > p, la bande Bi represente l’entier0, alors– si m ∈ dom(f), M s’arrete apres un temps fini et sur les bandes sont

representes successivement les entiers (m1, . . . ,mp, f(m), 0, . . . , 0) ;– si m 6∈ dom(f), M ne s’arrete jamais (c’est-a-dire ef n’est jamais at-

teint).

3. La fonction partielle f est dite T -calculable s’il existe une machine deTuring M qui calcule f .

Lemme 4.4.1. Les fonctions de base (C00 , S et les Pni ) sont T -calculables.

Demonstration. C00 est calculable par M a une bande et avec E = {ei, ef}, ou

la table de transition est donnee par M(d, ei) = (d, ef , 0). (Ici comme dans lasuite, nous nous contentons de donner la partie essentielle de M .)

S est calculable parM a deux bandes, avec E = {ei, ef} et ou M(d, d, ei) =(d, d, ei,+1),M(|, b, ei) = (|, |, ei,+1) et M(b, b, ei) = (b, |, ef , 0).

Pni est calculable parM a n+ 1 bandes, avec E = {ei, ef} et ou la table detransition est donnee par M(d, . . . , d, ei) = (d, . . . , d, ei,+1) ainsi que

M(s1, . . . , sn, b, ei) =

{(s1, . . . , sn, |, ei,+1), si si =|,(s1, . . . , sn, b, ef , 0), si si = b.

Lemme 4.4.2. L’ensemble des fonctions partielles T -calculables est clos parcomposition.

Demonstration. Soient f1, . . . , fn ∈ F∗p et g ∈ F∗n T -calculables, et soit h =g(f1, . . . , fn).

Par hypothese il existe Mi, 1 ≤ i ≤ n, a pi ≥ p + 1 bandes et ensembled’etats Ei calculant fi, ainsi que M′ a n′ ≥ n + 1 bandes et ensemble d’etatsE′ calculant g.

Soit M une machine de Turing a p + (n′ − n) +∑ni=1(pi − p) bandes et

ensemble d’etats E = {ed, en}∪E′∪⋃iEi. On declare que l’etat initial deM est

celui de M1, l’etat final celui de M′.Voici le fonctionnement deM (la description exacte de la table de transition

de M est laissee en exercice) :Etant representes (m1, . . . ,mp, 0, . . . , 0) sur les bandes,M commence a cal-

culer f1(m1, . . . ,mp) commeM1 le ferait, en se servant des etats dans E1 \{e1f}

et de (p1− p) bandes supplementaires (disjointes de Bp+1). En l’etat e1f , elle re-

vient en debut des bandes, puis se met dans l’etat e2i ∈ E2 et calcule f2(m) en se

servant des etats dans E2\{e2f} et de (p2−p) bandes supplementaires (disjointes

56

de Bp+1). Ainsi, M calcule successivement f1(m), . . . , fn(m). Une fois fn(m)calculee, M se met dans l’etat initial de M′ et calcule h(f1(m), . . . , fn(m))comme M′ le ferait, en se servant de E′ et de n′ − n bandes supplementaires(disjointes de Bp+1). Elle utilise pour ce calcul les bandes sur lesquelles sont ins-crites les fi(m) comme bandes d’entree et Bp+1 comme bande de sortie. Il faudradonc renumeroter les bandes pour pouvoir se servir des tables de transition deM1,. . . ,Mn et M′ en etablissant la table de M.

Une fois h(f1(m), . . . , fn(m)) calculee, au lieu de passer a l’etat final deM′,M se met dans l’etat ed qui sert pour retrouver le debut de bande, puis nettoieles bandes sur lesquelles sont representes les fi(m), en se servant de l’etat en,pour enfin se mettre dans l’etat final.

Lemme 4.4.3. L’ensemble des fonctions partielles T -calculables est clos parschema µ.

Demonstration. Exercice. (C’est facile.)

Lemme 4.4.4. L’ensemble des fonctions partielles T -calculables est clos parrecurrence.

Demonstration. Soit g ∈ F∗p calculee par M a p + 1 + k bandes et ensembled’etats E, et soit h ∈ F∗p+2 calculee par M′ a p + 3 + k′ bandes et ensembled’etats E′. On considere la fonction partielle f ∈ F∗p+1 definie par f(x, 0) = g(x)et f(x, y + 1) = h(x, y, f(x, y)).

Voici la description informelle d’une machine de Turing N qui calcule f :N a p + 4 + k + k′ bandes, et son ensemble d’etats est compose de E∪E′ pluscertains etats auxiliaires, avec eNi = eMi et eNf = eM

′

f .Fonctionnement de N sur l’entree (m1, . . . ,mp+1) :

(1) Calcul de g(m1, . . . ,mp) avec bandes d’entree B1, . . . , Bp, bande de sortieBp+2 et bandes auxiliaires Bp+5, . . . , , Bp+4+k, en travaillant comme M,a renumerotation des bandes pres.

(2) Comparer mp+1 et le contenu y de Bp+3 (tout au long du calcul, la bandeBp+3 representera un entier ≤ mp+1) :– si mp+1 = y, aller a l’etape (5) ;– si mp+1 > y, aller a l’etape (3).

(3) Calculer h(m1, . . . ,mp, y, f(x, y)) = f(x, y + 1) comme le ferait M′, avecbandes d’entree B1, . . . , Bp, Bp+3, Bp+2, bande de sortie Bp+4 et les k′

dernieres bandes comme bandes auxiliaires.

(4) Copier le contenue de Bp+4 sur la bande Bp+2, puis nettoyer Bp+4 etincrementer le contenu de Bp+3 par un baton, c’est-a-dire passer de y ay + 1. Revenir a l’etape (2).

(5) Nettoyer Bp+3 et s’arreter.

Theoreme 4.4.5. Les fonctions partielles recursives sont T -calculables.

Demonstration. On combine les quatre lemmes precedents.

57

Exercice. Decrire une machine de Turing qui calcule λxy.x+ y.

Pour pouvoir etablir la reciproque du theoreme 4.4.5, nous allons coder lesmachines de Turing ainsi que leur fonctionnement.Codage des machines de Turing :On identifie S = {b, d, |} a {0, 1, 2}, via 0 ↔ b, 1 ↔ d et 2 ↔|. Une suite(si)i≤n, ou une suite (si)i∈N avec si = 0 pour presque tout i, est codee parΓ((si)) =

∑i≥0 si3

i ∈ N.Soit M une machine de Turing. Elle est donnee par– n = n(M) ≥ 1, le nombre de bandes de M ;– l’ensemble fini d’etats E : on supposera que E = {0, . . . ,m} (m ≥ 1 est

donc egal a card(E)− 1), avec ei = 0 et ef = 1 ;– la table de transition M : Sn × E → Sn × E × {−1, 0, 1} : pour coderM , si ρ = (s1, . . . , sn, e) ∈ Sn × E et M(ρ) = (t1, . . . , tn, e′, ε), on poser1(ρ) = α2(Γ(s1, . . . , sn), e) et r2(ρ) = α3(Γ(t1, . . . , tn), e′, ε+ 1), puis

pMq =∏

ρ∈Sn×Eπ(r1(ρ))r2(ρ).

Pour decoder, on utilisera la fonction δ, avec δ(i, x) := µz ≤ x(π(i)z+1 - x

).

On a alors δ(α2(Γ(s1, . . . , sn), e), pMq) = α3(Γ(t1, . . . , tn), e′, ε+ 1).Enfin, l’indice de M est donne par pMq = α3(n,m, pMq).

Lemme 4.4.6. Pour p ≥ 0, l’ensemble

Ip = {pMq | M est une machine de Turing a ≥ p+ 1 bandes}

est primitif recursif.

Demonstration. On voit facilement que l’on peut reconnaıtre de maniere pri-mitive recursive si les contraintes sur la table de transition sont satisfaites. Lesdetails sont laisses en exercice.

Une configuration C = C(t) deM (a un instant t) est un element (si)i ∈ SN

tel que snv+w soit l’element ecrit sur la (v + 1)e case de la bande Bw+1). (Onsuppose qu’il n’y a qu’un nombre fini de symboles non blancs et que le symboled est ecrit au debut de bande et uniquement la.)

On note Γ(C) := Γ((si)) le code de la configuration C. Pour decoder, onutilisera la fonction η(Γ(C), u, v, n) = r

(q(Γ(C), 3n(u−1)+(v−1)), 3

), (q etant le

quotient de la division avec reste, r etant le reste) qui donne le symbole s ecritsur la ue case de la bande Bv. Si σ = (s1, . . . , sn) est la suite des symboles ecritssur les cases no u, alors Γ(σ) = ε(Γ(C), u, n), ou ε(x, y, z) = r

(q(x, 3z(y−1)), 3z

).

La situation de M (a un instant t) est donnee par Sit = Sit(t) = (e, k, C(t)),ou e designe l’etat de M a l’instant t, k est le no de case devant laquelle latete se trouve a l’instant t et C(t) la configuration a l’instant t. On la code viaΓ(Sit(t)) = α3(e, k,Γ(C(t)).

58

Lemme 4.4.7. Soit p ≥ 0. Il existe une fonction primitive recursive gp ∈ F2

telle que– gp(i, x) = 0 si i 6∈ Ip ;– si i = pMq et x est le code de la situation deM a l’instant t, alors gp(i, x)

est le code de la situation de M a l’instant t+ 1.

Demonstration. On suppose i = pMq ∈ Ip. Alors– l’etat de la machine est β3

1(x) = e ;– le no des cases observees est β3

2(x) = k ;– le code de la configuration C(t) est β3

3(x) = Γ(C(t)) ; le nombre de bandesest donne par β3

1(i) = n ;– le nombre d’etats de M moins 1 est egal a β3

2(i) = m ;– le code de la table de transition est donne par β3

3(i) = pMq ;– le code de ce que lit la tete a l’instant t est donne par

ε (Γ(C(t)), k, n) = ε(β3

3(x), β32(x), β3

1(i))

=: c.

Si x n’est pas le code d’une situation, on pose gp(i, x) = 0. C’est le cas siβ3

1(x) > m, si β32(x) = 0 ou si β3

3(x) n’est pas le code d’une configuration avec den debut de bande et uniquement la (la derniere condition s’exprime de maniereprimitive recursive, en utilisant les fonctions ε et η).

Sinon, soit δ := δ (α2(c, e), pMq). Alors c′ = β31(δ) est le code de la suite

ecrite a la place de celle codee par c. On pourra poser gp(i, x) = α3 (e′, k′,Γ(C ′)),ou Γ(C ′) =

(Γ(C) + 3n(k−1) · c′

)−(

3n(k−1) · c)

est le code de la configuration,

e′ = β32(δ) l’etat de la machine, et enfin k′ =

(β3

2(x) + β33(δ)

)−1 le no des cases

observees a l’instant t+ 1.

On definit une fonction STp ∈ Fp+2 :– STp(i, t, x) = 0, si i 6∈ Ip ;– sinon, STp(i, t, x) est le code Γ(Sit(t)) de la situation a l’instant t de la

machineM d’indice i qui a commence a fonctionner en t = 0 sur la confi-guration suivante : sur B1, . . . , Bp sont representes les entiers x1, . . . , xp,et les autres bandes representent 0.

Theoreme 4.4.8. Pour tout p ≥ 0, la fonction STp est primitive recursive.

Demonstration. La fonction λix.STp(i, 0, x) est primitive recursive. (C’est facileet laisse en exercice.) Puis, on a STp(i, t+ 1, x) = gp (i,STp(i, t, x)).

On appelle configuration de sortie pour l’entree x = (x1, . . . , xp) une confi-guration ou les bandes B1, . . . , Bp representent x1, . . . , xp, la bande Bp+1 repre-sente un entier, et ou les autres bandes repesentent 0.

Pour p ≥ 0, on definit un predicat Ep ⊆ Np+2 de la maniere suivante :(i, c, x) ∈ Ep) ⇐⇒ i ∈ Ip et c est le code d’une configuration de sortie pourl’entree x.

59

Il est facile a voir que Ep est un ensemble primitif recursif. [Exercice. Pourexprimer par exemple que Bp+1 represente un entier, notons que dans la for-mule ∀z

(η(c, z, p+ 1, n) = 2 ∧ z ≥ 3→ η(c, z−1, p+ 1, n) = 2

), on peut borner

le quanteur universel par c.]On definit aussi les ensembles suivants :

Bp ={

(i, t, x) ∈ Np+2 | β31 (STp(i, t, x)) = 1 et (i, β3

3(STp(i, t, x)), x) ∈ Ep}

(a l’instant t, la machine d’indice i se trouve dans l’etat final, et sa configurationest une configuration de sortie pour l’entree x)

Cp ={

(i, y, t, x) ∈ Np+3 | (i, t, x) ∈ Bp et y est represente sur Bp+1

}Les ensembles Bp et Cp sont primitifs recursifs.

Soit maintenant f ∈ F∗p une fonction partielle T -calculable. Choisissons unemachine de Turing M qui calcule f , et posons i = pMq. On peut definir lafonction partielle TM (qui donne le temps de calcul) comme

TM(x) := µt ((i, t, x) ∈ Bp) .

Alors on a

f(x) =(µy ≤ TM(x)

)((i, y, TM(x), x) ∈ Cp

). (4.2)

On appelle (4.2) la forme normale de Kleene de f .

En particulier, nous avons montre les deux resultats suivants.

Theoreme 4.4.9. Les fonctions (partielles) T -calculables sont recursives.

Proposition 4.4.10. 1. Si f est totale et T -calculable en un temps primitifrecursif, alors f est primitive recursive.

2. L’ensemble des fonctions partielles recursives est le plus petit sous-ensemblede F∗ contenant les fonctions primitives recursives et clos par compositionet schema µ.

3. L’ensemble des fonctions totales recursives est le plus petit sous-ensemblede F contenant les fonctions primitives recursives et clos par compositionet schema µ total. Autrement dit, toute fonction recursive totale s’obtientpar un nombre fini d’applications des regles (R0)− (R3).

On observera que nos arguments pour montrer que toute fonction T -calculableest recursive ne sont pas specifiques aux machines de Turing. Cela justifie la

These de Church.Toute fonction calculable (au sens intuitif du terme) est recursive.

60

4.5 Fonctions universelles

Il suffit de varier l’indice de la machine de Turing pour obtenir une fonctionuniverselle. On definit d’abord la fonction T p ∈ F∗p+1 comme suit :

– si i 6∈ Ip, T p(i, x) n’est pas definie ;– si i ∈ Ip, on pose T p(i, x) = µt ((i, t, x) ∈ Bp).Ensuite, on definit la fonction partielle recursive ϕp ∈ F∗p+1,

ϕp(i, x) = µy [(i, y, T p(i, x), x) ∈ Cp] .

On note ϕpi = λx.ϕp(i, x).

Proposition 4.5.1. ϕp est une fonction partielle recursive universelle : toutefonction partielle recursive en p variables est de la forme ϕpi pour un entier iconvenable.

Theoreme 4.5.2 (Theoreme SMN). Pour tout couple d’entiers m et n il existeune fonction smn ∈ Fn+1 primitive recursive telle que pour tout i ∈ N, x ∈ Nn ety ∈ Nm on ait

ϕn+mi (x, y) = ϕmsmn (i,x)(y).

Demonstration. Soit M une machine de Turing a ≥ m + n + 1 bandes. Etantdonne (a1, . . . , an) ∈ Nn, on considere la machine M′ qui fonctionne ainsi :

(1) Elle ecrit a1, . . . , an sur les bandes Bm+2, . . . , Bm+n+1.(2) Puis, elle travaille comme M, a permutation des bandes pres, et ecrit le

resultat sur la bande Bm+1.(3) Elle nettoie les bandes Bm+2, . . . , Bm+n+1, puis s’arrete.

Il est clair qu’il existe une fonction primitive recursive g ∈ Fn+1 qui calculepM′q ∈ Im a partir de pMq et a1, . . . , an, c’est-a-dire g(pMq, a1, . . . , an) =pM′q et g(i, a) = 0 si i 6∈ Im+n. Il suffit donc de poser smn = g.

Theoreme 4.5.3 (Theoreme du point fixe). Soit m > 0 et α ∈ F1 recursivetotale. Alors il existe i ∈ N tel que ϕmi = ϕmα(i).

Demonstration. On considere g = λyx1 . . . xm.ϕm(α(sm1 (y, y)), x1, . . . , xm). Par

universalite (Proposition 4.5.1), on a g = ϕm+1a pour un indice a ∈ N. On calcule

ϕmα(sm1 (y,y))(x) = ϕm+1a (y, x) = ϕmsm1 (a,y)(x).

Il suffit de poser i := sm1 (a, a) pour obtenir ϕmα(i) = ϕmi .

Le theoreme du point fixe fournit un argument elegant pour montrer le re-sultat suivant (cf. Exercice 4.3.1).

Proposition 4.5.4. La fonction d’Ackermann ξ est recursive.

Demonstration. On definit θ ∈ F∗3 recursive partielle comme suit :– θ(i, y, x) = 2x si y = 0 ;

61

– θ(i, y, x) = 1 si x = 0 ;– θ(i, y, x) = ϕ2(i, y−1, ϕ2(i, y, x−1)) sinon.

Par universalite, il existe a ∈ N tel que θ = ϕ3a. Par le theoreme SMN, on a donc

θ(i, y, x) = ϕ2s21(a,i)(y, x).

Posons α = λi.s21(a, i). Par le theoreme du point fixe il existe i0 ∈ N tel que ϕ2

i0=

ϕ2α(i0). La fonction ϕ2

i0est recursive et satisfait aux relations qui definissent la

fonction d’Ackermann : pour y, x ≥ 1, on a

ϕ2i0(y, x) = θ(i0, y, x) = ϕ2(i0, y − 1, ϕ2(i0, y, x− 1)) = ϕ2

i0(y − 1, ϕ2i0(y, x− 1)).

(Notons que la totalite de ϕ2i0

s’obtient egalement par recurrence.)

4.6 Ensembles recursivement enumerables

Definition. Un ensemble R ⊆ Nn est appele recursivement enumerable (r.e.)s’il existe S ⊆ Nn+1 recursif tel que R = π(S), ou π est la projection sur les npremieres coordonnees.

Une relation R(x1, . . . , xn) sur N est donc recursivement enumerable s’ilexiste une relation recursive S(x, y) telle que (dans N) R(x) ⇐⇒ ∃yS(x, y).

Remarque. Tout ensemble recursif est r.e.

Proposition 4.6.1. L’ensemble des relations r.e. est clos par conjonction, dis-jonction, quantification universelle bornee et par quantification existentielle. Deplus, si f1, . . . , fn ∈ Fm sont recursives et si R ⊆ Nn est r.e., alors {x ∈ Nm |(f1(x), . . . , fm(x)) ∈ R} est r.e.

Demonstration. Soient P , Q et R des relations telles que P (x) ⇐⇒ ∃yP (x, y),Q(x) ⇐⇒ ∃yQ(x, y) et R(x, z) ⇐⇒ ∃yR(x, z, y) pour P ,Q et R recursives.Alors on a les equivalences suivantes :

(P (x) ∨Q(x)) ⇐⇒ ∃y(P (x, y) ∨Q(x, y)

)(P (x) ∧Q(x)) ⇐⇒ ∃y

(P (x, β2

1(y)) ∧Q(x, β22(y))

)∃zR(x, z) ⇐⇒ ∃z∃yR(x, z, y) ⇐⇒ ∃sR(x, β2

1(s), β22(s))

R(f1(x), . . . , fn(x)) ⇐⇒ ∃yR(f1(x), . . . , fn(x), y)

∀z ≤ wR(x, z) ⇐⇒ ∀z ≤ w∃yR(x, z, y) ⇐⇒ ∃s∀z ≤ wR(x, z, (s)z)

Ici, (s)z designe la fonction composante du lemme 4.1.4.

Theoreme 4.6.2. Soit X ⊆ Nn. Sont equivalents :

1. X est r.e.

2. X est vide ou l’image d’une fonction f = (f1, . . . , fn) : N → Nn avecf1, . . . , fn ∈ F1 recursives (totales).

62

3. X = dom(f) pour une fonction partielle recursive f ∈ F∗n.

4. Il existe Y ⊆ Nn+1 primitif recursif tel que X = π(Y ).

Demonstration. Quitte a identifier Nn et N par αn (une fonction primitive re-cursive), on peut supposer n = 1.(1)⇒(2) : Soit r ∈ X et X = P 2

1 (Y ) pour Y recursif. Alors X = im(f), pourf ∈ F1 definie ainsi :

f(z) :=

{β2

1(z), si (β21(z), β2

2(z)) ∈ Y ;r, sinon.

(2)⇒(3) : On a ∅ = dom(g) pour g = λx.µt(x > x). Si X = im(f), on definitg = λx.µt(x = f(t)). Alors dom(g) = im(f) = X.(3)⇒(4) : Soit f ∈ F∗1 recursive partielle et X = dom(f). Alors par universaliteil existe i0 ∈ N tel que f = ϕ1

i0, c’est-a-dire

X = {x ∈ N | ∃t[(i0, t, x) ∈ B1

]}.

Cela etablit (4), puisque B1 est primitif recursif.(4)⇒(1) : Trivial.

Remarque. Notons que la preuve de (1)⇒(2), compte tenu de l’equivalenceentre (1) et (4), montre que l’on pourra meme supposer dans (2) que les fonc-tions f1, . . . , fn sont primitives recursives.

Corollaire 4.6.3. L’ensemble U = dom(ϕn) ⊆ Nn+1 est universel r.e. : il estr.e. et pour tout R ⊆ Nn r.e. il existe e ∈ N tel que R = {x | (e, x) ∈ U}.

Theoreme 4.6.4. Un ensemble X ⊆ Nn est recursif ssi X et Nn \X sont r.e.

Demonstration. ”⇒” est clair.Quant a ”⇐”, soit X ⊆ Nn tel que X = π(Y ) et Nn \ X = π(Y ′) avec

Y, Y ′ ⊆ Nn+1 recursifs. Alors 1X(z) = 1Y (z, µt[(z, t) ∈ Y ∪ Y ′])).

Theoreme 4.6.5. L’ensemble dom(ϕ1) n’est pas recursif. En particulier, ilexiste un ensemble r.e. qui n’est pas recursif.

Demonstration. On montre que g = λx.ϕ1(x, x) n’est pas de domaine recursif.(On ne peut pas decider si une machine s’arrete quand on la fait fonctionner surson propre code.)

Soit D = N\dom(g). Si D etait r.e., alors D = dom(ϕ1i0

) pour un i0 ∈ N parle corollaire 4.6.3. En particulier, on aurait i0 ∈ D si et seulement si ϕ1(i0, i0)est definie. Or, par definition de g, i0 ∈ D si et seulement si ϕ1(i0, i0) n’est pasdefinie. Absurde.

Une petite variation montre que le probleme de l’arret n’est pas decidable :

63

Theoreme 4.6.6 (Undecidabilite du probleme de l’arret). L’ensemble des in-dices des machines de Turing qui s’arretent lorsqu’elles commencent a fonction-ner sur l’entree vide n’est pas recursif.

Demonstration. Par l’absurde. Si l’ensemble

Ia = {i ∈ I1 | M d’indice i s’arrete si elle est lancee sur l’entree vide}

est recursif, il est facile a voir que l’ensemble Is = dom(λx.ϕ1(x, 0)

)est recursif

aussi, ou Is est donc l’ensemble des indices des machines de Turing qui s’arretentsur une configuration de sortie pour 0 lorsqu’elles sont lancees sur l’entree vide :si i ∈ Ia, alors i ∈ Is ssi

(i, β3

3(ST1(i, µt[β31(ST1(i, t, 0)) = 1], 0)), 0

)∈ E1.

On considere A ⊆ N r.e. non recursif (un tel A existe par 4.6.5). SoitM unemachine de Turing qui calcule une fonction f ∈ F∗2 avec dom(f) = A×{0}. Soiti0 l’indice de M. Alors A = {n ∈ N | s1

1(i0, n) ∈ Is}, ce qui montre que A estrecursif. Contradiction.

Theoreme 4.6.7 (Theoreme de Rice). Soit X un ensemble de fonctions par-tielles recursives a une variable. On suppose que X est non vide et distinctde l’ensemble de toutes les fonctions partielles recursives a une variable. AlorsI = {i ∈ N | ϕ1

i ∈ X} n’est pas recursif.

Demonstration. Quitte a passer au complement, on peut supposer que la fonc-tion de domaine vide est dans X . On choisit j ∈ N \ I, et on note ψ(x, y, z) =(ϕ1(j, z) + ϕ1(x, y)

)−ϕ1(x, y), puis ψx,y = λz.ψ(x, y, z). Alors

ψx,y ∈ X ⇐⇒ (x, y) 6∈ dom(ϕ1) = U.

On a ψ = ϕ3i0

pour un entier i0, donc ψx,y = ϕ1s12(i0,x,y)

par le theoremeSMN. Posons h = λxy.s1

2(i0, x, y). C’est une fonction primitive recursive. Ona (x, y) ∈ N2 \ U ⇐⇒ h(x, y) ∈ I. Comme N2 \ U n’est pas recursif par letheoreme 4.6.4, I n’est pas recursif non plus.

Exemples 4.6.8. 1. Soit f ∈ F∗1 une fonction partielle recursive. Alors l’en-semble {i ∈ N | ψ1

i = f} n’est pas recursif.2. {(i, j) ∈ N2 | ϕ1

i = ϕ1j} ⊆ N2 n’est pas recursif.

3. L’ensemble des indices des fonctions totales (recursives) n’est pas recursif.

4.7 Elimination de la recurrence

Theoreme 4.7.1 (Elimination de la recurrence). Toute fonction recursive to-tale s’obtient a partir des fonctions de base C0

0 , S, Pni ,+, · et 1<, en appliquant

uniquement les regles (R1) et (R3).

Demonstration. Une fonction totale est appelee #-recursive si elle satisfait a laconclusion du theoreme 4.7.1. Par la proposition 4.4.10(3), il suffira de montrerque la classe des fonctions #-recursives est close par (R2) (recurrence).

64

Lemme 4.7.2. (1) La fonction λxy.x−y est #-recursive.(2) La classe des ensembles #-recursifs est close par combinaisons booleennes

et quantification bornee.(3) 1= est #-recursive.(4) L’ensemble {(x, y, z) | x ≡ y mod z} est #-recursif.(5) La classe des fonctions #-recursives est close par definition par cas (voir

Lemme 4.1.2(5)), si les fonctions et les ensembles de la partition sont#-recursifs.

Preuve du lemme 4.7.2. (1) x−y = µz (x < (y + z) + 1)On a 1Xc = 1−1X et 1X∩Y = 1X · 1Y , ce qui etablit la cloture par combi-

naisons booleennes.(3) On a x = y ⇐⇒ (¬x < y ∧ ¬y < x).Maintenant, soit X ⊆ Nn+1 un ensemble #-recursif. On definit g ∈ Fn+1,

g(x, z) := µy ((x, y) ∈ X ou y = z + 1) .

Comme la condition entre parentheses s’exprime facilement par f(x, y, z) = 0pour une fonction #-recursive f , on voit que g est #-recursive aussi. On a∃y ≤ z : (x, y) ∈ X ⇐⇒ g(x, z) < z + 1, d’ou la cloture par quantificationexistentielle bornee. Comme ∀y ≤ z ϕ est equivalent a ¬∃y ≤ z ¬ϕ, la preuve de(2) est terminee.

(4) On a x ≡ y mod z ⇐⇒ ∃w ≤ x+ y(x = y + w · z ∨ y = x+ w · z

).

(5) Soit Nn = A1∪ . . . ∪Ak une partition avec Ai #-recursif pour tout i,et soient f1, . . . , fk ∈ Fn des fonctions #-recursives. Par induction sur k, onmontre que

∑ki=1 1Ai · fi est #-recursive.

Lemme 4.7.3 (La fonction β de Godel). Il existe une fonction #-recursiveβ ∈ F3 telle que pour toute suite finie d’entiers (c0, . . . , cn−1) il existe a, b ∈ Navec β(a, b, i) = ci pour i = 0, . . . , n− 1.

Demonstration. On pose β(a, b, i) := µz [z ≡ a mod (b(i+ 1) + 1)]. La fonctionβ est #-recursive par le lemme 4.7.2. Soient c0, . . . , cn−1 donnes, et soit b ∈ N,b divisible par n! et b > ci pour tout i. Alors b + 1, 2b + 1, 3b + 1, . . . , nb + 1sont 2 a 2 premiers entre eux. En effet, si p premier divise ib+ 1 et jb+ 1 pour1 ≤ i < j ≤ n, alors p - b et p | b(i − j). Donc p | (i − j). Comme (i − j) | n!,c’est absurde.

Par le theoreme chinois il existe a tel que pour tout i = 0, . . . , n − 1 on aita ≡ ci mod ((i + 1)b + 1). Comme ci < (i + 1)b + 1 pour tout i, ci est le pluspetit entier z tel que z ≡ a mod ((i+ 1)b+ 1).

Revenons a la preuve du theoreme 4.7.1. Soient donc g ∈ Fn et h ∈ Fn+2 #-recursives, et soit f ∈ Fn+1 definie par recurrence a partir de g et h, c’est-a-diref(x, 0) = g(x) et f(x, y + 1) = h(x, y, f(x, y)). La relation

R(x, y, a, b) :⇐⇒ [β(a, b, 0) = g(x) ∧ ∀i ≤ y (β(a, b, i+ 1) = h(x, i, β(a, b, i)))]

65

est #-recursive par les lemmes 4.7.2 et 4.7.3.Par le choix de β, on a ∀x, y∃a, bR(x, y, a, b). Alors la fonction e qui a (x, y)

associe µs (∃a ≤ s∃b ≤ sR(x, y, a, b)) est #-recursive.Enfin, f(x, y) = µz [∃a ≤ e(x, y)∃b ≤ e(x, y) (R(x, y, a, b) ∧ z = β(a, b, y))],

ce qui montre que f est #-recursive.

66

Chapitre 5

Modeles de l’arithmetiqueet theoremes de limitation

5.1 Codage des formules et des preuves

Soit σL = {λ1, . . . , λl} une signature finie. On associe aux symboles s de Lleur nombre de Godel psq comme suit : a =,∧,¬, (, ),∃ on associe successivement〈0, 0〉, 〈0, 1〉, . . . , 〈0, 5〉, a λi on associe 〈0, i+ 5〉, et a vi (i ∈ N) on associe 〈1, i〉.

A un mot m = s1 · · · sn sur l’alphabet L on associe le nombre de Godel

#m = 〈ps1q, . . . , psnq〉.

Ce codage est evidemment injectif.

Lemme 5.1.1. Les ensembles suivants sont primitifs recursifs :1. Term = {#t | t est un L-terme}2. Form = {#ϕ | ϕ est une L-formule}3. {(#t, n) | t est un L-terme dans lequel vn a une occurrence} et{(#t, n) | t est un L-terme dans lequel vn n’a pas d’occurrence}

4. {(#ϕ, n) | ϕ est une formule dans laquelle vn a une occurrence},de meme pour ‘n’a pas d’occurrence’, ‘a au moins une occurrence libre’,‘n’a pas d’occurrence libre’, ‘a au moins une occurrence liee’ et ‘n’a pasd’occurrence liee’ a la place de ‘a une occurrence’.

5. {#ϕ | ϕ est un L-enonce}.

Demonstration. On utilise les proprietes du codage 〈. . .〉 des suites finies (Lemme4.1.4), en particulier n = lg(〈s0, . . . , sn−1〉) ≤ 〈s0, . . . , sn−1〉 et la fonction pri-mitive recursive de decodage a deux places λxi.(x)i.

Par les proprietes de lecture unique, on pourra non seulement argumenter parinduction sur la longueur, mais aussi par induction sur la hauteur (des termeset des formules). Par exemple si x est le code d’un mot m qui commence avec

67

‘(’, alors x est le code d’une formule si et seulement s’il existe y1, y2 < x tels queyi = #ϕi pour des formules ϕ1, ϕ2 et tels que m = (ϕ1 ∧ ϕ2). Les details sontlaisses en exercice.

Rappelons que nous avons defini la substitution dans les termes et les for-mules. Si x1, . . . , xn sont n variables 2-a-2 distinctes, et s1, . . . , sn des termes,nous avons defini ts/x et ϕs/x. On montre sans probleme que les fonctions sui-vantes St : N3 → N et Sf : N3 → N sont primitives recursives : St est la fonctionqui a (a, b, c) associe #ts/vi1 ,...,vin si a = #t ∈ Term, b = 〈i1, . . . , in〉 est le coded’une suite d’entiers 2-a-2 distincts et c = 〈#s1, . . . ,#sn〉, ou #si ∈ Term pourtout i, et 0 sinon.

La fonction Sf est definie de la meme maniere, c.-a-d. pour (a, b, c) =(#ϕ, 〈i1, . . . , in〉, 〈#s1, . . . ,#sn〉) convenable on a Sf (a, b, c) = #ϕs/vi1 ,...,vin .

En particulier, nous obtenons donc le resultat suivant.

Lemme 5.1.2. Il existe des fonctions primitives recursives Substt,Substf ∈F3 telles que pour tout n, si s et t sont des termes et ϕ une formule, alorsSubstt(n,#s,#t) = #ts/vn et Substf (n,#s,#ϕ) = #ϕs/vn .

De la meme maniere, on code les formules du calcul propositionnel, via F 7→#F ∈ N, ou F ∈ FmlP .

Lemme 5.1.3. L’ensemble Taut des codes des tautologies du calcul des predicatest primitif recursif.

Demonstration. On montre :– FormP = {#F | F ∈ FmlP} est un ensemble primitif recursif ;– la fonction qui a (d, x) associe la valeur de verite (0 ou 1) de la for-

mule F = F [p0, . . . , pn−1] pour la distribution des valeurs de verite d =〈d0, . . . , dn−1〉 si d est le code d’une suite de 0 et 1 de longueur n et x = #Fest le code de F ∈ FmlP ne contenant que des variables propositionnellespi avec i ≤ n− 1, et 0 sinon, est primitive recursive ;

– l’ensemble TautP = {#F | F est une tautologie} est primitif recursif ;– il existe une fonction primitive recursive qui a (〈#ϕ0, . . .#ϕn−1〉,#F )

associe #Fϕ/p si F = F [p0, . . . , pn−1].Ceci permet de conclure.

On peut egalement reconnaıtre de maniere primitive recursive les codes desaxiomes de l’egalite ainsi que les codes des axiomes du quanteur existentiel(compte tenu du lemme 5.1.2). Nous avons donc montre le theoreme suivant.

Theoreme 5.1.4. L’ensemble Ax des codes #ϕ des axiomes logiques ϕ de Lest primitif recurisf.

Codage des preuves formelles

Si d = (ϕ0, . . . , ϕn−1) est une suite finie de L-formules, on la code via ##d =〈#ϕ0, . . . ,#ϕn−1〉.

68

Lemme 5.1.5. Dem = {(x,#ϕ) | x = ##d et d est une preuve formelle de ϕ}est un ensemble primitif recursif.

Demonstration. Il suffit de decoder et de tester si toutes les composantes de xsont des codes de L-formules ϕi, la derniere etant egale a ϕ, et si pour tout i,soit ϕi est un axiome logique (ce qui se voit de maniere primitive recursive parle theoreme 5.1.4), soit elle peut s’obtenir par une regle de deduction a partirde formules deja obtenues avant.

Proposition 5.1.6. U = {#ϕ | ` ϕ} est recursivement enumerable.

Demonstration. On a n ∈ U ⇔ ∃d (d, n) ∈ Dem.

5.2 Theories decidables

Pour T une theorie, on note Thm(T ) = {ϕ L-enonce | T ` ϕ}, la cloturedeductive de T .

Definition. Soit T une L-theorie.

1. T est dite recursive si {#ϕ | ϕ ∈ T} est un ensemble recursif.

2. T est dite recursivement (ou effectivement) axiomatisable s’il existe uneL-theorie recursive T0 telle que Thm(T ) = Thm(T0).

3. T est dite decidable si Thm(T ) est une theorie recursive, c.-a-d. si l’en-semble #Thm(T ) = {#ϕ | T ` ϕ} est recursif.

Si T est une L-theorie, on definit l’ensemble

Dem(T ) = {(##d,#ϕ) | d est une preuve de ϕ dans T}.

Lemme 5.2.1. Si T est recursive, Dem(T ) est un ensemble recursif.

Demonstration. Exercice.

Theoreme 5.2.2. Si T est effectivement axiomatisable, alors #Thm(T ) estrecursivement enumerable.

Demonstration. Soit T0 une theorie recursive telle que Thm(T ) = Thm(T0).On a ϕ ∈ Thm(T ) si et seulement si ϕ est un L-enonce et il existe une preuve

de ϕ dans T0. On conclut par les lemmes 5.1.1(5) et 5.2.1.

Remarque 5.2.3. La reciproque du theoreme 5.2.2 est vraie aussi.

Demonstration. Supposons que l’ensemble #Thm(T ) est recursivement enume-rable. Il existe donc f ∈ F1 recursive telle que #Thm(T ) = {f(i) = #ϕi | i ∈N}. La fonction g qui a n associe #

∧ni=0 ϕi est recursive et on a g(n) ≥ n pour

tout n. Son image est donc un ensemble recursif. Par ailleurs, {∧ni=0 ϕi | n ∈ N}

est une axiomatisation de Thm(T ).

69

Theoreme 5.2.4. Soit T effectivement axiomatisable et complete. Alors T estdecidable.

Demonstration. Par le theoreme 5.2.2, on sait que #Thm(T ) est recursivementenumerable. Or, son complementaire N \#Thm(T ) est donne par la renuion de{x | x n’est pas le code d’un L-enonce} et de {#ϕ | ¬ϕ ∈ Thm(T )}.

Le premier ensemble est primitif recursif, et le deuxieme est recursivementenumerable, car #ϕ 7→ #¬ϕ est donne par une fonction (primitive) recursive.On conclut par le theoreme 4.6.4.

Exemples 5.2.5. 1. Toute theorie finiment axiomatisable est effectivementaxiomatisable. [Clair.]

2. CACp, p premier ou 0, est decidable.[En effet, l’axiomatisation que nous avons donnee est certainement re-cursive, et on conclut donc en combinant le theoreme 3.5.3 (CACp estcomplete) avec le theoreme 5.2.4.]

3. CAC est une theorie decidable.[En effet, comme CAC est effectivement axiomatisable, il suffit de montrerque l’ensemble X = {#ϕ | ϕ est un enonce et CAC 6|= ϕ} est recursive-ment enumerable. Or, CAC 6|= ϕ si et seulement s’il existe p premier telque CACp |= ¬ϕ. (C’est une consequence du Principe de Lefschetz.) Celaest equivalent a CAC |= χp → ¬ϕ, ou χp = 1 + · · ·+ 1=0︸ ︷︷ ︸

p fois

.

Il s’en suit que #ϕ ∈ X si et seulement s’il existe p premier et y tels que(y,#(χp → ¬ϕ)) ∈ Dem(CAC). Comme l’application (p,#ϕ) 7→ #(χp →¬ϕ) est (primitive) recursive, on conclut que X est recursivement enume-rable.]

4. La theorie du corps ordonne des reels R est decidable (c’est un resultatde Tarski).[Comme elle est complete, il suffit de donner une axiomatisation effective.On peut montrer que tout corps ordonne 〈K; +,−, 0, 1, ·, <〉 satisfaisantaux deux proprietes suivantes est elementairement equivalent a R :– tout element positif est un carre (∀x(x ≥ 0→ ∃y y · y=x)) ;– K a la propriete de la valeur intermediaire pour les fonctions poly-

nomiales, c.-a-d. si P (X) ∈ K[X] est un polynome et a < b avecP (a) · P (b) < 0, alors il existe c ∈ K tel que a < c < b et P (c) = 0.

Pour le prouver, Tarski a montre que Th(R) admet l’elimination des quan-teurs dans le langage des corps ordonnes, un resultat que nous ne pouvonspas presenter dans ce cours, par manque de temps.]

Exercice 5.2.6. Si T est decidable et ϕ0, . . . , ϕn−1 sont des L-enonces, alorsT ∪ {ϕ0, . . . , ϕn−1} est decidable.

5.3 Arithmetique de Peano

On considere le langage de l’arithmetique Lar = {0, S,+, ·, <}.

70

Definition. L’ensemble des axiomes de Peano faibles est l’ensemble fini P0 des8 axiomes suivants :

(A1) ∀v0 ¬Sv0=0(A2) ∀v0 ∃v1(¬v0=0→ Sv1=v0)(A3) ∀v0∀v1 (Sv0=Sv1 → v0=v1)(A4) ∀v0 v0 + 0=v0

(A5) ∀v0∀v1 v0 + Sv1=S(v0 + v1)(A6) ∀v0 v0 · 0=0(A7) ∀v0∀v1 v0 · Sv1=(v0 · v1) + v0

(A8) ∀v0∀v1 (v0 < v1 ↔ (∃v2v2 + v0=v1 ∧ ¬v0=v1))

L’ensemble des axiomes de Peano est l’ensemble (infini) P forme de P0, ainsique pour chaque Lar-formule ϕ = ϕ[v0, . . . , vn] de l’axiome d’induction suivant(on pose v = (v1, . . . , vn)) :

∀v1∀v2 · · · ∀vn((ϕ(0, v) ∧ ∀v0(ϕ(v0, v)→ ϕ(Sv0, v))→ ∀v0ϕ(v0, v)).

Remarque 5.3.1. 1. On a N = 〈N; 0, succ,+, ·, <〉 |= P.

2. P0 est une expansion par definition de la Lar \ {<}-theorie (A1)-(A7).(C’est une consequence de (A8).)

3. P0 est une theorie tres faible. On peut construire des modeles dans les-quels l’addition (ou la multiplication) n’est pas commutative / associative ;de meme, il y a des modeles dans lesquels ≤ ne definit pas une relationd’ordre.

4. Pour n ∈ N, dans tout modele de P0 on trouve l’element qui interpreten = S · · ·S︸ ︷︷ ︸

n fois

0. Un element est dit non standard s’il est different de n

pour tout n ∈ N. Par compacite, il existe des modeles de P contenant deselements non standards.

Definition. Soit M ⊆ M′ deux Lar-structures. On dit que M est un segmentinitial de M′ si

– pour tout a′ ∈M ′ et tout a ∈M tel que M′ |= a′ < a on a a′ ∈M , et– pour tout a′ ∈M ′ \M et tout a ∈M on a M′ |= a < a′.

Lemme 5.3.2. Soit M |= P0. Alors N = {nM | n ∈ N} est l’ensemble de based’une sous-structure de M isomorphe a N qui forme un segment initial de M.

Demonstration. Soit M |= P0. On montre :(i) Pour tout m,n ∈ N on a P0 |= m+ n=m+ n.[Preuve par induction sur n, en utilisant (A4) et (A5).]

(ii) Pour tout m,n ∈ N on a P0 |= m · n=m · n.[Preuve par induction sur n, en utilisant (A6), (A7) et (i).]

(iii) P0 |= ∀x∀y(x < y ⇐⇒ Sx < Sy).

71

[En effet, si c ∈ M , alors M |= (c + x=y ∧ ¬x=y)(A3)⇔ M |= (S(c + x)=Sy ∧

¬Sx=Sy)(A5)⇔ M |= (c+ Sx=Sy ∧ ¬Sx=Sy). Le resultat suit de (A8).]

(iv) Pour tout n ∈ N on a P0 |= ∀x(x < n↔∨n−1i=0 x=i).

[Preuve par induction sur n. Si M |= c < 0 pour un c ∈ M , alors (dans M)a+ c = 0 pour un a ∈M et c 6= 0 (par (A8)), donc c = Sd pour un d (par (A2))et enfin (par (A5)) 0 = a + Sd = S(a + d), ce qui contredit (A1). Cela montrele cas n = 0.

Pour l’etape d’induction, on utlise (iii) ainsi que le fait que 0 < c pour toutc 6= 0 (consequence de (A4) et (A8)).]

(v) Soit c ∈M \N et n ∈ N. Alors M |= n < c.[Preuve par induction sur n, le cas n = 0 etant clair. Pour l’etape d’inductionn 7→ n + 1, notons que c = Sd pour un d 6∈ N . On a donc M |= n < d, ce quidonne M |= n+ 1 < c, en utilisant (iii).]

Il est clair que cela termine la preuve.

Quitte a nommer les elements de N par des constantes (ce qui est inutilepuisque tout element de N est donne par l’interpretation d’un terme), nousavons donc en particulier montre que si M |= P0, alors M |= ∆(N ).

Definition. – L’ensemble des formules Σ1 est le plus petit sous-ensembledes Lar-formules contenant les formules sans quanteurs et qui est clos par∧, ∨, quantification existentielle ∃x et quantification universelle bornee∀x < t, ou t est un terme. [On definit (∀x < t)ϕ := ∀x(x < t→ ϕ).]

– L’ensemble des formules Σ1 strictes est le plus petit sous-ensemble desLar-formules contenant les formules 0=x, sx=y, x + y=z, x · y=z, x=y,¬x=y, x < y, ¬x < y et qui est clos par ∧, ∨, ∃x et ∀x < y.

Lemme 5.3.3. 1. Toute formule Σ1 est equivalente a une formule Σ1 stricte.2. Si ϕ est une formule Σ1, alors toute formule ϕs/x obtenue par substitution

est Σ1 aussi.

Demonstration. On peut eliminer des termes complexes a l’aide de quanteursexistentiels, voir la preuve du lemme 3.3.1. Par exemple, la formule x ·Sy=z estequivalente a ∃u∃v(Sy=u ∧ x · u=v ∧ Sz=v). La seconde partie est claire.

Proposition 5.3.4. Tout enonce Σ1 vrai dans N est consequence de P0.

Demonstration. On montrera que pour toute formule Σ1 stricte ϕ(x1, . . . , xn)et tout m1, . . . ,mn ∈ N on a

N |= ϕ[m1, . . . ,mn]⇒ P0 |= ϕ(m1, . . . ,mn).

Cela suffira par le lemme 5.3.3.Si ϕ est une formule de base, c’est une consequence du lemme 5.3.2.Supposons que le resultat a ete demontre pour ϕ(x0, . . . , xn) et ψ(x0, . . . , xn).

Les cas (ϕ ∧ ψ) et (ϕ ∨ ψ) sont alors clairs. Quant au quanteur existentiel, si

72

N |= ∃x0ϕ[m1, . . . ,mn], alors il existe m0 ∈ N tel que N |= ϕ[m0, . . . ,mn],ce qui implique P0 |= ϕ(m0, . . . ,mn) par hypothese d’induction, d’ou P0 |=∃x0ϕ(m1, . . . ,mn).

Finalement, siN |= (∀x0 < x1)ϕ[m1, . . . ,mn], alorsN |= ϕ[m0,m1, . . . ,mn]pour tout m0 < m1 par definition de ∀x0 < x1. Par hypothese d’induction, on adonc P0 |= ϕ(m0, . . . ,mn) pour tout m0 < m1. Par (iv) de la preuve du lemme5.3.2, on obtient alors P0 |= (∀x0 < x1)ϕ(m1, . . . ,mn).

Definition. Soit f ∈ Fp. On dit que la formule ϕ = ϕ(x1, . . . , xp+1) representef si pour tout n1, . . . , np ∈ N on a

P0 |= ∀y(ϕ(n1, . . . , np, y)↔ y=f(n1, . . . , np)

).

On dit que ϕ(x1, . . . , xp) represente A ⊆ Np si pour tout n1, . . . , np ∈ N on a

n ∈ A⇒ P0 |= ϕ(n1, . . . , np) et n 6∈ A⇒ P0 |= ¬ϕ(n1, . . . , np).

Remarque. Si ϕ(x1, . . . , xp) represente A, alors 1A est representee par la for-mule (ϕ(x) ∧ xp+1=1) ∨ (¬ϕ(x) ∧ xp+1=0).

Reciproquement, si ψ(x, xp+1) represente 1A, alors ψ(x, 1) represente A.

Theoreme 5.3.5 (Theoreme de representabilite).Toute fonction recursive totale est representee par une formule Σ1.

Demonstration. – Les fonctions de base S, Pni , C00 ,+, · ainsi que 1< sont

representables par des formules sans quanteurs (qui sont Σ1 par definition).– Si f1, . . . , fp ∈ Fm sont representees par ϕ1, . . . , ϕp et si g ∈ Fp est repre-

sentee par ψ, alors h = g(f1, . . . , fp) ∈ Fm est representee par

∃y1, . . . ,∃ypp∧i=1

ϕi(x, yi) ∧ ψ(y1, . . . , yp, xm+1).

En particulier, l’ensemble des fonctions qui sont representables par uneformule Σ1 est clos par composition.

– Soit f ∈ Fp+1 et g ∈ Fp definie a partir de f par schema µ total, c.-a-d.g(x) = µy (f(x, y) = 0). Soit A = {(x, y) | f(x, y) = 0} ⊆ Np+1. On sup-pose que f est representee par une formule Σ1. Alors 1A = 1=(f(x, y), 0)est egalement representee par une formule Σ1 (c’est une composition defonction qui le sont), disons par ϕ(x, y, z). La fonction g est donc repre-sentee par la formule Σ1 ψ(x, y) = ϕ(x, y, 1) ∧ (∀y′ < y)ϕ(x, y′, 0).En particulier, l’ensemble des fonctions qui sont representables par uneformule Σ1 est clos par schema µ total.

On conclut par le theoreme 4.7.1.

Corollaire 5.3.6. Un ensemble A ⊆ Nn est recursivement enumerable si etseulement s’il existe une fomule Σ1 qui definit A (dans la structure N ).

73

Demonstration. Tout ensemble definissable sans quanteur est (primitif) recursif,donc un ensemble defini par une formule Σ1 est recursivement enumerable parcloture des ensembles recursivement enumerables par projection.

Reciproquement, comme un ensemble recursivement enumerable est la pro-jection d’un ensemble recursif, il suffit de montrer que tout ensemble recursifest definit par une formule Σ1, ce qui est une consequence du theoreme de re-presentabilite.

Proposition 5.3.7. Soit M un modele de P. Alors, les proprietes suivantessont satisfaites dans M :

1. + et · sont commutatives et associatives.

2. · est distributive par rapport a +.

3. < definit un ordre total, compatible avec + (si a < b, alors a+ c < b+ c)et avec la multiplication avec un element non nul (si a < b et c 6= 0, alorsa · c < b · c) ; 0 est l’element minimal, et pour tout a, Sa est le successeurimmediat de a.

4. Tout element est regulier pour l’addition (a+ c = b+ c⇒ a = b), et toutelement non nul est regulier pour la multiplication (si a · c = b · c et c 6= 0,alors a = b).

Demonstration. Toutes ces proprietes s’obtiennent facilement par les axiomesd’induction de P. A titre d’exemple, nous donnons les arguments pour l’asso-ciativite et la commutativite de l’addition. Le reste est similaire.

Associativite de l’addition. Soit ϕ(x, y, z) := x+ (y + z)=(x+ y) + z.Dans M, on a a+ (b+ 0) = a+ b = (a+ b) + 0 par (A4), ce qui montre que

M |= ∀x, y ϕ(x, y, 0).Si a, b, c ∈ M avec (a + b) + c = a + (b + c), alors on a a + (b + Sc) =

a + S(b + c) = S(a + (b + c)) = S((a + b) + c) = (a + b) + Sc par (A5), d’ouM |= ∀x, y (ϕ(x, y, z)→ ϕ(x, y, Sz)).

L’axiome d’induction associe a ϕ donne M |= ∀x, y, z ϕ(x, y, z).

Commutativite de l’addition. On montre les proprietes suivantes :(i) M |= ∀x 0 + x=x (par induction, en utilisant (A4) et (A5))(ii) M |= ∀x 1 + x=Sx (par induction, en utilisant (i) et (A5))(iii) M |= ∀x, y x+ y=y + x (par induction, en utilisant (i), (ii) et l’associa-

tivite de +)

Remarque. Cela montre que P suffit pour faire la theorie des nombres elemen-taire. P est une theorie incomplete (voir plus loin), mais il n’est pas facile detrouver un enonce mathematique independant de P. Le theoreme de Goodstein(TD no 2, exercice 6) en est un exemple.

Lemme 5.3.8 (Overspill). Soit M |= P non standard et ϕ = ϕ(x) une Lar-formule. Si M |= ϕ(n) pour tout n ∈ N, alors il existe c ∈ M non standard telque M |= ϕ[c].

74

Demonstration. Sinon, on aurait M |= ϕ(0) et M |= ∀x(ϕ(x) → ϕ(Sx)), car ϕn’est satisfaite que par les elements standards. Mais alors M |= ∀xϕ(x), ce quiest absurde car M contient des elements non standards par hypothese.

5.4 Les theoremes de Tarski et de Church

On considere une fonction primitive recursive subst ∈ F2 telle que si ϕ(v) estune Lar-formule a une variable libre v et n ∈ N, alors subst(#ϕ, n) = #ϕ(n).

Par le theoreme de representabilite, il existe une formule G(x, y, z) represen-tant subst et qui est Σ1. Pour ϕ = ϕ(v), on considere la formule

H(x) = ∃z (G(x, x, z) ∧ ϕ(z)) .

On pose n := #(¬H), puis ∆ϕ := ¬H(n).

Proposition 5.4.1 (L’argument diagonal). Soit ϕ = ϕ(v) une formule a unevariable libre. Alors

P0 ` ϕ(#∆ϕ)↔ ¬∆ϕ.

Demonstration. Comme subst(n, n) = subst(#(¬H), n) = #∆ϕ, pour tout mo-dele M |= P0, on a

M |= ∀z(G(n, n, z)↔ z=#∆ϕ

). (5.1)

Si M |= ϕ(#∆ϕ), alors M |= ∃z (G(n, n, z) ∧ ϕ(z))︸ ︷︷ ︸H(n)

par (5.1), et on a donc

M |= ¬∆ϕ par definition de ∆ϕ.

Reciproquement, si M |= ¬∆ϕ, alors M |= ∃z (G(n, n, z) ∧ ϕ(z)), et on adonc M |= ϕ(#∆ϕ) par (5.1).

Theoreme 5.4.2 (Theoreme de Tarski sur la non definissabilite de la verite).Soit M |= P0. Alors # Th(M) n’est pas definissable dans M, c’est-a-dire iln’existe pas de formule SM(x) a une variable libre telle que pour tout Lar-enonceϕ on ait M |= ϕ si et seulement si M |= SM(#ϕ).

Demonstration. Si S = SM est une telle formule, par l’argument diagonal onobtient P0 ` S(#∆S) ↔ ¬∆S . En particulier, on a M |= S(#∆S) ↔ ¬∆S , cequi est absurde, vu que S definit la satisfaction dans M.

Corollaire 5.4.3. Il n’existe pas de Lar-formule SN (x) telle que pour tout Lar-enonce ϕ on ait N |= ϕ si et seulement si N |= SN (#ϕ).

En particulier, Th(N ) n’est pas decidable.

Theoreme 5.4.4 (Theoreme de Church). Soit T ⊇ P0 une Lar-theorie consis-tante. Alors T n’est pas decidable.

75

Demonstration. Sinon, #Thm(T ) serait un ensemble recursif, et il existerait,par le theoreme de representabilite, une formule τ(x) representant #Thm(T ).

Si T ` ∆τ , c’est-a-dire si #∆τ ∈ #Thm(T ), on a P0 ` τ(#∆τ ) et doncP0 ` ¬∆τ par l’argument diagonal. Absurde.

Si T 6` ∆τ , c’est-a-dire si #∆τ 6∈ #Thm(T ), on a P0 ` ¬τ(#∆τ ) et doncP0 ` ∆τ par l’argument diagonal. Egalement absurde.

Corollaire 5.4.5 (Indecidabilite du calcul des predicats — Church). Il existe unlangage fini L tel que U = {#ϕ | ϕ est une L-formule universellement valide}n’est pas recursif.

Demonstration. Soit L = Lar. Supposons U recursif. Alors, comme ϕ est univer-sellement valide si et seulement si une cloture universelle de ϕ l’est, la Lar-theorievide est decidable. Comme P0 est une theorie finie, P0 serait donc egalementdecidable par l’exercice 5.2.6, contredisant le theoreme de Church.

[Voici l’argument pour le transfer de la decidabilite de la theorie vide a P0 :

On a ϕ ∈ Thm(P0) ssi P0 ` ϕ ssi `8∧i=1

Ai → ϕ︸ ︷︷ ︸ψϕ

ssi ψϕ ∈ Thm(∅).]

Remarque. Il suffit de considerer un langage L qui contient un seul symbolede relation binaire, c’est-a-dire Lens = {∈}, pour obtenir le resultat precedentde Church.

Par contre, les langages plus simples ne suffisent pas, comme le montrel’exercice suivant.

Exercice 5.4.6. Soit L = {P, c}, ou P est un predicat unaire et c une constante.

1. Determiner les L-structures finies et denombrables a isomorphisme pres.

2. En deduire : deux L-structures M et N sont elementairement equivalentessi et seulement si– M |= Pc ssi N |= Pc, et– M |= ∃≥kxQx ssi N |= ∃≥kxQx pour tout k ∈ N et tout Q ∈ {P,¬P}.

3. Montrer qu’un L-enonce ϕ est universellement valide ssi M |= ϕ pourtoute L-structure finie. En deduire que la L-theorie vide est decidable.

5.5 Les theoremes d’incompletude de Godel

Theoreme 5.5.1 (Premier theoreme d’incompletude de Godel). Soit T uneLar-theorie consistante, recursive et contenant P0. Alors T n’est pas complete.

Demonstration. Si T etait complete, elle serait decidable par 5.2.4, contredisantle theoreme de Church.

76

Dans la suite, nous gardons les hypotheses du theoreme 5.5.1, c’est-a-direT ⊇ P0 consistante et recursive. Il existe donc un enonce ψ tel que ni T ` ψ niT ` ¬ψ. Nous allons presenter une amelioration, due a Rosser, qui en fournitun exemple.

Rappel : Dem(T ) = {(#ϕ,##d) | d est une preuve formelle de ϕ dans T}est recursif. Par le theoreme de representabilite il existe une formule Σ1 PT (x, y)qui represente Dem(T ) ⊆ N2.

Soit Neg : N → N une fonction primitive recursive telle que Neg(#ϕ) =#(¬ϕ) et Neg(x) = 0 si x n’est pas le code d’une formule. On choisit une fomuleΣ1 ν(x, y) representant Neg, et on modifie PT en

PRT (x, y) := PT (x, y) ∧ ¬∃z ≤ y∃u(PT (u, z) ∧ ν(x, u)).

Considerons hRT (x) := ∃yPRT (x, y), puis ∆RT := ∆hRT

.

Theoreme 5.5.2 (Variante de Rosser du permier theoreme d’incompletude).Soit T ⊇ P0 consistante et recursive. Alors T 6` ∆R

T et T 6` ¬∆RT .

Demonstration. On pose ∆ := ∆RT et m := #∆. Par l’argument diagonal, on a

doncP0 `

(∃yPRT (m, y)↔ ¬∆

). (5.2)

Supposons T ` ∆. Alors il existe une preuve de ∆ dans T , autrement dit(m, p) ∈ Dem(T ) pour un p ∈ N, d’ou P0 ` PT (m, p). Comme T est consistante,pour tout p′ ∈ N on a P0 ` ¬∃u

(ν(m,u) ∧ PT (u, p′)

). Il suffit de noter que

P0 ` (x ≤ p ↔∨pi=0 x=i) pour deduire que P0 ` PRT (m, p). Par (5.2), on a

P0 ` ¬∆, d’ou T ` ¬∆ (car T ⊇ P0). Contradiction.

Supposons T ` ¬∆. Alors il existe p ∈ N tel que P0 ` PT (#¬∆, p). CommeT est consistante, pour tout p′ ∈ N on a P0 ` ¬PT (m, p′). Il s’en suit queP0 ` ¬∃yPRT (m, y), puisque N est un segment initial de tout modele de P0. Par(5.2), on a P0 ` ∆, donc T ` ∆. Contradiction.

Soient hT (x) := ∃yPT (x, y) et ∆T := ∆hT .

Lemme 5.5.3. Soit T ⊇ P0 consistante et recursive. Alors T 6` ∆T .

Demonstration. La preuve est similaire a celle de 5.5.2 et laissee en exercice.

Soit a := #(¬0=0) ∈ N. Pour T une theorie recursive (quelconque), on poseCoh(T ) := ¬∃yPT (a, y).

Remarque. On a N |= Coh(T ) si et seulement si T est une theorie consistante.

Theoreme 5.5.4 (Second theoreme d’incompletude de Godel — sans preuve).Soit T une theorie consistante recursive contenant l’arithmetique de Peano P.Alors T ∪ {Coh(T )} ` ∆T . En particulier, T 6` Coh(T ), c’est-a-dire T ne de-montre pas sa propre consistance.

77

Remarque 5.5.5. 1. Il suffit de demander que T contienne P0 plus tous lesaxiomes d’induction associes aux formules Σ1, pour obtenir la conclusiondu second theoreme d’incompletude.

2. Il s’en suit qu’il n’est pas exclus que T ` ¬Coh(T ). Ce sera le cas parexemple pour la theorie T ′ = T ∪ {¬Coh(T )} qui est consistante par letheoreme et qui ‘demontre’ sa propre inconsistance. Or, ce n’est pas cho-quant puisque N 6|= T ′. En effet, la ‘preuve’ de ¬0=0 en question provientd’un entier non standard.)Ce n’est pas le cas de P, puisque N |= P ∪ {Coh(P)}, plus generalementpour toute theorie recursive T dont N est un modele.

Idee de la preuve du second theoreme d’incompletude.La preuve complete est tres longue et compliquee. Nous nous contentons dedonner les etapes principales.

– On represente Dem(T ) et Dem(P0) par des formules PT (x, y) et PP0 demaniere naturelle, en demandant– ` PP0 → PT ;– `

(∃yPT (#ϕ, y) ∧ ∃yPT (#(ϕ→ ψ), y)

)→ ∃yPT (#ψ, y), de meme pour

∃-intro au lieu du modus ponens et pour PP0 au lieu de PT .– Nous avons vu dans la proposition 5.3.4 que pour tout enonce Σ1 ϕ, on aN |= ϕ→ ∃yPP0(#ϕ, y). On considere alors la theorie

P1 := P0 ∪ {ϕ→ ∃yPP0(#ϕ, y) | ϕ enonce Σ1}.

La theorie P1 est recursive, avec N |= P1.– On montre (cette etape n’est pas tres dificile) : Soit T consistante et re-

cursive avec T ` P1, c’est-a-dire T ` ψ pour tout ψ ∈ P1. Alors on aT ∪ {Coh(T )} ` ∆T , et donc en particulier, T 6` Coh(T ).

– On montre : P ` P1.C’est dans la preuve de cet enonce ou se trouve toute la difficulte. A la base,l’idee est tres simple. On montre P ` P1 ‘comme on a montre N |= P1’,en verifiant a chaque etape que l’on peut tout faire en ne raisonnant quedans l’arithmetique de Peano. Entre autre, il faut montrer une sorte detheoreme de completude dans Peano. Cela demande un travail considerablede codage.

78

Chapitre 6

Theorie axiomatique desensembles

Dans ce dernier chapitre du cours, nous formalisons la theorie des ensemblesa l’aide des outils que nous avons developpes, c’est-a-dire au premier ordre.Nous travaillons dans le langage L = Lens = {∈}, et nous considerons des Lens-structures U = 〈U ;∈〉 (U comme univers d’ensembles). Nous appelons ensembletout element de U . L’univers U , quant a lui, est un ensemble au sens naıf.L’appartenance entre deux ensembles est donnee par le symbole de relation ∈.

On peut alors former le langage LU (un ensemble au sens naıf).

Definition. Une partie naıve D de U est une classe s’il existe une LU -formuleϕ = ϕ(x) telle que D = ϕ[U ].

Notons que tout ensemble a definit une classe Ca, donnee par ϕ(x) := x ∈ a.Par l’axiome d’extensionalite, deux ensembles a et b sont egaux si Ca = Cb.

Par abus de notation, nous utilisons parfois ∈ pour designer l’appartenance(au sens naıf) a une classe, par exemple quand nous ecrivons c ∈ D au lieu deU |= ϕ[c], si D est definie par ϕ. Cela ne devrait pas creer de confusion.

6.1 Les axiomes de Zermelo-Fraenkel

Definition. 1. Le systeme d’axiomes de Zermelo-Fraenkel ZF est donne parles axiomes suivants : Axiome d’extensionalite, schema d’axiomes de com-prehension, axiome de la paire, axiome de la reunion, axiome des parties,schema d’axiomes de remplacement, axiome de fondation, axiome de l’in-fini.

2. Si on ajoute l’axiome du choix (AC) au systeme ZF, on on obtient lesysteme d’axiomes ZFC.

Remarque. L’axiome de fondation n’est pas toujours inclus dans ZF.

79

Dans ce qui suit, nous discutons les axiomes en detail.

Axiome d’extensionalite (Ext) ∀x, y (∀z(z ∈ x↔ z ∈ y)→ x=y)Il exprime que deux ensembles ayant les memes elements sont egaux.

Notation. Nous ecrivons x ⊆ y comme abbreviation de ∀z(z ∈ x→ z ∈ y).

Ainsi, (Ext) equivaut a ∀x, y ((x ⊆ y ∧ y ⊆ x)→ x=y).On observera que les cinq (schemas d’) axiomes suivants sont des cas parti-

culiers de la comprehension globale.

Schema d’axiomes de comprehension (Com)Pour toute Lens-formule ϕ = ϕ(v0, . . . , vn), un axiome de la forme

∀v1, . . . , vn+1∃vn+2∀v0 (v0 ∈ vn+2 ↔ (v0 ∈ vn+1 ∧ ϕ(v0, . . . , vn))) .

Il exprime : si a est un ensemble et D une classe, alors la classe {b ∈ a | b ∈ D}est un ensemble.

Voici quelques consequences de ces axiomes :– Si a et b sont deux ensembles, on peut former leur intersection a ∩ b ={c ∈ a | c ∈ b} ainsi que leur difference a \ b = {c ∈ a | c 6∈ b}.

– On obtient l’existence de l’ensemble vide, note ∅. En effet, soit a un en-semble arbitraire. Alors ∅ = {c ∈ a | ¬c=c}. L’unicite de ∅ suit de (Ext).

– Si a 6= ∅ est un ensemble, on obtient l’existence de⋂b∈a b. Il suffit de choisir

b0 ∈ a, puis de remarquer que⋂b∈a b = {c ∈ b0 | ∀x(x ∈ a→ c ∈ x)}.

Remarque 6.1.1. L’antinomie de Russel devient un theoreme dans ZFC. Eneffet, on a (Com) ` ¬∃x∀z z ∈ x. Sinon, {z | ¬z ∈ z} serait egalement unensemble, ce qui est absurde.

L’axiome de la paire (Paire) ∀y1, y2∃x∀z (z ∈ x↔ (z=y1 ∨ z=y2))Il exprime que si a et b sont deux ensembles, alors {a, b} est un ensemble.

Definition. La paire ordonnee (appelee aussi paire de Kuratowski) de deuxensembles a et b est l’ensemble (a, b) := {{a}, {a, b}}.

Lemme 6.1.2. Avec les axiomes que nous avons enonces jusqu’a maintenant,on a :

1. Il y a une formule qui definit la classe des paires ordonnees. De plus, ilexiste une Lens-formule ϕ(x, y) telle que l’on ait U |= ϕ[a, b] ssi a est unepaire de Kuratowski de la forme a = (b, c). Meme chose pour la deuxiemecomposante.

2. On a (b, c) = (b′, c′) si et seulement si b = b′ et c = c′.

Demonstration. Exercice.

80

L’axiome de la reunion (⋃

) ∀y∃x∀z (z ∈ x↔ ∃w(z ∈ w ∧ w ∈ y))Il exprime que pour tout ensemble a, la classe

⋃a := {z | ∃w(z ∈ w∧w ∈ a}

est un ensemble.Notons qu’en combinant (Paire) et (

⋃), on peut montrer que la reunion a∪b

de deux ensembles a et b est un ensemble.

L’axiome des parties (Parties) ∀y∃x∀z(z ∈ x↔ z ⊆ y)Il postule l’existence de l’ensemble des parties de a : P(a) = {b | b ⊆ a}.

Lemme 6.1.3. Les axiomes enonces jusqu’a maintenant entraınent l’existencedu produit cartesien de deux ensembles a et b : a × b = {(x, y) | x ∈ a ∧ y ∈ b}est un ensemble.

Demonstration. Si x ∈ a et y ∈ b, on a {x}, {x, y} ∈ P(a ∪ b), d’ou (x, y) ∈P(P(a ∪ b)). On conclut par (Com), en utilisant le lemme 6.1.2.

On peut egalement definir des triplets (x, y, z) := ((x, y), z), puis inductive-ment des n-uplets, via (x1, . . . , xn+1) := ((x1, . . . , xn), xn+1). On obtient alorsa× b× c, et plus generalement a1 × · · · × an.

Definition. – Une relation (binaire) R est un ensemble de paires ordonnees.On pose dom(R) := {x | ∃y(x, y) ∈ R} et im(R) := {y | ∃x(x, y) ∈ R}.

– Une fonction f est une relation qui est unique a droite, c’est-a-dire on a∀x, y1, y2 ((x, y1) ∈ f ∧ (x, y2) ∈ f → y1=y2).

Remarque. – On note que dom(R) et im(R) sont bien des ensembles, carsi (x, y) ∈ R, alors x, y ∈

⋃⋃R.

– Par definition, nous identifions une fonction avec son graphe.

On ecrira f(x) = y au lieu de (x, y) ∈ f . Parfois, pour x 6∈ dom(f), nousposons f(x) := ∅. Si a = dom(f) et im(f) ⊆ b, on ecrit f : a→ b.

Lemme 6.1.4. Soit a et b deux ensembles. Alors, avec les axiomes que nousavons enonces, on obtient :

1. {R | R est une relation avec dom(R) ⊆ a et im(f) ⊆ b} est un ensemble.2. {f | f : a→ b} est un ensemble.3. Les fonctions forment une classe. On note Fn(x) une formule qui definit

cette classe.

Demonstration. Exercice.

Remarque. Si I 6= ∅ est un ensemble et (ai)i∈I est une famille d’ensembles,c’est-a-dire donnee par une fonction f avec dom(f) = I, alors la classe

∏i∈I ai =

{g : I →⋃i∈I ai | ∀z(z ∈ I → g(z) ∈ z)} est un ensemble.

Definition. On dit que F ⊆ U2 est une classe fonctionnelle s’il existe uneLU -formule ϕ(x, y) qui definit F telle que

U |= ∀x, y1, y2 (ϕ(x, y1) ∧ ϕ(x, y2)→ y1=y2) .

La classe Dom(F ) definie par ∃yϕ est appelee le domaine de F .

81

Notons qu’a une classe fonctionnelle correspond une fonction naıve (dont laclasse fonctionnelle est le graphe et avec domaine la classe dom(F )).

Schema d’axiomes de remplacement (Rem)Pour toute Lens-formule ϕ = ϕ(x, y, v1, . . . , vn), un axiome de la forme

∀v0, v1, . . . , vn[∀x, y1, y2(ϕ(x, y1, v) ∧ ϕ(x, y2, v)→ y1=y2)→ ∃vn+1∀y(y ∈ vn+1 ↔ ∃x(x ∈ v0 ∧ ϕ(x, y, v))].

Il exprime que si F ⊆ U2 est une classe fonctionnelle et a un ensemble,alors F [a] := {z | ∃u(u ∈ a ∧ (u, z) ∈ F )} est un ensemble. (Il est obtenu en‘remplacant’ tout element de a par son image sous F .)

Ces axiomes ne sont pas independants. En effet :

Lemme 6.1.5. 1. Le schema (Rem) implique le schema (Com).2. (Paire) est une consequence des autres axiomes.

Demonstration. Soit ϕ(x) donnee. On pose F (x, y) := (x=y∧ϕ(x)). Alors {x ∈a | ϕ(x)} = F [a], d’ou (1).

Quant a (2), on se donne deux ensembles a et b. On remarque que ∅ ∈ P(∅) ={∅}, en particulier ∅ 6= P(∅). On pose F (x, y) := ((x=∅∧y=a)∨(x=P(∅)∧y=b)).C’est bien une relation fonctionnelle. Pour c = P(P(∅)) = {∅,P(∅)}, on a alorsF [c] = {a, b}.

Remarque. Nous pouvons travailler dans une expansion par definition et utili-ser par exemple des symboles de relation x ⊆ y (binaire) et f : x→ y (ternaire),des symboles de fonction x ∪ y, x ∩ y, x \ y,

⋃y, P(y), {x, y}, (x, y), x × y,

dom(R), im(R), la constante ∅ etc. dans les schemas d’axiomes (Com) et (Rem).Par la proposition 3.3.2, cela ne change rien.

Rappelons que x est un ordinal si x est un ensemble transitif tel que larelation d’appartenance ∈�x×x definit un bon ordre sur x, c’est-a-dire un ordretotal bien-fonde. (Cette derniere propriete se dit ainsi : ∀y(y ∈ P(x) ∧ ¬y=∅ →∃z(z ∈ y ∧ z ∩ y=∅)).) On note Ord(x) une formule qui definit la classe desordinaux. De meme, on peut definir la classe des cardinaux : Card(x) := Ord(x)∧∀y(y ∈ x→ ¬∃f : y → x surjective)

Notation. Dans la suite, nous utilisons α, β, γ etc. uniquement pour des ordi-naux, et nous ecrivons par exemple ∀γϕ au lieu de ∀γ(Ord(γ)→ ϕ).

L’axiome de fondation (AF) ∀x(¬x=∅ → ∃z(z ∈ x ∧ z ∩ x=∅))Notons que (AF), avec l’axiome de la paire, entraıne que pour tout ensemble

x on a x 6∈ x. En effet, sinon {x} contredirait (AF).

L’axiome de l’infini (AI) ∃x(∅ ∈ x ∧ ∀z(z ∈ x→ z ∪ {z} ∈ x))Il postule l’existence d’un ensemble contenant ∅ et clos par ‘successeur’. De

maniere equivalente, on pourrait postuler l’existence d’un ordinal infini (ou deω).

On note ω le plus petit ordinal limite, et Lim(x) une formule qui definit laclasse des ordinaux limites.

82

Remarque 6.1.6. 1. Sous ZF, les ordinaux verifient les memes proprietesque celles vues au premier chapitre du cours. De meme les cardinaux, sousZFC.

2. La classe des ordinaux n’est pas un ensemble (pareil pour les cardinaux).[Si a = Ord, alors a serait transitif et bien-ordonne par ∈, donc un ordinalet alors a ∈ a. Or a 6∈ a pour tout ordinal.]

Lemme 6.1.7 (Induction transfinie). Soit U |= ZF et soit ϕ(x) une LU -formule.Alors U satisfait la propriete d’induction suivante :

ϕ(∅)∧∀γ(ϕ(γ)→ ϕ(γ∪{γ})∧∀γ([Lim(γ)∧∀δ(δ ∈ γ → ϕ(δ))]→ ϕ(γ))→ ∀γϕ(γ).

Demonstration. Si U |= ϕ(∅) ∧ ∀γ(ϕ(γ) → ϕ(γ ∪ {γ}) ∧ ∀γ([Lim(γ) ∧ ∀δ(δ ∈γ → ϕ(δ))] → ϕ(γ)) et U |= ¬ϕ[α] pour un ordinal α, il suffit de choisir un telα minimal pour arriver a une contradiction.

On peut egalement considerer des classes fonctionnelles F qui correspondenta des fonctions naıves entre une classe D ⊆ Un et U .

Theoreme 6.1.8 (Definition par recurrence transfinie). Soit G une classe fonc-tionnelle de domaine Un+1. Alors il existe une unique classe fonctionnelle F dedomaine Un ×Ord telle que pour tout uplet d’ensembles w et tout ordinal α onait F (w,α) = G(w,F �{w}×α).

Demonstration. L’idee est d’approximer F par des fonctions. On montre d’abordque pour tout w et tout ordinal β il existe une unique fonction fw,β de domaineβ telle que

fw,β(α) = G(w, {w} × fw,β �α) pour tout α < β.

L’unicite est claire par induction (transfinie).Quant a l’existence, on montrera par induction sur β :

∀w∃fw,β fonction de domaine β : ∀α (α < β → fw,β(α)=G(w, {w} × fw,β �α))︸ ︷︷ ︸(∗)w,β

Si β = 0, on pose fw,β = ∅.

Soit β = β′ + 1 et fw,β′ une fonction satisfaisant a (∗)w,β′ .On pose fw,β = fw,β′ ∪ {(β′, G(w, {w} × fw,β′)}.

Soit β un ordinal limite. On considere l’ensemble suivant :Xw,β := {f | ∃β′ < β : f est une fonction satisfaisant (∗)w,β′ t.q. dom(f) = β′}.Par (Rem) et unicite, Xw,β est un ensemble. Egalement par unicite,

⋃f ′∈Xw,β f

′

est donc une fonction qui convient.

On pose (w, β, y) ∈ F :⇔ pour toute fonction f de domaine β+1 satisfaisanta (∗)w,β+1 on a f(β) = y.

Exemples 6.1.9 (Applications de la definition par recurrence transfinie).

83

1. Les fonctions de l’arithmetique ordinale (addition, multiplication et expo-nentiation ordinale) peuvent se definir par recurrence (voir la remarque1.5.7).

2. La hierarchie des ℵ est donnee par une classe fonctionnelle ℵ : Ord →Card. En effet, il suffit d’appliquer la recurrence transfinie a la classefonctionnelle G : U → U definie comme suit :– G(0) = ω ;– si f : α→ β pour deux ordinaux α, β, alors

G(f) =

{le plus petit cardinal > f(α′), si α = α′ + 1;⋃

im(f), si dom(f) est un ordinal limite.

– si x n’est pas une fonction entre deux ordinaux, alors G(x) = ∅.3. La hierarchie de von Neumann : par recurrence sur α ∈ Ord, on definit

une classe fonctionnelle α 7→ Vα via– V0 = ∅ ;– Vα+1 = P(Vα) ;– Vλ =

⋃α<λ Vα pour λ limite.

Proposition 6.1.10 (ZF − (AF)). L’ordinal ω muni des operations ordinales(addition, multiplication et successeur), avec 0 = ∅ et < donne par ∈ est unmodele de P.

Demonstration. Exercice.

6.2 Axiome du choix

L’axiome du choix (AC)

∀f [(Fn(f) ∧ ∅ 6∈ im(f))→ ∃g (Fn(g) ∧ dom(g)=dom(f) ∧ ∀x(x ∈ dom(g)→ g(x) ∈ f(x)))]

Il exprime que le produit d’une famille d’ensembles non vides est non vide.

Definition. Soit a un ensemble. On appelle fonction de choix sur a une fonctionh : P(a)′ := P(a) \ {∅} → a telle que h(A) ∈ A pour tout A ∈ P(a)′.

Proposition 6.2.1. (AC) est equivalent a l’existence d’une fonction de choixpour tout ensemble a.

Demonstration. Supposons (AC) et soit a un ensemble. Par l’axiome du choix,∏A∈P(a)′ A 6= ∅. Tout element de ce produit est une fonction de choix sur a.Reciproquement, soit (ai)i∈I une famille d’ensembles avec ai 6= ∅ pour tout

i ∈ I. Soit a =⋃i∈I ai et h : P(a)′ → a une fonction de choix sur a. Alors

h ◦ f ∈∏i∈I ai, ou f : I → P(a)′, f(i) := ai.

Theoreme 6.2.2. Dans ZF, son equivalents :

84

1. (AC) ;

2. le lemme de Zorn ;

3. le theoreme de Zermelo (Wohlordnungssatz).

Demonstration. (1)⇒(2) : Par l’absurde. Soit donc 〈X,<〉 un ordre partiel in-ductif sans element maximal. On considere l’ensemble

T = {T ∈ P(X) | T est totalement ordonne par <}.

Comme il n’existe pas d’element maximal dans X, pour tout T ∈ T , l’ensembleB(T ) := {x ∈ X | x > t ∀t ∈ T} est non vide. Par (AC), il existe une fonctionb : T → X telle que b(T ) ∈ B(T ) pour tout T ∈ T .

Soit G la classe fonctionnelle suivante :– si g est une fonction avec dom(g) ∈ Ord et im(g) ∈ T , alors G(g) =b(im(g)) ;

– G(g) = ∅ sinon.Par le theoreme 6.1.8 il existe une classe fonctionnelle F de domanie la

classe des ordinaux telle que F (α) = G(F � α) pour tout ordinal α. On verifiepar induction que F (α) ∈ X pour tout α et

α < β ⇒ F (α) < F (β). (6.1)

Par comprehension, OX := {x ∈ X | il existe un ordinal α tel que (α, x) ∈ F}est un ensemble.

En tant que fonction naıve, F est injective par (6.1). La classe F−1 definie par(x, α) ∈ F−1 :⇔ (α, x) ∈ F est donc une classe fonctionnelle. On a F−1[OX ] =Ord, et Ord est un ensemble par remplacement. Ceci contredit la remarque6.1.6(2).

(2)⇒(3) : Soit a un ensemble. Il faut montrer que a admet un bon ordre. Onconsidere X := {(b, R) | b ∈ P(a) et R est un bon ordre sur b}. Il est facile avoir que X est un ensemble (exercice).

Sur X, on definit un ordre partiel comme suit :

(b, R) ≤ (b′, R′) :⇔ b est un segment initial de (b′, R′) et R′ � b = R}.

Cet ordre est inductif. En effet, si (bi, Ri)i∈I est une partie totalement ordonneede X, alors (b, R) := (

⋃i∈I bi,

⋃i∈I Ri) est un majorant de cette partie. Par le

lemme de Zorn, il existe un element (b, R) ∈ X qui est maximal pour ≤. Sib 6= a, il existe y ∈ a \ b. On pose b′ = b ∪ {y} et R′ := R ∪ {(x, y) | x ∈ b}.Il est alors clair que R′ est un bon ordre sur b′ qui prolonge celui sur b, ce quicontredit la maximalite de (b, R).

(3)⇒(1) : Soit a un ensemble. Par hypothese, a peut etre bien-ordonne, disonspar <. La fonction f : P(a)′ → a qui a une partie non vide de a associe sonplus petit element est une fonction de choix sur a. On conclut par la proposition6.2.1.

85

Remarque 6.2.3 (Paradoxe de Skolem). Si ZFC est consistante, elle a unmodele (necesairement infini, vu les axiomes). Comme Lens est denombrable,ZFC a donc un modele denombrable M par le theoreme de Lowenheim-Skolemdescendant. Mais il existe des ensembles non-denombrables dans M, par exempleℵ1 ou R.Explication : La notion de ‘denombrabilite’ depend du modele de ZFC dans lequelon travaille. Elle est donc relative. Etre denombrable au sens de M et l’etre ausens du modele de la theorie des ensembles (naıf) de fond n’est pas la memechose. Qui plus est, l’ensemble de base M de M est un un ensemble du point devue naıf, et une classe propre du point de vue de M.

Plus generalement, la notion de cardinalite depend du modele. Ainsi, l’en-semble des entiers N (au sens de M) et l’ensemble des reels R (au sens de M)sont tous les deux denombrables d’un point de vue du modele de fond. Or, labijection entre les deux ensembles qui existe comme ensemble naıf n’est memepas represente par une classe dans M. En effet, sinon, par remplacement, elleserait donnee par un ensemble au sens de M, c’est-a-dire par un element de M .

6.3 La hierarchie de von Neumann et l’axiomede fondation

On note ZF− := ZF − (AF) et ZFC− := ZFC − (AF). Dans cette partie,nous supposons que U |= ZF−.

Definition. Soit a un ensemble. Par recurrence sur n ∈ ω, on definit a0 := a,an+1 := an ∪

⋃an. Puis, on pose ct(a) :=

⋃n∈ω an, appelee la cloture transitive

de a.

Lemme 6.3.1 (ZF−). L’ensemble ct(a) est le plus petit ensemble transitif conte-nant a comme partie. Plus precisement, on a les proprietes suivantes :

1. a ⊆ ct(a)

2. ct(a) est un ensemble transitif.

3. Si a ⊆ t avec t un ensemble transitif, alors ct(a) ⊆ t. En particulier,a ⊆ b⇒ ct(a) ⊆ ct(b).

4. Si a est transitif, alors ct(a) = a.

5. Si b ∈ a, alors ct(b) ⊆ ct(a).

6. ct(a) = a ∪⋃b∈a ct(b).

Demonstration. (1) et (2) sont clairs. Quant a (3), on montre par induction quean ⊆ t pour tout n ∈ ω. (4) est une consequence de (1-3)Preuve de (5) : On a b ∈ a ⇒ b ∈ ct(a) ⇒ b ⊆ ct(a) ⇒ ct(b) ⊆ ct(a). (Lapremiere implication suit de (1), la seconde de (2), et la derniere de (3).)Preuve de (6) : On a ct(a) ⊇ a∪

⋃b∈a ct(b) par (1) et (5). Pour l’autre inclusion,

par (3), il suffit de montrer que a ∪⋃b∈a ct(b) est transitif, ce qui est clair.

86

Rappelons la hierarchie de von Neumann : V0 := ∅, Vα+1 := P(Vα), Vλ :=⋃α<λ Vα (pour λ limite).

On definit la classe V par la formule ∃αx ∈ Vα. Informellement, on a donc“V =

⋃α∈Ord Vα”.

Definition. Soit a un ensemble. On pose

Rg(a) :=

{le plus petit ordinal γ tel que a ∈ Vγ+1, si un tel γ existe;∞, sinon.

On l’appelle le rang de a.

Lemme 6.3.2. 1. Vα est un ensemble transitif pour tout ordinal α.

2. β ≤ α⇒ Vβ ⊆ Vα3. Vα = {x ∈ V | Rg(x) < α}4. Si x ∈ V et y ∈ x, alors y ∈ V et Rg(y) < Rg(x).

5. Si x ∈ V , alors Rg(x) = sup{Rg(y) + 1 | y ∈ x}.6. Si x ∈ V est transitif, alors {Rg(y) | y ∈ x} est un ordinal α.

7. On a Rg(α) = α pour tout α. En particulier, α ∈ V et Vα ∩Ord = α.

8. Soit x un ensemble. Alors x ∈ V si et seulement si x ⊆ V .

9. On suppose (AC). Si x ∈ V est transitif, on a x ∈ Vcard(x)+ .

Demonstration. (1) & (2) Par induction transfinie sur α, on montre que Vαest transtif et que Vβ ⊆ Vα pour tout β ≤ α. Les cas α = 0 et α limite sontclairs. Soit donc α = γ + 1. Comme Vγ est transitif par hypothese d’induction,P(Vγ) = Vα est transitif aussi. Si β < α, alors β ≤ γ et inductiviement Vβ ⊆ Vγ ,d’ou Vβ ∈ Vα et enfin Vβ ⊆ Vα par transitivite.

(3) Si x ∈ V , on a Rg(x) < α ssi ∃β < α : x ∈ Vβ+1 ssi x ∈ Vα.

(4) Soit α = Rg(x). Alors x ∈ Vα+1 = P(Vα). Pour y ∈ x, on obtient y ∈ Vα,d’ou y ∈ V et Rg(y) < α (par (3)).

(5) Si x ∈ V , on pose α = sup{Rg(y) + 1 | y ∈ x}. Par (4), on a α ≤ Rg(x).Comme Rg(y) < α pour tout y ∈ x, (3) entraıne que x ⊆ Vα, d’ou x ∈ Vα+1 etalors α ≥ Rg(x) par definition.

(6) Soit x ∈ V transitif et β < Rg(x) donne. Par (5) il existe y ∈ x avecβ ≤ Rg(y). On choisit un tel y avec Rg(y) minimal. Si z ∈ y, on a z ∈ x (partransitivite de x) et Rg(z) < Rg(y) par (4), d’ou Rg(z) < β par minimalite deRg(y). Cela montre que y ⊆ Vβ et alors y ∈ Vβ+1, d’ou Rg(y) ≤ β.

(7) On demontre α ∈ V et Rg(α) = α par induction transfinie, le cas α = 0 etantclair. Supposons le resultat vrai pour tout β < α. Alors β ∈ Vβ+1 ⊆ Vα pourtout β < α, d’ou α ⊆ Vα et donc α ∈ Vα+1. Par (5), on a Rg(α) = sup{β + 1 |β < α} = α.

87

(8) x ∈ V ⇒ x ⊆ V est une consequence de (4). Reciproquement, si x estun ensemble tel que x ⊆ V , alors {Rg(y) + 1 | y ∈ x} est un ensemble parremplacement. Pour α = sup{Rg(y) + 1 | y ∈ x} on a donc x ⊆ Vα et enfinx ∈ Vα+1.

(9) est une consequence de (6).

Theoreme 6.3.3. Soit U |= ZF− = ZF− (AF). Sont equivalents :

1. U |= (AF)

2. U |= ∀xV (x)

Demonstration. (2)⇒(1) : Soit x un ensemble non vide. Il faut trouver un ele-ment y de x tel que y ∩ x = ∅. Par hypothese, tout ensemble est dans V . Onchoisit y ∈ x avec Rg(y) minimal. Alors y ∩ x = ∅ par le lemme 6.3.2(4).

(1)⇒(2) : Soit x un ensemble donne. On pose y := ct(x), et on considere l’en-semble z := {t ∈ y | t 6∈ V }. On a x ⊆ y. Par 6.3.2(8), pour montrer quex ∈ V , il suffit donc de montrer que tout element de y est dans V , autrementdit que z = ∅. Si z n’etait pas vide, par (AF) il existerait t ∈ z avec t ∩ z = ∅.Considerons un tel t. Pour u ∈ t, on a u ∈ y (car y est transitif) et donc u ∈ V(car t ∩ z = ∅). Mais alors t ∈ V par 6.3.2(8). Contradiction.

Remarque. Comme les elements de V sont construits a partir de l’ensemblevide (par un procede transfini), le theoreme 6.3.3 exprime que (AF) est equi-valent au fait que tout ensemble est construit a partir de l’ensemble vide.

Remarque 6.3.4. Dans ZFC−, sont equivalents :

1. (AF)

2. Il n’existe pas de suite (ai)i∈ω telle que ai+1 ∈ ai pour tout i ∈ ω.

Demonstration. (1)⇒(2) : (Cette implication n’utilise pas (AC).) Si (ai)i∈ω estune suite d’ensembles, on considere a = {ai | i ∈ ω}. Par (AF), il existe b ∈ a telque b∩ a = ∅. Donc pour un n ∈ ω on a an ∩ a = ∅, et en particulier an+1 6∈ an.

(2)⇒(1) : Soit a 6= ∅ un ensemble qui contredit (AF). Pour tout b ∈ a on a doncb∩ a 6= ∅. Par (AC) il existe une fonction f : a→ a telle que f(b) ∈ b pour toutb ∈ a. On choisit a0 ∈ a, puis on definit par recurrence sur ω une suite (ai)i∈ω,en posant ai+1 = f(ai).

Lemme 6.3.5. 1. Si x ∈ V , alors⋃x,P(x) et {x} sont dans V . Ce sont

des ensembles de rang plus petit que Rg(x) + ω.

2. Si x, y ∈ V , alors x× y, x∪ y, x∩ y, {x, y}, (x, y) et xy sont dans V aussi.De plus, le rang de ces ensembles est plus petit que max{Rg(x),Rg(y)}+ω.

Demonstration. Exercice.

Exercice 6.3.6. On travaille dans U |= ZF−, et on suppose que les ensemblesN,Z, . . . sont definis de maniere usuelle.

88

1. Montrer que les ensembles N,Z,R,C, C0([0, 1],C) sont dans Vω·2.

2. Calculer les rangs des ensembles mentionnes dans (1).

Remarque. Comme l’axiome d’extensionalite (qui dit en quelque sorte qu’il n’ya que des ensembles), l’axiome de fondation restreint l’univers des ensembles al’endroit ou les mathematiques usuelles ont lieu :

– Nous avons deja vu dans l’exercice precedent que des objets mathematiquesusuels sont dans V .

– Si on travaille dans ZFC−, toute structure (du premier ordre) a une copieisomorphe dans V . (Supposons σL fini pour simplifier la presentation.)En effet, soit M = 〈M ;Ri, cj , fk〉 une L-structure donnee et g : M ∼=card(M) = κ une bijection. Il existe une unique L-structure N avec en-semble de base κ telle que g soit un L-isomorphisme entre M et N. On aκ ∈ Vκ+1, puis N ∈ Vκ+ω par le lemme 6.3.5.

– En dehors des structures du premier ordre, cela reste vrai. Prenons parexemple le cas d’un espace topologique (X, T ) avec X un ensemble et T ⊆P(X) l’ensemble des ouverts de X. Alors si g : X ∼= κ est une bijection,on peut raisonner comme avant.

6.4 Quelques resultats d’incompletude, d’inde-pendance et de consistance relative

Dans cette derniere partie du chapitre sur la theorie des ensembles, noussupposons codees les formules ainsi que les preuves dans la theorie ZF−. Pourcela, on pourra par exemple se servir du codage que nous avons donne dansl’arithmetique et utiliser que si U |= ZF− et ω ∈ U , alors 〈ω; 0,+, ·, succ,∈�ω〉 |=P (voir 6.1.10). Nous continuons a ecrire #ϕ pour le code de la formule ϕ.

Les resultats d’incompletude de Godel ont alors leurs analogues en theoriedes ensembles (avec une preuve un peu plus simple). Notons que ZF−, ZF, ZFC−

et ZFC sont des theories recursives.

Theoreme 6.4.1 (Premier theoreme d’incompletude de Godel). Soit T ⊇ ZF−

une Lens-theorie recursive et consistante. Alors T est incomplete.

Remarque. Nous allons voir (sans preuve) que si ZF est consistante, alorsZF 6` (AC) et ZF 6` ¬(AC). De meme, ZFC 6` (CH) et ZFC 6` ¬(CH). Dansles deux cas, il s’agit de proprietes avec un sens mathematique. Contrairement acela, dans le cas de l’arithmetique, il fallait chercher loin pour trouver un enonceindependant de P.

Theoreme 6.4.2 (Second theoreme d’incompletude de Godel). Si T ⊇ ZF−

est une Lens-theorie recursive et consistante, alors T 6` Coh(T ).

On se place dans un modele U de ZF−. On peut alors coder la satisfactiondans U . Soit L un langage fini et A = 〈A; (ZA)Z∈σL〉 une L-structure avec A ∈ U .On identifie l’ensemble des affectations a valeur dans A a Aω, un element de U .

89

Le lemme suivant s’obtient par induction sur la hauteur d’une formule, ce quirevient a une induction sur ω. Les details sont laisses en exercice.

Lemme 6.4.3. Il existe une fonction dans U qui a (#ϕ, α) associe 1 si A |=ϕ[α], et 0 sinon.

En particulier, # Th(A) = {#ϕ | ϕ est un L-enonce tel que A |= ϕ} estdonne par un element de U .

Un theoreme de consistance relative a la forme suivante : etant donnees deuxtheories T1 et T2, alors, si T1 est consistante, T2 est consistante aussi. Le principede preuve sera de construire un modele de T2 a partir d’un modele de T1.

Commencons par un resultat qui etablit une relation entre la theorie desensembles et l’arithmetique. On verifie sans probleme que la preuve de la pro-position 6.1.10 se fait dans ZF−. Vu que ω est un ensemble, on peut deduire dulemme 6.4.3 le resultat suivant.

Proposition 6.4.4. On a ZF− ` Coh(P). En particulier, si ZF− est consis-tante, l’arithmetique de Peano P est consistante aussi.

Soit U |= ZF−. Si X est une classe non vide contenue dans U , on peutconsiderer la Lens-structure 〈X;∈�X〉.

Dans les preuves des resultats de consistance relative en theorie des ensemblesque nous allons donner, nous construisons des classes X telles que si U |= T1,alors 〈X;∈�X〉 |= T2, d’ou le resultat de consistance relative voulu.

Notation. On ecrira parfois X |= ϕ au lieu de 〈X;∈�X〉 |= ϕ.

Definition (Relativisation). Soit F (v0) une Lens-formule. Pour toute formuleϕ on definit, par induction sur ht(ϕ), une formule ϕF , la relativisee de ϕ a F :

– ϕF = ϕ si ϕ est atomique ;– (ϕ ∧ ψ)F = (ϕF ∧ ψF ) et (¬ϕ)F = ¬(ϕF ) ;– (∃xϕ)F = ∃x(F (x) ∧ ϕF )

Proposition 6.4.5. 1. Soit U |= ZF− et X ⊆ U une classe. On suppose queX = F [U ] = G[U ], c’est-a-dire que F (v0) et G(v0) definissent X. Alorspour toute formule ϕ, les formules ϕF et ϕG sont equivalentes dans U . Onpourra donc ecrire ϕX au lieu de ϕF , si on ne s’interesse qu’a la formulea equivalence pres.

2. Pour tout a1, . . . , an ∈ X et toute formule ϕ = ϕ(x1, . . . , xn), on a l’equi-valence suivante : U |= ϕX [a] ssi 〈X;∈�X〉 |= ϕ[a]

Demonstration. (1) Preuve par induction sur ht(ϕ) (exercice).

(2) Preuve par induction sur ht(ϕ). Seul le cas ϕ = ∃x0ψ est non trivial. On aU |= ϕX [a1, . . . , an] ssi U |= ∃x0(F (x0) ∧ ψX)[a1, . . . , an] ssi il existe b ∈ U telque U |= F [b] et U |= ψX [b, a] ssi il existe b ∈ X tel que U |= ψX [b, a] ssi il existeb ∈ X tel que X |= ψ[b, a] ssi X |= ϕ[a].

Definition. Soit X une classe definie par F (v0). Une formule ϕ(x1, . . . , xn) estdite absolue pour X si U |= ∀x1, . . . , xn

(∧ni=1 F (xi)→ (ϕ↔ ϕX)

).

90

Definition. L’ensemble des Lens-formules ∆0 est le plus petit ensemble deformules qui contient les formules atomiques et qui est clos par combinaisonsbooleennes et quantification bornee (si ϕ est ∆0, alors ∃x(x ∈ y ∧ ϕ) et ∀x(x ∈y → ϕ) sont des formules ∆0 aussi).

Lemme 6.4.6. 1. Si X est une classe transitive (c’est-a-dire z ∈ y ∈ X ⇒z ∈ X), alors toute formule ∆0 est absolue pour X.

2. Les proprietes suivantes s’expriment par des formules ∆0 : x ⊆ y, x = ∅,x = y ∪ {y}, ‘x est transitif ’, z = {x, y}, y =

⋃x

Demonstration. (1) Les formules atomiques sont absolues pour toute classe nonvide. De plus, pour toute classe X, l’ensemble des formules absolues est clos parcombinaisons booleennes. Montrons que si X est une classe transitive non videet si ϕ(x, y, v1, . . . , vn) est absolue pour X, alors la formule ∃x(x ∈ y ∧ ϕ) estabsolue pour X aussi. Pour b, c1, . . . , cn ∈ X, on a les equivalences suivantes :

U |= (∃x(x ∈ y ∧ ϕ))X [b, c]

(par definition) ⇐⇒ U |=(∃x(F (x) ∧ x ∈ y ∧ ϕX)

)[b, c]

⇐⇒ il existe a ∈ X ∩ b tel que U |= ϕX [a, b, c]

(hypothese d’induction) ⇐⇒ il existe a ∈ X ∩ b tel que U |= ϕ[a, b, c]

(par transitivite de X) ⇐⇒ il existe a ∈ b tel que U |= ϕ[a, b, c]

⇐⇒ U |= (∃x(x ∈ y ∧ ϕ)) [b, c]

La preuve de (2) est facile. Par exemple, la transitivite de x est exprimeepar la formule ∆0 suivante : ∀y (y ∈ x→ ∀z(z ∈ y → z ∈ x)) .

Lemme 6.4.7. On se place dans U |= ZF−.1. Si X est une classe transitive non vide, elle satisfait (Ext).2. Vα |= (

⋃) pour tout ordinal α > 0. De meme, V |= (

⋃).

3. Si λ est un ordinal limite, alors Vλ |= (Paire). De meme, V |= (Paire).4. Si ∅ 6= X est transitive telle que U |= ∀x ∈ X∃y ∈ X(P(x)∩X = y), alors

X |= (Parties). En particulier, Vλ |= (Parties) pour tout ordinal limiteλ, et V |= (Parties). De plus, y = P(x) est absolue dans ces deux cas.

Demonstration. (1) L’enonce ∀y ∈ X∀z ∈ X ([∀x ∈ X(x ∈ y ↔ x ∈ z]→ y=z)exprime (Ext)X . Comme X est transitive, si y, z ∈ X, alors y, z ⊆ X, donc(Ext)X est satisfait dans U .

(2) Commencons par une remarque generale : Si G(x, y) definit une classe fonc-tionnelle (dans U) de domaine U telle que G(x, y) soit une formule absolue pourX, alors, pour montrer X |= ∀x∃!yG(x, y), il suffit de montrer que si a ∈ X,alors l’unique b ∈ U tel que U |= G(a, b) est egalement dans X.

Comme y =⋃x est une formule ∆0 par le lemme 6.4.6, il suffit donc de

montrer que si x ∈ Vα, alors⋃x ∈ Vα, ce qui est clair. En effet, on a les

implications suivantes :

91

x ∈ Vα ⇒ Rg(x) = β < α ⇒ Rg(y) < β pour tout y ∈ x′ ∈ x⇒

⋃x ⊆ Vβ ⇒

⋃x ∈ Vβ+1 ⊆ Vα

Le meme argument donne le resultat pour V .

(3) x, y ∈ Vα ⇒ {x, y} ∈ Vα+1, en particulier x, y ∈ Vλ ⇒ {x, y} ∈ Vλ pourλ limite. Comme la formule z = {x, y} est ∆0, par la remarque generale on aVλ |= (Paire). De meme pour V au lieu de Vλ.

(4) On a U |= ∀x ∈ X ∃y ∈ X(P(x)∩X=y) si et seulement si U |= ∀x ∈ X ∃y ∈X ∀z ∈ X(z ⊆ x↔ z ∈ y). Ce dernier enonce est juste (Parties)X , compte tenudu fait que z ⊆ x est absolue pour X par transitivite de X.

Soit maintenant x ∈ Vα. On a alors P(x) ⊆ Vα et donc P(x) ∈ Vα+1.On obtient donc le resultat pour Vλ et pour V . L’absoluite de y = P(x) estclaire.

Lemme 6.4.8. Les formules Ord(x) et Card(x) sont absolues pour V ainsi quepour Vλ si λ est un ordinal limite.

Demonstration. Commencons par Ord(x). La transitivite de x ainsi que le faitque ∈� x definisse un ordre total s’expriment par des formules ∆0 et sont doncabsolues. Quant a la bonne fondation, on utilise l’absoluite de y = P(x) pourmontrer que la formule suivante est absolue aussi :

∀z (z ∈ P(x) ∧ z 6= ∅ → ∃u(u ∈ z ∧ ∀w(w ∈ z → w 6∈ u)))

La formule Ord(x) ∧ ∀y(y ∈ x → ¬∃f ∈ P(x× y) f : x ∼= y) est equivalentea Card(x). On montre que les formules f : x ∼= y (en les trois variables f, x, y)ainsi que z = x× y sont absolues pour V ainsi que pour Vλ si λ est un ordinallimite (exercice). Cela etablit l’absoluite de Card(x) dans les deux cas.

Definition. On se place dans ZF−.– Un cardinal λ est appele fortement limite si pour tout µ < λ on a 2µ < λ.– On dit que λ est (fortement) inaccessible s’il est fortement limite, regulier

et > ℵ0.

Exemple. On definit, par recurrence sur α ∈ Ord, une hierarche cardinalecomme suit : i0 := ℵ0, iα+1 := 2iα , et iλ := supα<λ iα pour λ limite.

Pour tout ordinal α limite, le cardinal iα est alors fortement limite. Parcontre, comme cof(iα) = cof(α) dans ce cas, iα est en general singulier.

Lemme 6.4.9. Soit U |= ZF−, et soit , X = V ou X = Vω, ou X = Vκ pour κinaccessible. Dans le dernier cas, on suppose de plus que U |= (AC).

Alors X satisfait au schema d’axiomes de remplacement ainsi qu’a l’axiomede fondation.

Demonstration. On choisit une formule F (x) qui definit X. Soit G(v0, v1) uneformule qui definit une classe fonctionnelle dans 〈X,∈� X〉. Alors la formuleH(v0, v1) = F (v0) ∧ F (v1) ∧ GF definit une classe fonctionnelle dans U . Soitb := H[a] = {H(c) | c ∈ a}, ou a est un element de X.

92

– Si X = V , alors b ∈ V car b ⊆ V et b est un ensemble.– Si X = Vω, alors, comme a est fini, b est fini et une partie de Vω, d’oub ⊆ Vn pour un n ∈ ω et enfin b ∈ Vω.

– Si X = Vκ pour κ inaccessible, essentiellement le meme argument marche.On montre par induction sur α que card(Vα) < κ pour tout α < κ.(Comme on suppose U |= (AC), on peut se servir de la notion de cardinal.)Pour α successeur, on utilise que κ est fortement limite ; pour α limite, onutilise la regularite de κ.Maintenant, si a ∈ Vκ, on a a ∈ Vα pour un α < κ et alors a ⊆ Vα+1.Il s’en suit que card(b) ≤ card(a) < κ. Par ailleurs, on a b ⊆ Vκ. Parregularite de κ, on obtient sup{Rg(c) | c ∈ b} < κ et enfin b ∈ Vκ.

Cela montre le schema d’axiomes de remplacement dans les trois cas.

Quant a (AF), on se donne ∅ 6= a ∈ X. On a a ⊆ X dans les trois cas, carX est transitive. Pour tout b ∈ a de rang minimal on a a∩ b = ∅, et un tel b estdans X.

Lemme 6.4.10. On a V |= (AI), Vκ |= (AI) pour κ inaccessible et Vω |= ¬(AI).

Demonstration. On a ω ∈ V , ω ∈ Vκ et ω 6∈ Vω. Les details sont laisses enexercice.

Lemme 6.4.11. Si U |= ZFC−, alors V |= (AC) et Vκ |= (AC), pour κ inac-cessible.

Demonstration. Soit (Xi)i∈I un element de Vκ. Alors I ∈ Vκ et tout elementg ∈

∏i∈I Xi est dans Vκ. Pour V , on conclut par le meme argument.

Theoreme 6.4.12 (Consistance relative de (AF)).

1. Si U |= ZF−, alors V |= ZF. En particulier, on a Coh(ZF−)⇒ Coh(ZF).

2. Si U |= ZFC−, alors V |= ZFC. En particulier, on a Coh(ZFC−) ⇒Coh(ZFC).

Demonstration. Il suffit de combiner les lemmes precedents. (Rappelons que leschema (Rem) implique le schema (Com), voir 6.1.5.)

Theoreme 6.4.13. Si U |= ZF−, alors Vω |= ZF−(AI)+¬(AI). En particulier,ZF− ` Coh(ZFC− (AI) + ¬(AI)).

Demonstration. Nous avons tout demontre dans les lemmes sauf Vω |= (AC). Ilsuffit de remarquer que tout element de Vω est un ensemble fini et admet doncun bon ordre, c’est-a-dire qu’il existe une bijection avec un element de ω. Unetelle bijection est dans Vω.

Axiome des cardinaux inaccessibles (CI) : Il existe un cardinal inaccessible.

Theoreme 6.4.14. Soit U |= ZFC− et κ ∈ U un cardinal inaccessible. AlorsVκ |= ZFC. En particulier, ZFC− + (CI) |= Coh(ZFC).

93

Demonstration. Nous avons montre tous les axiomes dans les lemmes prece-dents.

Par le second theoreme d’incompletude, le theoreme 6.4.14 a comme corol-laire que ZFC 6` (CI). Voici le resultat de consistance relative correspondant quenous montrons plus directement, sans faire appel au second theoreme d’incom-pletude.

Theoreme 6.4.15. On a Coh(ZFC)⇒ Coh(ZFC + ¬(CI)).

Demonstration. Soit U |= ZFC. On peut supposer que U |= (CI). Soit κ le pluspetit cardinal inaccessible dans U . Alors Vκ |= ZFC par le theoreme precedent.Il suffit de noter que Vκ |= ¬(CI), ce qui suit des observations suivaintes :

– y = P(x), Ord(x) et Card(x) sont des formules absolues pour Vκ (Lemmes6.4.7 et 6.4.8) ;

– “λ est un cardinal regulier” est absolu pour Vκ (cette propriete s’exprimepar la formule ¬∃α < λ(∃f : α→ λ cofinale), exercice) ;

– “λ est un cardinal fortement limite” est absolu pour Vκ (cette proprietes’exprime par la formule ∀α < λ(¬∃f : P(α)→ λ surjective), exercice).

A la fin de ce cours, nous mentionnons quelques resultats importants quenous citons sans preuve. Le livre de Kunen [4] est une reference excellente.

Le theoreme suivant peut s’obtenir de maniere assez elementaire par la me-thode de Fraenkel-Mostowski (voir la feuille de TD 14).

Theoreme 6.4.16. 1. Si ZF est consistante, alors ZFC− + ¬(AF) aussi.

2. Si ZF est consistante, alors ZF− + ¬(AC) aussi.

Il est possible de remplacer ZF− + ¬(AC) par ZF + ¬(AC) dans la secondepartie du theoreme precedent, mais la preuve est alors beaucoup plus difficile.

Rappelons que l’hypothese generalisee du continue GCH est donnee parl’enonce ∀α(2ℵα = ℵα+1).

Theoreme 6.4.17 (Godel). Si ZF est consistante, alors ZFC + (GCH) aussi.

Godel obtient ce resultat par la methode des constructibles. Voici l’idee de laconstruction qui est similaire a la celle de V .

– On suppose formalisees dans U |= ZF la syntaxe ainsi que la satisfactionpour des structures 〈a;∈�a〉, ou a ∈ U .

– On montre alors qu’il existe une classe fonctionnelle D qui donne l’en-semble des parties definissables, c’est-a-dire qu’on a b ∈ D(a) ⇔ b ⊆ aet il existe n ∈ ω, une formule ϕ[v0, . . . , vn] et c1, . . . , cn ∈ a tels queb = {c0 ∈ a | 〈a;∈�a〉 |= ϕ[c0, c1, . . . , cn]}.

– On definit L0 := ∅, Lα+1 := D(Lα), et Lλ :=⋃α<λ Lα pour λ limite.

Puis, on definit ”L =⋃α Lα” (une classe propre).

94

– Comme pour la hierarchie de von Neumann, on etablit certaines proprietesde base, par exemple α ≤ β ⇒ Lα ⊆ Lβ et la transitivite des Lα. On a doncune hierarchie croissante et continue d’ensembles transitifs (Lα)α∈Ord.

– On definit un rang RgL comme pour V , et on montre que RgL(α) = α,autrement dit Lα ∩Ord = α.

– On montre que LL = L (dans ZF), c’est-a-dire que L satisfait a l’axiomede constructibilite ∀xL(x). Pour cela, on utilise que la classe fonctionnelleD est absolue pour une classe X qui est modele de ZF− (Parties), et doncla classe fonctionnelle α 7→ Lα aussi.

– La preuve que L |= ZF est similaire a celle pour V .– Afin d’etablir L |= (AC) + (GCH), on construit, par recurrence sur α, un

bon ordre sur Lα tel que si α ≤ β, alors Lα est un segment initial deLβ . Dans l’etape successeur, a l’aide du bon ordre sur Lα, on construitun bon ordre sur L<ωα (l’ensemble des suites finies d’elements de Lα), puissur Lα+1, en enumerant les (codes des) formules egalement.

Theoreme 6.4.18 (Cohen). 1. Si ZF− est consistante, alors ZFC +¬(HC)aussi.

2. Si ZF− est consistante, alors ZF + ¬(AC) aussi.

Contrairement aux constructions de modeles de ZF− que nous avons vuesou esquissees jusqu’ici, les constructions utilisees pour montrer ce resultat ne sefont pas a l’interieur du modele de depart U . En revanche, la methode du forcing(introduite par Cohen en 1964 pour montrer son theoreme et utilisee en theoriedes ensembles jusqu’a nos jours) permet de construire des modeles de ZF quisont des extensions du modele de depart.

Affaiblissements de l’axiome du choix

L’axiome du choix dependant (ACD)

∀r∀a∀x0

[x0 ∈ a ∧ r ⊆ a2 ∧ ∀x ∈ a ∃y ∈ a (x, y) ∈ r

→ ∃f(f : ω → a ∧ f(0) = x0 ∧ ∀n ∈ ω ((f(n), f(n+ 1)) ∈ r)]

L’axiome du choix denombrable (ACC)

∀f [(Fn(f) ∧ dom(f)=ω ∧ ∅ 6∈ im(f))→ ∃g (Fn(g) ∧ dom(g)=ω ∧ ∀x(x ∈ dom(g)→ g(x) ∈ f(x)))]

L’axiome (ACC) exprime que le produit d’une famille denombrable d’en-sembles non vides est non vide.

Lemme 6.4.19. On a (AC)⇒(ACD)⇒(ACC).

Demonstration. (AC)⇒(ACD) : Soit h : P ′(a) → a une fonction de choix sura. Par induction sur ω, on definit une fonction f , via f(0) := x0, f(n + 1) :=h({y ∈ a | (f(n), y) ∈ r}). Il est clair que f convient.

95

(ACD)⇒(ACC) : Soit (Xn)n∈ω une famille denombrable d’ensembles non vides.On pose Yn := {n} ×Xn, a :=

⋃n∈ω Yn et

r := {(x, y) ∈ a2 | il existe n ∈ ω tel que x ∈ Yn et y ∈ Yn+1}.

Par (ACD) il existe une fonction f : ω → a telle que f(n) ∈ Yn pour tout n ∈ ω.Alors g ∈

∏n∈ωXn, ou g(n) := π((f(n)), avec π la projection sur la deuxieme

coordonnee.

La construction d’un ensemble non mesurable de reels qu’on voit au coursd’integration se fait dans ZFC. Cela donne le resultat suivant.

Proposition 6.4.20. ZFC |= ”il existe une partie de R non mesurable”

Le theoreme que nous mentionnons maintenant sans preuve est plus difficile.Pour le montrer, on utilise la technique du forcing.

Theoreme 6.4.21 (Solovay, 1970). Si ZFC + (CI) est consistante, alors latheorie ZF + (ACD) + ”toute partie de R est mesurable” est consistante aussi.

96

Bibliographie

[1] Rene Cori et Daniel Lascar, Logique mathematique, Tome 1, Dunod, 2003.

[2] Rene Cori et Daniel Lascar, Logique mathematique, Tome 2, Dunod, 2003.

[3] Heinz-Dieter Ebbinghaus, Jorg Flum et Wolfgang Thomas, MathematicalLogic, Second Edition, Undergraduate Texts in Mathematics, Springer, 1994.

[4] Kenneth Kunen, Set Theory. An Introduction to Independence Proofs, Stu-dies in Logic and the Foundations of Mathematics vol. 102, Elsevier, 1980.

[5] Francois Loeser, Un premier cours de logique, Notes de cours, 2010 (dispo-nible sur la page http://www.math.jussieu.fr/∼loeser/notes.php).

[6] Martin Ziegler, Mathematische Logik, Mathematik Kompakt, Birkhauser,2010.

97