Chapitre3 : Relations dordre
Dans tout ce qui suit E désigne un ensemble quelconque. I Généralités. A) Relations binaires. Définition : Une relation binaire définie sur E est une
Relations dordre
relation d'ordre strict) quand elle est irréflexive et transitive. quel choix de m et n dans N? ? la réponse et oui et on peut le montrer grâce.
RELATION BINAIRE
Montrer que est une relation d'ordre partiel sur . On considère dans la suite de l'exercice que l'ensemble est ordonné par la relation .
Relations dordre Exercice 1. Exercice 3. Ordre sur NN Exercice 4
Feb 19 2018 Montrer que A admet une borne supérieure. Exercice 6. On définit une relation R sur l'ensemble des fonctions RR
CHAPITRE I Relations dordre I.1 Ordre et ordre strict
Définition (ordre) Une relation binaire est un ordre (ou une relation d'ordre) montrer que la propriété est toujours vraie il suffit de montrer que.
Relation
Une relation binaire ? sur un ensemble E est une relation d'ordre si elle sur X. Pour montrer que pour tout x ? X la propriété P(x) est vraie il.
Relations dordre
Feb 22 2013 Donnez des exemples de relations d'ordre que vous connaissez (cherchez bien
Pour remettre un peu dordre dans R 1 Relation dordre sur R
Démontrer que inf A ? m. Exercice 2 Soit A une partie non vide de R. On pose ?A = {?x x ? A}. Démontrer que.
Relation déquivalence relation dordre
Déterminer la classe d'équivalence de chaque z ? C. Indication ?. Correction ?. Vidéo ?. [000209]. Exercice 2. Montrer
Relations dordre. Dénombrement. Plus grand élément. Borne
Pour montrer que a est égal `a la borne supérieure de A il faut montrer que a est le plus petit élément de l'ensemble des majorants de A. Or a est majorant de
CHAPITREIRelations d"ordre
Ce chapitre traite des relations d"ordre. Apr`es des rappels de notions abord´ees l"an dernier, on s"int´eresse plus particuli`erement aux "ordres bien fond´es" qui permettent de g´en´eraliser le principe de r´ecurrence.I.1Ordre et ordre strict D´efinition (relation binaire)SoitEun ensemble. Unerelation binaireRsurEest un sous-ensemble deE×E. On notexRypour signifier que (x,y)? Retx?Rypour signifier que (x,y)/? R.D´efinition (classification)SoitRune relation binaire surE. On dit queRest•r´eflexivequand?x?E,xRx;•irr´eflexivequand?x?E,xRx;•sym´etriquequand?x,y?E,xRy?yRx;•antisym´etriquequand?x,y?E,xRyetyRx?x=y;•transitivequand?x,y,z?E,xRyetyRz?xRz.
D´efinition (ordre)Une relation binaire est unordre(ou unerelation d"ordre) quand elle est r´eflexive, sym´etrique et transitive. D´efinition (ensemble ordonn´e)SoitEun ensemble et?une relation d"ordre surE. On dit que (E,?) est unensemble ordonn´e.?Attention, les d´efinitions ci-dessus correspondent `a l"ordre large mais pas `a l"ordre strict :
(R,<) o`ul"ensemble des entiers relatifs divisibles par 2, il n"y a ni minorant ni majorant.Th´eor`eme I.2Soit(E,?)un ensemble ordonn´e etFune partie non vide deE.Fa au
plus un plus petit ´el´ement et au plus un plus grand ´el´ement. D´efinition (´el´ement minimal)Soit (E,?) un ensemble ordonn´e etFune partie non vide deE. Un ´el´ementx?Fest un´el´ement minimaldeFquand aucun ´el´ement deF n"est strictement plus petit, pour?, quex:?y?F,y?x?y=x. D´efinition (´el´ement maximal)Soit (E,?) un ensemble ordonn´e etFune partie non vide deE. Un ´el´ementx?Fest un´el´ement maximaldeFquand aucun ´el´ement deF n"est strictement plus grand, pour?, quex:?y?F,x?y?y=x.I.3. PRODUIT D"ORDRES3I.3Produit d"ordres
D´efinition (ordre produit simple)Soit (E,?E) et (F,?F) deux ensembles ordonn´es. On d´efinit l"ordre produit simple?prodsurE×Fpar D´efinition (ordre produit lexicographique)Soit (E,?E) et (F,?F) deux ensembles ordonn´es. On d´efinit l"ordre produit lexicographique?prodsurE×Fpar, on notant?EetFles ordres stricts associ´es `a?Eet?F,
?x?Ex? ou x=x?ety?Fy?. ?Si?Eet?Fsont des ordres totaux,?lexest aussi un ordre total; ce n"est pas vrai pour prod.I.4Ordre bien fond´e D´efinition (ordre bien fond´e)Soit (E,?) un ensemble ordonn´e. On dit que?estbien fond´equand il n"existe pas de suite infinie strictement d´ecroissante d"´el´ements deE.?L"ordre usuel surNest bien fond´e, mais pas celui surZ, ni celui surR+.Th´eor`eme I.3(caract´erisation des ordres bien fond´es)Soit(E,?)un ensemble or-
donn´e. L"ordre?est bien fond´e si et seulement si tout partie non videFdeEadmet aumoins un ´el´ement minimal.Th´eor`eme I.4Le produit lexicographique de deux ordres bien fond´es est bien fond´e.
?Le programme suivant se termine pour toutes entr´eesnetmdansN?:while (m != n) { if (m > n) m = m - n; else n = n - m; En effet, si on consid`ere l"ordre lexicographique naturel surN?×N?, on s"aper¸coit qu"`a chaque it´eration le couple (m,n) est strictement inf´erieur `a celui d"avant. Comme l"ordrelexicographique surN?×N?est bien fond´e (d"apr`es le th´eor`eme pr´ec´edent), on ne peut
effectuer qu"un nombre fini d"it´erations dans le programme.4CHAPITRE I. RELATIONS D"ORDREI.5Ordres sur des ensembles finis, diagramme de Hasse
Quand (E,?) est un ensemble fini ordonn´e, on peut le repr´esenter graphiquement parsondiagramme de Hasse, qui est un graphe non-orient´e avec les contraintes suivantes :-les sommets sont les ´el´ements deE;-six?yon placexplus bas queysur le diagramme;-six?yet qu"il n"y a pas dez?Etel quex?z?y, on met une arˆete entrexety.
?Le diagramme de Hasse pour l"ordre?surE={1,2,3}est :{1,2,3}{2,3}{1,3}{1,2}{3}{2}{1}∅Th´eor`eme I.5Soit(E,?)un ensemble fini ordonn´e. L"ordre?est bien fond´e surE.I.6Ordres sur les mots
On se donne un ordre strict?sur l"alphabet.
D´efinition (ordre lexicographique sur les mots)SoitAun alphabet fini. On d´efinit ?uest pr´efixe dev ou ?w,s,t?A?,?a,b?A,a?betu=wasetv=wbt D´efinition (ordre militaire sur les mots)SoitAun alphabet fini. On d´efinit l"ordre ?|u|<|v| ou phique.CHAPITREIIR´ecurrence et induction
D´efinition (propri´et´e)Unepropri´et´esur un ensembleEest une application deEdans {Vrai,Faux}.II.1R´ecurrence Th´eor`eme II.1 (principe de r´ecurrence)SoitPune propri´et´e d´efinie surN. Pourmontrer que la propri´et´e est toujours vraie, il suffit de montrer que(initialisation)la propri´et´e est vraie en0:P(0) =Vrai;(h´er´edit´e)pour toutn?N, si la propri´et´e est vraie ennalors elle est encore vrai en
n+ 1: ?n?N, P(n)?P(n+ 1). ?Attention dans les preuves `a ne pas supposer quePest vrai pour toutn?N(il n"y a plus rien `a d´emontrer si on suppose ¸ca). ?Cela fonctionne aussi si on prendN≥k={k,k+1,...}l"ensemble des entiers sup´erieurs ou ´egaux `ak, mais il faut faire l"initialisation enk. n? i=1i=n(n+ 1)2.Th´eor`eme II.2 (principe de r´ecurrence g´en´eralis´ee)SoitPune propri´et´e d´efinie sur
N. Pour montrer que la propri´et´e est toujours vraie, il suffit de montrer que(initialisation)la propri´et´e est vraie en0:P(0) =Vrai;(h´er´edit´e)pour toutn?N?, si la propri´et´e est vraie pour toutk < nalors elle est
encore vraie enn: ?n?N?,(?k < n, P(k))?P(n).56CHAPITRE II. R´ECURRENCE ET INDUCTION?C"est quasiment la mˆeme chose, `a cause des propri´et´es structurelles de l"ensemble ordonn´e
?Si deux mots non vides commutent (uv=vu) alors ils sont puissance d"un mˆeme mot : ?w?A?,?k≥1,??≥1, u=wketv=w?. ?SoitGun graphe orient´e avecnsommets. S"il existe un chemin entrexetyalors il enexiste un de longueur au plusn-1 : par r´ecurrence sur la longueur?du chemin initial.II.3Induction bien fond´ee
Th´eor`eme II.3 (induction bien fond´ee)Soit(E,?)un ensemble muni d"un ordre bienfond´e. SoitPune propri´et´e surE. Si les deux hypoth`eses suivantes sont v´erifi´ees :1.P(x) =Vrai pour tout ´el´ement minimalxde(E,?),2.si pour tout ´el´ement non minimalx, on a la propri´et´e :
(?y?x,P(y) =Vrai)?P(x) =Vrai, alors pour toutx?E, P(x) =Vrai. ?Soit (E,?) o`uE=N\ {0,1}={2,3,...}et?est l"ordre "divise" : x?y? ?k?N?, y=kx. On a vu en TD que l"ordre "divise" est bien fond´e et que ses ´el´ements minimaux surEsont les nombres premiers. SoitPla propri´et´e "s"´ecrit comme un produit de nombres premiers". On montre par induction bien fond´ee pour cet ordre que cette propri´et´e est toujours vraie surE.CHAPITREIIIStructures Inductives
III.1Introduction
L"objectif est de formaliser des d´efinitions qui sont par nature r´ecursive (on dira plutˆot
inductivedans un contexte math´ematique) pour d´efinir des objets, comme par exemple desarbres binaires qui seront d´efinis de la fa¸con suivante :•?est un arbre binaire,•siAetBsont des arbres binaires,?/\
A Baussi.
Mais il faudrait rajouter un "il n"y a rien d"autre", ce qu"on va d´efinir formellement dans la suite.III.2D´efinitions On rappelle que si lesAi, pouri? I, sont des sous-ensembles d"un ensembleE, l"inter- section de tous lesAiest l"ensemble i?IA i={x?E| ?i? I, x?Ai}.III.2.1Fermeture inductive SoitUun ensemble, on noteFkl"ensemble des fonctions d"arit´ek(c"est-`a-dire des fonctions `akvariables) partielles deUk→U. On noteFtoutes les fonctions partielles `a une ou plusieurs variables : F=? k≥1F k. D´efinition (stabilit´e)Soit Ω un sous-ensemble deFetEun sous-ensemble deU.E est ditstablepar Ω quand pour toutf?Ud"arit´ek, et pour tout (x1,...,xk)?Ek, si f(x1,...,xk) existe alorsf(x1,...,xk)?E.78CHAPITRE III. STRUCTURES INDUCTIVESCela signifie donc que les images desk-uplets d"´el´ements deEsont dansE.
D´efinitionSoitUun univers (un ensemble),B?Ulabaseet Ω? Fun ensemble de fonctions partielles. Lafermeture inductiveEdeBpar Ω est le sous-ensemble deUd´efini par : E=?B?XXstable par ΩX.Th´eor`eme III.1La fermeture inductive deBparΩest le plus petit sous-ensemble deU,
pour l"inclusion qui v´erifie •(base)B?E •(induction)Eest stable parΩ. ?L"ensemblePdes mots bien parenth´es´es sont un sous-ensemble deA={a,b}, o`ua correspond `a une parenth`ese ouvrante etb`a une parenth`ese fermante. L"univers estA?. On aPd´efini inductivement par :B={ε},
Ω ={f}avecf(u,v) =aubv.Th´eor`eme III.2SoitEla fermeture inductive deBparΩ. Un ´el´ementx?Uest dans
Esi et seulement si :•ou bienx?B,•ou bien il existef?Ωd"arit´eketx1,···,xk?Etels quex=f(x1,···,xk).III.2.2D´efinition ascendante et descendante
La d´efinition donn´ee pour la fermeture inductive est appel´eed´efinition descendante:E est obtenu par intersection infinie de tous les ensembles v´erifiant (base) et (induction). SoitEla fermeture inductive deBpar Ω. On d´efinit la suite des sous-ensembles deE d´efinie par :-B0=B,-B
i+1= Ω(Bi)?Bi,?i?N.Th´eor`eme III.3On aE=?i≥0Bi. ?Cela signifie qu"on obtient les ´el´ements deEen appliquant un nombre fini de fois des r`egles de Ω, en partant des ´el´ements de la base. D´efinition (hauteur d"induction)SoitEla fermeture inductive deBpar Ω. Lahauteur, ouhauteur d"induction, dex?Eest le plus petit entierhtel quex?Bh. III.3. PRINCIPE D"INDUCTION STRUCTURELLE9III.2.3Arbre syntaxique Comme chaque ´el´ementxde la fermeture inductiveEdeBpar Ω se construit en appliquant successivement les r`egles de construction, il est souvent utile de d´ecrire par un arbre un proc´ed´e qui permet de construirex. Cet arbre s"appelle unarbre syntaxique.On construit donc un arbre dont les feuilles sont ´etiquet´es par des ´el´ements deBet dont
les noeuds internes sont ´etiquet´es par des ´el´ements de Ω : si une r`eglefd"arit´ekintervient
dans le processus de construction dex, le noeud associ´e aurakdescendants. ?Voil`a l"arbre syntaxique dex=f(f(α,β),g(α)), pourB={α,β}etfd"arit´e 2 etg d"arit´e 1.f fg ?Il est important de remarquer qu"unxdonn´e peut avoir plusieurs arbres syntaxiques :il peut tr`es bien il y avoir plusieurs fa¸cons de construirex.III.3Principe d"induction structurelle
C"est l"´equivalent de la r´ecurrence pour les structures inductives. C"est donc un desth´eor`emes les plus utiles de ce chapitre.Th´eor`eme III.4SoitEla fermeture inductive deBparΩ. SoitPune propri´et´e d´efinie
surE. Pour montrer que pour toutx?Ela propri´et´eP(x)est vraie, il suffit de montrerque :•(base d"induction)?x?B,P(x) =Vrai.•(´etape d"induction)pour toutf?Ωd"arit´eket toutx1,···,xk, siy=f(x1,···,xk)
est d´efinie, alorsP(y) =Vrai.III.4D´efinition de fonctions sur des ensembles inductifsIII.4.1Sch´emas libres
D´efinition (uniquement constructible)SoitEla fermeture inductive deBpar Ω. Un ´el´ementx?Eest dituniquement constructiblequand une et une seule des deux propositionssuivantes est v´erifi´ee :•x?B,•il existe une unique r`eglef, d"arit´ek, et un uniquek-uplet (x1,···,xk) tel que
x=f(x1,···,xk).10CHAPITRE III. STRUCTURES INDUCTIVESD´efinition (induction libre)SoitEla fermeture inductive deBpar Ω.Eestlibre,
oulibrement engendr´ee, ou est unsch´ema libre d"induction, quand tous ses ´el´ements sont
uniquement constructibles. Sifest une fonction d"arit´ek, deUkdansU, et queXest un sous-ensemble deU, on notef(X) l"ensemble des images des ´el´ements deX: f(X) ={f(x1,...,xk)|x1,...,xk?Xetf(x1,...,xk) existe}. On rappelle aussi que sifest une fonction deUndansUet queE?U, la restriction def`a E, not´eef|Eest la fonction deEndansUd´efinie, pour tout (x1,...,xn)?Endu domaine de d´efinition def, par f|E((x1,...,xn)) =f((x1,...,xn)).Th´eor`eme III.5SoitEla fermeture inductive deBparΩ.Eest librement engendr´ee si
et seulement si les trois points suivants sont v´erifi´es :•?f?Ω,f(E)∩B=∅.•?f?Ω,f|Eest injective.•?f,g?Ω,f(E)∩g(E) =∅.III.4.2Fonctions
L"id´ee est de d´efinir une fonction inductivement en donnant l"image des ´el´ements de sa
base et en expliquant comment transformer les r`egles. SoitEla fermeture inductivelibredeBpar Ω. La d´efinition inductive d"une applicationφdeEdans un ensembleFconsiste en-la donn´eeφ(x) pour tout ´el´ementx?B.-Pour toute r`eglef?Ω, d"arit´ek, la donn´ee de l"expression deφ(f(x1,···,xk)) en
fonction desxiet desφ(xi).?Si le sch´ema n"est pas libre il peut y avoir ambigu¨ıt´e. Par exemple, pourEd´efini par
ε,a,b?E
f(u,v) =uv?E?u,v?ESi on d´efinit la fonctionφdeEdansNpar
φ(ε) =φ(a) =φ(b) = 1
φ(f(u,v)) =φ(u) +φ(v)?u,v?E
On aφ(ab) =φ(a) +φ(b) = 2 etφ(ab) =φ(ε) +φ(ab) =φ(ε) +φ(a) +φ(b) = 3.
III.5. EXPRESSIONS11III.4.3Programmation
Les fonctions d´efinies inductivement sont la plupart du temps transformables directe- ment en fonction r´ecursives. Il existe mˆeme des langages de programmation (prog. fonc- tionnelle) dont c"est le principe de base. Le principe est de faire une fonction en deux parties. De la forme :phi(x) * Si x est dans B * retourner la valeur connue phi(x) * Sinon * x = f(x1...xk) * retourner l"expression en fonction de x1...xk et phi(x1)..phi(xk)?Il faut donc pouvoir "inverser"x=f(x1,···,xk), c"est `a dire retrouver lesxi.III.5Expressions
On d´efinit inductivement l"ensemble des expressions rationnelles non vides sur l"alphabetA, not´eEpar (ce sont des mots sur l"alphabet qu"il faut) :-{a} ? Epour touta?Aetε? E.-(E1?E2)-(E1·E2)-(E)?
?On consid`ere la fonctionφdeEdans{0,1}d´efinie parφ(ε) = 1,φ(a) = 0. Etφ(E1? E2) =φ(E1) ouφ(E2), etc. On aφ(E) = 1?Ereconnaˆıt le mot vide. Cette fonction associe `a une formule (l"expression) un langage (un ensemble de motsdeA?). ?On peut facilement faire des algorithmes r´ecursifs sur l"arbre de l"expression, ce qui revient, math´ematiquement, `a d´efinir des fonctions surE. ?Il y a beaucoup d"autres types d"expressions qui sont utilis´ees : formules logiques, ex- pressions arithm´etiques, etc. Toutes fonctionnent sur le mˆeme principe.quotesdbs_dbs47.pdfusesText_47[PDF] Montres que le lycée est un lieu régit par le Droit
[PDF] montrez
[PDF] montrez comment la structure de l'adn explique sa fonction de support de l'information génétique
[PDF] montrez comment le progrès technique stimule la croissance économique
[PDF] Montrez comment un pouvoir est politique et comment une question devient politique
[PDF] Montrez en citant des indices, que Les Confessions appartiennent au genre autobiographique
[PDF] montrez en quoi la croissance est un phénomène cumulatif
[PDF] Montrez l'importance des ressources alimentairess sur la reproduction des anchois
[PDF] montrez les différentes facettes du défi alimentaire auquel l'Inde est confrontée
[PDF] montrez que la 2 nd guerre mondiale fut une guerre d'aneantissement
[PDF] montrez que la détermination du salaire peut dépendre de l'intervention de l'état.
[PDF] montrez que la fiscalité peut contribuer ? la justice sociale.
[PDF] Montrez que la fonction f a pour expression
[PDF] montrez que le facteur capital est source de croissance économique.
