Mettre en relation des entités de toute nature est une opération commune et universelle. Le développement rapide des techniques (rebaptisées technologies par tropisme anglophile) n'a-t-il pas transformé notre planète en monde connecté ? Connecter, associer, relier, joindre, etc. sont des opérations incontournables, fondamentales et omniprésentes en informatique et en mathématiques.
Les relations permettent de modéliser des systèmes complexes, de résoudre des problèmes pratiques et de concevoir des algorithmes efficaces. Ce concept est au cœur même des bases de données relationnelles, dans lesquelles les données sont organisées en tables codant des relations entres ensembles de données. Les requêtes sont alors fondées sur des opérations permettant de combiner ces différentes relations. Les réseaux de télécommunication sont modélisés par des graphes dans lesquels les relations entre objets connectés jouent un rôle clef, les algorithmes de routage s'appuyent sur ces relations pour déterminer des chemins optimaux entre deux nœuds selon les débits et/ou la latence d'une connection, etc. Les fonctions constituent souvent des objets élémentaires des langages de programmation et sont à la base de l'apprentissage automatique, etc.
Encore une fois, nous allons commencer par exposer un problème ludique dont l'analyse et la résolution mettrons en évidence l'utilité, la versatilité et la force des concepts introduits dans ce chapitre :
Deux joueurs doivent à tour de rôle, retirer une, deux ou trois allumettes d'un tas jusqu'à ce qu'il soit vide. Le joueur qui ne peut plus retirer d'allumettes car le tas est vide a perdu.
Existe-t-il une stratégie gagnante à ce jeu ?
Relations, correspondances
Définitions
On généralise aisément la notion de graphe défini sur le produit cartésien de deux ensembles et au produit cartésien d'un nombre arbitraire d'ensembles :
Soit un entier non-nul et le produit cartésien de ensembles . On appelle -graphe, toute partie .
On parle de relation unaire quand , de relation binaire quand — auquel cas on retrouve naturellement le vocable usuel de graphe plutôt que -graphe — et de relation ternaire quand , etc.
Exemples :
Les couples* au sens propre et au sens de la théorie des ensembles formés par un homme et une femme, définissent une relation binaire entre des éléments particuliers de l'ensemble des hommes et de l'ensemble des femmes.
Pour définir une relation de couple moins hétéronormée, il suffit de la considérer sur le produit cartésien d'un même ensemble d'êtres humains.
Pour filer la métaphore familiale, la relation de parentalité est un exemple de relation ternaire entre hommes (ensemble ), femmes (ensemble ) et enfants (ensemble ), donc sur le produit cartésien , etc.
La possibilité ou non d'assembler deux pièces d'un puzzle définit une relation binaire entre les pièces du puzzle sur le produit cartésien où désigne l'ensemble des pièces du jeu.
Le jumelage entre communes françaises et étrangères constitue une relation binaire. Ainsi la ville de La Garde est jumelée avec la ville de Montesarchio en Italie ainsi que la ville de Spa en Belgique.
Relations -aires et -graphes sont deux facettes d'une même pièce. Il est clair que la donnée d'un -graphe défini sur un produit cartésien d'ensembles , définit indirectement une relation -aire sur ces ensembles. En effet si , on lui associe naturellement la relation -aire définie sur par
Parmi tous les types de relations, les relations binaires sont les plus utilisées et font l'objet d'une attention toute particulière. On note généralement une relation binaire de manière infixe , plutôt que préfixe , mimant ainsi plus fidèlement l'expression est en relation avec .
Une section spécifique de ce chapitre sera consacrée aux relations binaires entre éléments d'un même ensemble, i.e. .
Dans le cadre de cette étude, une relation binaire entre deux ensembles et est souvent rebaptisée correspondance, à des éléments de , on fait correspondre des éléments de . Sa définition s'appuie directement sur un graphe sans plus faire référence à un prédicat :
On représente une correspondance à l'aide d'un diagramme sagittal * En forme de flèche. qui en fournit une interprétation concrète. Les ensembles de départ et d'arrivée sont matérialisés par des patates et chaque couple du graphe par une flèche reliant à :
La flèche a pour premier mérite de mettre en évidence l'asymétrie de la construction puisque
Diagramme sagittal du jumelage de certaines villes.
Le diagramme sagittal ci-dessus illustre le jumelage de quelques villes. On constate que les villes de Mazaugues et Signes ne sont pas jumelées avec des villes étrangères et que les villes étrangères de Liski et Vegen ne correspondent à aucun jumelage.
Décrivez en extension les ensembles de départ, d'arrivée, le graphe ainsi que l'ensemble de définition et l'image de la correspondance définie par le diagramme ci-dessus.
Nous avons les ensembles suivants :
Nous avons noté une correspondance alors que dans la littérature mathématique, une correspondance est souvent codée par un triplet (on pourrait également considérer le codage ). Formellement, ces différentes écritures définissent des modèles distincts, mais le triplet joue simplement le rôle d'une boite à trois casiers pour y ranger les données nécessaire à la modélisation de l'objet, ces trois modèles sont donc équivalents et interchangeables. La motivation de la position infixe plutôt que postfixe ou préfixe du graphe dans ce cours est à vocation didactique, le graphe est la description abstraite des flèches du diagramme qui se situent entre les ensembles et . L'écriture usuelle postfixe est évidemment justifiée par le fait que nous lisons de gauche à droite et qu'il est logique de présenter les deux ensembles et avant de parler du graphe qui en dépend.
En inversant le sens des flèches du diagramme sagittal d'une correspondance et en inversant les rôles des ensembles de départ et d'arrivée , on obtient une nouvelle correspondance appelée correspondance réciproque de et on la note .
Le choix de la notation, qui n'est évidemment pas un quotient dans ce contexte, sera légitimé une fois étudiées la loi de composition des correspondances et ultérieurement les propriétés structurelles des lois de composition dans le chapitre consacré aux groupes.
Écrivez formellement la définition de la correspondance réciproque d'une correspondance .
Soit une correspondance. On appelle correspondance réciproque de la correspondance la correspondance notée où est le graphe défini par
Dans le plan réel , on considère un cercle de rayon et de centre , i.e. l'ensemble des points du plan réel qui sont à distance du point . Définissez formellement la correspondance dont le graphe est ce cercle. Quelle est sa correspondance réciproque ?
Si l'on note , il s'agit de la correspondance dont le graphe est défini par
On vérifie aisément que
Images directes et réciproques
Si est une correspondance, l'image directe par d'une partie de l'ensemble de départ, notée , est le sous-ensemble des éléments de l'ensemble d'arrivée atteints par les éléments de . Ainsi pour la partie de l'exemple introductif, on a
Réciproquement, l'image réciproque par d'une partie , notée , est l'image directe de pour la correspondance réciproque . Toujours avec l'exemple introductif et en considérant , on a
Plus formellement :
Soit une correspondance et une partie de . On appelle image directe de par le sous-ensemble de noté et défini par
Soit une correspondance et une partie de . On appelle image réciproque de par l'image directe de pour la correspondance réciproque de :
Si est réduit à un singleton , tout élément est appelé antécédent de .
D'après cette définition, on a donc . Notons qu'il est bien plus efficace de garder une image mentale d'une correspondance sous forme de diagramme sagittal pour retrouver aisément toutes ces définitions que de les apprendre par cœur. Pour reprendre la métaphore musicale de l'introduction de ce cours, il est beaucoup plus simple de retenir et fredonner la mélodie d'une chanson pour en retrouver la partition plutôt que d'apprendre cette partition.
Quel est le graphe de la correspondance réciproque de la correspondance définie dans cet exercice ?
Composition des correspondances
Le terme de correspondance est familier du lecteur qui a voyagé et a dû changer de train durant son périple. Pour illustrer le propos, on modélise une fiche horaire entre deux villes par une correspondance où les ensembles et contiennent respectivement les heures de départ et d'arrivée des différents trains reliant les deux villes et . Si l'on dispose d'une deuxième correspondance reliant les villes et , on définit implicitement une fiche horaire entre les villes et en passant par dont la modélisation mathématique n'est autre que la composition des correspondances et . Il suffit de rabouter les flèches qui arrivent en avec celles qui en partent et d'observer pour chaque élément de quels sont les éléments correspondants dans :
Diagramme sagittal de correspondances et .
Pour filer la métaphore ferrovaire, on observe dans le diagramme ci-dessus qu'il y a deux trains qui partent à h de la ville et permettent d'arriver à destination à la ville à h ou h en passant par la ville . Il s'agit bien d'une correspondance entre les villes et Il ne reste qu'à la définir formellement.
Soit et deux correspondances. On appelle composition des correspondances et la correspondance dont le graphe est défini par
On note cette correspondance (que l'on lit rond) et
Avec l'exemple du diagramme sagittal ci-dessus, on a :
Il ne faut pas être perturbé par l'ordre dans lequel on écrit la composition alors que la correspondance s'applique avant la correspondance . Nous mettons souvent et très logiquement la chronologie des événements que nous décrivons en cohérence avec l'ordre de lecture, donc de gauche à droite chez les occidentaux. La notation des correspondances étant préfixe et comme la correspondance s'applique après la correspondance , elle agit sur soit . Si les correspondances avaient été notées de manière postfixe, i.e. au lieu de , tout rentrerait dans l'ordre…
Soit , et trois correspondances. Vérifiez que
Cette propriété est appelée associativité de la composition.
Quel est le graphe de la correspondance où est la correspondance définie dans cet exercice ?
Soit et deux correspondances. Démontrez que
Fonctions, applications
Fonctions
Une fonction désigne un type de correspondance particulière telle qu'il y a au plus une flèche qui part d'un élément . C'est la transposition mathématique du terme largement employé dans le langage courant. Le montant à régler au parcmètre est fonction de la durée de stationnement, votre note au contrôle continu de l'ecue de Mathématiques pour l'Informatique est fonction du nombre de bonnes réponses, etc. Dans ce contexte, il ne peut y avoir qu'un seul montant à régler qui correspond avec la durée de stationnement et qu'une seule note associée au nombre de bonnes réponses.
Ainsi, l'exemple de la figure 1n'est pas une fonction car, entre autres, la ville de La Garde est en correspondance avec deux villes étrangères. La condition à respecter pour qu'une correspondance définisse une fonction s'exprime formellement de la manière suivante :
La façon d'exprimer mathématiquement au plus dans l'expression formelle ci-dessus peut sembler surprenante, mais elle répond bien à la contrainte : si deux couples avec la même première projection appartiennent au graphe de la correspondance, alors leurs deuxièmes projections sont nécessairement égales, autrement dit ces deux couples sont égaux.
Nous n'avons pas encore étudié formellement le cardinal d'un ensemble fini, mais nous aurions pu définir alors une fonction à l'aide de la propriété suivante plus simple à interpréter :
La définition d'une fonction via l'assertion est préférable car elle ne nécessite pas l'outillage des entiers naturels et de la cardinalité.
Exprimez formellement qu'une correspondance n'est pas fonctionnelle en écrivant la négation de l'expression . Réécrivez la définition d'une fonction en remplaçant l'expression par sa contraposée.
La négation de la proposition est
La contraposée de la proposition est
Dans le diagramme ci-dessous nous représentons la fonction qui associe le taux de tva à une activité ou une vente (si elle est assujettie à cette taxe).
Diagramme sagittal d'une fonction .
Comme on peut le constater par l'absence d'une flèche, les soins d'une carrie dentaire ne sont pas assujetis à la tva (les actes médicaux ne sont pas soumis à cette taxe). On aurait pu rajouter un taux de dans l'ensemble d'arrivée et inclure le couple au graphe , mais il est plus cohérent de le modéliser sans cet arc puisque la tva ne s'applique pas aux actes médicaux. On note également que certains taux de tva ne correspondent à aucune activité/vente.
Soit , d'après la caractérisation d'une fonction , soit l'image directe du singleton est l'ensemble vide , soit c'est un singleton . Ceci justifie la définition suivante :
Soit une fonction, et l'unique élément de tel que . On dit alors que est définie en et que est l'image de par notée .
L'ensemble de définition de la fonction dont le diagramme sagittal est donné en figure 3 est :
é
Dans l'autre sens, si l'on se donne et que la partie n'est pas vide, elle n'est pas nécessairement réduite à un unique élément, peut donc posséder plusieurs antécédents.
La fonction associée au diagramme de la figure 2 n'est pas définie en carrie. L'image de cinéma est , ce que l'on écrit . Il est important de réaliser que la notation n'a de sens que si la fonction est définie en , en revanche a toujours un sens, c'est l'image directe du singleton par la correspondance qui serait égale à l'ensemble vide dans le cas où la fonction n'est pas définie en . Par définition un élément admet au plus une image par la fonction , mais un élément peut avoir plusieurs antécédents. Par exemple smartphone et alcool sont deux antécédents de . Les valeurs , et n'admettent pas d'antécédents.
Le lecteur averti pourrait contester ce modèle mathématique simplifié en avançant que la tva de certains produits dépend du lieu de consommation. En effet, la tva appliquée à une glace est différente selon qu'elle est consommée sur place ou emportée . Autrement dit, il faudrait deux flèches pour la glace, une vers la valeur , l'autre vers le bon modèle mathématique serait alors la correspondance. Ce modèle serait tout de même incomplet, puisque l'information codant le fait que la glace est consommée ou non sur place n'est pas intégrée au modèle. Ce type de modélisation sera étudié en détail dans l'enseignement de théorie des graphes de la licence.
On utilise souvent l'écriture pour définir une fonction même si son graphe n'est pas spécifié. Cette omission est justifiée par le fait que étant une fonction, elle est définie en tout élément de son domaine de définition et son graphe est par conséquent
Parfois l'image d'un élément de par une fonction peut être calculée. En effet, nous verrons dans un prochain chapitre que les ensembles peuvent être équipés de lois de composition internes, comme l'addition ou la multiplication sur par exemple. Dans ce cas, cela induit une vision dynamique de la fonction* l'utilisation massive de flèches renforce également cette dynamique., comme s'il s'agissait d'une machine qui traitait la matière première en entrée et qui fournissait le produit fini en sortie :
Vision schématique d'une fonction calculable.
Par exemple la fonction qui calcule la circonférence d'un cercle en fonction de son rayon est définie par , dont le graphe est l'ensemble des couples tels que . Dans de tels cas, on complète souvent l'expression avec l'expression du calcul qu'elle effectue :
Il faut noter la différence entre la flèche qui relie les ensembles de départ et d'arrivée et celle munie d'un talon qui relie un élément de l'ensemble de départ à son image (quand elle existe) dans l'ensemble d'arrivée.
Il n'est pas toujours possible de calculer une fonction, c'est-à-dire d'exprimer l'image d'un élément par un processus calculatoire. La théorie de la calculabilité enseignée en master d'informatique a précisément pour objectif d'étudier cette question et d'en tirer des conséquences sur ce que nous pouvons réaliser ou non avec des ordinateurs.
On considère la fonction définie par . Quel est son domaine de définition ? Même question pour . Même question pour et .
Applications
Une fonction telle que , est appelée application de dans L'ensemble des applications de dans est noté
La notation peut sembler étrange à première vue. Nous verrons pourquoi il s'agit d'une bonne notation dans le chapitre consacré à la combinatoire.
La fonction définie en est bien une application, elle est en effet définie en tout nombre réel . En revanche, la fonction
n'est pas une application puisqu'elle n'est pas définie en . Son domaine de définition est l'ensemble . Notons que si cette fonction n'est pas définie en , ce n'est pas pour un quelconque interdit, mais parce qu'elle est définie via son graphe qui est constitué des couples satisfaisant l'équation Ce graphe ne contient donc aucun couple tel que ou .
Exprimez le graphe de la fonction définie en sans utiliser d'écriture en compréhension.
Il suffit de retirer de l'ensemble de tous les couples de réels ceux dont l'uneoul'autre des projections est nulle :
On dit que deux applications et coïncident sur une partie si elles sont égales en tout élément de :
Soit une application et une partie de . L'application de qui coïncide avec sur est appelée restriction de à et notée .
Il est très facile d'obtenir une application à partir d'une fonction qui n'est pas définie en tout point de son ensemble de départ . Il suffit de remplacer par le domaine de définition de cette fonction, autrement dit de considérer sa restriction . Dans le cas de la fonction de la figure 2, il suffit d'éliminer carrie de l'ensemble , i.e. le nouvel ensemble de départ est :
Diagramme sagittal de l'application obtenue par restriction de cette fonction à son domaine de définition.
Quant à la fonction définie en , il suffit d'éliminer pour en faire une application, il s'agit de la fonction définie par Attention, . En effet, une fonction est avant tout une correspondance, c'est-à-dire un triplet, or deux triplets sont égaux si et seulement si leurs trois projections sont égales respectivement. Autrement dit deux correspondances sont égales si et seulement si elles ont même ensemble de départ, même ensemble d'arrivée et même graphe
Soit des ensembles tels que et . On considère deux applications et . Quelle définition proposez-vous pour exprimer que est un prolongement de selon votre acception du terme prolongement ?
On dit que est un prolongement de si et seulement si coïncide avec sur .
Fonctions et applications sont deux concepts très voisins en théorie des ensembles. Historiquement le terme fonction était plutôt utilisé pour exprimer qu'une quantité physique variait selon une autre quantité physique (autrement dit les fonctions numériques de dans ) alors que le terme application avait une connotation plus géométrique, comme une carte. Le terme anglo-saxon map qui est la traduction du mot application est explicite à ce sujet.
La confusion entre fonction et application dans les textes mathématiques est courante et distinguer les deux peut sembler superfétatoire. En effet, quel est l'intérêt de considérer comme ensemble de départ un autre ensemble que l'ensemble de définition d'une fonction puisqu'elle n'est pas définie ailleurs ? Le premier est d'attirer l'attention sur cet ensemble de définition qu'il ne faut surtout pas négliger, et l'autre est que les questions qui vont suivre sur les propriétés remarquables des applications se justifient naturellement en considérant la correspondance réciproque qui peut être ou non une fonction, une application. Quoi qu'il en soit, il est très facile de transformer une fonction en application, il suffit de considérer que son ensemble de départ est son ensemble de définition.
Si la correspondance réciproque d'une fonction est elle-même une fonction, elle est appelée fonction réciproque. La section suivante est consacrée à l'étude des correspondances réciproques et de leur statut.
Les correspondances réciproques des correspondances des figures 1 & 2 définissent-elles des fonctions ? La fonction de dans définie par est-elle une application ? Sa correspondance réciproque est-elle une fonction ?
Injections, surjections, bijections
Quand on se donne une correspondance, il est naturel de s'intéresser à la correspondance réciproque (voir exercice), ne serait-ce que parce que sa construction est extrêmement simple, il suffit d'inverser le sens des flèches et d'échanger le rôle de l'ensemble de départ et de l'ensemble d'arrivée. L'étude de la réversibilité du processus est intéressante, en particulier quand il s'agit d'une fonction calculable.
On réalise immédiatement en construisant la correspondance réciproque de l'application de ce diagramme que celle-ci n'est plus une application, (ni , ni n'ont d'image), ni même une fonction (deux flèches partent de la valeur ). Quelles sont les conditions que doit satisfaire une application pour que sa correspondance réciproque soit une fonction, ou mieux une application ?
Pour que la correspondance réciproque soit une fonction, il ne faut pas que deux éléments distincts et de l'ensemble de départ aient la même image (comme smartphone et alcool qui ont la même tva à ), sans quoi la correspondance inverse aurait deux flèches partant de , l'une vers et l'autre vers ce qui est interdit pour une fonction.
Injections
Une application est dite injective, ou injection, si deux éléments quelconques et distincts de ont des images distinctes dans :
Dans ce cas on écrit .
La contraposée de la proposition logique est très souvent utilisée pour démontrer qu'une application est injective, à savoir
Il est en effet plus aisé de faire des déductions en partant d'une égalité que de la négation d'une égalité.
Indépendamment de l'étude des correspondances réciproques, l'injectivité est une propriété fort intéressante et souvent nécessaire pour modéliser certaines contraintes. Pour établir une communication téléphonique, on cherche a priori à exclure la possiblité que deux numéros de téléphone soient associés à la même carte sim* Subscriber Identity Module, la table de correspondance dont disposent les opérateurs n'est ni plus ni moins qu'une application injective. De la même manière, deux numéros de sécurité sociale distincts sont associés à des individus distincts, etc.
À gauche une application injective, à droite non.
Soit et deux ensembles tels que . L'application définie par est une injection appelée injection canonique. Si , cette application est appelée application identité de et on la note .
La correspondance réciproque d'une injection est donc une fonction. Si elle est définie en , autrement dit s'il existe tel que , alors est l'image de par et on la note .
Si l'on veut que cette fonction réciproque soit également une application, il faut que tous les éléments de l'ensemble d'arrivée soient atteints par une flèche de manière à ce que tous les éléments de l'ensemble aient une image pour la correspondance réciproque.
Surjections
Une application est dite surjective, ou appelée surjection, si tout élément admet (au moins) un antécédent :
Dans ce cas on écrit .
Cette propriété peut être satisfaite sans que l'application soit injective, tout élément de l'ensemble d'arrivée peut donc avoir plusieurs antécédents. C'est le cas de l'application à gauche dans la figure ci-dessous, elle est surjective mais pas injective. Celle de droite n'est ni injective ni surjective.
À gauche une application surjective, à droite non. Aucune n'est injective.
Bijections
Une application est dit bijective, ou appelée bijection, si elle est à la fois injective et surjective. Dans ce cas on écrit . L'ensemble des bijections de dans est noté .
On aurait tout aussi bien pu donner la définition suivante : une application est bijective si et seulement si sa correspondance réciproque est une application.
Une bijection associe de manière unique chaque élément d'un ensemble à un autre et réciproquement. Si les ensembles de départ et d'arrivée sont par exemple constitués respectivement par des étudiant⋅e⋅s de sciences et de lettres, disposer d'une bijection revient à créer des couples monogames où chacun⋅e a exactement un⋅e petit⋅e ami⋅e :
Diagramme sagittal d'une application bijective.
Les trois notions, injection, surjection et bijection sont absolument fondamentales en mathématiques et en informatique. Ces objets servent non seulement à la modélisation mais également à compter. L'existence d'une solution à une équation du type d'inconnue est liée à la surjectivité de et l'unicité d'une solution à l'injectivité de . Avant même d'avoir défini ce qu'est un ensemble fini* la compréhension intuitive du concept est suffisante ici., il semble évident que si les ensembles de départ et d'arrivée sont finis et en bijection, ils ont le même nombre d'éléments. Il n'est pas rare que l'on dénombre les éléments d'un ensemble en établissant une bijection avec un autre ensemble dont on connaît le cardinal. Dans le même ordre d'idées et intuitivement, disposer d'une injection (resp. une surjection) entre un ensemble et un ensemble impose que l'ensemble est plus grand que (resp. plus petit que ).
Soit et deux ensembles. Démontrez que les deux assertions suivantes sont équivalentes
Il existe une injection de dans ;
Il existe une surjection de dans .
Un premier résultat important sur les bijections est lié à la composition des applications.
La composée de deux applications injectives (resp. surjective, bijective) est injective (resp. surjective, bijective).
Notons et ces applications. Dans une premier temps, supposons que et soient injectives. Soit et deux éléments de tels que . On a donc ce qui entraîne que puisque est injective puis que puisque est injective. Autrement dit est injective.
Supposons à présent que et soient surjectives. Soit , il nous faut montrer qu'il admet un antécédent par , autrement dit qu'il existe un élément tel que . Comme est surjective, on sait que admet un antécédent par , c'est-à-dire tel que , mais étant surjective également, admet lui aussi un antécédent pour , autrement dit . Par conséquent, on a et est donc surjective.
Soit et deux applications. Montrez que si est injective alors est nécessairement injective et que si est surjective alors est nécessairement surjective.
Notons et ces applications. Supposons que soit injective. Alors pour tout tel que , on a ce qui impose que c'est-à-dire que soit injective. Supposons que soit surjective. Alors pour tout , il existe tel que , donc admet au moins comme antécédent par qui est par conséquent surjective.
Une application est bijective si et seulement s'il existe une application telle que
Dans ce cas, l'application est unique, il s'agit de l'application réciproque de appelée bijection réciproque.
S'il existe qui satisfait , alors d'après la proposition précédente, est surjective comme et elle est injective comme donc bijective. Symétriquement est bijective. D'autre part, si est bijective, alors il existe une application qui satisfait , c'est l'application qui a tout élément de associe son unique antécédent par . On conclut avec l'unicité, considérons deux applications et qui satisfont , alors
Et on en déduit que .
Soit une application. On peut donc composer avec elle même puisque les ensembles de départ et d'arrivée sont confondus. Par convention, on note avec . L'application est appelée -ème itérée de .
Une application bijective telle que est appelée involution ou dite involutive, autrement dit elle est sa propre bijection réciproque. Par exemple l'application définie par .
Une application telle que est dite idempotente. Par exemple la valeur absolue dans , en effet .
Soit et deux bijections. Démontrez que
Généralisez à la composition de applications où pour tout , avec :
Revenons aux images directes et réciproques dans le cas où la correspondance est une fonction . Alors l'égalité devient :
et on a
On rappelle que désigne l'ensemble des parties d'un ensemble . Soit et pour l'application définie par le diagramme sagittal ci-dessous. On a et .
Diagramme sagittal d'une application L'ensemble est une partie de et l'ensemble une partie de
Avec la fonction définie par le diagramme sagittal de la figure 8, calculez
,
,
,
,
.
Attention à ne pas confondre avec , ainsi avec l'exemple de la figure ci-dessus, on a alors que Dans l'autre sens, il ne faut surtout pas confondre avec , la confusion est encore plus grave. En effet, autant l'image réciproque existe toujours, autant l'expression n'a de sens que si la correspondance réciproque de est bien une fonction et définie en de surcroît ce qui impose que soit injective et que .
Cependant, les abus de langage sont légions et il n'est pas rare de voir écrit au lieu de quand bien même la fonction n'est pas injective. Tout ceci est sans conséquence si l'on comprend ce que l'on fait et les objets que l'on manipule.
De la même manière que l'on transforme facilement une fonction en application en remplaçant son ensemble de départ par le domaine de définition , on transforme une application quelconque en surjection en remplaçant son ensemble d'arrivée par son image .
Soit une application. On dit qu'une partie est stable par si elle vérifie et invariante par si on a l'égalité .
Si est tel que , on dit que c'est un point fixe de par .
Soit et deux ensembles et et deux applications de . Tout tel que est appelé solution de l'équation d'inconnue.
C'est principalement quand les ensembles sont munis d'opérations algébriques que l'on étudie des équations, par exemple l'addition et la multiplication dans . Ces opérations permettent de transformer les expressions de ces applications pour déterminer la ou les solutions si elles existent. Par exemple, si on considère l'application définie par et que l'on cherche ses points fixes, on doit résoudre l'équation
et la fonction de la définition ci-dessus est l'application identité de dans . Quelques manipulations algébriques légitimées par les propriétés de l'addition et de la multiplication de l'addition dans (les trouver en guise d'exercice) fournissent successivement les identités équivantes suivantes
Dans un anneau intègre et a fortiori dans un corps, un produit de facteurs est nul si et seulement si l'un au moins des facteurs est nul, il y a donc deux solutions à cette dernière équation. Ce sont les deux points fixes de l'application et l'ensemble des solutions de l'équation est le sous-ensemble de .
Soit et deux ensembles. On appelle famille d'éléments d'un ensemble et d'ensemble d'indexation, toute application . L'image d'un élément est notée plutôt que , et l'ensemble image de l'application définit l'ensemble des éléments de la famille. On note une telle famille .
Dans cette définition, rien ne distingue une famille d'une application, si l'on excepte l'usage des lettres et pour désigner respectivement l'ensemble de départ et d'arrivée en lieu et place des usuels et . Il s'agit ici de formaliser l'écriture mathématique indicielle pour désigner un élément d'un ensemble . Formellement on définit la famille et on écrit simplement au lieu de .
Nous n'avons pas encore étudié l'ensemble des entiers naturels, mais il est plus pertinent de ne pas différer les définitions suivantes :
On appelle suite d'éléments d'un ensemble toute famille d'éléments de indexée par l'ensemble des entiers naturels , i.e. toute application de dans .
On appelle système d'éléments d'un ensemble toute famille d'éléments de dont l'ensemble d'indexation est un ensemble fini. On appelle séquence ou suite finie d'éléments de tout système dont l'ensemble d'indexation est un intervalle⟦⟧ de .
Certains auteurs donnent des définitions différentes des suites. L'existence de plusieurs définitions pour un même objet peut sembler déroutant mais ne pose aucun problème tant que l'on rappelle le sens que l'on donne à cet objet dans un discours mathématique. Ces rappels préalables sont indispensables si la définition utilisée n'est pas celle qui est communément admise.
Ce qui importe dans ces trois notions est l'ordre dans lequel les éléments de ces trois types de familles sont rangés. C'est explicite pour une séquence ou une suite et pour un système dont l'ensemble d'indexation est totalement ordonné. C'est implicite pour un système dont l'ensemble d'indexation n'est pas ordonné, puisque étant fini, il est en bijection avec , ses éléments peuvent donc être ordonnés via cette bijection.
Considérons le système muni de l'ensemble d'indexation équipé de l'ordre alphabétique. On peut donc écrire , , etc.
Nous avons vu au chapitre dédié à la logique des prédicats et la théorie zf, comment était construit le produit cartésien de deux ensembles et et comment on pouvait le généraliser au produit cartésien de ensembles . On peut désormais procéder autrement avec une construction à la fois plus simple et plus générale. C'est tout simplement le produit fini de la séquence d'ensemble d'indexation .
Soit une famille d'ensembles. On appelle ensemble produit de la famille l'ensemble définit ci-dessous et noté
La fonction définie par
où
est appelée i-ème projection.
Si l'on se donne une application surjective , on peut faire une réindexation de la famille i.e.
Autres opérations.
Soit et deux familles d'ensembles. On a
Soit et deux familles d'ensembles de même ensemble d'indexation telles que . Alors
Soit une famille de parties d'un ensemble . Alors
Soit une partie d'un ensemble . On appelle fonction indicatrice de , la fonction 𝟙 définie par
𝟙
Images et images réciproques d'une réunion et d'une intersection.
Soit une application, une famille de parties de l'ensemble et une famille de parties de l'ensemble . On a
L'image réciproque d'une réunion (ou d'une intersection) est donc toujours la réunion (ou l'intersection) des images réciproques. En revanche, si l'image d'une réunion est bien la réunion des images, l'image d'une intersection n'est pas l'intersection des images.
Dans le plan euclidien, tracez les deux demi-droites et définies par
Montrez que . Considérons l'application définie par
. Calculez . Quelle propriété une application devrait satisfaire pour que l'inclusion en soit une égalité ?
Partition d'un ensemble
Étudier un ensemble en le découpant en parties cohérentes est très utile. On peut par exemple partitionner la population mondiale selon les pays, partitionner les instruments de musique selon qu'ils sont à vent, à corde ou à percussion, etc. Les trois propriétés mathématiques exigées pour ce découpage sont très naturelles : les parties ne doivent pas être vides, deux parties différentes ne doivent pas contenir d'éléments communs et la réunion de toutes ces parties est l'ensemble tout entier :
On appelle partition d'un ensemble toute famille de parties de qui satisfait les trois conditions suivantes :
,
,
.
Les parties sont appelées les classes de la partition.
En anticipant sur la section suivante, une partition d'un ensemble est intimement liée à une relation d'équivalence sur . Si est une partition de , on vérifie aisément que la relation sur définie par
est une relation d'équivalence. Les classes de pour cette relation sont évidemment les , d'où la terminologie dans la définition. Réciproquement, si on a une relation d'équivalence définie sur un ensemble les classes d'équivalences forment une partition de .
Une famille d'ensembles dont la réunion contient un ensemble s'appelle un recouvrement de (à la manière des tuiles d'un toit qui le recouvrent et se chevauchent par endroit). Une partition est donc un cas particulier de recouvrement.
Relations binaires sur un ensemble
Définition et propriétés remarquables
Comme nous l'avions annoncé dans la première section, une relation binaire sur un ensemble est tout simplement une relation binaire qui met en relation des éléments d'un même ensemble . Ce modèle est si versatile et fécond, qu'il a engendré à lui seul une théorie, la théorie des graphes. Cette théorie connaît des développements permanents, elle est enseignée dans toutes les formations d'informatique et à tous niveaux. C'est l'un des modèles les plus utisés dans cette discipline scientifique, il est donc très important de le comprendre et le maîtriser. Son rôle universel justifie d'en donner une définition spécifique, même s'il s'agit d'un cas particulier de la définition d'une relation -aire.
On appelle relation binaire sur un ensemble tout prédicat à deux variables dans l'ensemble L'ensemble est appelé le graphe de la relation binaire .
On rappelle que l'on note souvent une relation binaire de manière infixe, i.e. au lieu de . Les relations binaires ne sont que des cas particuliers de correspondances, on les représente également par leurs diagrammes sagittaux, en se contentant cette fois des flèches qui relient les éléments entre eux, autrement dit du graphe. Le schéma de la patate pour représenter l'ensemble de référence devient superflu. Un couple dans ce diagramme est alors représenté par une boucle.
Par exemple :
Graphe d'une relation binaire sur l'ensemble .
Décrivez en extension le graphe de la relation binaire décrite dans le diagramme sagittal ci-dessus.
C'est l'ensemble
Comme nous l'avions déjà noté dans la section consacrée aux relations -aires générales, une relation définit un graphe et réciproquement, ce sont deux façons équivalentes de considérer le même concept mathématique. Dans le cadre de la théorie des graphes, on préfère définir la relation a posteriori et mettre l'accent sur le graphe, d'où la définition suivante employée dans ce cadre.
On appelle graphe, tout couple où est un ensemble dont les éléments sont appelés sommets de et dont les couples sont appelés arcs de .
Il faut noter dans cette définition que ne désigne plus l'ensemble des couples définis sur un produit cartésien, rôle dévolu à , mais le couple constitué de l'ensemble des sommets et de l'ensemble des arcs . Le graphe est dit fini ou infini suivant la cardinalité de l'ensemble de ses sommets.
La relation associée au graphe au sens de cette définition est alors caractérisée par la proposition suivante :
Les relations binaires, et par conséquent les graphes au sens de la définition ci-dessus, peuvent posséder des propriétés remarquables.
Soit une relation binaire définie sur un ensemble . On définit les propriétés suivantes :
On parlera donc de relation réflexive ou de graphe réflexif, de relation symétrique ou de graphe symétrique, etc.
L'asymétrie est plus contraignante que l'antisymétrie, elle est parfois qualifiée d'antisymétrie forte (par opposition l'antisymétrie est alors qualifiée d'antisymétrie faible). Dans un graphe asymétrique, il ne peut y avoir de boucle alors que c'est possible dans un graphe antisymétrique.
Il faut immédiatement noter que les propriétés 4, 5 et 7 ne sont pas les négations des propriétés 1, 2 et 3 respectivement. Par exemple, la négation de la réflexivité s'écrit :
Autrement dit, il suffit d'un unique élément dans qui n'est pas en relation avec lui-même pour que la propriété de réflexivité ne soit pas satisfaite, quand bien même tous les autres éléments de sont en relation avec eux-mêmes. L'antiréflexivité est bien plus contraignante, et le préfixe anti est là pour le signifier, une relation antiréflexive impose qu'aucun élément ne soit en relation avec lui-même. Similairement, une relation binaire peut ne pas être symétrique (resp. transitive) sans pour autant être antisymétrique (resp. antitransitive).
Écrivez la négation logique de chacune des propriétés 2 à 7.
Quelles propriétés sont satisfaites par la relation binaire définie par le diagramme sagittal précédent ?
Pour chacune des propriétés 1, 2 et 3, trouvez un exemple de relation binaire sur un ensemble à deux éléments, qui satisfait :
Une seule des trois propriétés,
Deux des trois propriétés,
Les trois propriétés.
et dessiner son graphe.
Faites de même avec une relation sur un ensemble à trois éléments. Listez toutes les relations binaires sur une ensemble à 1 élement. Quelles propriétés satisfont ces relations ?
Il est courant quand on dispose d'une relation binaire sur un ensemble de considérer sa fermeture transitive. L'idée est simple et naturelle, l'expression les amis de mes amis sont mes amis l'illustre parfaitement. On construit à partir d'une relation sa fermeture transitive en rajoutant* La construction effective de cette nouvelle relation nécessite d'élaborer un algorithme. au graphe de la relation les couples nécessaires pour que cette nouvelle relation soit transitive.
La définition suivante nous sera utile dans les chapitres à venir, lorsque nous munirons les ensembles de nouveaux outils. Elle dit simplement qu'une application est compatible avec une relation binaire si deux éléments en relation ont la même image (Le prix payé par des personnes du même âge est le même).
On dit qu'une application est compatible avec une relation binaire sur si et seulement si
Relations d'équivalence
La notion de relation d'équivalence est déjà parfaitement intégrée par tous et en dehors de tout contexte mathématique. Dans les phrases Mettez un chapeau, , les termes tournevis, chapeau et homme ne font pas référence à un tournevis, un chapeau ou une voiture en particulier, mais à une classe dont les éléments ont des caractéristiques communes. Le formalisme mathématique tente de saisir l'essence de ce concept :
On peut définir aisément une relation sur l'ensemble des voitures, on dira par exemple que deux voitures sont en relation s'il s'agit du même modèle. La relation est évidemment réflexive, une voiture est bien du même modèle qu'elle même. La relation est également symétrique, si la voiture est du même modèle que la voiture , la voiture est bien du même modèle que . Elle est aussi transitive, puisque si la voiture est du même modèle que la voiture , qui elle même est du même modèle que la voiture , alors la voiture est du même modèle que la voiture . Le lecteur perspicace aura deviné qu'en définissant une relation binaire à partir de caractéristiques communes entre objets, elle sera toujours une relation d'équivalence.
Le couple classe d'équivalence/représentant est à la théorie des ensembles ce que le couple hyperonyme/hyponyme est à la linguistique.
L'Interceptor de Mad Max est un représentant (hyponyme) de la classe (hyperonyme) des Ford Falcon XB.
La terminologie ensemble quotient et le symbole de division sont légitimés par le fait que l'on a divisé l'ensemble en classes suivant la relation Le théorème suivant montre que partitions et relations d'équivalence sur un ensemble sont deux concepts étroitements liés.
Quand plusieurs relations sont en jeu, la classe d'équivalence d'un élément pour une relation est notée pour éviter les confusions.
Démontrez que si est une relation d'équivalence sur un ensemble et , alors
Dans le sens direct, soit et supposons que . Soit , donc et par transitivité de , on en déduit que , soit , ce qui prouve que . Le raisonnement est symétrique pour démontrer que et l'axiome d'extension permet de conclure. Pour l'implication réciproque, si alors .
Soit un ensemble. Si est une relation d'équivalence définie sur alors l'ensemble quotient est une partition de . Réciproquement, si est une partition de , alors il existe une unique relation d'équivalence sur telle que , définie par
Démontrez ce théorème.
L'application définie par qui à un élément de associe sa classe d'équivalence est évidemment surjective puisque l'ensemble d'arrivée est constitué de ses images, elle est appelée surjection canonique.
L'ensemble quotient est une partie de quel ensemble ?
C'est un sous-ensemble de .
Que doit satisfaire une application pour être compatible avec une relation d'équivalence (deux éléments de en relation doivent posséder la même image) ?
Soit une application, une relation d'équivalence définie sur et la surjection canonique. L'application est compatible avec si et seulement s'il existe une application telle que :
Dans ce cas est unique, on dit qu'elle est déduite de par passage au quotient
Montrons que la condition est nécessaire. Par hypothèse pour tout couple tel que on a , autrement dit la correspondance d'ensemble de départ et d'arrivée qui associe à la classe est une application puisque ne dépend pas du représentant de la classe, on peut donc écrire .
Réciproquement supposons qu'il existe une application telle que . Montrons que si alors . On a
Malgré les apparences, ce théorème n'a rien de bien compliqué. On a fait des paquets de tous les individus qui ont la même image par , et l'application n'est rien d'autre qu'une version de définie sur ces paquets.
Dans la section consacrée aux fonctions et aux applications, nous avons étudié comment transformer une fonction quelconque en application, il suffit de remplacer l'ensemble de départ par le domaine de définition de la fonction, puis comment transformer cette application en surjection, il suffit de remplacer l'ensemble d'arrivée par l'image de . Mais comment transformer cette dernière application en injection afin d'obtenir une bijection ?
L'étude que nous venons de mener nous donne la solution, il suffit de regrouper tous les éléments qui ont la même image par , autrement dit de remplacer les éléments de l'ensemble de départ par leur classe d'équivalence pour la relation d'équivalence (par construction est compatible avec ). Le diagramme sagittal ci-dessous explicite cette construction. Les éléments et sont écartés de l'ensemble de départ pour faire de une fonction et et sont écartés de l'ensemble d'arrivée pour faire de une surjection. On obtient les classes d'équivalence , et
Décomposition canonique d'une application Les éléments sont grisés.
L'application bijective ainsi construite est notée et appelée application décomposition canonique · de . Les applications qui relient les quatre ensembles , , et sont souvent représentées dans un diagramme appelé diagramme commutatif :
Diagramme commutatif de la décomposition canonique d'une application .
Dans un diagramme commutatif, plusieurs chemins peuvent relier deux ensembles et les différentes compositions d'applications suivant ces chemins différents sont égales. Ici deux chemins relient à , le premier est constitué d'une seule flèche, celle étiquetée , et l'autre est constitué de trois flèches étiquetées , et l'injection canonique. On a donc
Relations d'ordre
Trier des objets est une opération très courante, même pour un être humain, mais de toutes les opérations réalisées par les ordinateurs, c'est celle qui occupe de loin la plus grande part du temps cpu mondial. Trier des objets n'est possible que si l'on dispose d'un critère pour les comparer.
Une relation binaire définie sur un ensemble à la fois réflexive, antisymétrique et transitive est appelée relation d'ordre sur . Le couple est appelé un ensemble ordonné.
Soit un ensemble ordonné. Deux éléments et de sont dits comparables si et seulement si
Si tous les éléments de sont comparables deux-à-deux, la relation d'ordre est dite totale sinon partielle.
La relation binaire définie sur par si et seulement si et est appelée ordre strict associé à . Attention ! l'ordre strict n'est pas une relation d'ordre.* La terminologie est ici particulièrement maladroite.
Soit et deux éléments d'un ensemble totalement ordonné tels que . On définit les intervalles suivants :
Dans le cas particulier où la relation d'ordre est l'ordre naturel sur , les simplets crochets sont souvent remplacés par les doubles crochets⟦ et ⟧.
Certaines relations d'ordre sont tellement utilisées qu'elles bénéficient d'un symbole spécifique. C'est le cas de l'ordre naturel défini sur l'ensemble des entiers naturels qui est noté ou . Il s'agit d'une relation d'ordre total. C'est précisément par analogie avec l'ordre naturel que le symbole générique a été choisi pour représenter une relation d'ordre quelconque. On dira d'ailleurs de deux éléments et tels que que est plus petit que . Il faut néanmoins garder à l'esprit que cette analogie ne concerne que la terminologie, on peut parfaitement définir d'autres relations binaires sur l'ensemble des entiers naturels telles alors que pour l'ordre strict associé à l'ordre naturel , (cf. par exemple la relation de divisibilité dans cet exercice).
On démontre aisément que l'inclusion définie sur l'ensemble des parties d'un ensemble est une relation d'ordre. L'ordre strict associé est noté . La terminologie héritée de l'ordre naturel ne prête pas à confusion ici puisqu'il est d'usage de dire que l'ensemble est plus petit que l'ensemble si .
Démontrez que la relation binaire d'inclusion définie sur l'ensemble des parties d'un ensemble est une relation d'ordre.
Nous utilisons le symbole pour représenter la relation d'inclusion entre ensembles alors que de nombreux auteurs utilisent encore le symbole . Il s'agit de garder une cohérence entre les notations des différentes relations d'ordre. La propriété de réflexivité d'une relation d'ordre invite à suggérer l'égalité dans la graphie du symbole et à l'enlever pour l'ordre strict associé. C'est le choix qui a été fait pour la relation d'ordre naturel avec les symboles (ou ) pour l'ordre et pour l'ordre strict. Si l'inclusion est représentée par le symbole , comment représenter l'inclusion stricte ? Des solutions ont été fournies par l'introduction d'une multitude de notations plus ou moins baroques : ou encore voire , ce que nous souhaitons éviter.
La relation d'inclusion définie sur des ensembles est une relation d'ordre partiel. Considérons par exemple l'ensemble . L'ensemble de ses parties est
On ne peut pas comparer les parties et avec la relation d'inclusion par exemple, aucun des deux n'est inclus dans l'autre. Quand on dispose d'une relation d'ordre sur un ensemble fini comme ici, on représente le graphe de la relation à l'aide d'un diagramme appelé diagramme de Hasse# Helmut Hasse est un mathématicien allemand. de la relation :
Diagramme de Hasse de la relation sur l'ensemble {∅,{a},{b},{c},{a,b},{a,c},{b,c},X}.
Le diagramme de Hasse d'une relation d'ordre est construit de bas en haut. Si l'on a , on dessine un arc reliant le sommet vers le sommet qui est placé au dessus de . On ne représente aucune des relations que l'on peut déduire par transitivité. Dans l'exemple ci-dessus, l'ensemble vide est inclus dans toutes les parties de , mais on ne trace que les trois arcs le reliant aux trois singletons, puisque les autres arcs peuvent être déduits par transitivité. Ce diagramme permet dans une certaine mesure de visualiser la relation étudiée et mettre en évidence quelques éléments remarquables que nous allons étudier dans la suite.
Cette représentation n'a d'intérêt que pour une relation d'ordre partielle. En effet si la relation d'ordre est totale, le diagramme sera constitué de tronçons verticaux reliant les différents éléments de l'ensemble . Par exemple pour l'ensemble muni de l'ordre naturel :
Diagramme de Hasse de l'ordre naturel sur l'ensemble des entiers .
Quand on dispose d'une relation d'ordre sur un ensemble , certains éléments de l'ensemble peuvent posséder des propriétés remarquables.
Soit un ensemble ordonné et une partie de . Un élément tel que
est appelé un minorant (resp. majorant) de .
Une partie à la fois minorée et majorée, est appelée partie bornée. Il n'existe pas nécessairement de minorant ou de majorant à une partie d'un ensemble, par exemple la demi-droite de n'admet pas de majorant, et n'admet pas de minorant.
Soit un ensemble ordonné et une partie de Si est un minorant (resp. majorant) de et , alors est unique. On l'appelle le plus petit élément ou le minimum (resp. le plus grand élément ou maximum) de et on le note (resp. ).
S'il existe un plus grand minorant (resp. un plus petit majorant) d'une partie d'un ensemble ordonné , il est appelé infimum ou borne inférieure (supremum ou borne supérieure) de et on le note (resp. ).
Dans l'exemple de la figure 13, le plus petit élément et le plus grand élément de pour l'inclusion existent, il s'agit respectivement de et . L'ensemble des entiers naturels admet un plus petit élément pour l'ordre naturel, il s'agit de . En revanche n'admet pas de plus grand élément par essence, c'est l'une des trois propriétés qui le caractérisent comme nous le verrons au chapitre suivant.
La borne inférieure de appartient à si et seulement si admet un plus petit élément et dans ce cas . De même, la borne supérieure de appartient à si et seulement si admet un plus grand élément et dans ce cas .
Soit une application à valeurs dans un ensemble ordonné et . On parlera du minimum et du maximum de sur en lieu et place de et , s'ils existent. De même on parlera de la borne inférieure et de la borne supérieure de pour et , s'ils existent. On les note respectivement
Nous avons vu qu'un ensemble ordonné n'admet pas néessairement de plus petit ou de plus grand élément, a fortiori si la relation d'ordre est partielle puisque tous les éléments ne sont pas comparables. Cependant, on peut se demander s'il existe des éléments qui soient plus petits ou plus grands que tous ceux avec qui la comparaison est possible ?
Soit un ensemble ordonné. Un élément de tel que
est appelé un élément minimal (resp. un élément maximal) de pour la relation .
Il existe des moyens conventionnels de définir de nouvelles relations d'ordre à partir d'une ou plusieurs relations d'ordre prédéfinies. Quand on se donne une relation d'ordre sur un ensemble , la relation d'ordre notée définie par est appelée l'ordre opposé de l'ordre . Quand on restreint une relation d'ordre définie sur un ensemble à une partie , la relation ainsi crée s'appelle l'ordre induit par l'ordre sur . Si l'on se donne une famille d'ensembles ordonnés, la relation définie sur l'ensemble produit par
est une relation d'ordre appelée l'ordre produit des relations . Les relations d'ordre peuvent être totales sans que l'ordre produit le soit. Considérons par exemple l'ordre produit sur l'ensemble des couples d'entiers naturels munis chacun de l'ordre naturel :
Les couples et ne sont pas comparables. Pour obtenir une relation d'ordre total sur ce produit cartésien il faut fournir un peu plus d'efforts.
Limitons nous au cas fini où l'ensemble d'indexation est ⟦⟧ avec un entier naturel non-nul. On définit une relation binaire entre deux -uplets et par si et seulement s'il existe un rang ⟦⟧ tel que leurs -èmes projections coïncident pour tout ⟦⟧ et que ou que leurs -èmes projections sont toutes égales sauf pour où . Il s'agit d'une relation d'ordre total appelée ordre lexicographique.
Malgré une définition qui semble alambiquée, c'est une relation bien connue du lecteur. Si les ensembles désignent tous le même alphabet latin muni de l'ordre alphabétique, il s'agit de l'ordre du dictionnaire. C'est également l'ordre qui est utilisé pour ranger les nombres réels quand ils sont représentés sous forme décimale.
On définit la relation de divisibilité sur l'ensemble des entiers naturels par
Démontrez qu'il s'agit d'une relation d'ordre partiel. Vérifiez que 0 est le plus grand élément pour cette relation. Existe-t-il un plus petit élément ? Si l'on restreint cette relation à l'ensemble , existe-t-il toujours un plus petit élément ? Un plus grand élément ? Quels sont alors les éléments minimaux s'il en existe ? Les éléments maximaux s'il en existe ?
Tracez le diagramme de Hasse de la relation de divisibilité restreinte à l'ensemble .
Écrivez sous forme logique avec quantificateurs la définition de l'ordre lexicographique entre -uplets et .
Démontrez qu'il s'agit bien d'une relation d'ordre et que si les relations d'ordre sont totales alors l'ordre lexicographique est une relation d'ordre total.
Pour réaliser des algorithmes de tri comparatif, il est nécessaire que la relation d'ordre utilisée pour comparer les objets soit totale.
Démontrez que pour tout couple où est un intervalle ou une demi-droite, tout élément compris entre et appartient à l'intervalle .
Attention, la négation de la croissance n'est pas la décroissance ! En effet une application peut très bien croître par moment et décroître par d'autres. Si l'on remplace dans la définition les relations d'ordre et par leurs ordres stricts et on parle d'application strictement croissante et strictement décroissante. Une application qui est croissante ou décroissante (resp. strictement croissante ou décroissante) est dite application monotone (resp. application strictement monotone).
Démontrez que toute application monotone et injective est strictement monotone. Démontrez que la composition de deux applications monotone est monotone.
Relations de précédence
Dans les systèmes multiprocesseurs multiprogrammés, on modélise le fonctionnement des processus par un ensemble de tâches à réaliser. Ces tâches sont représentées par des couples dont la première projection est l'instant où la tâche débute son exécution et la seconde projection est l'instant où elle finit son exécution. Certaines tâches ne peuvent débuter leur exécution qu'une fois que d'autres tâches ont fini la leur. Ces différentes contraintes temporelles sont modélisées par une relation binaire définie sur l'ensemble des tâches à réaliser. Si et sont deux tâches, on interprète par la tâche termine son exécution avant que la tâche ne débute la sienne, i.e.
On dit alors que la tâche précède la tâche ou que la tâche succède la tâche .
Si deux tâches et sont telles que l'exécution de l'une ne nécessite pas l'exécution de l'autre au préalable, i.e. telles que , on dit que ce sont des tâches parallèles et on écrit sinon elles sont en série.
La relation est antiréflexive, en effet une tâche ne peut pas terminer son exécution avant même d'avoir commencé, elle est antisymétrique et bien sûr transitive.
Le graphe d'une relation de précédence est représenté par un diagramme qui omet tous les arcs que l'on peut déduire par transitivité. Deux questions classiques sont étudiées dans les cours de systèmes d'exploitation des formations en informatique :
Trouver un ordonnancement séquentiel de l'ensemble des tâches compatible avec la relation de précédence ;
Trouver un ordonnancement parallèle de l'ensemble des tâches compatible avec la relation de précédence.
Le premier cas correspond à la situation où les différentes tâches sont exécutées par un unique processeur, le deuxième cas si le système alloue plusieurs processeurs pour exécuter des tâches en parallèle. Considérons par exemple la relation de précédence définie sur l'ensemble par la fermeture transitive du graphe
Son diagramme de précédence est représenté ci-dessous. Seuls les numéros des tâches sont indiqués :
Diagramme de précédence de la relation sur un ensemble de tâches.
Pour organiser un séquencement de ces tâches, que ce soit de manière séquentielle ou parallèle, il faut bien sûr commencer par des tâches qui n'ont aucun arc incident vers le sommet correspondant dans le diagramme, c'est-à-dire telles qu'il n'existe aucune tâche telle que . Il n'y a que les tâches et qui ne sont précédées par aucune tâche.
Un ordonnancement séquentiel possible (il n'y pas nécessairement unicité) comme solution du premier problème est :
Nous verrons au chapitre consacré à la combinatoire qu'une telle solution constitue une permutation de l'ensemble . L'ordonnancement parallèle solution du second problème est :
Ces solutions sont faciles à trouver à la main sur une instance aussi petite que celle de cet exemple, mais dans toute leur généralité ces problèmes nécessitent d'élaborer des algorithmes pour les résoudre et on souhaite qu'ils soient efficaces.
D'autres questions sont soulevées par les relations de précédences. Il ne faut pas que dans un graphe de précédence apparaisse un circuit, c'est-à-dire une séquence de tâches telle que
⟦⟧
Plus simplement, la condition exprime qu'il ne faut jamais être en mesure de partir d'une tâche du graphe et d'y revenir en suivant des flèches. La raison est simple, si un tel circuit existe, alors par transitivité de la relation , on a ce qui contredit l'antiréflexivité.
Comment savoir s'il existe des circuits dans un graphe ? Est-on capable de les trouver rapidement ? C'est ce genre de questions qui sont étudiées en théorie des graphes et on en saisit bien l'utilité.
En théorie de la complexité, en master, qui a pour objectif de classifier des problèmes en termes de ressources en temps et/ou en espace nécessaires pour les résoudre, on définit une relation binaire entre langages définis sur un même alphabet appelée transformation polynomiale, qui est réflexive et transitive mais qui n'est ni symétrique, ni antisymétrique. Cette relation joue un rôle majeur dans cette théorie et cette classification.
Résolution du problème introductif
Modélisation avec les graphes
La modélisation de ce problème, appelé Jeu de Nim, se fait dans le cadre de la théorie des graphes.
Notons le nombre d'allumettes sur le tas au début de la partie et
considérons le graphe d'ensemble de sommets ⟦⟧ et d'arcs
Autrement dit, contient toutes les valeurs possibles du nombre d'allumettes sur le tas lors du déroulement des parties et on relie une valeur à une valeur si et seulement s'il s'agit d'un coup autorisé.
Graphe du jeu de Nim pour allumettes.
Chaque sommet de ce graphe code une position du jeu et un joueur dans cette position doit choisir parmi les coups possibles , et , celui ou ceux qui peuvent l'amener à une victoire, si un tel coup existe.
Il n'est pas difficile de constater que si un joueur est en position , ou , il peut toujours amener le joueur adverse dans la position perdante puisqu'il peut retirer , ou allumettes. Mais pour être certain d'être dans l'une de ces trois positions gagnantes, il fallait nécessairement que le joueur adverse soit en position au préalable, elle aussi perdante par conséquent, et ainsi de suite. Cette analyse empirique montre qu'un joueur dans l'une des positions en jaune peut toujours amener le joueur adverse sur l'une des positions perdantes en rouge. Par conséquent, le joueur qui connaît cette stratégie et qui commence cette partie est sûr de gagner, sinon il faut qu'il compte sur l'ignorance du joueur adverse pour pouvoir se retrouver sur une position gagnante avant que toutes les allumettes soient retirées.
Le graphe définit indirectement la correspondance que nous noterons encore par abus de langage. Observons les propriétés de la partie . Aucune flèche ne permet de relier deux sommets de , on dit dans ce cas que est indépendante du graphe :
D'autre part, tout sommet hors de est relié à un sommet de , et on dit alors que est une absorbante du graphe :
Une partie de à la fois indépendante et absorbante est appelée noyau du graphe
Notons qu'un graphe n'admet pas nécessairement de noyau, mais s'il en admet un celui-ci est unique, ce qui permet de parler du noyau d'un graphe. Le cas échéant, on dispose d'une stratégie générale pour gagner à tous les jeux similaires. Par exemple, deux personnes veulent cueillir des fleurs à tour de rôle sur une rangée de fleurs, mais ils ne peuvent qu'en couper une à chaque fois et il est interdit de cueillir une fleur à côté d'une fleur qui a été coupée. La cueillette s'arrête quand il n'est plus possible de cueillir de fleur. Quel stratégie faut-il adopter pour être le dernier à cueillir une fleur ? Autre exemple : deux joueurs sont faces à plusieurs tas de pièces et peuvent retirer chacun leur tour un nombre arbitraire de pièces mais d'un seul tas, qui peut en revanche être différent à chaque tour de jeu. Comment éviter d'être celui qui ne pourra plus retirer de pièce ?
Calculez le noyau des graphes qui modélisent les deux jeux cités dans les exemples précédents, pour une rangée de fleurs pour le premier jeui et pour trois tas de , et pièces pour le deuxième jeu.
La question qui se pose à présent est de déterminer comment calculer le noyau d'un tel graphe autrement que de manière empirique ?
Fonctions de Grundy
de la section :
Le mathématicien britannique Patrick Grundy s'est intéressé à ce type de problèmes et a développé l'outillage nécessaire en théorie des graphes pour les analyser et identifier les positions gagnantes et perdantes.
Dans le graphe modélisant les différentes configurations du jeu des allumettes et les transitions qui les relient, on constate aisément que l'on peut regrouper les sommets suivant leur statut dans le déroulement du jeu : les sommets , et qui sont les positions perdantes, les sommets , et qui permettent de les atteindre en retirant allumette, les sommets , en retirant allumettes et les sommets et en retirant allumettes. Il y a donc groupes de positions différents dans le graphe.
Plus généralement, s'il y a groupes de positions différentes, une fonction de Grundy fournit simplement pour un sommet du graphe, le numéro de son groupe, sachant que les groupes sont numérotés de à et que la valeur nulle est attribuée aux sommets du noyau du graphe.
Soit un graphe antiréflexif. On appelle fonction de Grundy, toute application telle que
On comprend aisément l'intérêt d'une telle fonction, les positions gagantes/perdantes sont déterminées par la valeur de leur fonction de Grundy. Reste à déterminer les conditions qu'un graphe doit satisfaire pour qu'il admette une fonction de Grundy et, le cas échéant, comment construire cette fonction.
Montrez que si un graphe admet une fonction de Grundy, alors il admet
Travaux pratiques
L'objectif de ce TP est de transposer en Python quelques manipulations vues en cours sur les correspondances, fonctions et applications.
En séance
Une correspondance est codée dans un fichier texte contenant un couple du graphe par ligne. Cliquez sur ce lien et sauvegardez cet exemple dans le répertoire où vous écrirez vos scripts.
Un couple est codé par la séquence x > y. Une ligne contenant > y sans premier membre (resp. x > sans second membre) code un élément de l'ensemble d'arrivée (resp. de départ) qui n'est pas en relation avec un élément de l'ensemble de départ (resp. d'arrivée). Cela permet de déterminer tous les éléments des ensembles de départ et d'arrivée de la correspondance, y compris ceux qui ne sont pas en relation.
Écrivez une fonction PythonLire(nomfichier) qui lit le fichier dont le nom est passé en paramètre et renvoie un triplet codé à l'aide d'un tuplePython comportant :
L'ensemble de départ codé par un set.
Le graphe codé par un dictionnaire. Les éléments de tels que constituent les clefs de ce dictionnaire et la valeur associée à une clef est l'image directe de codée par un set. On ne codera pas la clef vide dans le dictionnaire (celle qui correspond à une ligne > y sans premier membre).
Indications : voir les travaux pratiques #2 pour la lecture d'un fichier texte et la manipulation des ensembles (type set).
On rappelle que l'on peut découper une chaîne de caractères chaine suivant un séparateur sep (une chaîne de caractère également, par défaut un espace) grâce à la méthode split(sep) qui renvoie la liste des sous-chaînes séparées par la chaîne sep. Ici on obtient la liste constitué des deux termes du couple en utilisant le symbole > comme séparateur :
1 couple = chaine.rstrip().split(">")
L'appel à rstrip() permet d'éliminer le caractère invisible retour charriot à la fin de chaque ligne du fichier. Vous pourrez utiliser la fonction et la procédure suivantes pour formater un ensemble et une correspondance c (cliquer ici pour les télécharger. Leurs modes d'emploi sont fournis en commentaire :
1def Formater(X):
2return str(X).replace("'",'')
3def Afficher(names, c):
4 print(names[0],":")
5for i in range(3):
6 print("\t"+names[i+1]+" = ",Formater(c[i]))
7 print()
Écrivez une fonction PythonDomaineDef(c) qui renvoie le domaine de définition de la correspondance passée en paramètre.
Écrivez une fonction PythonCreerDico(c) qui renvoie un dictionnaire dont les clefs sont tous les . La valeur associée à chaque clef est l'image directe de par , i.e. .
Voir les travaux pratiques #3 pour l'usage des dictionnaires. Pour l'exemple fourni, en notant D ce dictionnaire, on a D["a"]={"1","2"}, D["b"]={"1"}, D["c"]={"2","3"} et D["e"]={"4"}.
Écrivez une fonction PythonEstFonction(c) qui décide (renvoie vrai ou faux) si la correspondance passée en paramètre est une fonction.
Indication : Utilisez le dictionnaire de c et vérifier que pour toute entrée, sa valeur contient au plus un élément.
Écrivez une fonction PythonEstApplication(c) qui décide si la correspondance passée en paramètre est une application.
Indication : appliquer littéralement la définition du cours.
Écrivez une fonction PythonReciproque(c) qui renvoie la correspondance réciproque de celle passée en paramètre.
Écrivez une fonction PythonImageDirecte(c,A) qui renvoie l'image directe d'une partie de l'ensemble de départ de la correspondance passée en paramètre.
Écrivez une fonction PythonImageReciproque(c,B) qui renvoie l'image réciproque d'une partie de l'ensemble d'arrivée de la correspondance passée en paramètre.
Écrivez une fonction PythonComposer(g,f) qui renvoie la composition des deux correspondances et passées en paramètres. Composez cette correspondance avec sa correspondance réciproque. Est-ce l'identité ?
Indication : n supposera que l'ensemble d'arrivée de la correspondance est égal à l'ensemble de départ de
Compléments hors séance
Écrivez une fonction PythonEstInjection(c) qui décide si la correspondance passée en paramètre est une injection.
Écrivez une fonction PythonEstSurjection(c) qui décide si la correspondance passée en paramètre est une surjection.
Écrivez un script Python qui réalise la décomposition canonique d'une application . Les fonctions sont encore une fois encodées par leurs graphes codés dans un fichier texte. Pour cela, écrivez une fonction DC(f) qui renvoie la liste des couples formés par les classes d'équivalence suivant et de l'image commune des représentants de la classe .
Écrivez une fonction en PythonComparer(x,y) qui compare deux chaînes de caractères et pour l'ordre l'ordre lexicographique sur l'alphabet latin et renvoie si , si et si . Écrivez un programme qui saisit deux chaînes de caractères et les compare.