Bináris reláció

A matematika , egy bináris reláció közötti két E és F (vagy egyszerűen közötti kapcsolat E és F ) határozza meg egy részhalmaza a Descartes-szorzat E × F , azaz a gyűjtemény párok amelynek első komponens E és a második az F-ben . Ezt a gyűjteményt a relációs gráf jelöli . A komponenseket egy pár tartozó grafikon egy kapcsolatban R kifejezve a kapcsolat által R . A bináris kapcsolatot néha a két halmaz közötti megfelelésnek nevezik .

Például síkgeometria viszonynak beesési között egy pont és egy egyenes a sík „a lényeg A vonalon van d ” egy bináris reláció közötti pontok halmaza, és a beállított sorok a gépet. Az E halmaz funkciói vagy alkalmazásai F halmazba az E és F közötti bináris kapcsolatok speciális eseteinek tekinthetők .

Ha F = E , akkor fontos egy pár két komponensének sorrendje. Például a „… szigorúan kisebb, mint…” összefüggés, amelyet a természetes számok N halmazánál észleltünk, az N kapcsolata ; Jelöljük n < p , jelezve, hogy n és p jelentése kapcsolatban. Az (1, 2) pár a gráf eleme, ellentétben a (2, 1) párral.

A reláció fogalmát kétnél több érvre lehet általánosítani, lásd: „ Reláció (matematika) ”.

Bevezetés

Informálisan két halmaz közötti kapcsolat olyan javaslat, amely összekapcsolja az első halmaz egyes elemeit a második halmaz más elemeivel.

Például egy lányokból álló F és egy fiúkból álló G halmazon meghatározhatnánk egy "Alice szereti Bernardot" vagy egy másik "Béatrice ismeri Paul" relációt ... Ezért láthatjuk, hogy a kapcsolat az összekötő szálak két elemének elemei.

Ha a reláció belső összetétel ugyanazon halmazon belül, vagy két halmaz között, amelyek közül az egyik teljesen vagy részben lefedi a másikat, a szagittális ábrázolás inkább egy irányított gráf ábrázolása lehet, hogy csak egyet helyezzen el ugyanabban a helyen a grafikonon azok a csomópontok, amelyek a két halmazban jelen lévő elemeket képviselik. (A nyilak irányát kifejezetten meg kell adni, és nem szabad kihagyni egy csomópont önmagához való kapcsolódását az egyes reflexesen kapcsolódó elemeknél, hacsak nem implicitak a belső reláció összes elemére.)

Véges halmaz esetén ezután megpróbálhatjuk ábrázolni a relációt. Ha F = {Lucie, Béatrice, Delphine, Alice} és ha G = {Bernard, Antoine, Paul, Charles}, akkor a szerelmi viszonyt a mellékelt ábra sematizálhatja (ezt a diagramot sagittális diagramnak nevezzük ).

Ezt a viszonyt, egy kétirányú táblázatot is képviselhetjük, az F halmaz elemeiből származó első oszloplistával és az érkezési G elemeinek élvonalában . A párokat keresztekkel jelölik az első komponens sorának és a második komponens oszlopának kereszteződésében lévő mezőkben.

Példa a mátrixábrázolásra .

.	Bernard	Antoine	Pál	Károly
Lucy	x	x	x	.
Beatrice	.	x	.	.
Delphine	.	.	.	.
Alice	x	.	x	.

Sajnálhatjuk azt a tényt, hogy Delphine senkit sem szeret, Lucie nagylelkű szívvel rendelkezik, és Charles egyedül érezheti magát.

Megpróbálhatjuk felsorolni a kapcsolat párjait is (a nagyobb kényelem érdekében csak a keresztnév első két betűjét fogjuk megőrizni):

Gr = {(Lu, Be), (Lu, An), (Lu, Pa), (Bé, An), (Al, Pa), (Al, Be)}

A matematikában a "pár" két, zárójelben elhelyezett elemből áll, meghatározott sorrendben. A relációt párok halmazaként definiáljuk, vagyis ha két elem kapcsolódik egymáshoz, akkor a pár a reláció halmazának eleme . Ha hívjuk F halmazát lányok, és G halmaza fiúk, akkor az összes lehetséges pár az úgynevezett „Descartes termék F által G ” és jelöljük F × G és a kapcsolat szereti alapján lehet meghatározni, a beállított F , a G halmaz és az F × G részhalmaza .

Formális meghatározás

Az E halmaz R bináris relációját F halmazhoz az E × F G része határozza meg .

Ha ( x , y ) ∈ G , akkor azt mondjuk, hogy x kapcsolatban van y-vel, és jelöljük az " x R y " -t ( infix jelölés ), " R ( x , y )", " R xy " ( előtag jelölések ).

Figyeljük meg, hogy szükség van rá, egy bináris reláció, hogy adja meg a set E (az úgynevezett kezdő készlet ), a beállított F (úgynevezett érkezés set ), és az a része G az E × F úgynevezett grafikon a kapcsolatot.

Amikor egy bináris reláció van határolva egy sor E maga felé (más szóval az E = F az előző meghatározás, tehát által meghatározott részét G a E 2 ), is nevezik belső kapcsolatot a E , vagy egyszerűen reláció E .

Példák

Bármilyen set E , a tagsági viszony a E × P ( E ) kezdődik készlet E és mindenkorra befejezni a beállított P ( E ) rész E .
A P ( E ) -re vonatkozó inklúziós reláció egy belső összefüggés ( a sorrendben ).

A definíciós készlet , vagy domén az R jelentése a kép annak grafikon az első kiálló , azaz a beállított: ${\ displaystyle E \ szorozza meg F \ -et E-ig}$ ${\ displaystyle \ {x \ E \ középen \ létezik y \ F \ quad (x, y) \ -ban G \}.}$ A kép , vagy értékrend az R az a kép, a grafikon a második kiálló , azaz a készlet: ${\ displaystyle E \ szorozza meg az F-t F-ig}$ ${\ displaystyle \ {y \ in F \ mid \ létezik x \ E \ quad (x, y) \ -ban G \}.}$

Ha R és S két összefüggés E- től F-ig , akkor S finomabbnak mondható, mint R, ha a grafikonja benne van az R-ben , azaz ha x S y ⇒ x R y .

A bináris reláció „ többértékű függvényként ” is tekinthető, más néven „levelezésnek”, és a szókincs ebben az összefüggésben ugyanazokat a fogalmakat jelöli (különösen: grafikon, definíciókészlet, kép, reciprok).

Összetétel, kölcsönös és kiegészítő

Fogalmazás

Ha egy kapcsolatban az E a F és az F a G , tudjuk meg egy kapcsolatban az E a G szerint: ${\ mathcal R}$ ${\ mathcal {S}}$ ${\ displaystyle {\ mathcal {S}} \ circ {\ mathcal {R}}}$

{\ displaystyle {\ mathcal {G}} _ {{\ mathcal {S}} \ circ {\ mathcal {R}}} = \ balra \ {(x, y) \ E \ -szeresen G \ mid \ létezik z \ in F \ quad (x, z) \ in {\ mathcal {G}} _ {R} {\ text {et}} (z, y) \ in {\ mathcal {G}} _ {S} \ right \}.}

Pontozás: ha egy belső kapcsolatban egy sor E és n egy természetes szám, van a készítmény önmagával n -szer, azzal a konvencióval, hogy jelöli az egyenlőség kapcsolatban a E . ${\ mathcal R}$ ${\ displaystyle {\ mathcal {R}} ^ {n}}$ ${\ mathcal R}$ ${\ displaystyle {\ mathcal {R}} ^ {0}}$

Kölcsönös

Ha van összefüggés a E a F , tudjuk meg egy rokona F on E úgynevezett inverz kapcsolatban , kölcsönös vagy fordítottja által: ${\ mathcal R}$

{\ displaystyle {\ mathcal {G}} _ {{\ mathcal {R}} ^ {- 1}} = \ balra \ (x, y) \ in F \-szer E \ közepe (y, x) \ in {\ mathcal {G}} _ {\ mathcal {R}} \ right \}.}

Példák:

A „kevesebb, mint” (≤) és a „nagyobb, mint” (≥) egymás kölcsönös kapcsolatai (bármely ≤ rendű reláció esetén); A „szeret” és a „szeretett” szintén kölcsönös.

A kölcsönös reláció ábrázolása egyszerűen levezethető a kezdeti levelezésből:

a sagittális ábrázoláshoz a linkek irányának megváltoztatásával (balról jobbra nézve a diagramon);
egy mátrixábrázoláshoz sorok és oszlopok felcserélésével, vagyis az átültetett mátrix felvételével .

Konstrukció szerint a bináris reláció reciproka a következő tulajdonságokkal rendelkezik:

A domén és a kép R -1 rendre a képet, és a domain R ;
az R reláció reciprokjának reciproka maga az R reláció .

Sőt, a belső reláció akkor szimmetrikus (vagy reflexív , vagy antireflexív ), ha (és csak akkor), ha kölcsönös.

Kiegészítő

Ha összefüggés van E- től F-ig , akkor definiálhatunk egy E- től F-ig tartó kapcsolatot , amelyet komplementer relációnak vagy logikai komplementernek nevezünk : ${\ mathcal {R}}$

{\ displaystyle {\ mathcal {G}} _ {\ mathcal {{} \ over R}} = \ balra \ (x, y) \ E \ -szer F-közép (x, y) \ notin {\ mathcal {G}} _ {\ mathcal {R}} \ jobb \}.}

Példák:

A „Kevesebb” (≤) és a „szigorúan nagyobb, mint” (>) kapcsolatok kiegészítik egymást bármely ≤ sorrend esetében (például a valós feletti sorrend); A "lájkolások" és "nemtetszések" is kiegészítik egymást.

Az R komplementer reláció ábrázolása egyszerűen levezethető R-ből :

a szagittális ábrázoláshoz az összes már meglévő kapcsolat eltávolításával és a még nem létező linkek hozzáadásával (ideértve az ellentétes irányúakat is, ha belső kompozícióról van szó, és az ábrázolás egyetlen halmazra orientált grafikon, különben hozzáadva azokat, amelyek ugyanabban az irányban hiányzik a két külön elkülönített elem eleme között);
mátrixábrázoláshoz úgy, hogy a mátrix egyes celláinak logikai értékeit lecseréljük logikai kiegészítésükre.

Konstrukció szerint a bináris reláció komplementere a következő tulajdonságokkal rendelkezik:

az R reláció komplementerének kiegészítése maga az R reláció ;
az R reláció inverzének komplementere az R kiegészítő R reciproka .

Ezenkívül a belső kapcsolat :

akkor és csak akkor szimmetrikus, ha komplementer kapcsolata az;
akkor és csak akkor reflexív, ha kiegészítő kapcsolata antireflexív .

Funkcionális kapcsolat

Amikor, bármely elem X a E , X jelentése kapcsolatban csak 0 vagy 1 elemet y a F , azt mondjuk, hogy a reláció funkcionális . Ez egy elemi módszer a funkció fogalmának meghatározására . Formális nyelven az előző tulajdonság meg van írva:

{\ displaystyle \ forall x \ in E \ quad \ forall y \ in F \ quad \ forall z \ in F \ quad [(x, y) \ in {\ mathcal {G}} _ {\ mathcal {R}} \ land (x, z) \ in {\ mathcal {G}} _ {\ mathcal {R}}] \ Rightarrow (y = z).}

Fontos példa:

Az E átlóját a következők határozzák meg:

{\ displaystyle \ Delta _ {E} = \ bal \ {(x, x) \ x közepe \ -ban E \ jobb \}.}

Ez az egyenlőség grafikonja az E-n , = E , vagy = az adott halmaz kétértelműségének hiányában. Ez a viszony függvénye is, az identitás az E jelölt id E .

Kapcsolat egy halmazon (vagy abban)

Abban a speciális esetben, ha E = F , akkor azt mondjuk, hogy az R egy bináris reláció meghatározása az E vagy az E .

A reflexivitással kapcsolatos tulajdonságok

Reflexív kapcsolat

Az összefüggés a E azt mondják, hogy a reflexív , ha bármely elemének E összefüggésben van önmagával, azaz, ha: ${\ mathcal {R}}$

{\ displaystyle \ forall x \ E \ quad x {\ mathcal {R}} x.}

Nem reflektáló kapcsolat

Az összefüggés a E jelentése irreflexive vagy tükröződésmentesítő ha nincs elem E összefüggésben van önmagával, azaz, ha: ${\ mathcal {R}}$

{\ displaystyle \ forall x \ in E \ quad x {\ cancel {\ mathcal {R}}} x.}

A kapcsolat nem lehet sem reflexív, sem antireflexív.

A szimmetriával kapcsolatos tulajdonságok

Szimmetrikus kapcsolat

Az összefüggés a szimmetrikus , ha: ${\ mathcal {R}}$

{\ displaystyle \ forall (x, y) \ in E ^ {2}, x {\ mathcal {R}} y \ Rightarrow y {\ mathcal {R}} x.}

Antiszimmetrikus kapcsolat

A relációt ezt mondják: ${\ mathcal {R}}$

antiszimmetrikus (vagy gyengén antiszimmetrikus), ha: ${\ displaystyle \ forall (x, y) \ E ^ nyelven {2}, (x {\ mathcal {R}} y \ ék y {\ mathcal {R}} x) \ Rightarrow x = y}$ ;
aszimmetrikus (vagy erősen antiszimmetrikus), ha: ${\ displaystyle \ forall (x, y) \ in E ^ {2}, x {\ mathcal {R}} y \ Rightarrow \ lnot (y {\ mathcal {R}} x),}$ vagy ha egyszerre antiszimmetrikus (a gyenge értelemben vett) és visszatükröző .

A kapcsolat nem lehet sem szimmetrikus, sem antiszimmetrikus.

Transzitivitás

Az összefüggés a E jelentése tranzitív ha, mikor az első eleme E összefüggésben van egy másik elem maga kapcsolatban egy harmadik, az első elem összefüggésben is a harmadik, azaz, ha: ${\ mathcal {R}}$

{\ displaystyle \ forall x, y, z \ in E \ quad (x {\ mathcal {R}} y \ ék y {\ mathcal {R}} z) \ Rightarrow x {\ mathcal {R}} z,}

vagy megint, ha a grafikonja magában foglalja a kompozit grafikáját, amely a következő:

{\ mathcal {G}} _ {{{{mathcal {R}} \ circ {\ mathcal {R}}}} \ subseteq {\ mathcal {G}} _ {{{\ mathcal {R}}}}.

Hívjuk tranzitív lezárása, illetve tranzitív lezárása az összefüggés ${\ mathcal {R}}$

{\ displaystyle {\ mathcal {R}} ^ {trans} = \ bigcup _ {n \ geq 1} {\ mathcal {R}} ^ {n}.}

Ez a legkisebb (a grafikonok beillesztése szempontjából), amely transzitív relációt tartalmaz . ${\ mathcal {R}}$

Teljes kapcsolat

Az összefüggés a E jelentése teljes (in) , ha: ${\ mathcal {R}}$

{\ displaystyle \ forall x, y \ E \ quad x {\ mathcal {R}} y \ vee y {\ mathcal {R}} x}

vagy még egyszer, ha a grafikonjának és a reciprokjának az uniója megegyezik az E derékszögű négyzetével , amely a következő:

{\ displaystyle {\ mathcal {G}} _ {\ mathcal {R}} \ cup {\ mathcal {G}} _ {{\ mathcal {R}} ^ {- 1}} = E ^ {2}}

Ezt a minősítőt leggyakrabban a rendelési viszonyok kapcsán használják .

Minden teljes kapcsolat reflexív .

Ekvivalencia reláció

Az ekvivalencia reláció reflexív , transzitív és szimmetrikus reláció .

Rendelési viszony

Egy megbízás vonatkozásában a reflexív , tranzitív és antiszimmetrikus reláció .

Ha egy rendelési reláció teljes , akkor azt mondjuk, hogy ez egy teljes megrendelés . Az ellenkező esetben , azt mondják, hogy csak részleges sorrendben.

A bajnokság kapcsolata

A verseny egy bináris reláció teljes és ferde .

Ezt a meghatározást össze kell hasonlítani (anélkül, hogy ennek teljesen megfelelne) a gráfelméletben a verseny definíciójával: a verseny egy gráf, amely igazolja

{\ displaystyle \ forall (x, y) \ in E ^ {2}, x \ neq y, (x, y) \ in {\ mathcal {A}} \ Balra mutató nyíl (y, x) \ notin {\ mathcal { NÁL NÉL}}}

Egy verseny lehetővé teszi a versenyek modellezését olyan sportversenyeken, ahol minden csapat döntetlen nélkül játszik az összes többi ellen.

Megalapozott kapcsolat

A bináris relációk száma véges halmazokon

Tekintsük az n bíboros véges E halmazát és a p bíboros véges F halmazát . Van annyi bináris kapcsolatok a E , hogy az F , mint ahány térképeket E × F {0, 1}, amely 2 np kapcsolatok.

Különösen, ha az E = F , azt találjuk, 2 ( n 2 ) bináris kapcsolatok E , amelynek

2 n ( n - 1) reflexív összefüggés,
2 n ( n + 1) / 2 szimmetrikus összefüggés.
Az átmeneti kapcsolatok számához még mindig nincs „zárt” képlet.

Az ekvivalencia-relációk száma megegyezik a halmaz partícióinak számával, vagyis a Bell-számmal .

A bináris relációk kategóriája

A bináris relációk és a relációk összetétele egy olyan kategóriát alkotnak, amelyet kapcsolatok kategóriájának nevezünk , és amelyet Rel-rel jelölünk .

Megjegyzések és hivatkozások

Bourbaki , p. E II.10, előnézet a Google Könyvekben .
Dany-Jack Mercier, A versenyek alapjainak megszerzése , vol. 1, Publibook ,2012( online olvasható ) , p. 104.
Lásd például a rövid tanfolyam 5. definícióját .
Nathalie Caspard, Bruno Leclerc, Bernard Monjardet, Véges rendezett halmazok: fogalmak, eredmények és felhasználások , Springer, 2007, 2.24. Definíció, p. 59
Houmem Belkhechine. Grafikonok és versenyek szétszerelhetetlensége , Általános matematika, Claude Bernard Egyetem - Lyon I; Sfaxi Egyetem. Természettudományi Kar, 2009, p. 14.

Kapcsolatok

N. Bourbaki , A matematika elemei : halmazelmélet [ a kiadások részlete ]
Halmos Paul , Bevezetés a halmazelméletbe [ a kiadások részlete ]
(en) Yiannis Moschovakis , Megjegyzések a halmazelméletről [ a kiadások részlete ]
Alfred Tarski és Givant, Steven, 1987. 2004, „A halmazelmélet formalizálása változók nélkül”, American Mathematical Society.
Maddux, Roger D. (en) , 2006. Relation Algebras , vol. 150 a "Logikai tanulmányok és a matematika alapjai" című részben, Elsevier Science.