Table des mati`eres
Par exemple sur N ou sur R la relation ? est une relation d'ordre. Nous introduirons aussi les relations dites d'équivalence
1. Relations binaires 2. Relations déquivalence 3. Relations dordre
2. Relations d'équivalence. Définition. Une relation binaire est une relation d'équivalence si et seulement si elle est réflexive symétrique et transitive.
Relations binaires. Relations déquivalence et dordre
20 août 2017 Définition 1 : Une relation binaire ? définie sur un ensemble E est au choix : • une propriété qui relie ou non deux éléments x et y de E.
RELATION BINAIRE
1. Vérifier que la relation est une relation d'équivalence. 2. Faire la liste des classes d'équivalences distinctes et donner l'ensemble quotient .
CHAPITRE 3 : Relations déquivalence et ensemble quotient
7 mars 2018 1.0.1 Définition: une relation R:AxA est une relation d'équivalence sur A si R est reflexive symétrique et transitive.
1 Exemples simples de relations déquivalence 2 Construction de
Déterminer [(x0y0)]
Rappel : relation déquivalence • Nouveaux nombres : Q et Z /mZ. • C
C'est une relation d'équivalence sur U : MAT1500. 7 of 40. Page 8. Démonstration. Soient (n1d1)
Relations 1 Introduction aux relations déquivalence : classer les
Définir une relation d'équivalence c'est précisément définir un critère Il y a deux "classes d'équivalence" : la “classe des hommes" et la “classe des.
Relation déquivalence relation dordre
est une relation d'équivalence. Préciser pour x fixé dans R
Ensembles Relations déquivalence
https://livres-mathematiques.fr/onewebmedia/L1-MI-arith-ch1.pdf
Math 127: Equivalence Relations - CMU
Math 127: Equivalence Relations Mary Radcli e 1 Equivalence Relations Relations can take many forms in mathematics In these notes we focus especially on equivalence relations but there are many other types of relations (such as order relations) that exist De nition 1 Let X;Y be sets
An Infinite Descent into Pure Mathematics
relationship between equivalence relations and partitions Note that throughout this lecture we have already seen that an equivalence relation induces a partition but now we shall formally prove this phenomenon Theorem 1 If R is an equivalence relation on a set S then the equivalence classes of R partition S Proof
Lecture 3: Equivalence Relations - UC Santa Barbara
Equivalence relations are remarkably useful because they allow us to work with the concept of equivalence classes: De nition Take any set S with an equivalence relation R For any element x 2S we can de ne the equivalence class corresponding to x as the set fs 2S jsRxg Again you have worked with lots of equivalence classes before For mod 3
Equivalence Relations - Mathematical and Statistical Sciences
An Important Equivalence Relation Let S be the set of fractions: S ={p q: pq??q?0} Define a relation R on S by: a b R c d iff ad=bc This relation is an equivalence relation 1) For any fraction a/b a/b R a/b since ab = ba (Reflexitivity) 2) If a/b R c/d then ad = bc so cb = da and c/d R a/b (Symmetry)
Equivalence Relations - mathcmuedu
1 Determine whether the following relations are equivalence relations on the given set S If the relation is in fact an equivalence relation describe its equivalence classes (a) S = Nnf0;1g; (x;y) 2R if and only if gcd(x;y) > 1 (b) S = R; (a;b) 2R if and only if a2 + a = b2 + b: (c) S = R; (x;y) 2R if and only if there exists n 2Z such that
Searches related to relation d+equivalence pdf PDF
Using equivalence relations to de?ne rational numbers Consider the set S = {(xy) ? Z × Z: y 6= 0 } We de?ne a rational number to be an equivalence classes of elements of S under the equivalence relation (ab) ’ (cd) ?? ad = bc An equivalence class is a complete set of equivalent elements
What are equivalence relations?
Equivalence classes What makes equivalence relations so useful is they give us a way of ignoring information that is irrelevant to the task at hand. For example, suppose a and b are two very large natural numbers, each with several trillion (decimal) digits. We want to know what the last digit of ab is.
Which equivalence class is F?
Let F be any partition of the set S. Define a relation on S by x R y iff there is a set in F which contains both x and y. Then R is an equivalence relation and the equivalence classes of R are the sets of Pf: Since F is a partition, for each x in S there is one (and only one) set of F which contains x.
What is a leaner definition of equivalence?
A leaner de?nition is: If R is an equivalence relation on a set S, then we de?ne the equivalence class of an element x ? S to be the set of all elements of S equivalent to x. Then we need to prove: 5 Theorem 1.
What is an equivalence class?
An equivalence class is a complete set of equivalent elements. I.e., it’s a set of elements of S, all of which are equivalent to each other, and which contains all of the pairs that are equivalent to those pairs. (Stricly speaking we need to use some properties of equivalence relations to check that this makes sense ...more about that later.)
CHAPITRE 3 : Relations d"équivalence et
ensemble quotientMichaël PÉRIM
March 7, 2018
Contents
1 Rappel des définitions 2
1.0.1 Définition: une relation R:AxA est une relation d"équivalence
sur A si R est reflexive, symétrique et transitive . . . . 21.0.2 Exemples de relations d"équivalence . . . . . . . . . . 2
1.0.3 Classes d"équivalence . . . . . . . . . . . . . . . . . . . 3
1.0.4 Une relation d"équivalence ~:AxA definit une partition
de A en classes d"équivalences : . . . . . . . . . . . . . 31.0.5 Réciproquement, une partition de A définit une rela-
tion d"équivalence . . . . . . . . . . . . . . . . . . . . . 42 Utilités des relations d"équivalences 4
2.1 La réprésentation de données . . . . . . . . . . . . . . . . . . 4
2.1.1 Exemple des les expressions arithmétiques . . . . . . . 4
2.1.2 Exemple des rationnels . . . . . . . . . . . . . . . . . . 5
2.1.3 Exemple des ensembles . . . . . . . . . . . . . . . . . . 5
2.2 Représentant canonique et relation d"équivalence induite . . . 5
2.2.1 Exemple des rationnels . . . . . . . . . . . . . . . . . . 6
2.2.2 Exemple des expressions arithmétiques . . . . . . . . . 6
2.2.3 Exemple des ensembles . . . . . . . . . . . . . . . . . . 6
2.3 Ensemble quotient et ensemble des représentants canoniques . 7
2.3.1 Définition: L"ensemble quotient de A par la relation
d"équivalence ~, noté A/~, est l"ensemble des classes d"équivalence de la relation ~ : . . . . . . . . . . . . . 72.3.2 Définition: L"ensemble des représentants canoniques
de A, noté A/[], est en bijection avec l"ensemble quo- tient A/~ . . . . . . . . . . . . . . . . . . . . . . . . . 7 12.3.3 Exemple des rationnels Q . . . . . . . . . . . . . . . . 7
2.4 Attention, certaines opérations ne préservent pas la canonicité 7
2.4.1 Cas des expressions arithmétiques . . . . . . . . . . . 8
2.4.2 Cas des ensembles . . . . . . . . . . . . . . . . . . . . 8
3 Les relations d"équivalences sont partout ! 8
1 Rappel des définitions
1.0.1 Définition: une relation R:AxA est une relation d"équivalence
sur A si R est reflexive, symétrique et transitive Notationon utilise souvent le symbole "~":AxA au lieu de R:AxA pour une relation d"équivalence "~" est reflexive ie. QQ a:A. a ~ a "~" est symétrique ie. QQ a1,a2:A. a1 ~ a2 ==> a2 ~ a1 "~" est transitive ie. QQ a1,a2,a3:A. a1 ~ a2 /na2 ~ a3 ==> a1 ~ a31.0.2 Exemples de relations d"équivalence
Sans le savoir vous vivez dans un monde d"équivalences !1. La plus petite relation d"équivalence (celle qui a le moins d"arcs) est la
relation d"égalité sur A qu"on note "=" :2. Relation d"équivalence sur les heures :
18:45 ~ 6:45 PM ~ 7h moins le quart
3. Relation d"équivalence sur les sacs d"aspirateurs : regardez votre boîte
de sacs d"aspirateurs vous verrez que vos sacs conviennent à plusieurs marques d"aspirateursHoover 500 ~ Miele Boost ~ Rowenta Plus
Dyson ~ Air pulse II ~ Philips Clean (qui n"ont pas de sacs...) mais Hoover 500/Dyson4. Les mathématiciens aiment faire remarquer qu"il existe une relation
d"équivalence sur les rationnels3/2 ~ 6/4 ~ 9/6 et 1/2 ~ 2/4 ~ 3/6
25. La définition des ensembles repose sur une relation d"équivalence qui
dit que {1,2} ~ {2,1} ~ {1,1,1,1,2} ~ {1,2,1,2}1.0.3 Classes d"équivalence
La classe d"équivalence d"un élémentade A est notéeCl(a) c"est l"ensemble des éléments qui sont équivalent àapour la relation "~"Cl(a) = { x:A | x ~ a }
Exemples
1. Cl(Hoover 500) = { Hoover 500, Miele Boost, Rowenta Plus }
2. Cl(Hoover 500) = Cl(Miele Boost) = Cl(Rowenta Plus) puisque ces
trois références de sacs sont équivalentes.1.0.4 Une relation d"équivalence ~:AxA definit une partition de
A en classes d"équivalences :
1. L"ensemble A correspond exactement à la réunion des classes d"équivalences
de "~"A = Union
a:ACl(a) Autrement dit, les classes d"équivalences de "~" partionnent l"ensembleA en sous-ensembles disjoints :
•les éléments équivalents à a1 •les éléments équivalents à a2 ...2. si a/a" alors Cl(a) inter Cl(a")= {}
si deux éléments a et a" ne sont pas équivalents alors leurs classes d"équivalences n"ont pas d"éléments en commun.3. si a ~ a" alors Cl(a) = Cl(a")
si deux éléments a et a" sont équivalents alors leurs classes d"équivalences sont les mêmes Les propriétés 2 et 3 se résume ainsi : deux classes d"équivalences sont soit disjointes soit confondues. 31.0.5 Réciproquement, une partition de A définit une relation
d"équivalence Supposons que l"ensemble A correspondent à l"union de sous-ensemblesA1,...., An
ie.A = A1 union A2 union .... union An alors la relation R:AxA définit par x R ysi et seulement si il existe i tel que x et y sont dans le même sous-ensemble Ai est une relation d"équivalence.2 Utilités des relations d"équivalences
2.1 La réprésentation de données
Regardez un dictionnaire, vous verrez que l"informatique est définie comme " l"activité de traitement automatisé d"informations». Chaque fois qu"un in- formaticien doit écrire un programme de traitement d"informations, il com- mence par se demander comment représenter en mémoire les données à traiter. Nous allons voir qu"aussitôt surgissent des questions qui font appels aux relations d"équivalences, classes d"équivalence, représentant canonique, ensemble quotient. Pour illustrer ce cours nous considérerons trois exemples : les ensembles et les expressions arithmétiques et les rationnels.2.1.1 Exemple des les expressions arithmétiques
On aimerait représenter des expressions arithmétiques qui comportent des variables a,b,... ; des opérateurs +,-,*, ... ; des constances 0, 1, ...; des parenthèse (,).Exemple : a + b + c
On constate rapidement qu"il y a une infinité de manière de représenter a + b + c :1. a + b + c
2. a + c + b
3. (a + c) + b
4. (a + 0 + c) * 1 + b
5. 1 * (0 + 1 * (0 + 1 * (0 + a + b + c)))
46. ...
et que toutes ces représentations sont équivalentes (tiens, tiens, voici qu"apparaît la notion d"équivalence). mais que " a + b + c » est la version la plus élégante, la plus " canon » (tiens, tiens, voici qu"apparaît la notion de représentant canonique). Remarque: Il faut bien différencier la notion d"égalité de la notion d"équivalence. •" a + b + c » et " a + c + b » ne sont pas égale (noté "=") puisqu"on remarque bien que c et b ne sont pas à la même place dans ces deux expressions. •En revanche elles sont équivalentes (noté "~") puisqu"elles donneront la même valeur qu"elles que soient les valeurs de a,b,c. Les mathématiciens ont la facheuse habitude d"écrire " a + b + c » = " a + c + b » (égalité) alors queil faudrait écrire" a + b + c » ~ " a + c + b » ( ~ signifie équivalence)2.1.2 Exemple des rationnels
Il y a de nombreuses façons équivalentes de réprésenter chaque fraction :1/2 ~ 2/4 ~ 3/6 ~ 4/8 ~ ...~ 4.10
248/ 8.10248~ ...
3/2 ~ 6/4 ~ 9/6 ~ 12/8 ~ ...~ 12.10
248/ 8.10248~ ...
2.1.3 Exemple des ensembles
Il y a de nombreuses façons équivalentes de représenter chaque ensemble : {1} ~ {1,1} ~ {1,1,1} ~ ... ~ {1,1,...,1} ~ ... {1,2} ~ {2,1} ~ {1,2,1} ~ {2,2,1} ~ ... C"est troublant mais ce sont bien des réprésentations équivalentes puisque la définition ditDeux ensembles E et F sont équivalents si les élé- ments de E apparaissent (au moins une fois) dans F et réciproqe- ment.2.2 Représentant canonique et relation d"équivalence induite
Dés qu"ils ont choisi une représentation des données A. Les informaticiens définissent une fonctioncanon : A -> Aqui à chaque élémenta:Aassocie sonreprésentant canonique. 5 Les informaticiens ont l"habitude de définir la relation d"équivalence à partir du représentant canonique de la manière suivante : PropositionDeux éléments a1,a2:A sont équivalents si leur représen- tants canoniques sont les mêmes. Les informaticiens définissent une fonction (equiv : A * A -> bool ) let equiv (a1,a2) := canon(a1)?canon(a2)2.2.1 Exemple des rationnels
canon ( a / b ) := fraction reduite( a/b ) où fractionreduite( a / b) : = a divisé par pgcd(a,b) / b divisé par pgcd(a,b) equiv ( a/b , c/d) := canon(a/b)?canon(c/d)Exemple :
canon( 15/21 ) = 5/7 campm( 10/14 ) = 5/7 et donc equiv( 15/21, 10/14 ) == true2.2.2 Exemple des expressions arithmétiques
canon ( ea ) := l"expression ea sans symbole inutile avec les variables appa- raissant dans l"ordre alphabétique equiv ( ea1, ea2 ) := canon(ea1)?canon(ea2)Exemple:
canon(" 0 + (a + b) + c » ) == " a + b + c » canon(" b + c + a » ) == " a + b + c » et donc equiv(" 0 + (a + b) + c » , " b + c + a » ) == true2.2.3 Exemple des ensembles
canon ( ens ) := l"ensemble sans répétition avec les éléments rangés dans l"ordre croissant equiv (ens1, ens2) := canon(ens1)?canon(ens2)Exemple :
canon ({1,2,2,1}) == {1,2} canon( {2,1} ) == {1,2} et donc equiv ( {1,2,2,1} , {2,1} ) == true 62.3 Ensemble quotient et ensemble des représentants canon-
iques2.3.1 Définition: L"ensemble quotient de A par la relation
d"équivalence ~, noté A/~, est l"ensemble des classes d"équivalence de la relation ~ : A/~ = { Cl(a) | a:A } c"est un ensemble d"ensemble2.3.2 Définition: L"ensemble des représentants canoniques de A,
noté A/[], est en bijection avec l"ensemble quotient A/~ A/[] = { [a] | a:A } c"est un sous-ensemble de A, qui ne conserve qu"un élément par classes d"équivalence (l"élément le plus "canon"...) Les mathématiciens notent [a] pour le représentant canonique donné par la fonction canon : [a] c"est plus rapide à écrire que canon(a)Remarque
•Les mathématiciens ont l"habitude de travailler avec l"ensemble quo- tient A/~ qui est un ensemble d"ensemble. Ça les oblige à travailler avec des ensembles d"ensembles (mais ils n"ont pas de problèmes de mé- moire limitée...) mais cela leur évite d"avoir à choisir un représentant canonique. •Les informaticiens préfèrent travailler avec l"ensembles A/[] des représen- tants canonique qui est une sous-ensemble de A. Ça les oblige à définir la fonction canon mais ça leur donne des représentations plus simples qui prennent moins de places en mémoire.2.3.3 Exemple des rationnels Q
Q/~ = { Cl(1/2) , Cl(1/3) , ... }
= { {1/2, 2/4, 3/6, ...} , {1/3, 2/6, 4/8, ...} , ... }Q/[] = { 1/2, 1/3, ... }
2.4 Attention, certaines opérations ne préservent pas la
canonicité Pour les informaticiens il est plus simple de travailler avec l"ensemble A/[] des représentants canoniques. Il faut donc faire attention à programmer les opérations sur A de façon à ce qu"elle ne produise QUE des représentants canoniques. 72.4.1 Cas des expressions arithmétiques
Si on programme l"addition entre deux expressions arithmétiques comme ceci addition (ea1 , ea2) := ea1 "+" ea2 on n"obtient pas forcément un représentant canonique : addition ( " a + b + c » , " a + b » ) == " a + b + c + a + b » n"est pas canonique il fallait retourenr " 2 a + 2 b + c » Bien sûr, on pourrait programmer l"addition en faisant le " + » naïf comme ci-dessous puis appeler la fonction " canon » pour prendre le représen- tant canonique. addition canonique( ea1 , ea2) := canon (ea1 "+» ea2 ) Ça marcherait mais ça ne serait pas efficace. Il est préférable de chercher un algorithme qui canonise pendant qu"il fait le " + ».2.4.2 Cas des ensembles
Si on programme l"union de deux ensembles comme ceci: union ( { ens1 } , { ens2 } ) := { ens1, ens2 } on n"obtient pas forcément un représentant canonique : union ( {1,2,3} , {0,2,5} ) == {1,2,3,0,2,5} n"est pas canonique il fallait retourenr {0,1,2,5} On peut trouver un algorithme qui fait l"union efficacement et retourne un représentant canonique3 Les relations d"équivalences sont partout !
On a vu le cas des expressions arithmétiques, des rationnels, des ensembles, des sacs d"aspirateurs, des heures et il y a beaucoup d"autres. Chaque fois que vous dîtes " et des brouettes » , " à deux pouièmes » , " modulo des broutilles » , " plus ou moins des poussières » , " au signe près » , " indépendamment de la vitesse », etc... cela cache une relation d"équivalence. Lorsque vous demandez dans une crepèrie de remplacer le jambon par un oeuf et que le prix ne change pas c"est que les deux crèpes sont équivalentes (pour le prix). Lorsque le pharmacien vous propose de remplacer un médicament par son médicament générique. Il vous dit que ces médicaments sont équivalents. Ce qu"il ne vous dit pas (mais faîtes lui remarquer la prochaine fois) c"est que le médicament générique est le représentant canonique ! 8quotesdbs_dbs12.pdfusesText_18[PDF] relation binaire exercices corrigés pdf
[PDF] relation d'équivalence et classe d'équivalence
[PDF] exo7 relation binaire
[PDF] liste des verbes d'action
[PDF] liste des verbes d'état cm2
[PDF] exercice sur les verbes d'état et d'action cm2
[PDF] les verbes d'action pdf
[PDF] film éthique et culture religieuse
[PDF] les verbes d'état pdf
[PDF] tous les verbes d'état
[PDF] liste des verbes attributifs
[PDF] surclassement pop corn c'est quoi
[PDF] upload file magazines gaumont 262 web
[PDF] exercice de maths rapport et proportion
