A reláció ekvivalenciareláció? Bináris relációk – MT1102: Lineáris algebra (bevezetés a matematikába) – Üzleti informatika

Megjegyzés: Számos új fogalmat írnak le, mint például az ekvivalenciarelációt, a részleges sorrendű relációt és az izomorf részhalmazokat. Ebben a témában számos tételt részletes magyarázatokkal, grafikonokkal és példákkal bizonyítunk. A részleges megrendelésekre számos példa található. Számos olyan konstrukciót ismertetünk, amelyek lehetővé teszik másokból rendezett halmazok készítését. Az előadást számos önálló megoldást szolgáló feladat jellemzi

Egyenértékűség és sorrendi összefüggések

Emlékezzünk erre bináris reláció egy halmazon részhalmaznak nevezzük; ahelyett gyakran írnak.

Egy halmaz bináris relációját nevezzük ekvivalencia reláció, ha a következő tulajdonságok teljesülnek:

A következő nyilvánvaló, de gyakran használt állítás igaz:

11. tétel. (a) Ha egy halmaz diszjunkt részhalmazok uniójára van felosztva, akkor az „ugyanabban a részhalmazban lenni” reláció ekvivalencia reláció.

(b) Bármi ekvivalencia reláció a leírt módon valamilyen partícióból származik.

Bizonyíték. Az első állítás egészen nyilvánvaló; A másodikat bizonyítjuk, hogy látható legyen, hol van az ekvivalencia definíciójának minden pontja. Tehát legyen egy ekvivalencia reláció. Minden elemnél vegye figyelembe ekvivalencia osztály- mindazok halmaza, amelyekre igaz.

Bizonyítsuk be, hogy két különböző esetén az ilyen halmazok vagy nem metszik egymást, vagy nem esnek egybe. Hagyja, hogy keresztezzék egymást, azaz legyen közös elemük. Akkor és , honnan (szimmetria) és (tranzitivitás), valamint (szimmetria). Ezért bármelyikből következik (tranzitivitás) és fordítva.

Meg kell jegyeznünk, hogy a reflexivitás miatt minden elem az általa meghatározott osztályhoz tartozik, vagyis az egész halmaz diszjunkt osztályokra oszlik.

78. Mutassuk meg, hogy a szimmetria és a tranzitivitás követelményei eggyel helyettesíthetők: (a reflexivitás követelményének megtartása mellett).

79. Hány különböző ekvivalencia reláció létezik a halmazon ?

80. Két ekvivalenciarelációt adunk meg a halmazon, és jelöléssel, amelyeknek és ekvivalenciaosztályaik vannak. A metszéspontjuk ekvivalencia reláció lesz? Hány órája lehet? Mit mondhatsz róla kapcsolatok egységesítése?

81. (Ramsey tétel) Egy végtelen halmaz összes elemi részhalmazának halmazát osztályokra osztjuk (, - természetes számok). Bizonyítsd be, hogy van végtelen halmaz, amelynek minden elemi részhalmaza ugyanabba az osztályba tartozik.

(Ez nyilvánvaló: ha végtelen halmaz véges számú osztályra van osztva, akkor az egyik osztály végtelen. Mikor és az állítás a következőképpen fogalmazható meg: végtelen emberhalmaz közül választhatunk vagy végtelenül sok páronkénti ismerőst, vagy végtelenül sok páronként idegent. Ennek az állításnak a végső változata – hogy bármely hat ember között vagy három páronkénti ismerős, vagy három páronként idegen – az iskolások körében jól ismert probléma.)

Az ekvivalencia osztályok halmazát ún tényező - sok ekvivalenciarelációval halmazok. (Ha a reláció konzisztens a -n lévő további struktúrákkal, az eredmény faktorcsoportok, faktorgyűrűk stb.)

Az ekvivalencia relációkkal nem egyszer találkozunk, de most a fő témánk a sorrendi viszonyok.

Egy halmaz bináris relációját nevezzük részleges rend kapcsolat, ha a következő tulajdonságok teljesülnek:

(Hagyományt követve a rendi reláció jeleként szimbólumot (nem betűt) használunk.) A halmazt, amelyen részleges sorrendi relációt adunk meg, ún. részben megrendelt.

Azt mondják, hogy két elem részben megrendelt készletek hasonló, ha vagy . Vegye figyelembe, hogy a részleges sorrend meghatározása nem követeli meg, hogy a halmaz bármely két eleme összehasonlítható legyen. Ezt a követelményt hozzáadva megkapjuk a definíciót lineáris sorrend (lineárisan rendezett halmaz).

Íme néhány példa a részleges rendelésekre:

  • Numerikus halmazok a szokásos sorrendi relációval (itt a sorrend lineáris lesz).
  • Az összes valós számpár halmazán bevezethetjük részleges rend, figyelembe véve, hogy ha és . Ez a sorrend már nem lesz lineáris: a párok nem összehasonlíthatók.
  • Valós argumentumokkal és értékekkel rendelkező függvények halmazán megadhat részleges rend, tekintettel arra, hogy ha mindenki előtt. Ez a sorrend nem lesz lineáris.
  • A pozitív egész számok halmazán úgy határozhatjuk meg a sorrendet, hogy figyelembe vesszük, hogy ha osztja . Ez a sorrend sem lesz lineáris.
  • A „egy szám bármely prímosztója egy szám osztója is” reláció nem lesz sorrendi reláció a pozitív egész számok halmazán (reflexív és tranzitív, de nem antiszimmetrikus).
  • Legyen tetszőleges halmaz. Ekkor a halmaz összes részhalmazának halmazán a befogadási reláció részleges sorrend lesz.
  • Az orosz ábécé betűin a hagyomány egy bizonyos sorrendet határoz meg (). Ez a sorrend lineáris – bármely két betűnél meg lehet állapítani, hogy melyik jön előbb (ha szükséges, a szótárban megnézve).
  • Az orosz ábécé szavaival definiálva lexikográfiai sorrendben (mint a szótárban). Formálisan a következőképpen definiálható: ha egy szó a szó eleje, akkor (például ). Ha egyik szó sem a másik kezdete, nézze meg az első betűt abban a sorrendben, amelyben a szavak különböznek: akkor az a szó, ahol ez a betű kisebb abc-rendben, kisebb lesz. Ez a sorrend is lineáris (egyébként mit csinálnának a szótárfordítók?).
  • Az egyenlőségi reláció () is részleges rend kapcsolat, amelyhez nem lehet két különböző elemet összehasonlítani.
  • Mondjunk most egy hétköznapi példát. Legyen sok kartondoboz. Vezessünk be rajta rendet, tekintve, hogy ha a doboz teljesen belefér a dobozba (vagy ha és ugyanaz a doboz). A dobozkészlettől függően ez a sorrend lehet lineáris vagy nem.

I. Osztályokra bontás. Egyenértékűségi reláció

Meghatározás 2.1. Nevezzük felcserélhetőnek egy adott M halmaz azon objektumait és csak azokat, amelyek ugyanazokkal a formális jellemzők halmazával rendelkeznek, amelyek egy adott helyzetben lényegesek.

Jelöljük M x-el az x objektummal felcserélhető objektumok halmazát. Nyilvánvaló, hogy x M x és az összes M x uniója (minden lehetséges x-re M-ből) egybeesik az M teljes halmazzal:

Tegyünk úgy, mintha. Ez azt jelenti, hogy van olyan z elem, amely egyidejűleg a és és a közé tartozik. Tehát x felcserélhető z-vel, z pedig y-vel. Ezért x felcserélhető y-val, tehát bármely elemével. És így. A fordított kapcsolás ugyanígy látható. Így a (2.1) unióban előforduló halmazok vagy nem metszik egymást, vagy teljesen egybeesnek.

Meghatározás 2.2. Egy M halmaz nem üres részhalmazainak (M 1, M 2,….) rendszerét a halmaz partíciójának nevezzük, ha

Magukat a halmazokat partícióosztályoknak nevezzük.

Meghatározás 2.3. Egy M halmaz c relációját ekvivalenciának (vagy ekvivalenciarelációnak) nevezzük, ha az M halmaznak van olyan partíciója (M 1, M 2,...), amelyre (x, y) akkor és csak akkor teljesül, ha x és y egy adott partíció valamelyik általános M i osztályába tartozik.

Legyen (M 1 , M 2 ,….) az M halmaz egy partíciója. E partíció alapján határozzuk meg a c és M közötti összefüggést: (x, y), ha x és y valamilyen általános M i osztályba tartozik. ennek a partíciónak. Nyilvánvalóan a -val való kapcsolat ekvivalencia. Hívjuk meg az adott partíciónak megfelelő ekvivalenciarelációval.

Meghatározás 2.4. Ha minden M i részhalmazban kiválasztjuk a benne foglalt x i elemet, akkor ezt az elemet nevezzük szabványnak minden y elemre, amely ugyanabban az M i halmazban szerepel. Definíció szerint tegyük fel, hogy teljesül a c* „szabványnak lenni” (x i, y) reláció

Könnyen belátható, hogy az adott partíciónak megfelelő c ekvivalencia a következőképpen definiálható: (z, y) ha z-nek és y-nek van közös szabványa (x i, z) és (x i, y).

2.1. példa: Tekintsük M-nek az egész számok halmazát nem negatív számokés vegye fel a partícióját egy páros számokból álló M 0 és a páratlan számokból álló M 1 halmazba. A megfelelő ekvivalencia relációt az egész számok halmazán a következőképpen jelöljük:

és így szól: n összevethető m modulo 2-vel. Természetes, hogy a páros számokhoz 0-t, páratlanhoz pedig 1-et választunk szabványként. Hasonlóképpen, ha ugyanazt az M halmazt felosztjuk k M 0, M 1,... M k-1 részhalmazra, ahol M j mindazon számokból áll, amelyeket k-val elosztva j maradékot kapunk, az ekvivalencia relációhoz jutunk:

ami teljesül, ha n-nek és m-nek ugyanaz a maradéka, ha elosztjuk k-val.

Természetes, hogy minden M j-ben a megfelelő j maradékot választjuk standardnak.

II. Tényezőkészlet

Legyen egy ekvivalenciareláció. Ekkor a tétel szerint az M halmazt felosztjuk (M 1, M 2,....) egymással ekvivalens elemosztályokra - az úgynevezett ekvivalencia osztályokra.

Meghatározás 2.5. A relációra vonatkozó ekvivalenciaosztályok halmazát M/-vel jelöljük, és az M halmaz egy relációra vonatkozó hányadoshalmazaként olvassuk.

Legyen μ: M > S az M halmaz szürjektív leképezése valamilyen S halmazra.

Tetszőleges μ: M > S - szürjektív leképezés esetén van egy ekvivalencia reláció az M halmazon úgy, hogy M/ és S egy az egyhez megfeleltetésbe helyezhető.

III. Egyenértékűségi tulajdonságok

Meghatározás 2.6. Egy M halmaz c relációját ekvivalenciarelációnak nevezzük, ha reflexív, szimmetrikus és tranzitív.

2.1. Tétel: Ha egy c reláció egy M halmazon reflexív, szimmetrikus és tranzitív, akkor az M halmaznak van olyan partíciója (M 1 , M 2 ,….), amelyre (x, y) akkor és csak akkor teljesül, ha x és y egy adott partíció valamelyik általános M i osztályába tartozik.

Fordítva: Ha egy partíció adott (M 1, M 2,....) és a c bináris reláció úgy van megadva, hogy „a partíció általános osztályába tartozik”, akkor c reflexív, szimmetrikus és tranzitív.

Bizonyíték:

Tekintsünk egy c reflexív, szimmetrikus és tranzitív relációt M-hez. Legyen minden olyan z, amelyre (x, z) c

2.1 lemma: Bármely x és y esetén a vagy

A c reláció lemmájából és reflexiósságából következik, hogy az M halmaz egy partícióját képezik az alak halmazai (ezt a partíciót természetesen az eredeti relációnak megfelelő partíciónak nevezhetjük). Legyen most (x, y) c. Ez azt jelenti, hogy y. De x-et is (x, x) c alapján. Ezért mindkét elem benne van. Tehát, ha (x, y) c, akkor x és y benne van általános osztály válaszfalak. Fordítva, legyen u és v. Mutassuk meg, hogy (u, v) c Valóban van (x, u) c és (x, v) c. Ezért a szimmetria alapján (u, x) c. A tranzitivitás szerint (u, x) c és (x, v) c következik (u, v) c. A tétel első része bizonyítást nyert.

Legyen adott az M halmaz egy partíciója (M 1, M 2,….). a partíció összes osztályának uniója egybeesik M-mel, akkor bármely x benne van valamelyik osztályban. Ebből következik, hogy (x, x) c, azaz. s - reflexszerűen. Ha x és y valamelyik osztályba tartozik, akkor y és x ugyanabba az osztályba tartozik. Ez azt jelenti, hogy (x, y) c azt jelenti, hogy (y, x) c, azaz. a kapcsolat szimmetrikus. Legyen most (x, y) c és (y, z) c teljesül. Ez azt jelenti, hogy x és y valamelyik osztályba tartozik, y és z pedig valamilyen osztályba tartozik. Az osztályoknak van egy közös eleme y, ezért egybeesnek. Ez azt jelenti, hogy x és z benne van az osztályban, azaz. (x, z) teljesül, és a reláció tranzitív. A tétel bizonyítást nyert.

IV. Egyenértékűségek műveletei.

Itt definiálunk néhány halmazelméleti műveletet az ekvivalenciákra, és bemutatjuk fontos tulajdonságaikat bizonyítás nélkül.

Emlékezzünk vissza, hogy egy reláció egy pár (), ahol M a relációba belépő elemek halmaza, és azoknak a pároknak a halmaza, amelyekre a reláció teljesül.

Meghatározás 2.7. A (c 1, M) és (c 2, M) relációk metszéspontja a megfelelő részhalmazok metszéspontja által meghatározott reláció. (x, y) 1-ből 2-ből akkor és csak akkor, ha (x, y) 1-ből és (x, y) 2-ből egyszerre.

2.2. Tétel: Az 1-es és 2-es ekvivalenciák és az 1-es 2-es metszéspontja maga is egy ekvivalencia-reláció.

Meghatározás 2.8. A relációk uniója (1-gyel, M) és (2-vel, M-mel) a megfelelő részhalmazok uniója által meghatározott reláció. (x, y) 1-vel 2-vel akkor és csak akkor, ha (x, y) 1-gyel vagy (x, y) 2-vel.

2.3. Tétel: Ahhoz, hogy az ekvivalenciák egyesítése 1-gyel 2-vel önmagában ekvivalencia reláció legyen, szükséges és elégséges, hogy

1-től 2-től = 1-től 2-től

Meghatározás 2.9. A (c 1, M 1) és (c 2, M 2) összefüggések közvetlen összegét aránynak nevezzük. A közvetlen összeget (c 1, M 1) (c 2, M 2) jelöljük.

Így ha (c 1, M 1) (c 2, M 2) = (), akkor M =.

2.4. Tétel: Ha, és az összefüggések ekvivalenciák, akkor a (c 1, M 1) (c 2, M 2) = () relációk közvetlen összege is ekvivalencia.

V. Kapcsolatok típusai

Mutassunk be néhány fontosabb kapcsolattípust. Példákat adunk a harmadik fejezetben.

Meghatározás 2.10. Az M halmazon lévő c relációt toleranciának nevezzük, ha reflexív és szimmetrikus.

Meghatározás 2.11. Az M halmazon lévő c relációt szigorú rendű relációnak nevezzük, ha antireflexív és tranzitív.

Meghatározás 2.12. A c szigorú sorrendű relációt tökéletes szigorú sorrendnek nevezzük, ha M-ből bármely x és y elempárra igaz az (x, y) vagy (y, x).

Meghatározás 2.13. Az M halmazon lévő c relációt nem szigorú rendű relációnak nevezzük, ha a következő formában ábrázolható:

ahol M-en szigorú sorrend van, E pedig átlós reláció.

KAPCSOLAT

A kapcsolatok ugyanazon halmaz elemei közötti megfelelések, azaz olyan megfelelések, amelyek alaphalmazai egybeesnek:

x A, y A hozzáállás Г = ((x,y)| P(x,y)), P(x,y) valamilyen állítás (állítás).

Ha (x,y) Г, akkor azt mondják x kapcsolatban vannak G Nak nek nál nél.

Például, ha ugyanaz a maradék (számoknál), egy vonaltól azonos távolságra van (pontokhoz), családi vagy szomszédi kapcsolatok (sok ember számára).

Szigorúbb meghatározás:

A bináris reláció két halmaz:

1) A tartókészlet,

2) Г=((x,y)| x A, y A párok halmaza, amely a támasztóhalmaz négyzetének részhalmaza.

Egy n-áris reláció, vagy egy n-áris (terner, quaterner, ...) reláció egy támogató halmaz Aés sordimenziós halmazok n, amely a halmaz egy részhalmaza A n.

Példa a háromoldalú kapcsolatra: a „három játékos” része.

Ha egy relációt egyszerűen sorok halmazaként értünk (támogató halmaz nélkül), akkor a halmazelmélet összes törvénye használható. Az univerzális halmaz a támogató halmaz négyzete lesz, vagyis az összes lehetséges sor halmaza (amikor minden elem minden más elemhez viszonyítva van).

A relációt objektumváltozók kéthelyes predikátumaként is definiálhatjuk x, y, amely az „igaz” értéket veszi fel, ha (x, y) Gés hamis ha nem tartozik.

Megnevezések: (x, y) Г, у = Г(x), у = Гx vagy egyszerűen xGu például az egyenlőségi relációt (x = y), rendelési viszony (X< у) .

Ha (x, y) G, Azt xGu az "igaz" értéket veszi fel, egyébként - "hamis".

Ha a relációkat egy diszkrét halmazon adjuk meg, akkor mátrix formájában is felírhatók

A i , j =

Hozzáállás – különleges eset levelezés, ehhez bevezethet inverz relációkat, relációk összetételét:

Г -1 =((y,x)| (x,y) Г), Г ◦ Δ = ((x,z) | y ((x,y) Г &(y,z Δ))).

Bevezetik az „egységelem” fogalmát Δ 0 = ((x,x)) – „magához viszonyítva lenni”. Mátrixábrázolásnál ez lesz a főátló).

Tulajdonságok bináris relációk

1 Reflexivitás – "önmagához képest lenni"

xGx - igaz(például kapcsolatok x=x, x≤x, x≥x).

2 Antireflexivitás - "nem viszonyulni önmagához"

xGx - hazugság(például kapcsolatok x≠x, x x).

Ha egy halmaz nem „reflexív”, ez nem jelenti azt, hogy „antireflexív”.

3 Szimmetria „függetlensége attól, hogy melyik elem az első és melyik a második”

хГу – igazság → уГх – igazság(például kapcsolatok x=y, x≠y).

4 Antiszimmetria "nem haladja meg a"

(xGy – igaz) & (yGx – igaz) → (x=y) (például relációk x≤y, x≥y).

5 Aszimmetria (nem szimmetria) "felülmúl"

xGy – igaz → yGx – hamis (például kapcsolatok x<у, х>nál nél).

6. Tranzitivitás "terjedés"

(xГу – igaz) & (yГz – igaz) → (хГz – igaz)(például kapcsolatok x=y, x<у, х>y, x≤y, x≥y, hozzáállás x≠y nincs tranzitivitása).

KÜLÖNLEGES BINÁRIS KAPCSOLATOK

Tekintsük az „ekvivalencia relációt”, a „nem szigorú rendű relációt”, a „szigorú rendű relációt” és a „dominancia relációt”.

Egyenértékűségi reláció

Az ekvivalenciareláció reflexív(x~x), szimmetrikus ((x~y)=(y~x)), tranzitív ((x~y)&(y~z)→(x~z)) hozzáállás.

Példák: egyenlőség, azonosság, halmazok ekvivalenciája, logikai állítások ekvivalenciája, hasonlóság geometriai formák, az egyenesek párhuzamossága, de az egyenesek merőlegessége nem ekvivalencia reláció.

Egy elemmel egyenértékű elemek egy részhalmazát nevezzük ekvivalencia osztály vagy rokon osztály.

Az osztály bármely elemét osztályreprezentatívnak nevezzük.

Tulajdonságok.

Az osztály minden eleme egyenértékű egymással.

A különböző osztályokból származó elemek nem egyenértékűek.

Egy elem csak a saját osztályába tartozhat.

A teljes készlet osztályszövetségként ábrázolható.

Így az ekvivalenciaosztályok halmaza vagy az osztályok teljes rendszere a támogató halmaz egy partícióját alkotja. Emlékeztető: egy halmaz particionálása diszjunkt részhalmazokként jeleníti meg.

Partíciós index– az ekvivalencia osztályok száma.

Tényezőkészlet az ekvivalenciarelációt tekintve ez egy osztály összes osztályának vagy képviselőjének halmaza.

Egy tényezőhalmaz számossága megegyezik a partíciós indexszel.

Rendelési kapcsolatok

A sorrendi reláció kétféle bináris relációra utal.

Hozzáállás laza rend reflexívnek nevezzük (x≥x), antiszimmetrikus ((x≤y)&(y≤x)→ (x=y)), tranzitív ((x≥y)&(y≥z)→(x≥z)) hozzáállás.

Azt mondják, egy készletnek laza a sorrendje. A ≤ , ≥ fogalmak tágabb jelentéssel bírnak: nem rosszabb - nem jobb, nem korábban - nem később, és így tovább. A halmazelméletben a nem szigorú sorrend példája a nem szigorú beillesztés (lévén egy másik halmaz részhalmaza0.

Hozzáállás szigorú rend antireflexívnek nevezik ((X , antiszimmetrikus ((x , tranzitív

((x>y)&(y hozzáállás.

Azt mondják, hogy egy készletnek szigorú rendje van. Fogalmakban< , >tágabb jelentéssel bírnak: rosszabb a jobb, korábban később stb. A halmazelméletben a szigorú sorrend példája a szigorú befogadás (egy másik halmaz részhalmaza anélkül, hogy egyenlő lenne vele).

Megrendelt készletek

A készlet ún lineárisan rendezett, ha bármely elem összehasonlítható (azaz mondjuk: nagyobb, kisebb vagy egyenlő).

Valós vagy egész számok halmaza: klasszikus példák rendezett halmazra.

Ha egy halmazon lehetséges sorrendi relációt létrehozni, de nem minden elempárra, akkor egy ilyen halmazt ún. részben megrendelt.

Ez vektorok halmaza, komplex számok halmaza, halmazok halmazai a halmazelméletben. Egyes esetekben azt mondhatjuk, hogy „több kevesebb” vagy „legyen szuperhalmaz és részhalmaz”, de nem minden esetben.

Egyenértékű elemek osztályai és tulajdonságaik

Legyen %%R%% — ekvivalencia reláció a készleten %%M%% és %%a%% - valamilyen elem a %%M%%-ból. Tekintsük az összes olyan elem halmazát a %%M%%-tól, amely a %%R%% és a %%a%% elem között van kapcsolatban.

Egyenértékűségi osztály%%M_a%%

az összes olyan %%M%% elem halmaza, amelyek %%R%% kapcsolatban állnak a %%a%% elemmel, azaz a halmaz

$$ M_a = \(x \in M: x~R~a\). $$

Példa

Legyen %%M%% Oroszország összes lakosának halmaza, %%R%% pedig az „ugyanabban a városban élni” ekvivalenciareláció. Keresse meg az egyenértékű elemek osztályait %%M_a%% a következőhöz: %%a \in M%%.

A %%a%% elemmel egyenértékű elemosztály alakja: $$ M_a = \(x \in M: x \text( ugyanabban a városban él, mint a személy ) a\) $$

A %%a%% elemtől függően több ekvivalenciaosztályt kapunk. Például a moszkvai vagy szentpétervári lakosok egyenértékűségi osztálya.

Az ekvivalencia osztályok tulajdonságai

Legyen %%R%% egy ekvivalenciareláció a %%M%% halmazon, a %%M_a, M_b, \dotsc, M_z, \dotsc%% pedig a %%R%% reláció összes ekvivalenciaosztálya. Ekkor ezek az osztályok a következő tulajdonságokkal rendelkeznek.

1. tulajdonság

Bármely %%a \in M%% elemre teljesül a $$ a \in M_a $$ feltétel

Valójában definíció szerint a %%M_a osztály = \(x \in M: x~R~a\)%%. Ekkor a %%a%% elemre a %%a \in M_a \leftrightarrow a~R~a%% feltételnek teljesülnie kell, ami teljesül, mivel a %%R%% reláció a definíció szerint reflexív. egy ekvivalencia relációról. Ezért %%a \in M_a%%.

Következésképpen Ezzel a tulajdonsággal azt mondhatjuk, hogy minden %%M_a%% osztály egy nem üres halmaz.

2. tulajdonság

Legyenek %%M_a%% és %%M_b%% a %%R%% reláció ekvivalenciaosztályai. A %%M_a%% és a %%M_b%% osztályok akkor és csak akkor egyenlőek, ha a %%a%% elem %%R%% és %%b%% relációban van. $$ M_a = M_b \bal jobbra nyíl a~R~b. $$

3. tulajdonság

Legyenek %%M_a%% és %%M_b%% a %%R%% reláció ekvivalenciaosztályai. Ekkor a %%M_a%% és a %%M_b%% osztályoknak nincsenek közös elemei. $$ M_a \neq M_b \rightarrow M_a \cap M_b = \varnothing $$

4. tulajdonság

A %%M%% halmaz összes ekvivalenciaosztályának uniója megegyezik a %%M%% halmazzal. $$ \bigcup_(a\in M)(M_a) = M. $$

Egy halmaz felosztása

A %%M%% halmaz %%M_i%% részhalmazainak gyűjteménye, ahol %%i \in I%% (az indexek halmazához), a %%M%% halmaznak hívva hasításállítsa be a %%M%% értéket, ha a következő feltételek teljesülnek:

  1. A %%M_i%% részhalmazok mindegyike nem üres.
  2. Az összes %%M_i%% részhalmaz egyesítése megegyezik a %%M%% halmazzal.
  3. Két különböző részhalmaz, %%M_i%% és %%M_j%%, ahol %%i \neq j%%, nem rendelkeznek közös elemekkel.

Tétel. Legyen %%R%% egy ekvivalenciareláció a %%M%% halmazon. Ezután a %%M%% halmaz ekvivalenciaosztályainak halmaza alkotja a partícióját.

Valóban, ha a %%M_a%% ekvivalenciaosztályokat a %%M_i%% részhalmazaiként vesszük, akkor mindhárom feltétel teljesül:

  1. Minden ekvivalenciaosztály egy nem üres halmaz, aszerint tulajdonság 1.
  2. Az összes ekvivalencia osztály uniója a %%M%%, szerint tulajdonság 4.
  3. Két különböző ekvivalenciaosztálynak nincs közös eleme tulajdonság 3.

A partíció meghatározásának minden feltétele teljesül. Ezért az ekvivalenciaosztályok a %%M%% halmaz partíciói.

Példák

Legyen adott a %%M = \(1, 2, 3, 4, 5, 6, 7, 8, 9, 0 \)%% halmaz, akkor ennek a halmaznak a következő halmazgyűjtemények lehetnek partíciói:

  1. %%A_1 = \(1, 2, 3\), A_2 = \(4, 5, 6, 7\), A_3 = \(8, 9, 0\)%%.
  2. %%B_1 = \(0, 7, 2\), B_2 = \(1, 3, 5\), B_3 = \(4, 6, 8, 9\)%%.

De a következő aggregátumok nem partíciók:

  1. %%C_1 = \(1, 2, 3\), C_2 = \(4, 5, 6, 7\), C_3 = \(8, 9, 0, 3\)%%.
  2. %%D_1 = \(0, 7, 2\), D_2 = \(1, 3, 5\), D_3 = \(4, 6, 8, 9\), D_4 = \varnothing%%.
  3. %%E_1 = \(0, 1, 2\), E_2 = \(3, 4, 5\), E_3 = \(6, 7, 8\)%%.

A %%C_i%% halmaz nem partíció, mert nem teljesíti a particionálási halmazok 3. feltételét: a %%C_1%% és a %%C_3%% halmazoknak van egy közös eleme %%3%%.

A %%D_i%% halmaz nem partíció, mert nem teljesíti a particionálási halmazok 1. feltételét: a %%D_4%% halmaz üres.

A %%E_i%% halmaz nem partíció, mert nem teljesíti a particionáló halmazok 2. feltételét: a %%E_1, E_2%% és %%E_3%% halmazok uniója nem alkotja a %%M%% halmazt.

Egyenértékűségi reláció egy olyan reláció, amely reflexivitás, szimmetria és tranzitivitás tulajdonságokkal rendelkezik. A tábla jelzi ~, rekord A ~ V azt jelenti, hogy A egyenértékű V .

A definíció szerint az ekvivalenciareláció a következő tulajdonságokkal rendelkezik:

Példák az ekvivalencia összefüggésekre – egyenlőség, háromszögek hasonlósága.

Az ekvivalenciareláció használatával lehetőség van egy halmaz ekvivalenciaosztályokra történő particionálására.

Egyenértékűségi osztály , amelyet az elem generál – az összes elem halmaza , kezdve az egyenértékűséggel kapcsolatban. Az ekvivalencia osztály meghatározása a következő:

, Mert
elemek vannak kiválasztva
, amelyek összhangban vannak az elemmel x .

Az ekvivalencia relációnak nagy gyakorlati alkalmazása van, lehetővé téve a halmazok ekvivalenciaosztályokra való felosztását. Az ekvivalenciaosztályt akkor kaphatjuk meg, ha a kiválasztott elemre x sokaktól x elemeket választhat ki
, található x egy ekvivalencia osztályban

Tényezőkészletek készletek ekvivalencia relációvalφ – az összes különböző ekvivalenciaosztály halmaza, jelölveA/φ .

Partíciós index , amelyet a reláció generálφ a tényezőhalmaz hatványa A/φ .

Példa2 .11.

A) Egyenlőségi viszony
bármely halmazon egy ekvivalencia reláció.

Az egyenlőség egy minimális ekvivalencia reláció abban az értelemben, hogy amikor eltávolítunk egy párat a
(vagyis bármely mértékegység a mátrix átlóján
) megszűnik reflexív lenni, és ezért többé nem ekvivalencia.

b) Az űrlap nyilatkozatai
vagy
, amely egyenlőségjellel összekapcsolt képletekből áll, bináris relációt definiál az elemi függvények szuperpozícióit leíró képlethalmazon. Ezt az összefüggést általában ekvivalenciarelációnak nevezik, és a következőképpen definiálják: a képletek ekvivalensek, ha ugyanazt a függvényt határozzák meg. Az ekvivalenciát, bár = jellel jelöljük, különbözik az egyenlőség relációjától
, hiszen különféle képletekre is végrehajtható. Hozzáállás
képleteknél ez a helyesírási képletek egybeesése. Ezt hívják grafikus egyenlőség .

V) Tekintsünk háromszögek halmazát egy síkon, feltéve, hogy adott egy háromszög, ha adottak a csúcsainak koordinátái. Két háromszöget nevezünkegybevágó (egyenlő ) , ha egymásra helyezve egybeesnek, vagyis valamilyen mozdulattal egymásba alakíthatók. A kongruencia egy ekvivalencia reláció háromszögek halmazán.

G) Hozzáállás" osztva ugyanannyi marad 9" egyenértékű
. Ez az összefüggés a (12, 21), (17, 36) párokra érvényes, a (11, 13), (19, 29) párokra nem.

Engedd a forgatásra adott ekvivalencia reláció . Végezzük el a következő konstrukciót. Válasszunk ki egy elemet
és alkotnak egy osztályt (részhalmazt ), a következőket tartalmazza ; majd válassza ki az elemet
és alkotnak egy osztályt , a következőket tartalmazza és minden elem egyenértékű stb. Az eredmény egy osztályrendszer
(esetleg végtelen) úgy, hogy bármely elem a legalább egy osztályba tartozik, azaz
. Ez az osztályrendszer a következő tulajdonságokkal rendelkezik:

    kialakul partíció, vagyis az osztályok párban ne keresztezze egymást;

    bármely két elem ugyanabból az osztályból egyenértékű;

    bármely két elem a különböző osztályokból nem egyenértékűek.

Mindezek a tulajdonságok a reflexivitásból, a szimmetriából és a tranzitivitásból következnek . Valóban, ha például az osztályok És , metszenek, akkor közös elemük lenne , egyenértékű És , de akkor a tranzitivitás miatt lenne
, ami ellentmond a konstrukciónak . A másik két tulajdonság hasonlóképpen bizonyított.

A felépített partíciót, vagyis az osztályrendszert rendszernek nevezzük ekvivalencia osztályok kapcsolatban . Ennek a rendszernek a számosságát partíciós indexnek nevezzük. Másrészt bármilyen partíció osztályok egy bizonyos ekvivalencia relációt határoznak meg, nevezetesen a relációt egy adott partíció azonos osztályába tartoznak».

Példa. 2.12.

A) Minden ekvivalencia osztály az egyenlőségi reláció tekintetében
egy elemből áll.

b) Az azonos elemi függvényt leíró képletek az ekvivalenciareláció tekintetében ugyanabba az ekvivalenciaosztályba tartoznak. Ebben a példában maga a képletkészlet, az ekvivalenciaosztályok halmaza (vagyis a partíciós index) és az egyes ekvivalenciaosztályok megszámlálhatók.

c) Partíció
kapcsolatban " van teljes maradéka, ha elosztjuk vele A 7" végső indexe 7, és 7 számlálási osztályból áll: 0, 7, 14, ...; 2, 9, 16, …; ...; 6, 13, 20,…



Hasonló cikkek