Lemme de König
En mathématiques, le lemme de Kőnig est un lemme de la théorie des graphes que l'on doit au mathématicien hongrois Dénes Kőnig en 1927[1]. Il énonce que :
Pour les articles homonymes, voir Théorème de König.
- « Tout arbre infini à branchement fini a une branche infinie. »
Il a des applications en logique.
Historique modifier
Définitions modifier
Un arbre est un ensemble de nœuds, muni d'une relation binaire de succession immédiate qui vérifie les conditions suivantes :
- On distingue la racine R, qui n'est le successeur immédiat d'aucun nœud ;
- Tout nœud sauf R est le successeur immédiat (ou fils) d'un unique nœud ;
- Tous les nœuds sont des descendants de la racine R.
Un nœud D est un descendant d'un nœud A s'il existe un chemin de A à D.
Un arbre est à branchement fini lorsque tous les nœuds n'ont qu'un nombre fini de fils.
Un arbre est infini lorsqu'il a un nombre infini de nœuds.
Une branche d'un arbre est une suite finie ou infinie de nœuds N(i), qui commence par la racine, et qui est telle que pour tout i, N(i+1) est un fils de N(i).
Démonstration modifier
Considérons un arbre infini à branchement fini. Soit N(0) la racine.
- Comme N(0) a un nombre infini de descendants et a un nombre fini de fils, l'un d'entre eux au moins, noté N(1), a un nombre infini de descendants.
- Comme N(1) a un nombre infini de descendants et a un nombre fini de fils, l'un d'entre eux au moins, noté N(2), a un nombre infini de descendants.
- etc.
On définit ainsi une suite infinie de nœuds N(0), N(1), ... qui forme une branche infinie.
Applications modifier
Compacité modifier
Le lemme de Kőnig permet de démontrer que : étant donné un ensemble de tuiles de Wang, le plan est pavable si, et seulement si tout carré fini est pavable si, et seulement si le quart de plan est pavable[2].
Calculabilité modifier
Le lemme de Kőnig intervient dans la démonstration du fait que si un langage est décidé par une machine de Turing non-déterministe (qui s'arrête sur toutes les entrées) alors il est décidé par une machine de Turing déterministe[3]. La démonstration considère l'arbre de calcul de la machine de Turing non-déterministe. Comme toutes les branches sont de longueur finie (car la machine s'arrête sur toutes les entrées) et que l'arbre de calcul est à branchement fini, le lemme de Kőnig implique que l'arbre de calcul est fini. On construit alors une machine de Turing déterministe qui réalise un parcours en largeur de l'arbre de calcul. Ce parcours termine puisque l'arbre de calcul est fini.
Mathématiques récréatives modifier
Smullyan a utilisé le lemme de Kőnig pour démontrer la terminaison du jeu "arbres et boules"[4]. Le jeu fonctionne comme suit. Au début, la boîte contient une boule numérotée par un nombre positif. À chaque étape, le joueur tire une boule numérotée k de la boîte puis place un nombre arbitrairement grand de boules numérotées par des nombres positifs strictement inférieurs à k. Le jeu s'arrête lorsque le joueur tire une boule numérotée 0. L'arbre dont les nœuds sont les boules manipulées et on met un arc entre une boule k et une autre k' avec k' < k si le joueur a mis k' à l'étape où la boule k a été tiré. L'arbre est à branchement fini et toutes les branches sont finies (vu que les numéros des boules décroissent strictement). Par le lemme de Kőnig, l'arbre est fini.
Discussions modifier
Formulation alternative sans référence à l'infini modifier
Dans cette sous-section, on donne une autre reformulation[5] du lemme de Kőnig qui ne fait pas référence à l'infini (le mot "infini" n'apparaît pas). En particulier, la démonstration n'utilise pas de négation (le mot "fini" n'est pas sous la portée d'une négation). Le lemme de Kőnig est une conséquence de la propriété suivante :
- Une relation acyclique à branchement fini est globalement finie si et seulement si tous les éléments sont accessibles.
Une relation sur est à branchement fini si pour tout l'ensemble est fini.
Une relation est globalement finie si pour tout l'ensemble est fini, où est la fermeture réflexive et transitive de .
Une relation est acyclique si et implique .
L'ensemble des éléments accessibles par est le plus petit ensemble tel que .
Axiome du choix modifier
La démonstration utilise l'axiome du choix dépendant, forme faible de l'axiome du choix.
Généralisation modifier
De façon assez surprenante, le lemme de Kőnig ne se généralise pas aux arbres non dénombrables ; voir l'article Arbre d'Aronszajn pour plus de détails.
Notes et références modifier
- (de) Dénes Kőnig, « Über eine Schlussweise aus dem Endlichen ins Unendliche », Acta Sci. Math. (Szeged), no 3(2-3), , p. 121-130 (lire en ligne)
- H. Hermes, « Hao Wang. Popular lectures on mathematical logic. Van Nostrand Reinhold Company, New York etc., and Science Press, Beijing, 1981, ix + 273 pp. », Journal of Symbolic Logic, vol. 47, , p. 908–909 (ISSN 1943-5886, DOI 10.2307/2273114, lire en ligne, consulté le )
- (en) Michael Sipser, Introduction to the Theory of Computation, , 3e éd., p. 187, Exercice 3.3.
- (en) Raymond M. Smullyan, « Trees and Ball Games », Annals of the New York Academy of Sciences, vol. 321, , p. 86–90 (ISSN 1749-6632, DOI 10.1111/j.1749-6632.1979.tb14111.x, lire en ligne, consulté le )
- (en) Franz Baader et Tobias Nipkow, Term Rewriting and All That, Cambridge (GB), Cambridge University Press, , 301 p. (ISBN 0-521-77920-0, lire en ligne), p. 15
