Un ensemble ordonné ayant un minimum est dit inductif si toute chaîne admet une borne supérieure.
Cette notion est importante dans l'étude des fonctions récursives mais aussi celle des jeux à deux joueurs.
Une arène est un graphe orienté bipartite, c'est-à-dire qu'on peut diviser ses sommets en deux catégories :
et aucun arc ne joint deux sommets de même catégorie.
Voici un exemple d'arène à 6 sommets. Les sommets d'Ève portent un numéro pair (even) :
Le sommet 1 (qui est un sommet d'Adam) a été colorié parce que le but du jeu est
Dans un jeu à deux joueurs (Adam et Ève), on commence par poser un pion sur un sommet de départ choisi à l'avance, par exemple le sommet 6 (qui est à Ève) :
Comme le sommet 6 appartient à Ève, c'est à Ève de jouer. Elle a le choix entre amener le pion en 1 (sommet grisé) et amener le pion en 5 (en haut à droite). Elle choisit par exemple de mener le pion en 5 :
Le pion est maintenant sur un sommet d'Adam. C'est donc à Adam de jouer. Il a le choix entre ramener le pion en 6 (départ) ou continuer à le faire avancer vers le sommet 4 (en haut à gauche). C'est ce qu'il choisit :
Le sommet 4 appartenant à Ève, c'est à son tour de jouer. Elle n'a en fait pas d'autre choix que d'avancer le pion en 1 (sommet gris) :
Comme elle a mené le pion sur un sommet gris, Ève a gagné le jeu. En fait, elle pouvait gagner du premier coup, en menant le pion (qui était en 6 à droite) directement à l'arrivée.
L'inclusion ⊆ est une relation d'ordre (et l'inclusion stricte ⊂ est une relation d'ordre strict). Cela signifie que si A⊆B et B⊆C alors A⊆C.
Si on considère une chaîne d'ensembles (en fait, de sous-ensembles d'un ensemble fini Ω) E0⊆E1⊆E2⊆...⊆En alors elle a une borne supérieure En : l'ensemble des parties de Ω est inductif pour l'inclusion (le plus petit élément est ∅).
Une fonction ƒ d'un ensemble inductif (E,≺) dans un ensemble inductif (F,⥽) telle que pour toute chaîne x0≺x1≺x2≺x3≺..., la chaîne y0⥽y1⥽y2⥽y3⥽... admet une borne supérieure qui est l'image par ƒ de la borne supérieure de x0≺x1≺x2≺x3≺..., est dite continue.
Démonstration laissée en exercice
Ce théorème (admis) permet de faire de l'induction structurelle.
Le plus petit point fixe de ƒ est la borne supérieure de la chaîne ⊥≺ƒ(⊥)≺ƒ(ƒ(⊥))≺ƒ(ƒ(ƒ(⊥)))≺...
Le théorème de Scott est important dans l'étude des fonctions récursives (voir plus bas).
On cherche à savoir depuis quelles positions de départ Ève a une stratégie gagnante sur cette arène :
Pour cela on construit une chaîne (pour l'inclusion) d'ensembles appelés attracteurs. Le premier est l'état final E0={1}. Ensuite
Avec l'arène ci-dessus, on obtient successivement
(il y a un arc allant de 4 à 1 et un arc allant de 6 à 1)
puis
(les arcs issus de 5 vont vers 4 et 6 qui sont déjà dans E1)
Mais ensuite, comme il n'y a aucun sommet d'Ève dont un successeur immédiat soit colorié en gris, on ne rajoute plus de sommet et l'algorithme se termine à ce stade. Avec E0={1}, E1={1,4,6} et E2={1,4,5,6} on a E0⊂E1⊂E2=E3=E4=...
La chaîne En est stationnaire. Ceci est la conséquence du fait que l'arène est finie et que l'ensemble des parties de ses sommets est inductif.
Avec 1 comme état final, Ève dispose donc d'une stratégie gagnante si, au départ, le pion est en 1, en 4, en 5 (dans ce cas c'est Adam qui joue en premier) ou en 6. Par exemple si le pion est en 5 (c'est Adam qui joue en premier),
Si par contre le pion est en 2, c'est Adam qui dispose d'une stratégie gagnante en ramenant systématiquement le pion en 2.
Un jeu d'accessibilité ne nécessite pas qu'il n'y ait qu'un seul état final, par exemple avec ces deux sommets
on trouve successivement
puis
et enfin
ce qui veut dire de quelle que soit la position initiale du pion, Ève dispose d'une stratégie gagnante lui permettant de mener le pion, soit en 2, soit en 4.
On joue maintenant à cet autre jeu d'accessibilité, où il s'agit de mener le pion au sommet grisé :
Montrer que cette fois-ci, Ève n'a pas de stratégie gagnante. On numérote ainsi les sommets pour calculer les attracteurs :
On s'intéresse à cette arène :
Jusqu'ici, les deux joueurs essayaient, l'un de mener le pion vers un sommet gagnant, l'autre de l'en empêcher. Mais on peut imaginer des sommets gagnants différents pour chaque joueur.
Adam essaye d'amener le pion vers le sommet rouge, et Ève essaye non seulement d'empêcher que le pion aille sur le sommet rouge, mais en plus d'amener le pion vers le sommet bleu :
On calcule séparément les attracteurs.
Avec la définition ci-dessus, les sommets attracteurs pour Ève sont les sommets bleus :
On rappelle que cela signifie que si au départ, le pion est sur un des sommets bleus, Ève dispose d'une stratégie gagnante.
En intervertissant les rôles d'Adam et Ève dans l'algorithme on obtient les sommets rouges sur lesquels poser le pion au départ pour qu'Adam dispose d'une stratégie gagnante :
On constate qu'aucun sommet n'est à la fois bleu et rouge :
Par contre il y a deux sommets qui ne sont ni bleu, ni rouge ; si on pose le pion sur un de ces sommets, ni Adam ni Ève ne disposent d'une stratégie gagnante. Si chacun d'entre eux joue au mieux, il y a une partie nulle, où le pion fait infiniment souvent des allers-retours entre les deux sommets blancs.
Une fonction f de E dans F est moins définie qu'une fonction g de E dans F, si pour tout x de E tel que f(x) est défini, g(x) est aussi défini et f(x)=g(x).
On note f⊑g si f est moins définie que g.
Une fonction récursive est le plus petit point fixe d'une fonctionnelle continue pour la relation d'ordre produit à partir de ⊑.