[PDF] [PDF] Contribution Relations binaires dans un ensemble à 3 éléments

View - Download [PDF] Contribution Relations binaires dans un ensemble à 3 éléments

Previous PDF

Next PDF

Contribution

Relations binaires dans un ensemble à 3 éléments

Jacques Sormany et Corentin Guimet,

Université du Québec à Chicoutimi

RésuméCombien de relations binaires peut-on établir dans un ensemble ànéléments? Parmi

celles-ci, combien sont réflexives? symétriques? transitives? Les cas oùn=0, 1 ou 2 ont une portée très limitée, mais déjà pourn= 3on obtient une situation très riche en possibilités. Les 512 relations peuvent être regroupées en 104 graphes sagittaux qui seront présentés ici de façon synoptique. Quelques tableaux résumeront l"information sur

le nombre d"occurrences des différentes propriétés; les interactions entre ces propriétés

seront aussi analysées. On compilera aussi le nombre d"opérations internes possibles, avec leurs propriétés : idempotence, commutativité et associativité.

Mots clés :

relation (binaire, interne, complémentaire, vide), réflexivité, symétrie, transitivité,

graphe (sagittal, dual), opération interne.

1 Relation binaire

Unerelation binaireRd"un ensembleEvers un ensembleFest définie comme un ensemble de couples(x;y)?E×F, c"est-à-dire un sous-ensemble du produit cartésienE×F; siE=F, on dit queRest unerelation internedansE: alorsRest un sous-ensemble du produit cartésienE2. Pour dire qu"un couple(x;y)appartient àR, ou vérifie la relation, on écrit aussi :x R y. Legraphe sagittald"une relationRdans un ensembleEest un diagramme où chaque élément deEest représenté par un point, chaque couple(x;y)par une flèche orientée dexversy(une

double flèche, ou un simple trait, si la relation est aussi vérifiée deyversx), et chaque couple

(x;x)par une boucle reliantxà lui-même. Dans un ensemble ànéléments, combien y a-t-il de relations binaires possibles?

Il y an2couples possibles, et pour chaque couple deux possibilités : appartenir àR(vérifier la

relation), ou ne pas appartenir àR(ne pas la vérifier). Il y a donc2n2relations possibles. Cette

formule est valide pourn= 0: dans l"ensemble vide∅il existe une seule relation, larelation vide.

64-Bulletin AMQ, Vol. LIX, no3, octobre 2019c?Association mathématique du QuébecAssociation

math´ematique duQu´ ebec L"AssociationMath´ematiqueduQu´e becregroupedespersonnes,dessoci´e- t´es,´ecoles,comm issionsscolaires,coll`e ges,universit´es,institutsd erecherche, soci´et´esindustrielles,oucomme rcialesquis"int´eressent`al"enseignement,` ala recherche,aud´eveloppement,`ala diffusionoulavulgar isat iondesm ath´ema- tiques. Ellevise`aaid erles´educat eurs,d uprimaire`al" Universit ´e,dansleurtravail enmett ant`aleurdisposition divers servicesetr essources.

Ellefavorise les´echangesentrelesdiff´erentsordresd"enseigne mentdesmath´emat iquesetcollabore

auxinit iativesduMinist`eredel"´educati onquis" inscriventdanscesens. Ellefavoriseu nemise`ajourcontinuede l"enseigne mentdesmath´ ematiqu es,etpourc efaireelle

collaboreaveclesinsti tutionsd"ens eignement, les´editeursetdiversmath´ematicien squioeuvrenten

dehorsdesmilieux acad´emiqu es.

Ellesuscitep arsesactivit´esetsespu blicati onsunint´ erˆetplusgrandpourlesmath´emati ques.

www.mat.ulaval.ca/amq/ L"AssociationMath´ematiqueduQu´e becpublieleBulletinAMQ4foi sparann´ee, soitles 15mars,

15mai ,15octobree t15d ´ecembre.

Lesnum´ erosdesann´eesant´erieu ressontd´e pos´essurlesitedel "AMQunanapr`esleurparutionen

versionsurpapier. Touslesmem bresdel"As sociationMath´ematiquedu Qu´ebe cre¸coiventuneversionsurpapierd u BulletinAMQ.Pou rdevenirm embre,rempliretenvoy er`al"adresseindiqu´e eleformulaired"adh´esion disponiblesurlesite.Enconsul tantsurle sitela Politiqueder´edactionduBulletinAMQ,ont rouv e lastru cturedecontenudubulletinains iquele sth`emesabord´esparc elui-c i.Onytrouveaussila

mani`eredontsontg´er´es lesdroitsd ereprodu ction,d"adaptationetdetrad uctiondest extespubli´es

danslebull etin. Lesauteu rspotentielsytrouve rontaussil"adresse`alaquelleen voy erleurspropositionsdetexte s ainsiquelade scriptiond uproce ssusd"arbitrage. Ilsdevraie ntdeplusconsulterlesNormesdepr´esenta tionenvigue uraubulletin. Enfin,c"estdansla sectionGabaritsquelesaut eurspotent ielstrouverontdeuxgab aritsTeX,l"un pourd´ebut ants(GabaritAMQ101)etl"autrepourles initi´es(GabaritAMQpro).Ilstrou verontd es consignesd"ordretypographi quedanslesNormesdepr´esentat ion. Mercidefaireconn aˆıtre l"Association Math´ematiqueduQu´ebecetsare vueautourde vousetd"y proposer oususciter desarticles(indicat ions pourlessoumissionssurle sitedel"asso ciation)

1Certaines relations présentent le même graphe sagittal, en permutant les éléments. Bien que

des calculs combinatoires puissent aider à dénombrer les types de graphes, nous ne connaissons pas de formule simple qui permette d"y arriver directement à partir du nombre d"éléments de l"ensemble (voir l"Encycl opédieen ligne des suites de nom bresen tiers

Le tableau

1 indique le nom brede couple sd"élémen tsde la forme (x;x)ou(x;y), impliqués dans chaque graphe ou relation. Le nombrekde couples est compris entre0etn2; on voit que le nombre de relations comportantkcouples s"obtient directement par la formule des combinaisons :n2!k!(n2-k)!.Nombren= 2n= 3de couplesG NG N

01 11 1

12 42 9

24 68 36

32 417 84

41 124 126

524 126

617 84

78 36
82 9
91 1

Total10 16104 512

Tableau1 - Nombre de couples par relation

G= nombre de graphesN= nombre de relations

2 Réflexivité

On qualifie deréflexiveune relation dans laquelle tout couple(x;x)vérifie la relation, c"est-à-

dire que?x?E:x R x; une relation est diteantiréflexivesi aucun couple(x;x)ne vérifie la relation. Pour qu"une relation soit réflexive, il faut aussi qu"?x?E|x R x. En vertu de cette condition, la relation vide, qui est antiréflexive dans tout ensemble non vide, l"est aussi dans l"ensemble vide. Parmi les2n2relations binaires dans un ensemble ànéléments, combien sont réflexives? DansE2, il y an(n-1)couples de composantes distinctesx?=y, et pour chacun de ces couples

2 possibilités : vérifier ou non la relation. Pourn >0il y a donc2n(n-1)relations réflexives, et

le même nombre de relations antiréflexives.

Bulletin AMQ, Vol. LIX, no3, octobre 2019-65Ledegré de réflexivitéd"une relation est le nombre d"éléments de l"ensembleEen relation

avec eux-mêmes : il est compris entre 0 (pour une relation antiréflexive) etn(pour une relation

réflexive); c"est aussi le nombre de boucles visibles sur le graphe sagittal.

3 Symétrie

On qualifie desymétriqueune relation dans laquelle?(x;y)?E2, x R y?y R x. Il n"est

pas nécessaire qu"il existe de couple vérifiant la relation : par exemple, la relation vide est

symétrique. Une relation non symétrique est diteantisymétriquequand pour tout couple d"éléments

distincts considérés, si la relation est vérifiée dexversy, elle ne l"est jamais dans l"autre sens.

Pour qu"une relation soit symétrique, il suffit que son graphe sagittal ne comporte aucune

simple flèche. Celui d"une relation antisymétrique ne doit comporter aucune double flèche, mais

au moins une flèche simple. La présence ou l"absence de boucles n"affecte pas la propriété de

symétrie ou d"antisymétrie. On qualifie toutefois defortement antisymétriqueune relation à la fois antisymétrique et antiréflexive. On pourrait appelerdegré de symétriele nombre de doubles flèches sur un graphe; mais

comme un graphe symétrique peut ne présenter aucune double flèche, il paraît plus pertinent de

parler dedegré d"antisymétried"une relation : le nombre de couples qui vérifient la relation

dans un sens seulement mais non dans l"autre, ce qui est représenté par autant de flèches simples

sur le diagramme sagittal. Le degré d"antisymétrie est donc égal à0si et seulement si la relation

est symétrique; pour une relation non symétrique ou antisymétrique, il est compris entre 1 et

n(n-1)/2. Parmi les relations internes d"un ensemble ànéléments, combien sont symétriques? Auxn(n-1)/2paires d"éléments distincts il faut ajouter lesncouples(x;x), pour un total de n(n+ 1)/2couples pouvant chacun vérifier ou non la relation. Il y a donc2n(n+1)/2relations symétriques possibles. Le calcul du nombre de relations antisymétriques est un peu plus compliqué. Chacun des

élémentsxpeut ou non être en relation avec lui-même, ce qui donne2npossibilités; et pour

lesn(n-1)/2paires d"éléments distincts, il y a 4 possibilités : dexversy, deyversx, ni

l"un ni l"autre, ou les deux. Cette dernière éventualité (illustrée par une double flèche) étant

incompatible avec l"antisymétrie, il reste(4-1)n(n-1)/2possibilités, dont on exclura le cas où

aucune flèche simple n"apparaîtrait sur le graphe (degré nul d"antisymétrie). Cela laisse donc

finalement2n(3n(n-1)/2-1)relations antisymétriques; cette formule demeure correcte dans les cas oùn= 0ou 1, pour lesquels toute relation est nécessairement symétrique.

66-Bulletin AMQ, Vol. LIX, no3, octobre 20194 Transitivité

On qualifie detransitiveune relation pour laquelle

?x, y, z?E, x?=y, y?=z: (x R y)?(y R z)?(x R z).L"existence de triplets illustrant la propriété n"est pas nécessaire : par exemple, la relation vide

est transitive. Sur le graphe sagittal d"une relation transitive, deux flèches consécutives doivent

être complétées par une troisième flèche allant du premier élément,x, vers le dernier,z. Un cas

particulier est celui oùx=z: pour que la relation soit transitive, il faut qu"une boucle soit présente aux deux extrémités de toute double flèche. Une relation non transitive est diteantitransitivesi la conjonction(x R y)?(y R z)implique

que la relation n"est pas vérifiée dexversz. Un graphe sagittal antitransitif ne comporte aucun

triplet respectant la transitivité, et aucune double flèche munie de boucle à une extrémité; mais

il doit présenter au moins une occurrence où la transitivité est prise en défaut. On pourrait définir ledegré de transitivitéet celuid"antitransitivitéd"une relation : ce

dernier serait, sur le graphe, le nombre de flèches consécutives non munies de raccourci, plus le

nombre de boucles manquantes aux extrémités des doubles flèches; il serait égal à0pour toute

relation transitive. Mais on ne connaît aucune formule permettant de calculer directement, à partir du nombre nd"éléments de l"ensembleE, le nombre de relations internes transitives ou antitransitives possibles, ni le degré d"antitransitivité d"une relation quelconque dans cet ensemble. Des

algorithmes ont toutefois été trouvés pour compiler le nombre de relations transitives dans des

ensembles ànéléments (ici encore, le lecteur pourra consulterl"Encyclop édieen l ignedes su ites

de nombres entiers

Le tableau

2 présen tele nom breNde relations internes, le nombreGde graphes sagittaux

ainsi que le nombre de relations réflexives(R+), antiréflexives(R-), symétriques(S+), antisy-

métriques(S-), transitives(T+)et antitransitives(T-)pour les petites valeurs den, cardinal de l"ensembleEconsidéré :nN= 2n2GR +R -= 2n(n-1)S += 2n(n+1)/2S -T +T -011011010

122112020

216104488131

351210464646420817197

465 5363 0444 0964 0961 02411 6483 994?

533 554 532291 9681 048 5761 048 57632 7681 889 536154 303

Tableau2 - Nombre et types de relations

Bulletin AMQ, Vol. LIX, no3, octobre 2019-675 Relation réciproque, relation complémentaire, graphe

dualToute relation binaireRd"un ensembleEvers un ensembleFadmet une et une seule relation réciproque, généralement notéeR-1, définie deFversEcomme suit : R -1={(y;x)?(F×E)|(x;y)?R}. SiE=F, la relation réciproque est donc elle aussi interne dansE. La réciproque de la réciproque est la relation elle-même :(R-1)-1=R.

Les propriétés (réflexivité, etc.) d"une relation et de sa réciproque sont les mêmes; leurs graphes

sagittaux sont semblables, sauf que toutes les flèches simples sont changées de sens. Plus

particulièrement, toute relation symétrique est sa propre réciproque (c"est la cas pour la relation

vide); les degrés de réflexivité, d"antisymétrie et de transitivité ou d"antitransitivité de deux

relations mutuellement réciproques restent les mêmes. Toute relation binaire dans un ensemble non videEadmet une et une seule relation dite

complémentaire, que nous noterons ici¬R(on trouve aussiR?,¯R,≂R, etc.), définie de la

façon suivante :

¬R={(x;z)?E2|(x;z)??R}.

La complémentaire de la complémentaire est la relation elle-même :¬(¬R) =R.

L"intersection d"une relation avec sa complémentaire est vide; la réunion d"une relation avec sa

complémentaire est larelation pleineE2. La complémentaire d"une relation vide est pleine, sauf dans∅où l"unique relation possible (vide) n"a pas de complémentaire.

Dans un ensembleEconstitué denéléments, la somme des degrés de réflexivité deRet de¬R

est égale àn; en particulier, la complémentaire d"une relation réflexive est antiréflexive, et vice

versa.

La complémentaire d"une relation symétrique est symétrique, mais celle d"une relation antisy-

métrique n"est pas nécessairement antisymétrique. Pour la transitivité ou l"antitransitivité, il

n"y a pas de règle absolue. On appellegraphe dualle graphe sagittal de la relation complémentaire. Chaque élément de Esera muni d"une boucle, soit sur le graphe deR, soit sur le graphe de¬R(duaux l"un de l"autre). Si une relationRest vérifiée dexversymais non dans l"autre sens, la relation¬Rle sera uniquement deyversx: sur le graphe dual donc, toute flèche simple change de sens.

Si deux éléments ne sont pas reliés par la relationR, ils le seront dans les deux sens par la

relation complémentaire : une arête (double flèche) apparaîtra alors sur le graphe de¬R. De

même, toute double flèche sur le graphe deRdisparaîtra lors du passage au graphe dual.

68-Bulletin AMQ, Vol. LIX, no3, octobre 2019(Il peut arriver que les relationsRet¬Raient le même graphe : pour cela, elles doivent avoir

le même degré de réflexivité, ce qui est impossible pournimpair). Pour tout ensemble non vide, on qualifie decompletle graphe représentatif du produit cartésien

E2. Il comporte une boucle à chaque élément, une arête (flèche double) entre chaque couple

d"éléments. Le graphe complet est réflexif, symétrique et transitif, mais n"est pas le seul à

combiner ces trois propriétés. Il est dual du graphevidequi, lui, est le seul à être à la fois

antiréflexif, symétrique et transitif.

6 Nombre de graphes et de relations dans les ensembles

à au plus 3 éléments

La relation vide est donc la seule à pouvoir exister dans l"ensemble vide; antiréflexive, symétrique et transitive, elle est sa propre réciproque et n"a pas de complémentaire. Dans unensemble singleton, il y a deux relations, toutes deux symétriques et transitives,

complémentaires l"une de l"autre : la relation pleine (réflexive) et la vide (antiréflexive).

Il est relativement aisé de compiler toutes les relations possibles dans unensemble à deux

éléments

. Il y en a 16, dont 4 réflexives et 4 antiréflexives. Toutes sont, soit symétriques, soit

antisymétriques. Mais déjà, pour la transitivité, on voit apparaître une irrégularité dans la

répartition, comme l"indique le tableau 3 compilan tle nom brede graph eset de relations de chaque type dans des ensembles à 2 ou 3 éléments.n= 2n= 3G NG N

Total10 16104 512

+3 415 64

RO4 874 384

-3 415 64 +6 820 64

SO0 044 249

-4 840 208 +8 1339 171

TO1 246 244

-1 119 97

Tableau3 - Fréquence des propriétés

G= nombre de graphesN= nombre de relations

Bulletin AMQ, Vol. LIX, no3, octobre 2019-69Sur les tableaux et les figures, les abréviationsR+signifient que la relation est réflexive,R-

antiréflexive etRoni l"une ni l"autre; les mêmes conventions sont utilisées pour la symétrie et

la transitivité. Le symbole de multiplication×indique le nombre de relations distinctes auquel un même graphe sagittal convient.

La figure

1 (en annexe page 75
) montre tous les graphes sagittaux possibles dans des ensembles

de 0 , 1 ou 2 éléments. Pour simplifier le dessin, les flèches doubles (aller-retour) sont remplacées

par de simples traits. Parmi les 10 graphes représentatifs des relations dans un ensemble à 2 éléments, on peut remarquer deux cas où les relations complémentairesRet¬Ront le même graphe.

7 Ensembles à 3 éléments

La compilation exhaustive des graphes sagittaux dans unensemble à trois élémentsest

beaucoup plus difficile que pour un ensemble à deux éléments. On constate que les 512 relations

peuvent être représentées par 104 graphes différents. La relation vide, la relation pleine et deux

autres relations ont leur propre graphe; quelques graphes peuvent illustrer 2 ou 3 relations, mais la plupart conviennent pour 6 relations différentes, en permutant les éléments.

Sur les figures

2 et 3 (en annexe, pages 76
77
), pour faciliter le décompte, deuxgraphes duaux l"un de l"autre seront toujours présentés côte à côte. La figure 2 regroup eles re lationsoù la

propriété de symétrieS+,SoouS-est préservée en passant d"une relation à sa complémentaire,

ce qui est le cas notamment pour tous les graphes symétriques(S+). La figure3 illustre les relations qui sont antisymétriques, mais dont la complémentaire ne l"est pas.

La réflexivité ou l"antiréflexivité, tout comme la symétrie ou l"antisymétrie, peuvent être aperçues

au premier coup d"oeil sur un graphe sagittal, ce qui n"est pas le cas pour la transitivité ou l"antitransitivité, qui doivent être vérifiées cas par cas.

8 Combinaison des propriétés

Considérant que les trois propriétés (réflexivité, symétrie, transitivité) peuvent se manifester

selon trois modalités chacune(+,0,-), il y a théoriquement33= 27combinaisons possibles de

propriétés. Certaines d"entre elles sont-elles plus fréquentes que d"autres? Certaines sont-elles

au contraire rares, voire impossibles?

Les effectifs d"un ensemble à 2 éléments sont insuffisants pour répondre à ces questions;

l"ensemble à 3 éléments permet au contraire toutes sortes de constatations intéressantes qui

pourront s"étendre aux ensembles plus grands. Le tableau 4 recense les o ccurrencesde c hacune des combinaisons de propriétés pour des ensembles à 2 ou 3 éléments.

70-Bulletin AMQ, Vol. LIX, no3, octobre 2019Bulletin AMQ, Vol. LIX, no3, octobre 2019-71n=2n=3

Typederelation

RSTGNGN

+++2235Žquivalence

O++1239

-++1111vide ++O13

O+O12836

-+O11 ++-00(impossible) O+-13 -+-1126opposition +O+26 OO+26 -O+00(impossible) +OO424

OOO28162

-OO418 +O-00(impossible)

OO-212

-O-212 +-+12418ordrelarge

O-+2420108

--+12418ordrestrict +-O00(possiblepournff4)

O-O00(possiblepournff4)

--O00(possiblepournff4) +--28

O--848

---28

Total1016104512

Tableau4ÐC lass iÞcationdesrelations

G=nombredegraphesN=nombrederelations

90ÐBulletinAMQ,Vol.LIX,n

o

3,octobre 2019On appellerelation d"équivalenceune relationréflexive, symétrique et transitive. Parmi

elles se trouve la relation pleine; les autres subdivisent l"ensembleEen sous-ensembles disjoints

appelésclasses d"équivalence, chaque classe étant constituée des éléments reliés entre eux et

pas aux autres. On appellerelation d"ordreune relationantisymétrique et transitive. Si en plus elle est

antiréflexive (donc fortement antisymétrique), on la qualifiera d"ordrestrict; si elle est réflexive,

d"ordrelarge. On appellerelation d"oppositionune relationantiréflexive, symétrique et antitransi- tive. Il s"agit de la seule relation antitransitive possible dans un ensemble à 2 éléments. Voici quelques exemples d"observations ou de démonstrations que l"on peut déduire : Toute relation antiréflexive, symétrique et transitive est vide. DémonstrationSupposons une relationRnon vide. Elle doit comporter au moins un couple.

Puisqu"elle est antiréflexive, ce couple ne peut pas être de la forme(x;x): il est donc de la forme

(x;y). La relation étant symétrique, on a doncx R yety R x. Mais pour qu"elle soit transitive,

il faut alors qu"on aitx R x, ce qui contredit l"hypothèse d"antiréflexivité. La relationRne

comporte aucun couple de la forme(x;x)et aucun de la forme(x;y): elle est donc vide.2 Toute relation non vide antiréflexive et transitive est antisymétrique. DémonstrationSi elle est antiréflexive, aucun couple(x;x)ne vérifie la relation. Supposons qu"elle ne soit pas antisymétrique. Non vide et non réflexive, elle doit comporter un couple tel quex R yety R x. Mais par transitivité on devrait alors avoirx R x, ce qui contredit l"hypothèse d"antiréflexivité.2 CorollaireToute relation non vide antiréflexive et transitive, est une relation d"ordre strict. Toute relation réflexive et antitransitive est antisymétrique. DémonstrationSoitRune relation réflexive. Supposons qu"elle ne soit pas antisymétrique. Ou bien son graphe ne comporte aucune flèche, mais alors la relation serait transitive; ou bien il comporte une double flèche,x R yety R x, mais puisqu"elle est réflexive on a aussix R x, et elle n"est donc pas antitransitive. Une relation réflexive non antisymétrique ne peut donc pas

être antitransitive : par contraposition, toute relation à la fois réflexive et antitransitive doit

quotesdbs_dbs43.pdfusesText_43

[PDF] ensemble quotient exercice corrigé

[PDF] relation d'equivalence exercice corrigé pdf

[PDF] exercice relation d'equivalence

[PDF] chargaff adn

[PDF] ordre de grandeur de la voie lactée

[PDF] a+t / g+c

[PDF] niveaux d'organisation du vivant svt

[PDF] les différents niveaux d'organisation du vivant

[PDF] niveau d'organisation du vivant exercices

[PDF] les différents niveaux d'organisation des êtres vivants

[PDF] niveau d'organisation biologique

[PDF] décomposition d'un vecteur dans une base 1ere s

[PDF] diamètre du noyau d'un atome

[PDF] ordre de grandeur electron

[PDF] ordre de grandeur d'un noyau atomique