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 suffit de montrer
Previous PDF | Next PDF |
[PDF] Chapitre 3 :Relations dordre
Dans tout ce qui suit, E désigne un ensemble quelconque I Généralités A) Relations binaires Une relation binaire définie sur E est une propriété que chaque
[PDF] RELATION BINAIRE - Licence de mathématiques Lyon 1
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 2 Soit { } Déterminer
[PDF] Relation - Université de Toulouse
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 suffit de montrer
[PDF] 1 Relations binaires 2 Relations déquivalence 3 Relations dordre
relations sur l'ensemble des droites du plan ou de l'espace L'inclusion ⊂ est une relation sur P(X), où X est un ensemble quelconque Définitions Soit R
[PDF] Ch 1 Relations - LACIM
relation d'équivalence Montrer aussi que R détermine une relation d'ordre sur l' ensemble des classes d'équivalence de ~ 2 On définit une relation R sur Z par
[PDF] Relation déquivalence Relation dordre - PAGE WEB DANDRE
Montrer que R est une relation d'équivalence 2 Déterminer la classe d' équivalence de z ∈ C Exercice 4 Soit R une relation binaire sur un ensemble E
[PDF] RELATIONS BINAIRES - Christophe Bertault
symétrie des rôles de x et y, il nous suffit de montrer que : cl(x) ⊂ cl(y) Exemple La relation de divisibilité n'est pas une relation d'ordre sur , mais c'en est
[PDF] Relations binaires Relations déquivalence et dordre
20 août 2017 · Exemples : Les relations que l'on utilise couramment en mathématiques • La relation d'égalité sur un ensemble E «=» • Les relations sur R « < »
[PDF] Pour remettre un peu dordre dans R 1 Relation dordre sur R 2
Montrer que B est bornée puis comparer sup A, sup B, inf A et inf B Exercice 5 Soient A et B deux parties non vides et bornées de R On pose −A = {−x, x ∈
[PDF] Montres que le lycée est un lieu régit par le Droit
[PDF] montrez
[PDF] montrez ? l'aide d'un exemple comment le progrès technique peut contribuer ? la croissance
[PDF] Montrez Comment la société médiévale s'organise progréssivement entre le XI et XIII siècle
[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 certaines caractéristiques des plantes sont en rapport avec la vie fixé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.
Relation
Université de Toulouse
Année 2020/2021
1 / 35
Relations
Relations2 / 35
Définition
Relation binaire
Unerelation binaireRd"un ensemble de départEvers un ensemble d"arrivéeFest définie par une partieGREF. Si(x;y)2GR, on dit quexesten relation avecyet l"on notexRy.SiE=Fon dit queRest unerelation internesurE.Exemples :SoientA=fa;b;c;d;egl"ensemble des élèves etB=fMath;Info;Ang;Physg
l"ensemble des cours. On peut définir les relations suivantes :Rqui décrit si un étudiant suit un cours régulièrement :
GR=f(a;Math);(a;Phys);(b;Info);(c;Ang);(d;Ang);(e;Math);(e;Ang)gla relationSdécrit si un étudiant a acheté un cadeau à un autre étudiant définit par
GS=f(b;a);(a;a);(c;a);(a;d);(d;c)gRelations3 / 35
Mode de représentation
Diagramme cartésien et matrice de relationRMathPhysAngInfo aVV bV cV dV eVVSabcde aV bVV cVV dV eDiagramme sagittal
a b c d eMathPhysAngInfoa bcdeRelations4 / 35
Relation fonctionnelle
Une fonctionf:E!Fassocie a chaque élément deEau plus un élément deF. On peut alors définir la relationRfdéfinie par le graphe GRf=f(x;f(x)) :x2Eg EF:
Réciproquement, pour une relationRtelle que pour toutx2Eil y a au plus uny2FvérifiantxRyalors on peut lui associer une fonctionftelle quef(x) =ysi et seulement sixRy. On dit queRest unerelation fonctionnelle.Relations5 / 35Relation réflexive
Réflexivité
Une relationRestréflexivesi pour toutx2Eon axRx:Diagramme cartésien : la diagonale doit être notée.
Diagramme sagittal : chaque sommet admet une boucle. 123123
1VVV 2VV 3V Exemples :Quel que soit l"ensemble, la relation d"égalité=est réflexive. Sur?, la relation est réflexive, mais
Symétrie
Une relationRestsymétriquesi pour toutx;y2Eon axRysi et seulement siyRx:Diagramme cartésien : symétrie par rapport à la diagonale. Diagramme sagittal : quand une flèche va deaversb, il y a aussi une flèche debversa.123 1231VV 2V 3V Exemples :Quel que soit l"ensemble, la relation d"égalité=est symétrique. Sur?, la relation est n"est pas symétrique.
La relation
lsurAest symétrique.Relations7 / 35Relation transitive
Transitivité
Une relationResttransitivesi pour toutx;y;z2Etel quexRyetyRz alors nécessairement on axRz.Diagramme sagittal : tout chemin qui part d"un sommetset va à un sommets0en suivant la direction des flèches admet un raccourci, c"està dire un chemin de longueur un.1
2341234
1V 2VVVV 3 4V Exemples :Quel que soit l"ensemble, la relation d"égalité=est transitive. Sur?, la relation est transitive. La relation "est le père de" n"est pas transitive.Relations8 / 35
Relation antisymétrique
Antisymétie
Une relationRestantisymétriquesi pour toutx;y2EvérifiantxRyet yRxalors on ax=y:12341234
1V 2VV 3VV 4VVExemples :Sur?, la relationest antisymétrique.
La relation
lsurAn"est pas antisymétrique.Relations9 / 35Relations d"équivalence
RelationsRelations d"équivalence10 / 35
Définition et exemples
Définition
Une relation binaire définie sur un unique ensembleEest unerelationd"équivalencesi elle est réflexive, symétrique et transitive.Exemples :Par définition, pourx;y2?, on notexy[modn], lirexest congru àymodulo
n, si et seulement s"il existek2?tel quexy=kn. On a défini une relation d"équivalence sur?car on peut vérifier :Réflexivité :xx[modn]carxx=0:net 02?.Symétrie :sixy[modn]alors il existek2?tel quexy=k:n, on a donc
yx=k:netk2?d"oùyx[modn].Transitivité :sixy[modn]etyz[modn]alors il existek;k02?tels que xy=k:netyz=k0:n. Ainsixz=xy+yz= (k+k0):n. On en déduit que xz[modn]RelationsRelations d"équivalence11 / 35Définition et exemples
Définition
Une relation binaire définie sur un unique ensembleEest unerelation d"équivalencesi elle est réflexive, symétrique et transitive.Exemples :Sur n"importe quel ensemble la relation=est une relation d"équivalence..Sur l"ensemble des motA, la relationlest une relation d"équivalence.Sur l"ensemble des personnes, la relation "a le même âge que" est une relation
d"équivalence. Des personnes liées appartiennent à la même tranche d"âge.Sur l"ensemble des triangles, la relation "a les mêmes angles que" est une relation
d"équivalence. Des triangles liés par cette relation sont dits semblables.La relationRdéfinie sur?rf0gparxRysi et seulement sixy>0 est une relation
d"équivalence. Deux réels liés par cette relation ont le même signe.RelationsRelations d"équivalence12 / 35
Classes d"équivalence et partition
Classes d"équivalence
SoitRune relation d"équivalence sur un ensembleE. Laclasse d"équivalenced"un élémentx, notéCl(x), est l"ensemble des éléments deEqui sont en relation avecx. Autrement dit
Cl(x) =fy2E:xRyg:Proposition
Une classe d"équivalence n"est jamais vide.
L"intersection de deux classes d"équivalence distinctes est vide.RelationsRelations d"équivalence13 / 35
Classes d"équivalence et partition
Partition
SoitEun ensemble, la famille d"ensembles(Ai)i2Iindexée parIest unepartitionsi :l"union des(Ai)i2Iest égale àE, c"est à direE=[i2IAi,deux éléments de(Ai)i2Idistincts sont disjoints, c"est à dire que si
i6=jalorsAi\Aj=;.Théorème Etant donné une relation d"équivalence sur un ensemble, les classes d"équivalences forment une partition.RelationsRelations d"équivalence14 / 35
Ensemble quotient
Ensemble quotient
SoitEun ensemble munit d"une relation d"équivalenceR. L"ensemble quotient est l"ensemble des classes d"équivalence de tous les éléments deE.On le noteE=R.Théorème
Etant donné une relation d"équivalenceRsurE, la fonction suivante est surjective : f:E!E=R x7!Cl(x)RelationsRelations d"équivalence15 / 35Relations d"ordre
RelationsRelations d"ordre16 / 35
Définition
Définition
Une relation binairesur un ensembleEest unerelation d"ordresi elle est réflexive, transitive et antisymétrique. Autrement dit : réflexive :on a xxpour toutx2E. transitive :si xyetyzalorsxz. antisymétrique :si xyetyxalorsx=y.Un ordre esttotalsi pour tous élémentsx;y2Eon axyouyx. Unordre est ditpartielpour souligner qu"on n"a pas forcément cette propriété.RelationsRelations d"ordre17 / 35
Exemples d"ordres sur les nombres
etsont des relations d"ordre total sur?qui s"étendent à?,?ou?.
Ordres sur les mots
Il existe différentes notions pour ordonner l"ensemble des motsA:La relationuest préfixe dev, notéeuvperdvet définit par9w2 A
tel quev=u:w, est une relation d"ordre qui n"est pas totalSoitun ordre total surAon définit l"ordre lexicographiquesur
A ulexv()8 >:upréfixe dev ou bien9m2?tel queu1:::um=v1:::vmetum+1vm+1
C"est une relation d"ordre total surA. Par exemple : alexfa,poulelexpoulet,avionlextrain, livraisonlexlivre,footlexfort.RelationsRelations d"ordre20 / 35Mode de représentation
123123
1VVV 2VV 3V Pour simplifier la lecture du diagramme, on supprime les boucles dues à la réflexivité et les flèches déductibles par transitivité :123 L"idée est de représenter les sommets du diagramme et tracer seulement les flèches correspondant aux successeurs immédiats. On dit queyest un successeur immédiat dexsixy,x6=yet il n"existe pas deztel que xzy.RelationsRelations d"ordre21 / 35Fonctions croissantes et décroissantes
Definition
SoientAetBdeux ensembles munis respectivement des relations d"ordreAetBetf:A!Bune application. On dit quefestcroissantesixAyalorsf(x)Bf(y).festdécroissantesixAyalorsf(y)Bf(x).feststrictement croissantesixAyetx6=yalorsf(x)Bf(y)
etf(x)6=f(y).feststrictement décroissantesixAyetx6=yalors f(y)Bf(x)etf(x)6=f(y).Proposition Une application strictement croissante ou strictement décroissante dont l"espace de départ est muni d"un ordre total est injective.RelationsRelations d"ordre22 / 35
Elément minimal, borne inférieure
Soit(E;)un ensemble ordonné etAE.x2AestminimaldeAs"il n"admet pas d"élément plus petit dansA.x2EminorantdeAsi8y2Aon axyAadmet au plus un seul minorant dansA(par antisymétrique), c"est
le plus petit élémentdeA, s"il existe on le notemin(A).Le plus grand des minorants est laborne inférieure, on la note
inf(A). Autrement dit :8y2Aon ainf(A)yet8zminorant deAon azinf(A)RelationsRelations d"ordre23 / 35
Elément maximal, borne supérieure
Soit(E;)un ensemble ordonné etAE.x2AestmaximaldeAs"il n"admet pas d"élément plus grand dansA.x2EmajorantdeAsi8y2Aon ayxAadmet au plus un seul majorant dansA(par antisymétrique), c"est
le plus grand élémentdeA, s"il existe on le notemax(A).Le plus petit des majorants est laborne supérieure, on la note
sup(A). Autrement dit :8y2Aon aysup(A)et8zmajorant deAon asup(A)zRelationsRelations d"ordre24 / 35
Induction
RelationsInduction25 / 35
Ordre bien fondé
Définition
Un ensemble ordonné(E;)estbien fondés"il n"existe pas de suite infinie strictement décroissante d"éléments deE.De manière équivalente, on a :Théorème
Un ensemble ordonné(E;)est bien fondé si et seulement si toute partie non vide admet au moins un élément minimal.Examples L"ordre usuelsur?est bien fondé mais il ne l"est pas sur?,?,[0;1].L"ordrejsur?n f0;1gdéfini par "ajb()adiviseb" est bien fondé.SoitAun alphabet contenant au moins deux lettres,vperdest bien
fondé mais paslex.RelationsInduction26 / 35Application à la terminaison d"algorithme
Variant de boucles
Etant donné(E;)un ordre bien fondé, unvariantde boucle est une fonction de l"ensemble des états du programme dansEstrictement décroissant à chaque passage dans la boucle.Proposition Si une boucle admet un variant alors elle termine.Algorithme d"Euclide :
Donnée :(x;y)2?2
Résultat : le pgcd dexety
a x b y whileb6=0dotmp a a b b tmp[modb]RelationsInduction27 / 35 Application à la terminaison des algorithmes récursifsProposition
Soitfune fonction récursive définit sur un ensemble ordonné(E;)bien fondé. Sifest défini sur les éléments minimaux et si pour toutx2Enon minimal, le définition def(x)ne fait appel à des valeursf(y)pouryx avecx6=yalorsfest bien définit.Examples : On considère la fonctionfactdéfinie par :fact(0) =1;fact(n+1) = (n+1)fact(n). Elle est bien définie car(?;)est bien fondé.On considère la fonctionfdéfinie sur?n f0;1gpar :f(p) =1 sippremier;f(n) =f(a) +f(b)sin=abeta6=1 etb6=1.
Elle est bien définie car(?n f0;1g;j)est bien fondé.RelationsInduction28 / 35 ?et le principe de récurrencePrincipe de récurrence SoitPune propriété dépendant d"un élémentnde?. Si les deux hypothèses suivantes sont vérifiéesInitialisation :P(0)est vraie,
Héridité :8n2?on a "P(n)est vraie=)P(n+1)est vraie"Alors pour toutn2?, la propriétéP(n)est vraie.Preuve :On raisonne par l"absurde : supposons que les hypothèses du théorème sont vraies
mais que la conclusion est fausse. SoitX=fn2?;P(n)est fausseg. L"ensembleXest une partie non vide de?, comme(?;) est bien fondé,Xadmet un plus petit élément notén0. CommeP(0)est vraie, on an0>0 doncn01 est un entier positif ou nul, autrement dit n012?.P(n01)est vraie carn01=2X. Par hypothèseP(n01) =)P(n0)donc
P(n0)est vraie ce qui est contradictoire avec le fait quen02X.RelationsInduction29 / 35 ?et le principe de récurrence généraliséPrincipe de récurrence généralisé SoitPune propriété dépendant d"un élémentnde?. Si les deux hypothèses suivantes sont vérifiéesInitialisation :P(0)est vraie,
Héridité :8n2?on a
"P(k)est vraie pourkPrincipe d"induction
Principe d"induction
SoitPune propriété dépendante d"un élémentxdeEmuni d"un ordre bien fondé. Si les deux hypothèses suivantes sont vérifiées : Initialisation :P(x)est vraie pour tout éléments minimaux deE,Héridité :
Si p ourtout x2Equi n"est pas minimal on a :
P(y)est vraie8yxavecy6=x=)P(x)est vraie
Alors pour toutx2E, la propriétéP(x)est vraie.Preuve :On raisonne par l"absurde. SoitX=fx2E;P(x)est fausseg. L"ensembleXest une partie non vide deE, comme(E;) est bien fondé,Xadmet un plus petit élément notéx0. CommePest vraie pour tout élément minimal deE, l"élémentx0n"est pas minimal. Pour tout y2Etel queyx0ety6=x0, la propriétéP(y)est vraie carx0minimal dansXet doncy=2X. Par hypothèse d"héréditéP(x0)est vraie ce qui est contradictoire avec le fait quex02X.RelationsInduction31 / 35
Définition inductive
Définition inductive d"un ensemble
SoitEun ensemble. Une définition inductive d"un sous-ensembleXdeEconsiste à la donnée :d"un sous-ensembleBdeEappelébase,d"un ensembleKd"opérations':Er'!Eoùr'est l"arité de'.
L"ensembleXest alors défini comme le plus petit (pour l"inclusion) ensemble vérifiant les assertions suivantes :Base :BX,
Induction :
p ourtout '2Ket pour tousx1;x2;:::;xr'2Xon a '(x1;x2;:::;xr')2X. On dit queXest lafermeture inductive deBparK.RelationsInduction32 / 35Quelques ensembles définis inductivement :
L"ensemble des entiers naturels est défini par :Base :B=f0g,
Induction :
succ:?!? n7!n+1.L"ensemble des entiers pairs est défini par :Base :B=f0g,
Induction :
n7!n+2.L"ensemble des entiers impairs est défini par :Base :B=f1g,
Induction :
n7!n+2.L"ensemble des mots binaires est défini par :Base :B=f"g,
Induction :
'0:A! A u7!0uet'1:A! A u7!1u.RelationsInduction33 / 35 Preuve pour des ensembles définis par inductionPreuve par induction
SoitXEla fermeture inductive deBparK. SoitPune propriété définie surX. Pour montrer que pour toutx2Xla propriétéP(x)est vraie, il suffit de montrer que :Base :
P ourtout x2B, on aP(x)vraie.
Induction
P ourtout '2Kd"aritér'et tousx1;x2;:::;xr'alors on a P(x1);P(x2);:::;P(xr')vraies=)P('(x1;x2;:::;xr'))vraieRelationsInduction34 / 35Exemple de preuve par induction
On considère l"ensemble des mots de Dyck f0;1gdéfini par :Base :B=f"g,Induction : :A A! A (u;v)7!0u1v. On veut montrer par induction que tout motw2vérifie la propriétéP(w): "wa autant de 0que de 1 et tout préfixe dewa plus de 0 que de 1".Base :"vérifie la propriété demandée,Induction :Soient u;v2tels queP(u)etP(v)soient vérifiées. On note
w= (u;v) =0u1v. Commeuetvont autant de 0 et de 1, il en est de même pourw.Soittun préfixe dew. Il y a deux cas :
I Sijtj 1+jujalorstest un préfixe de 0u. Il s"écritt=0t0oùt0est un préfixe de u. Comme les préfixes deuont plus de 0 que de 1, on en déduit queta plus de 0 que de 1. I Sijtj>1+jujalorsts"écritt=0u1t0oùt0est un préfixe dev. Comme lespréfixes devont plus de 0 que de 1, on en déduit queta plus de 0 que de 1.RelationsInduction35 / 35
quotesdbs_dbs47.pdfusesText_47