Chapitre 2

Récursivité et induction

2.1 Motivation
Les définitions récursives sont omniprésentes en informatique. Elles sont présentes
à la fois dans les langages de programmation, mais aussi présentes dans de nombreux
concepts que l’on manipule.

Exemple 2.1 (Listes en JAVA) En JAVA, avec

class Liste {
i n t contenu ;
Liste suivant ;
}
Liste lst ;

on définit la classe Liste de façon récursive (inductive) : en utilisant dans la définition

de la classe, le champ “ suivant ” du type de la classe Liste elle même.

Exemple 2.2 (Arbres ordonnés) Nous avons défini les arbres ordonnés dans le cha-
pitre précédent en passant par la notion de graphe. Une alternative naturelle serait de
présenter les arbres ordonnés par une définition récursive : un arbre ordonné est soit
vide, soit réduit à un sommet (une racine), soit constitué d’un sommet (une racine) et
une liste (ordonnée) d’arbres ordonnés (ses fils).

Dans ce chapitre, nous nous attardons sur les définitions inductives d’ensembles et
de fonctions, qui permettent de donner un sens à des définitions récursives.
Nous discutons, par ailleurs comment il est possible de faire des preuves sur des
structures définies inductivement, en introduisant les preuves par induction structurelle.

2.2 Raisonnement par récurrence sur N

L’induction structurelle est une généralisation de la preuve par récurrence : reve-
nons sur cette dernière pour avoir les idées au clair.

1
2 CHAPITRE 2. RÉCURSIVITÉ ET INDUCTION

Lorsque l’on raisonne sur les entiers, le premier principe d’induction aussi appelé
principe de récurrence mathématique est un mode de raisonnement particulièrement
utile.

Théorème 2.1 Soit P (n) un prédicat (une propriété) dépendant de l’entier n. Si les
deux conditions suivantes sont vérifiées :
(B) P (0) est vrai ;
(I) P (n) implique P (n + 1) pour tout n ;
alors pour tout entier n, P (n) est vrai.

Démonstration : Le raisonnement se fait par l’absurde. Considérons X = {k ∈

N|P (k) est faux}. Si X est non vide, il admet un plus petit élément n. D’après la
condition (B), n 6= 0, et donc n − 1 est un entier, et P (n − 1) est vrai par définition de
X. On obtient une contradiction avec la propriété (I) appliquée pour l’entier n − 1. 
Pour faire une preuve par récurrence, on établit donc une propriété en 0 (cas de
base), et on établit que la propriété est héréditaire, ou inductive : P (n) implique P (n +
1) pour tout n.
Le concept de preuve inductive généralise cette idée à d’autres ensembles que les
entiers, à savoir aux ensembles qui se définissent inductivement.
Exercice 2.1. On considère Sn = 13 + 23 + · · · + (2n − 1)3 . Prouver par récurrence
que Sn = 2n4 − n2 .
Pn 1 n
Exercice 2.2. Prouver par récurrence que k=1 4k2 −1 = 2n+1 .

Exercice 2.3. Le théorème plus haut est parfois nommé “premier principe d’induc-
tion”. Prouver le “second principe d’induction” : soit P (n) une propriété dépendant
de l’entier n. Si la propriété suivante est vérifiée : si pour tout n ∈ N, si en supposant
pour tout entier k < n la propriété P (k) on déduit P (n), alors pour tout n ∈ N, la
propriété P (n) est vraie.

Exercice 2.4. On fixe un alphabet Σ. On rappelle qu’un langage sur Σ est une partie
de Σ∗ . Si L1 et L2 sont deux langages de Σ∗ , on définit leur concaténation par L1 .L2 =
{u.v|u ∈ L1 , v ∈ L2 }. La concaténation est une opération associative admettant {}
comme élément neutre. On peut alors définir les puissances d’un langage L de la façon
suivante : L0 = {}, et pour un S entiernn > 0, L
n+1
= Ln .L = L.Ln . L’étoile d’un
∗
langage L est défini par L = n∈N L .
Soient L et M deux langages sur Σ, avec  6∈ L. Montrer que dans P(Σ) (les
langages sur Σ), l’équation X = L.X ∪ M admet pour unique solution le langage
L∗ .M .

2.3 Définitions inductives

Les définitions inductives visent à définir des parties d’un ensemble E.
2.3. DÉFINITIONS INDUCTIVES 3

Remarque 2.1 Cette remarque est pour les puristes. Elle peut être évitée lors de la
première lecture de ce document.
Nous nous restreignons dans ce document au cadre où l’on souhaite définir par
induction des objets qui correspondent à des parties d’un ensemble déjà connu E.
Nous faisons cela pour éviter les subtilités et paradoxes de la théorie des ensembles.
Le lecteur très attentif pourra observer que l’on considérera dans la suite très
souvent l’écriture syntaxique des objets plutôt que les objets eux-mêmes. En effet, en
faisant ainsi, on garantit que l’on se place sur l’ensemble E = Σ∗ pour un certain
alphabet Σ, et on évite de se poser la question de l’existence de l’ensemble E sous-
jacent dans les raisonnements qui suivent.
Par exemple, pour formaliser complètement l’exemple 2.1 plus haut, on chercherait
plutôt à définir une représentation syntaxique des listes plutôt que les listes.

Lorsque l’on veut définir un ensemble, ou une partie d’un ensemble, une façon de
faire est de le définir de façon explicite, c’est-à-dire en décrivant précisément quels sont
ses éléments.

Exemple 2.3 Les entiers pairs peuvent se définir par P = {n|∃k ∈ N n = 2 ∗ k}.

Malheureusement, ce n’est pas toujours aussi facile, et il est souvent beaucoup plus
commode de définir un ensemble par une définition inductive. Un exemple typique de
définition inductive est une définition comme celle-ci :

Exemple 2.4 Les entiers pairs correspondent aussi au plus petit ensemble qui contient
0 et tel que si n est pair, alors n + 2 est pair.

Remarque 2.2 Observons que l’ensemble des entiers N vérifie bien que 0 est un entier,
et que si n est un entier n + 2 aussi. Il y a donc besoin de dire que c’est le plus petit
ensemble avec cette propriété.

2.3.1 Principe général d’une définition inductive

Intuitivement, une partie X se définit inductivement si on peut la définir avec la
donnée explicite de certains éléments de X et de moyens de construire de nouveaux
éléments de X à partir d’éléments de X.
De façon générique, dans une définition inductive,
– certains éléments de l’ensemble X sont donnés explicitement (c’est-à-dire on se
donne un ensemble B d’éléments de X, qui constitue l’ensemble de base de la
définition inductive) ;
– les autres éléments de l’ensemble X sont définis en fonction d’éléments appar-
tenant déjà à l’ensemble X selon certaines règles (c’est-à-dire on se donne des
règles R de formation d’éléments, qui constituent les étapes inductives de la dé-
finition récursive).
On considère alors le plus petit ensemble qui contient B et qui est stable (on dit
aussi parfois clos ou fermé) par les règles de R.
4 CHAPITRE 2. RÉCURSIVITÉ ET INDUCTION

2.3.2 Formalisation : Premier théorème du point fixe

Formellement, tout cela se justifie par le théorème qui suit.

Définition 2.1 (Définition inductive) Soit E un ensemble. Une définition inductive

d’une partie X de E consiste à se donner
– un sous ensemble non vide B de E (appelé ensemble de base)
– et d’un ensemble de règles R : chaque règle ri ∈ R est une fonction (qui peut
être partielle) ri de E ni → E pour un certain entier ni ≥ 1.

Théorème 2.2 (Théorème du point fixe) A une définition inductive correspond un plus
petit ensemble qui vérifie les propriétés suivantes :
(B) il contient B : B ⊂ X ;
(I) il est stable par les règles de R : pour chaque règle ri ∈ R, pour tout x1 , · · · , xni ∈
X, on a ri (x1 , · · · , xni ) ∈ X.
On dit que cet ensemble est alors défini inductivement.

Démonstration : Soit F l’ensemble des parties de E vérifiant (B) et (I). L’en-

semble F est non vide car il contient au moins un élément : en effet, l’ensemble E
vérifie les conditions (B) et (I) et donc E ∈ F.
On peut alors considérer X défini comme l’intersection de tous les éléments de F.
Formellement, \
X= Y. (2.1)
Y ∈F

Puisque B est inclus dans chaque Y ∈ F, B est inclus dans X. Donc X vérifie la
condition (B).
L’ensemble obtenu vérifie aussi (I). En effet, considérons une règle ri ∈ R, et des
x1 , · · · , xni ∈ X. On a x1 , · · · , xni ∈ Y pour chaque Y ∈ F. Pour chaque tel Y ,
puisque Y est stable par la règle ri , on doit avoir r(x1 , · · · , xni ) ∈ Y . Puisque cela est
vrai pour tout Y ∈ F, on a aussi r(x1 , · · · , xni ) ∈ X, ce qui prouve que X est stable
par la règle ri .
X est le plus petit ensemble qui vérifie les conditions (B) et (I), car il est par
définition inclus dans tout autre ensemble vérifiant les conditions (B) et (I).


2.3.3 Différentes notations d’une définition inductive

Notation 2.1 On note souvent une définition inductive sous la forme
(B) x ∈ X
avec une ligne comme celle là pour chaque x ∈ B
(ou éventuellement on écrit B ⊂ X ) ;
(I) x1 , · · · xni ∈ X ⇒ ri (x1 , · · · , xni ) ∈ X
avec une telle ligne pour chaque règle ri ∈ R.

Exemple 2.5 Selon cette convention, la définition inductive des entiers pairs (de l’exemple
2.4) se note
2.4. APPLICATIONS 5

(B) 0 ∈ P ;
(I) n ∈ P ⇒ n + 2 ∈ P.

Exemple 2.6 Soit Σ = {(, )} l’alphabet constitué de la parenthèse ouvrante et de

la parenthèse fermante. L’ensemble D ⊂ Σ∗ des parenthésages bien formés, appelé
langage de Dyck, est défini inductivement par
(B)  ∈ D;
(I) x ∈ D ⇒ (x) ∈ D;
(I) x, y ∈ D ⇒ xy ∈ D.

Notation 2.2 On préfère parfois écrire une définition inductive sous la forme de règles
de déduction :
x 1 ∈ X . . . x ni ∈ X
B⊂X ri (x1 , . . . , xni ) ∈ X
Le principe de cette notation est qu’un trait horizontal signifie une règle de
déduction. Ce qui est écrit au dessus est une hypothèse. Ce qui est écrit en dessous est
une conclusion. Si ce qui est au dessus est vide, alors c’est que la conclusion est valide
sans hypothèse.

Notation 2.3 On écrit aussi parfois directement

x1 . . . xni
b ri (x1 , . . . , xni )
pour chaque b ∈ B,
ou
x1 . . . xni
b∈B ri (x1 , . . . , xni )
ou encore plus rarement parfois
x1 . . . xni
B ri (x1 , . . . , xni )

2.4 Applications
2.4.1 Quelques exemples
Exemple 2.7 (N) La partie X de N définie inductivement par
n
0 n+1

n’est autre que N tout entier.

Exemple 2.8 (Σ∗ ) La partie X de Σ∗ , où Σ est un alphabet, définie inductivement par

(B)  ∈ X;
(I) w ∈ X ⇒ wa ∈ X, pour chaque a ∈ Σ ;
6 CHAPITRE 2. RÉCURSIVITÉ ET INDUCTION

n’est autre que Σ∗ tout entier.

Exemple 2.9 (Langage {an bcn }) Le langage L sur l’alphabet Σ = {a, b} des mots
de la forme an bcn , n ∈ N, se définit inductivement par
(B) b ∈ L;
(I) w ∈ L ⇒ awc ∈ L.

Exercice 2.5. Définir inductivement l’ensemble des expressions entièrement paren-

thésées formées à partir d’identificateurs pris dans un ensemble A et des opérateurs +
et ×.

2.4.2 Arbres binaires étiquetés

Reprenons le texte suivant du polycopié de INF421 (version 2010-2011) : “la notion
d’arbre binaire est assez différente des définitions d’arbre libre, arbre enraciné et arbre
ordonné. Un arbre binaire sur un ensemble fini de sommets est soit vide, soit l’union
disjointe d’un sommet appelé sa racine, d’un arbre binaire appelé sous-arbre gauche,
et d’un arbre binaire appelé sous-arbre droit. Il est utile de représenter un arbre binaire
non vide sous la forme d’un triplet A = (Ag , r, Ad ).”
On obtient immédiatement une définition inductive de l’écriture des arbres binaires
étiquetés à partir de ce texte.

Exemple 2.10 (Arbres binaires étiquetés) L’ensemble AB des arbres binaires éti-
quetés par l’ensemble A est la partie de Σ∗ , où Σ est l’alphabet Σ = A ∪ {∅, (, ), ,},
définie inductivement par
(B) ∅ ∈ AB ;
(I) g, d ∈ AB ⇒ (g, a, d) ∈ AB, pour chaque a ∈ A.

Remarque 2.3 Dans l’écriture plus haut, (g, a, d) désigne la concaténation du mot de
longueur 1 (, du mot g, du mot , de longueur 1, du mot a, du mot , de longueur 1, du
mot d et du mot ) de longueur 1. Tous ces mots sont bien des mots sur l’alphabet Σ qui
contient tous les symboles nécessaires.

Remarque 2.4 g, d ∈ AB ⇒ (g, a, d) ∈ AB, pour chaque a ∈ A désigne le fait que

l’on répète, pour chaque a ∈ A, la règle g, d ∈ AB ⇒ (g, a, d) ∈ AB. C’est donc en
réalité pas une règle, mais une famille de règles, une pour chaque élément a de A.

Remarque 2.5 Attention : un arbre binaire n’est pas un arbre ordonné dont tous les
nœuds sont d’arité au plus 2.

Exemple 2.11 Par exemple, l’arbre binaire étiqueté

2.4. APPLICATIONS 7

et l’arbre binaire étiqueté

ne sont pas les mêmes, car le premier correspond au mot (((∅, 3, ∅), 2, ∅), 1, ∅) et le
second au mot (∅, 1, ((∅, 3, ∅), 2, ∅)). Pourtant si on considère ces arbres comme des
arbres ordonnés, ce sont les mêmes.

Exercice 2.6. Soit A un alphabet. On définit récursivement la suite d’ensemble

(ABn )n∈N par
– AB0 = {∅}.
– ABn+1 = AB Sn ∪ {(a, g, d)|a ∈ A, g, d ∈ ABn }
Montrer que X = n∈N ABn correspond aussi à l’ensemble AB des arbres binaires
étiquetés par l’ensemble A.

2.4.3 Expressions arithmétiques

On peut définir les expressions arithmétiques bien formées sur l’alphabet Σexp de
l’exemple ??. Rappelons que l’on avait défini l’alphabet

Σexp = {0, 1, 2, · · · , 9, +, −, ∗, /, (, )}.

Commençons par définir ce qu’est un nombre écrit en base 10. A priori on écrit un
entier en base 10 sans débuter par un 0 (sauf pour 0). Par exemple 000192 n’est pas
autorisé. Par contre 192 est bien une écriture valide.
On obtient la définition inductive suivante.

Exemple 2.12 L’ensemble N des nombres entiers non-nuls écrits en base 10 est la
partie de Σexp ∗ , définie inductivement par
8 CHAPITRE 2. RÉCURSIVITÉ ET INDUCTION

(B) a ∈ N pour chaque a ∈ {1, 2, . . . , 9} ;

(I) g ∈ N ⇒ ga ∈ N , pour chaque a ∈ {0, 1, 2, . . . , 9}.
On peut ensuite définir les expressions arithmétiques de la façon suivante :
Exemple 2.13 L’ensemble Arith des expressions arithmétiques est la partie de Σexp ∗ ,
définie inductivement par
(B) 0 ∈ Arith ;
(B) N ⊂ Arith ;
(I) g, d ∈ Arith ⇒ g + d ∈ Arith ;
(I) g, d ∈ Arith ⇒ g ∗ d ∈ Arith ;
(I) g, d ∈ Arith ⇒ g/d ∈ Arith ;
(I) g, d ∈ Arith ⇒ g − d ∈ Arith ;
(I) g ∈ Arith ⇒ (g) ∈ Arith ;
Ainsi, on a (1 + 2 ∗ 4 + 4 ∗ (3 + 2)) ∈ Arith qui correspond bien à une expression
valide. Par contre +1 − /2( n’est pas dans Arith.

2.4.4 Termes
Les termes sont des arbres ordonnés étiquetés particuliers. Ils jouent un rôle essen-
tiel dans beaucoup de structures en informatique.
Soit F = {f0 , f1 , · · · , fn , · · · } un ensemble de symboles, appelés symboles de
fonctions. A chaque symbole f est associé un entier a(f ) ∈ F , que l’on appelle arité
de f et qui représente le nombre d’arguments du symbole de fonction f . On note Fi
pour le sous-ensemble des symboles de fonctions d’arité i. Les symboles de fonctions
d’arité 0 sont appelés des constantes.
Soit Σ l’alphabet Σ = F ∪ {(, ), , } constitué de F et de la parenthèse ouvrante, de
la parenthèse fermante, et de la virgule.
Définition 2.2 (Termes sur F ) L’ensemble T des termes construit sur F est la partie
de Σ∗ définie inductivement par :
(B) F0 ⊂ T
(c’est-à-dire : les constantes sont des termes)
(I) t1 , t2 , · · · , tn ∈ T ⇒ f (t1 , t2 , · · · , tn ) ∈ T
pour chaque entier n, pour chaque symbole f ∈ Fn d’arité n.
Remarque 2.6 Dans la définition plus haute, on parle bien de mots sur l’alphabet Σ :
f (t1 , t2 , · · · , tn ) désigne le mot dont la première lettre est f , la seconde (, les suivantes
celle de t1 , etc.
Exemple 2.14 Par exemple, on peut fixer F = {0, 1, f, g}, avec 0 et 1 d’arité 0 (ce
sont des constantes), f d’arité 2 et g d’arité 1.
f (0, g(1)) est un terme sur F . f (g(g(0)), f (1, 0)) est un terme sur F . f (1) n’est
pas un terme sur F .
Les termes sur F correspondent à des arbres ordonnés étiquetés particuliers : les
sommets sont étiquetés par les symboles de fonctions de F , et un sommet étiqueté par
un symbole d’arité k possède exactement k fils.
2.5. PREUVES PAR INDUCTION 9

2.5 Preuves par induction

On va devoir régulièrement prouver des propriétés sur les éléments d’un ensemble
X défini implicitement. Cela s’avère possible en utilisant ce que l’on appelle la preuve
par induction, parfois appelée preuve par induction structurelle, qui généralise le prin-
cipe de la preuve par récurrence.

Théorème 2.3 (Preuve par induction) Soit X ⊂ E un ensemble défini inductivement

à partir d’un ensemble de base B et de règles R. Soit P un prédicat exprimant une
propriété d’un élément x ∈ E : c’est-à-dire une propriété P(x) qui est soit vraie soit
fausse en un élément x ∈ E.
Si les conditions suivantes sont vérifiées :
(B) P(x) est vérifiée pour chaque élément x ∈ B ;
(I) P est héréditaire, c’est-à-dire stable par les règles de R : Formellement, pour
chaque règle ri ∈ R, pour chaque x1 , · · · , xni ∈ E, P(x1 ), · · · , P(xni ) vraies
impliquent P(x) vraie en x = r(x1 , · · · , xni ).
Alors P(x) est vraie pour chaque élément x ∈ X.

Démonstration : On considère l’ensemble Y des éléments x ∈ E qui vérifient le

prédicat P(x). Y contient B par la propriété (B). Y est stable par les règles de R par
propriété (I). L’ensemble X, qui est le plus petit ensemble contenant B et stable par
les règles de R, est donc inclus dans Y . 

Remarque 2.7 La preuve par induction généralise bien la preuve par récurrence. En
effet, N se définit inductivement comme dans l’exemple 2.7. Une preuve par induction
sur cette définition inductive de N correspond à une preuve par récurrence, c’est-à-dire
aux hypothèses du théorème 2.1.

Exemple 2.15 Pour prouver par induction que tous les mots du langage défini impli-
citement dans l’exemple 2.9 possèdent autant de a que de c, il suffit de constater que
c’est vrai pour le mot réduit à une lettre b, qui possède 0 fois la lettre a et la lettre c, et
que si cela est vrai pour le mot w alors le mot awb possède aussi le même nombre de
fois la lettre a que la lettre c, à savoir exactement une fois de plus que dans w.

Exercice 2.7. On considère le sous-ensemble ABS des arbres binaires stricts défini
comme le sous-ensemble du langage AB (des arbres binaires étiquettés par A) défini
inductivement par :
(B) (∅, a, ∅) ∈ ABS, pour chaque a ∈ A.
(I) g, d ∈ ABS ⇒ (g, a, d) ∈ ABS, pour chaque a ∈ A.
Montrer
– qu’un élément de ABS est toujours non-vide et sans sommet avec un seul fils
non-vide.
– que dans un arbre binaire strict, le nombre de sommets n vérifie n = 2f − 1, où
f est le nombre de feuilles.
10 CHAPITRE 2. RÉCURSIVITÉ ET INDUCTION

Exercice 2.8. Montrer que tout mot du langage de Dyck possède autant de paren-
thèses fermantes qu’ouvrantes.

Exercice 2.9. Montrer que tout expression arithmétique, c’est-à-dire tout mot du
langage Arith, possède autant de parenthèses fermantes qu’ouvrantes.

Exercice 2.10. Un arbre binaire est dit équilibré si pour chaque sommet de l’arbre,
la différence entre la hauteur de son sous-arbre droit et la hauteur de son sous-arbre
gauche vaut soit −1, 0 ou 1 (i.e. au plus un en valeur absolue).
– Donner une définition inductive de l’ensemble AV L des arbres binaires équili-
brés.
– On définit la suite (un )n∈N par u0 = 0, u1 = 1, et pour tout n ≥ 2, un+2 =
un+1 + un + 1.
Montrer que pour tout x ∈ AV L, n ≥ uh+1 où h et n sont respectivement la
hauteur et le nombre de sommets d’un arbre.

2.6 Dérivations
2.6.1 Écriture explicite des éléments : Second théorème du point
fixe
Nous avons vu jusque-là plusieurs exemples d’ensembles X définis inductivement.
L’existence de chaque ensemble X découle du théorème 2.2, et en fait de l’équation
(2.1) utilisée dans la preuve de celui-ci.
On parle de définition de X par le haut, puisque l’équation (2.1) définit X à par-
tir de sur-ensembles de celui-ci. Cela a clairement l’avantage de montrer facilement
l’existence d’ensembles définis inductivement, ce que nous avons abondamment uti-
lisé jusque-là.
Cependant, cela a le défaut de ne pas dire quels sont exactement les éléments des
ensembles X obtenus.
Il est en fait aussi possible de définir chaque ensemble X défini inductivement par
le bas. On obtient alors une définition explicite des éléments de X, avec en prime une
façon de les obtenir explicitement.
C’est ce que dit le résultat suivant :

Théorème 2.4 (Définition explicite d’un ensemble défini implicitement) Chaque en-
semble X défini implicitement à partir de l’ensemble de base B et des règles R s’écrit
aussi [
X= Xn ,
n∈N

où (Xn )n∈N est la famille de parties de E définie par récurrence par

– X0 = B
– Xn+1 = Xn ∪ {ri (x1 , · · · , xni )|x1 , · · · , xni ∈ Xn et ri ∈ R}.
2.6. DÉRIVATIONS 11

Autrement dit, tout élément de X est obtenu en partant d’éléments de B et en

appliquant un nombre fini de fois les règles de R pour obtenir des nouveaux éléments.
Démonstration : Il suffit de prouver que cet ensemble est le plus petit ensemble
qui contient B et qu’il est stable par les règles de R.
D’une part, puisque X0 = B, B est bien dans l’union des Xn . D’autre part, si
l’on prend une règle ri ∈ R, et des éléments x1 , · · · , xni dans l’union des Xn , par
définition chaque xj est dans un Xkj pour un entier kj . Puisque les ensembles Xi sont
croissants (i.e. Xi ⊂ Xi+k pour tout k, ce qui se prouve facilement par récurrence
sur k), tous les x1 , · · · , xni sont dans Xn0 pour n0 = max(k1 , · · · , kni ). On obtient
immédiatement que r(x1 , · · · , xni ) est dans Xn0 +1 , ce qui prouve qu’il est bien dans
l’union des Xn .
Enfin, c’est le plus petit ensemble, car tout ensemble qui contient B et qui est stable
par les règles de R doit contenir chacun des Xn . Cela se prouve par récurrence sur n.
C’est vrai au rang n = 0, car un tel ensemble doit contenir X0 puisqu’il contient B.
Supposons l’hypothèse au rang n, c’est-à-dire X contient Xn . Puisque les éléments de
Xn+1 sont obtenus à partir d’éléments de Xn ⊂ X en appliquant une règle ri ∈ R, X
contient chacun de ces éléments. 

2.6.2 Arbres de dérivation

La définition par le bas de X du théorème précédent invite à chercher à garder
la trace de comment chaque élément est obtenu, en partant de X et en appliquant les
règles de R.

Exemple 2.16 Le mot 1+2+3 correspond à une expression arithmétique. En voici une
preuve.
1∈N 2∈N
1 + 2 ∈ Arith 3 ∈ Arith
1 + 2 + 3 ∈ Arith
Ce n’est pas la seule possible. En effet, on peut aussi écrire
2∈N 3∈N
1 ∈ Arith 2 + 3 ∈ Arith
1 + 2 + 3 ∈ Arith

Pour coder chaque trace, la notion naturelle qui apparaît est celle de terme, sur un
ensemble de symboles F bien choisi : on considère que chaque élément b de la base B
est un symbole d’arité 0. A chaque règle ri ∈ R on associe un symbole d’arité ni . Un
terme t sur cet ensemble de symboles est appelé une dérivation.
A chaque dérivation t est associé un élément h(t) comme on s’y attend : si t est
d’arité 0, on lui associe l’élément b de B correspondant. Sinon, t est de la forme
ri (t1 , · · · , tni ), pour une règle ri ∈ R et pour des termes t1 , · · · , tni , et on associe
à t le résultat de la règle ri appliquée aux éléments h(t1 ), · · · , h(tni ).

Exemple 2.17 Pour les expressions arithmétiques, notons par le symbole + d’arité 2,
la règle g, d ∈ Arith ⇒ g + d ∈ Arith ;
12 CHAPITRE 2. RÉCURSIVITÉ ET INDUCTION

La première preuve de l’exemple 2.16 correspond à la dérivation +(+(1, 2), 3). La

seconde à la dérivation +(1, +(2, 3)). L’image par la fonction h de ces dérivations est
le mot 1 + 2 + 3.
On peut alors reformuler le théorème précédent de la façon suivante.
Proposition 2.1 Soit un ensemble X défini implicitement à partir de l’ensemble de
base B et des règles de R. Soit D l’ensemble des dérivations correspondant à B et à
R. Alors
X = {h(t)|t ∈ D}.
Autrement dit, X est précisément l’ensemble des éléments de E qui possèdent une
dérivation.
On voit dans l’exemple précédent, qu’un élément de X peut à priori avoir plusieurs
dérivations.
Définition 2.3 On dit qu’une définition inductive de X est non ambiguë si la fonction
h précédente est injective.
Intuitivement, cela signifie qu’il n’existe qu’une unique façon de construire chaque
élément de X.
Exemple 2.18 La définition suivante de N2 est ambigüe.
(B) (0, 0) ∈ N2 ;
(I) (n, m) ∈ N2 ⇒ (n + 1, m) ∈ N2 ;
(I) (n, m) ∈ N2 ⇒ (n, m + 1) ∈ N2 .
En effet, on peut par exemple obtenir (1, 1) en partant de (0, 0) et en appliquant la
deuxième puis la troisième règle, mais aussi en appliquant la troisième règle puis la
deuxième règle.
Exemple 2.19 La définition de Arith de l’exemple 2.13 est ambigüe puisque 1 + 2 + 3
possède plusieurs dérivations.
Exemple 2.20 Ce problème est intrinsèque aux expressions arithmétiques, puisque
lorsqu’on écrit 1 + 2 + 3, on ne précise pas dans l’écriture si l’on veut parler du
résultat de l’addition de 1 à 2 + 3 ou de 3 à 1 + 2, l’idée étant que puisque l’addition
est associative, cela n’est pas important.
Exemple 2.21 Pour éviter ce problème potentiel, définissons l’ensemble Arith0 des
expressions arithmétiques parenthésées comme la partie de Σexp ∗ , définie inductive-
ment par
(B) 0 ∈ Arith ;
(B) N ⊂ Arith0 ;
(I) g, d ∈ Arith0 ⇒ (g + d) ∈ Arith0 ;
(I) g, d ∈ Arith0 ⇒ (g ∗ d) ∈ Arith0 ;
(I) g, d ∈ Arith0 ⇒ (g/d) ∈ Arith0 ;
(I) g, d ∈ Arith0 ⇒ (g − d) ∈ Arith0 ;
(I) g ∈ Arith0 ⇒ (g) ∈ Arith0 ;
Cette fois, 1 + 2 + 3 n’est pas un mot de Arith0 . Par contre, (1 + (2 + 3)) ∈ Arith0
et ((1 + 2) + 3) ∈ Arith0 .
L’intérêt de cette écriture est que l’on a cette fois des règles non-ambigües.
2.7. FONCTIONS DÉFINIES INDUCTIVEMENT 13

2.7 Fonctions définies inductivement

Nous aurons parfois besoin de définir des fonctions sur des ensembles X définis
inductivement. Cela peut se faire facilement lorsque X admet une définition non am-
bigüe.

Théorème 2.5 (Fonction définie inductivement) Soit X ⊂ E un ensemble défini in-

ductivement de façon non ambigüe à partir de l’ensemble de base B et des règles R.
Soit Y un ensemble.
Pour qu’une application f de X dans Y soit parfaitement définie, il suffit de se
donner :
(B) la valeur de f (x) pour chacun des éléments x ∈ B ;
(I) pour chaque règle ri ∈ R, la valeur de f (x) pour x = ri (x1 , · · · , xni ) en
fonction de la valeur x1 , . . . , xni , f (x1 ), . . ., et f (xni ).

Autrement dit, informellement, si l’on sait “programmer récursivement”, c’est-à-

dire “décrire de façon récursive la fonction”, alors la fonction est parfaitement définie
sur l’ensemble inductif X.
Démonstration : On entend par l’énoncé, qu’il existe alors une unique application
f de X dans Y qui satisfait ces contraintes. Il suffit de prouver que pour chaque x ∈ X,
la valeur de f en x est définie de façon unique. Cela se prouve facilement par induction :
c’est vrai pour les éléments x ∈ B. Si cela est vrai en x1 , · · · , xni , cela est vrai en
x = ri (x1 , · · · , xni ) : la définition de X étant non ambigüe, x ne peut être obtenu que
par la règle ri à partir de x1 , · · · , xni . Sa valeur est donc parfaitement définie par la
contrainte pour la règle ri . 

Exemple 2.22 La fonction factorielle F act de N dans N se définit inductivement par

(B) F act(0) = 1;
(I) F act(n + 1) = (n + 1) ∗ F act(n).

Exemple 2.23 La hauteur h d’un arbre binaire étiqueté se définit inductivement par
(B) h(∅) = 0;
(I) h((g, a, d)) = 1 + max(h(g), h(d)).

Exemple 2.24 La valeur v d’une expression arithmétique de Arith0 se définit inducti-

vement par (v est une fonction qui va des mots vers les rationnels)
(B) v(0) = 0 ;
(B) v(x) = h(x) pour x ∈ N ;
(I) v((g + d)) = v(g) + v(d) ;
(I) v((g ∗ d)) = v(g) ∗ v(d) ;
(I) v((g/d)) = v(g)/v(d), si v(d) 6= 0 ;
(I) v((g − d)) = v(g) − v(d) ;
(I) v((g)) = v(g) ;
où h est la fonction qui à un mot de N associe sa valeur en tant que rationnel : h
se définit inductivement par
(B) h(a) = a pour chaque a ∈ {1, 2, . . . , 9} ;
(I) h(ga) = 10 ∗ h(g) + a pour chaque a ∈ {0, 1, 2, . . . , 9}.
14 CHAPITRE 2. RÉCURSIVITÉ ET INDUCTION

On observera que ces définitions ne sont essentiellement que la traduction de com-

ment on peut les programmer de façon récursive. L’utilisation d’une définition non-
ambigüe évitant toute ambiguïté sur l’évaluation.

Remarque 2.8 Pour les expressions arithmétiques, 1+2∗3 ∈ Arith est aussi ambigüe
à priori. Un évaluateur qui prendrait en entrée un mot de Arith devrait aussi gérer
les priorités, et comprendre que 1 + 2 ∗ 3 n’est pas le résultat de la multiplication de
1 + 2 par 3. En utilisant la définition de Arith0 , on évite complétement aussi cette
difficulté, puisque les expressions codent explicitement comment les évaluer, et une
définition inductive devient possible. A priori, la valeur d’une expression de Arith ne
se définit pas aussi simplement inductivement, ne serait-ce qu’en raison du problème
que la valeur de x + y ∗ z ne s’obtient pas directement à partir de celle de x + y et de
z uniquement.

2.8 Notes bibliographiques

Lectures conseillées Pour aller plus loin sur les notions évoquées dans ce chapitre,
nous suggérons la lecture de [Arnold and Guessarian, 2005]. Pour une présentation
plus générale des définitions inductives et des théorèmes de points fixes, nous sug-
gérons la lecture de [Dowek, 2008].

Bibliographie Ce chapitre a été rédigé grâce aux ouvrages [Dowek, 2008] et [Arnold and Guessarian, 2005].
Index

(Ag , r, Ad ), 6, voir arbre binaire ∨, voir disjonction

(V, E), voir graphe ∧, voir conjonction
(q, u, v), voir configuration d’une machine uqv, voir configuration d’une machine de
de Turing Turing
., voir concaténation hhM i, wi, voir codage d’une paire
Ac , voir complémentaire hM i, voir codage d’une machine de Tu-
F (G/p), voir substitution ring
L(M ), voir langage accepté par une ma- hmi, voir codage
chine de Turing hφi, voir codage d’une formule
⇔, voir double implication hw1 , w2 i, voir codage d’une paire
⇒, 4, voir définition inductive / différentes
notations d’une, voir implica- AB, 6, 9
tion ABS, 9
Σ, voir alphabet ambiguë, voir définition
Σ∗ , voir ensemble des mots sur un alpha- arbre
bet binaire, 6
Σexp , 7 étiqueté, 6, 7
∩, voir intersection de deux ensembles strict, 9
∪, voir union de deux ensembles de dérivation, 11
, voir mot vide enraciné, 6
≡, voir équivalence entre formules, voir libre, 6
équivalence entre problèmes ordonné, 1, 6
∃, voir quantificateur arité
∀, voir quantificateur d’un symbole de fonction, 8
≤m , voir réduction Arith, 7–9, 11–13, voir expressions arith-
|w|, voir longueur d’un mot métiques
≤, voir réduction Arith0 , 12, 13, voir expressions arithmé-
N , 7, 11–13 tiques parenthésées
P(E), voir parties d’un ensemble
|=, voir conséquence sémantique codage
¬, voir négation notation, voir h.i
6|=, voir conséquence sémantique d’une formule
⊂, voir partie d’un ensemble notation, voir hφi
×, voir produit cartésien de deux ensembles d’une machine de Turing
`, voir démonstration, voir relation suc- notation, voir hM i
cesseur entre configurations d’une d’une paire
machines de Turing notation, voir hhM i, wi, voir hw1 , w2 i

15
16 INDEX

complémentaire définie inductivement, 12

notation, voir Ac
du problème de l’arrêt des machines graphe
de Turing notation, voir (V, E)
notation , voir HALTING − PROBLEM
complétude HALTING − PROBLEM, voir problème
RE-complétude, voir RE-complet de l’arrêt des machines de Tu-
concaténation ring
notation, voir . HALTING − PROBLEM, voir complé-
conclusion d’une règle de déduction, 5 mentaire du problème de l’arrêt
configuration d’une machine de Turing d’une machine de Turing
notation, voir (q, u, v), voir uqv héréditaire, voir propriété, 9
constantes, 8 hypothèse d’une règle de déduction, 5

définition induction structurelle, 1

explicite, 3 intersection de deux ensembles
inductive, 1–4, 6, 12 notation, voir ∩
différentes notations d’une, 4, 5
non-ambiguë, 12 langage
par le bas, 10, 11 accepté par une machine de Turing
par le haut, 10 notation, voir L(M )
récursive, 1 longueur d’un mot
démonstration notation, voir |w|
par récurrence, 2
mot
dérivation, 10, 11
vide
ensemble notation, voir 
clos par un ensemble de règles
synonyme : ensemble stable par un partie
ensemble de règles, voir ensemble d’un ensemble
stable par un ensemble de règles notation, voir ⊂
de base d’une définition inductive, 3, parties
4 d’un ensemble
fermé par un ensemble de règles notation, voir P(E)
synonyme : ensemble stable par un prédicat, 2, 9
ensemble de règles, voir ensemble preuve
stable par un ensemble de règles par induction (structurelle), 1, 2, 8
stable par un ensemble de règles, 3, 9 par récurrence, 1, 2
équivalence principe
entre problèmes d’induction, 2
notation, voir ≡ de récurrence, 2
expressions arithmétiques, 7 problème
notation, voir Arith de l’arrêt des machines de Turing
parenthésées, 12 notation, voir HALTING − PROBLEM
notation , voir Arith 0 produit cartésien
de deux ensembles
fonction notation, voir ×
INDEX 17

propriété
héréditaire
synonyme : propriété inductive, voir
propriété inductive
inductive, 2

R, voir décidable
racine d’un arbre, 6
RE, voir récursivement énumérable
récusivement énumérable
notation, voir RE
réduction
notation, voir ≤, voir ≤m
règle
de déduction, 5
inductive, 4
relation successeur entre configurations d’une
machine de Turing
notation, voir `

sous-arbre
droit d’un arbre binaire, 6
gauche d’un arbre binaire, 6
symboles
de fonctions, 8

terme, 8
théorème
du point fixe, 4, 10
premier théorème, 4
second théorème, 10
théorie
des ensembles, 3

union de deux ensembles

notation, voir ∪

équilibré, 9
18 INDEX
Bibliographie

[Arnold and Guessarian, 2005] Arnold, A. and Guessarian, I. (2005). Mathématiques

pour l’informatique. Ediscience International.
[Dowek, 2008] Dowek, G. (2008). Les démonstrations et les algorithmes. Polycopié
du cours de l’Ecole Polytechnique.

19