Lemme de König

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Tout arbre infini à branchement fini a une branche infinie.
Page d'aide sur l'homonymie Pour les articles homonymes, voir Théorème 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 :

« Tout arbre infini à branchement fini a une branche infinie. »

Il a des applications en logique, par exemple, pour démontrer le théorème de compacité de la logique propositionnelle[réf. nécessaire].

Historique[modifier | modifier le code]

Définitions[modifier | modifier le code]

La publication de König en 1927

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 | modifier le code]

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 | modifier le code]

Etant 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.

Compacité[modifier | modifier le code]

Le lemme de König permet de démontrer le théorème de compacité de la logique propositionnelle[réf. nécessaire]. Des résultats de compacité similaires peuvent être obtenus. Par exemple, 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].

Mathématiques récréatives[modifier | modifier le code]

Smullyan a utilisé le lemme de König pour démontrer la terminaison du jeu "arbres et boules"[3]. Le jeu fonctionne comme suit. Au début, la boîte contient une boule numérotée par un nombre positif. A 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écroient strictement). Par le lemme de König, l'arbre est fini.

Discussions[modifier | modifier le code]

Formulation alternative sans référence à l'infini[modifier | modifier le code]

Dans cette sous-section, on donne une autre reformulation[4] 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 \,R sur \,E est à branchement fini si pour tout x\in E l'ensemble \{y \in E\mid x R y\} est fini.

Une relation \,R est globalement finie si pour tout x\in E l'ensemble \{y \in E \mid x R^* y\} est fini, où \,R^* est la fermeture réflexive et transitive de \,R.

Une relation \,R est acyclique si x\,R^*\, y et y\,R^*\,x implique x\,=\,y.

L'ensemble des éléments accessibles par \,R est le plus petit ensemble tel que ((\forall y\in E)~ x R y \Rightarrow Acc_R(y)) \Rightarrow Acc_R(x) .

Axiome du choix[modifier | modifier le code]

La démonstration utilise l'axiome du choix dépendant, forme faible de l'axiome du choix.

Généralisation[modifier | modifier le code]

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.

Note et référence[modifier | modifier le code]

  1. (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)
  2. 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)
  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)
  4. (en) Franz Baader et Tobias Nipkow, Term Rewriting and All That, Cambridge University Press,‎ (ISBN 0521779200), p. 15

Voir aussi[modifier | modifier le code]