I matematik defineres et binært forhold mellem to sæt E og F (eller simpelthen forholdet mellem E og F ) ved en delmængde af det kartesiske produkt E × F , det vil sige en samling par, hvis første komponent er i E og sekund i F . Denne samling er betegnet med forholdsgrafen . Komponenterne i et par tilhørende grafen for en relation R udtrykt i forholdet af R . Et binært forhold kaldes undertiden en korrespondance mellem de to sæt.
For eksempel i plangeometri er indfaldsforholdet mellem et punkt og en linie i planet "punktet A er på linjen d " et binært forhold mellem sæt af punkter og linjesættet i planet. De funktioner eller anvendelser af et sæt E i et sæt F kan ses som specialtilfælde af binære relationer mellem E og F .
Når F = E , er rækkefølgen af de to komponenter i et par vigtig. For eksempel er forholdet "... strengt mindre end ...", bemærket <på sæt N af naturlige tal er en relation til N ; vi betegner med n < p for at indikere, at n og p er i relation. Parret (1, 2) er et element i grafen i modsætning til parret (2, 1).
Begrebet relation kan generaliseres til mere end to argumenter, se “ Relation (matematik) ”.
Uformelt er et forhold mellem to sæt et forslag, der forbinder nogle elementer i det første sæt med andre elementer i det andet sæt.
På et sæt F bestående af piger og et sæt G bestående af drenge, kunne vi f.eks. Definere en relation "Alice kan lide Bernard" eller en anden relation "Béatrice kender Paul" ... Vi kan derfor se forholdet som værende af sønnerne, der forbinder elementer i to sæt.
Hvis forholdet er en intern sammensætning inden for det samme sæt eller mellem to sæt, hvoraf det ene helt eller delvist dækker det andet, kan den sagittale repræsentation snarere være den for en rettet graf for kun at placere en én gang på samme sted på grafen de noder, der repræsenterer elementer til stede i de to sæt. (Pilens retning skal udtrykkeligt angives, og linkene til en knude til sig selv for hvert af de refleksivt relaterede elementer bør ikke udelades, medmindre de er implicitte for alle elementerne i en intern relation).
I tilfælde af et endeligt sæt kan vi derefter prøve at repræsentere forholdet ved hjælp af et diagram. Hvis F = {Lucie, Béatrice, Delphine, Alice} og hvis G = {Bernard, Antoine, Paul, Charles}, kan kærlighedsforholdet skematiseres ved hjælp af det vedhæftede diagram (et sådant diagram kaldes et sagittaldiagram ).
Vi kan også repræsentere dette forhold, en to-vejs bord, med første kolonne liste fra elementer i sættet F , og i spidsen for elementerne i ankomst G . Parene er repræsenteret af kryds i felterne ved skæringspunktet mellem rækken for den første komponent og kolonnen for den anden komponent.
. | Bernard | Antoine | Paul | Charles |
---|---|---|---|---|
Lucy | x | x | x | . |
Beatrice | . | x | . | . |
Delphine | . | . | . | . |
Alice | x | . | x | . |
Vi kan beklage det faktum, at Delphine ikke elsker nogen, at Lucie har et generøst hjerte, og at Charles kan føle sig alene.
Vi kan også prøve at liste parene i dette forhold (for mere bekvemmelighed beholder vi kun de to første bogstaver i fornavnet):
Gr = {(Lu, Be), (Lu, An), (Lu, Pa), (Bé, An), (Al, Pa), (Al, Be)}I matematik består et "par" af to elementer placeret i parentes i en bestemt rækkefølge. Relationen er defineret som et sæt par, det vil sige, hvis to elementer er relateret til hinanden, så er parret et element i relationssættet . Hvis vi kalder F sæt af piger og G sæt af drenge, så kaldes sættet af alle mulige par ”Cartesian product of F by G ” og betegnes F × G, og forholdet likes defineres derefter af sættet F sættet G og en undergruppe af F × G .
En binær relation R af et sæt E til et sæt F defineres af en del G af E × F .
Hvis ( x , y ) ∈ G , siger vi, at x er i relation til y, og vi betegner " x R y " ( infixnotation ), " R ( x , y )", " R xy " ( prefixnotationer ).
Bemærk, at det er nødvendigt for en binær relation at specificere sættet E (kaldet startsættet ), sættet F (kaldet ankomstsættet ) og delen G af E × F kaldet grafen for forholdet.
Når en binær relation er defineret ud fra et sæt E fremad selv (med andre ord E = F i den tidligere definition, defineret således ved en del G i E 2 ), er det også kaldes indre forhold på E , eller blot forhold på E .
EksemplerDen definition sæt , eller domæne af R er billedet af dens graf af første fremspring , dvs. sæt: Det billede , eller sæt værdier for R er billedet af dens graf af det andet fremspring , dvs. sæt:
Hvis R og S er to relationer fra E til F , siges S at være finere end R, hvis dens graf er inkluderet i grafen for R , dvs. hvis x S y ⇒ x R y .
En binær relation kan også ses som en “ funktion med flere værdier ”, også kaldet “korrespondance”, og ordforrådet betegner i denne sammenhæng de samme forestillinger (især graf, definitionssæt, billede, gensidig).
Hvis er en relation af E i F og af F i G , kan vi definere en relation af E i G ved:
Scoring: hvis er et internt forhold på et sæt E og n et naturligt tal, der er præparatet med sig selv n gange, med den konvention, betegner forhold ligestilling på E .
Hvis er en relation af E på F , kan vi definere en relation af F på E kaldet omvendt forhold , gensidigt eller omvendt ved at:
Eksempler:
"Mindre end" (≤) og "større end" (≥) er gensidige relationer mellem hinanden (for ethvert forhold af ordre ≤); "Elsker" og "er elsket af" er også gensidige.Repræsentationen af et gensidigt forhold udledes simpelthen fra den oprindelige korrespondance:
Ved konstruktion har det gensidige af et binært forhold følgende egenskaber:
Endvidere er en indre forhold er symmetrisk (hhv. Refleksiv , hhv. Antireflexive ) hvis (og kun hvis) dens reciprokke er.
Hvis er en relation fra E til F , kan vi definere en relation fra E til F kaldet en komplementær relation eller logisk komplement ved:
Eksempler:
"Mindre end" (≤) og "strengt større end" (>) er relationer, der supplerer hinanden for enhver total ordre ≤ (som rækkefølgen over realerne); "Synes godt om" og "kan ikke lide" supplerer også hinanden.Repræsentationen af R 's komplementære forhold er simpelthen udledt af R :
Ved konstruktion har komplementet til et binært forhold følgende egenskaber:
Derudover er et internt forhold :
Når for ethvert element x af E , x er i forhold kun med 0 eller 1 element y af F , siger vi, at forholdet er funktionel . Det er en elementær måde at definere begrebet funktion på . På formelt sprog er den foregående egenskab skrevet:
Vigtigt eksempel:
Den diagonale af E er defineret ved: Det er grafen over forholdet mellem lighed på E , betegnet = E eller = i mangel af tvetydighed på det pågældende sæt. Dette forhold er også en funktion, identitet af E , betegnet id E .I det særlige tilfælde, hvor E = F , siger vi, at R er en binær relation defineret på E eller i E .
Forholdet til E siges at være refleksivt, hvis ethvert element i E er i forhold til sig selv, det vil sige hvis:
Irrefleksivt forholdForholdet til E er irrefleksiv eller antireflexiv, hvis intet element i E er i forhold til sig selv, det vil sige hvis:
Et forhold kan hverken være refleksivt eller antirefleksivt.
Forholdet er symmetrisk, hvis:
Antisymmetrisk forholdForholdet siges:
Et forhold kan hverken være symmetrisk eller antisymmetrisk.
Forholdet på E er transitivt , hvis det første element i E er i forhold til et andet element i forhold til et tredje, det første element også er i forhold til det tredje, det vil sige hvis:
eller igen, hvis dens graf indeholder den af dens sammensatte med sig selv, som er skrevet:
Vi kalder transitiv lukning eller transitiv lukning af forholdet
Det er det mindste (i betydningen medtagelse af grafer), der indeholder transitivt forhold .
Forholdet på E er total (in), hvis:
eller igen, hvis foreningen af dens graf med den for dens reciprokke er lig med kartesiske firkant af E , der er skrevet:
.Denne kvalifikator bruges oftest i forbindelse med ordrerelationer .
Ethvert totalt forhold er refleksivt .
En ækvivalensrelation er en refleksiv , transitiv og symmetrisk relation .
En ordrerelation er en refleksiv , transitiv og antisymmetrisk relation .
Hvis en ordrerelation er total , siger vi, at det er en total ordre . I det modsatte tilfælde siges det, at kun en delvis ordre.
En turnering er et totalt og antisymmetrisk binært forhold .
Denne definition skal sammenlignes (uden fuldt ud at svare til den) med turneringens i grafteori: en turnering er en graf, der verificerer
En turnering gør det muligt at modellere turneringer i sportskonkurrencer, hvor hvert hold spiller mod alle de andre uden uafgjort.
Overvej et endeligt sæt E af kardinal n og et endeligt sæt F af kardinal p . Der er lige så mange binære relationer fra E til F, som der er kort fra E × F til {0, 1}, hvilket giver 2 np relationer.
Især hvis E = F , finder vi 2 ( n 2 ) binære relationer på E , hvoraf
Antallet af ækvivalensrelationer er lig med antallet af partitioner i et sæt, det vil sige Bell-nummeret .
Binære relationer og sammensætningen af relationer danner en kategori, der kaldes den kategori af relationer, og som vi betegner med Rel .