Példák az egyenlőtlen kapcsolatokra. Bináris relációk – MT1102: Lineáris algebra (bevezetés a matematikába) – Üzleti informatika
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 azon objektumok halmazát, amelyek felcserélhetők az x objektummal. 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. Az M halmazon lévő c reláció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ó valamely á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 M i általános 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 a c* „szabványnak lenni” (x i, y) reláció teljesül
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 a nem-negatív egész számok halmazát, és vegye fel a partícióját a páros számok M 0 halmazára és a páratlan számok M 1 halmazára. 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 hányadoshalmazaként olvassuk egy relációhoz képest.
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. Az M halmazon lévő c reláció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ó valamely á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 az következik, hogy a forma halmazai az M halmaz egy partícióját alkotják (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 az általános partíciós osztályban. Fordítva, legyen u és v. Mutassuk meg, hogy (u, v) c Valóban van (x, u) c és (x, v) c. Ezért szimmetria szerint (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 közös elem y, és ezért egybeesik. 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-gyel 2-vel és 1-vel 2-vel való ekvivalenciák metszéspontja maga is egy ekvivalencia-reláció.
Meghatározás 2.8. A (c 1, M) és (c 2, M) relációk uniója 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 még néhányat fontos típusok kapcsolatok. 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ó.
Tekintsük az egyenlőségi relációt az X = ( ) törtek halmazán. Ez a kapcsolat:
Reflexszerűen, hiszen minden tört önmagával egyenlő;
Szimmetrikusan, hiszen abból, hogy egy tört egyenlő a törttel, az következik, hogy a tört egyenlő a törttel;
Tranzitív, hiszen abból, hogy a tört egyenlő a törttel, a tört pedig törttel, az következik, hogy a tört egyenlő törttel.
A törtek egyenlőségének relációját ekvivalenciarelációnak mondjuk.
Meghatározás. Egy X halmazon lévő R relációt ekvivalenciarelációnak nevezünk, ha egyszerre rendelkezik reflexivitás, szimmetria és tranzitivitás tulajdonságaival. .
Az ekvivalencia viszonyok példái közé tartoznak az egyenlőségi viszonyok geometriai formák, az egyenesek párhuzamosságának összefüggése (feltéve, hogy az egybeeső egyeneseket párhuzamosnak tekintjük).
Miért emelik ki ezt a típusú kapcsolatot a matematikában? Tekintsük az X = ( ) halmazon definiált törtek egyenlőségi összefüggéseit. (7. ábra).
Látjuk, hogy a halmaz három részhalmazra oszlik: Ezek a részhalmazok nem metszik egymást, és uniójuk egybeesik az X halmazzal, vagyis az X halmaznak van egy partíciója osztályokra. Ez nem véletlen.
Egyáltalán ha egy ekvivalencia reláció adott egy X halmazon, akkor ennek a halmaznak egy partícióját generálja páronként diszjunkt részhalmazokra (ekvivalencia osztályokra).
Így megállapítottuk, hogy az egyenlőségi reláció egy törtek halmazán
X = ( ) megfelel ennek a halmaznak az ekvivalencia osztályokra való felosztásának, amelyek mindegyike egymással egyenlő törtekből áll.
Ez fordítva is igaz: Ha egy X halmazon definiált bármely reláció ennek a halmaznak egy partícióját generálja osztályokba, akkor ez egy ekvivalencia reláció.
Tekintsük például az X = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) halmazban azt az összefüggést, hogy „ugyanaz a maradéka, ha elosztjuk 3-mal”. Létrehozza az X halmaz egy partícióját osztályokra: az egyik tartalmazza az összes olyan számot, amelyek maradéka 3-mal osztva 0 (ezek a 3, 6, 9 számok), a második olyan számokat tartalmaz, amelyeket 3-mal osztva 1 marad ( ezek 1, 4, 7, 10 számok, a harmadikban pedig minden szám, 3-mal elosztva a maradék 2 (ezek 2, 5, 8 számok). Valójában az eredményül kapott részhalmazok nem metszik egymást, és uniójuk egybeesik az X halmazzal. Következésképpen az X halmazon definiált „ugyanaz legyen a maradék, ha elosztjuk 3-mal” reláció ekvivalenciareláció. Vegyük észre, hogy az ekvivalenciareláció és a halmaz osztályokra való felosztása közötti kapcsolatra vonatkozó állítás bizonyítást igényel. Letesszük. Tegyük fel, hogy ha egy ekvivalencia relációnak van neve, akkor a megfelelő nevet kapják az osztályok. Például, ha egy egyenlőségi relációt szegmensek halmazán adunk meg (és ez egy ekvivalencia reláció), akkor a szegmensek halmazát egyenlő szegmensek osztályaira osztjuk (lásd 4. ábra). A hasonlósági reláció egy háromszöghalmaz hasonló háromszögek osztályaira való felosztásának felel meg.
Tehát, ha egy adott halmazon van egy ekvivalencia reláció, ezt a halmazt osztályokra oszthatjuk. De megteheti az ellenkezőjét is: először osztja fel a halmazt osztályokra, majd definiál egy ekvivalenciarelációt, figyelembe véve, hogy két elem akkor és csak akkor ekvivalens, ha a kérdéses partíció azonos osztályába tartozik.
A halmaz osztályokba való felosztásának elve valamilyen ekvivalenciareláció segítségével a matematika egyik fontos elve. Miért?
Először, ekvivalens - ez azt jelenti, hogy egyenértékű, felcserélhető. Ezért az azonos ekvivalenciaosztály elemei felcserélhetők. Így azok a törtek, amelyek ugyanabban az ekvivalenciaosztályban találják magukat, nem különböztethetők meg
az egyenlőség relációja szempontjából, és a tört helyettesíthető pl.
Másodszor, mivel az ekvivalenciaosztályban vannak olyan elemek, amelyek valamilyen reláció szempontjából megkülönböztethetetlenek, ezért úgy gondoljuk, hogy az ekvivalenciaosztályt annak bármelyik képviselője határozza meg, pl. ennek az osztálynak egy tetszőleges eleme. Így az egyenlő törtek bármely osztálya megadható az ehhez az osztályhoz tartozó bármely tört megadásával. Az ekvivalenciaosztály egy képviselő általi meghatározása lehetővé teszi, hogy a halmaz összes eleme helyett az ekvivalenciaosztályok egyedi képviselőinek halmazát tanulmányozzuk. Például a sokszögek halmazán definiált „ugyanolyan számú csúcsot” ekvivalenciareláció létrehozza ennek a halmaznak a felosztását háromszögek, négyszögek, ötszögek stb. osztályaira. Egy adott osztályban rejlő tulajdonságokat annak egyik képviselőjén veszik figyelembe.
Harmadik, egy halmaz osztályokra particionálása ekvivalenciareláció segítségével új fogalmak bevezetésére szolgál. Például a „vonalköteg” fogalma úgy definiálható, mint ami a párhuzamos vonalakra jellemző.
Általánosságban elmondható, hogy minden fogalom, amellyel egy személy működik, az ekvivalencia egy bizonyos osztályát képviseli. „Asztal”, „ház”, „könyv” - mindezek a fogalmak általános elképzelések sok konkrét objektumról, amelyeknek ugyanaz a célja.
Egy másik fontos kapcsolattípus a rendelési kapcsolat. Ennek meghatározása a következő.
Meghatározás. Egy X halmazon lévő R relációt rendbeli relációnak nevezzük, ha egyszerre rendelkezik antiszimmetria és tranzitivitás tulajdonságaival.
Példák a sorrendi relációkra: „kisebb, mint” relációk a természetes számok halmazán; kapcsolat
„rövidebbek” a szegmensek halmazán, mivel antiszimmetrikusak és tranzitívak.
Ha egy rendbeli relációnak az összekapcsoltság tulajdonsága is van, akkor lineáris rendkapcsolatnak mondjuk.
Például a természetes számok halmazán a „kisebb, mint” reláció lineáris rendű reláció, mivel rendelkezik antiszimmetria, tranzitivitás és kapcsolódási tulajdonságokkal.
Meghatározás. Egy X halmazt rendezettnek nevezünk, ha van sorrendi kapcsolata.
Így a természetes számok N halmaza a „kisebb, mint” reláció megadásával rendezhető.
Ha egy X halmazon meghatározott sorrendi relációnak az összekapcsoltság tulajdonsága van, akkor azt mondjuk, hogy lineárisan rendezi az X halmazt.
Például a természetes számok halmaza a "kisebb, mint" relációval és a "többszörös" relációval is rendezhető – mindkettő sorrendi reláció. De a „kevesebb, mint” relációnak, a „többszörös” relációval ellentétben, megvan az összekapcsolódás tulajdonsága is. Ez azt jelenti, hogy a „kisebb, mint” reláció lineárisan rendezi a természetes számok halmazát.
Nem szabad azt gondolni, hogy minden reláció ekvivalencia- és sorrendi viszonyokra oszlik. Rengeteg olyan reláció van, amely nem ekvivalenciareláció, sem nem sorrendi reláció.
Kapcsolódó definíciók
Az összes ekvivalenciaosztály halmazát jelöli.
Példák ekvivalencia relációkra
Több összetett példa, de elengedhetetlen:
Amikor az orvos gyógyszert ír fel Önnek, a receptben az egyenértékű gyógyszerek osztályát nem tudja feltüntetni a tabletták vagy ampullák csomagolásának teljesen konkrét példányát. Azok. Mindenféle gyógyszert osztályokba osztanak az ekvivalencia viszonyok alapján. Ha ez nem lenne, a modern orvostudomány egyszerűen nem lenne lehetséges.
Így mindenféle saláta- és koktélrecept, GOST-ok és osztályozók is meghatározzák a létfontosságú ekvivalencia összefüggéseket. Az ekvivalenciarelációk egész életünket kitöltik, és nem absztrakt időtöltés a matematikusok számára.
A leképezések faktorizálása
Az ekvivalencia relációnak megfelelő ekvivalenciaosztályok halmazát a szimbólum jelöli és hívja faktor-készlet viszonylag . Sőt, a szürjektív leképezés
hívott természetes megjelenítés(vagy kanonikus vetület) a faktorhalmazhoz.
Legyen , halmazok, leképezés, majd a szabály által meghatározott bináris reláció
egy ekvivalencia reláció -on. Ebben az esetben a leképezés a szabály által meghatározott leképezést indukálja
vagy mi ugyanaz,
.Ebben az esetben kiderül faktorizáció leképezések szürjektív leképezésre és injektív leképezésre.
A térképfaktorizációt széles körben használják bölcsészettudományok illetve a technika azon területein, ahol nem lehet számértékeket használni. A leképezési faktorizáció lehetővé teszi, hogy képleteket nélkülözzön ott, ahol képletek nem használhatók. Adjunk egy példát, amely mindenki számára érthető lesz, és nem igényli a bonyolult matematikai szimbolika megértését.
Az iskolai órarend a faktorizáció tipikus példája. Ebben az esetben az összes tanuló halmaza, az összes tanulmányi tárgy halmaza, a hét napjai szerint elosztva, az órai időpontok megadásával. Az ekvivalencia osztályok osztályok (tanulók csoportjai). Kijelző – a tanulói naplókban megjelenített órarend. Kijelző - órarend kifüggesztve az iskola halljában. Itt van egy kijelző is - az osztályok listái. Ez a példa nagyon jól mutatja a faktorizáció gyakorlati előnyeit: lehetetlen az órarendet olyan táblázatként elképzelni, amely az iskola összes diákját egyénileg tükrözi. A faktorálás lehetővé tette a tanulók számára szükséges információk kompakt formában történő megjelenítését olyan helyzetekben, ahol képletek nem alkalmazhatók.
A faktorizáció előnyei azonban nem korlátozódnak erre. A faktorizálás lehetővé tette a munkamegosztást a tevékenységben résztvevők között: az igazgató órarendet készít, a tanulók pedig beírják a naplójukba. Hasonlóképpen, a receptek faktorizálása lehetővé tette a munkamegosztást a diagnózist felállító és a receptet felíró orvos és a felírt gyógyszerek egyenértékűségét biztosító gyógyszerész között. A faktorizáció apoteózisa a futószalag, amely az alkatrészek szabványosításával valósítja meg a maximális munkamegosztást.
De a faktorizáció előnyei nem korlátozódnak erre. A faktorizáció lehetővé tette a modularitást modern technológia, ami a funkciók soha nem látott rugalmasságát biztosítja. Megtarthatja a régi SIM-kártyát, és vásárolhat hozzá egy teljesen új telefont, vagy új videomemóriát helyezhet a régi számítógépébe. Mindez a rugalmasság, a modularitás, ami a faktorizáción alapul.
Irodalom
- A. I. Kostrikin, Bevezetés az algebrába. M.: Nauka, 1977, 47-51.
- A. I. Malcev, Algebrai rendszerek, M.: Nauka, 1970, 23-30.
- V. V. Ivanov, Matematikai elemzés. NSU, 2009.
Lásd még
- A tolerancia relációja az ekvivalencia legyengült formája.
- Az ekvivalencia egy logikai művelet.
Wikimédia Alapítvány. 2010.
- Kórházi tüdőgyulladás
- Mitel
Nézze meg, mi az „ekvivalenciareláció” más szótárakban:
ekvivalencia reláció- - Távközlési témák, alapfogalmak EN ekvivalencia reláció... Műszaki fordítói útmutató
Egyenlőségi típusú reláció- ekvivalenciareláció, logikai és matematikai fogalom, amely kifejezi ugyanazon jelek (tulajdonságok) különböző objektumokban való jelenlétét. Az ilyenekkel kapcsolatban közös vonásai ezek a különböző tárgyak megkülönböztethetetlenek (azonosak, egyenlők,... ...
A tolerancia hozzáállása- Ennek a kifejezésnek más jelentése is van, lásd: Tolerancia. A tolerancia reláció (vagy egyszerűen tolerancia) egy halmazon egy bináris reláció, amely kielégíti a reflexivitás és a szimmetria tulajdonságait, de nem feltétlenül... ... Wikipédia
Arány (matematika)- Ennek a kifejezésnek más jelentése is van, lásd: Hozzáállás. A reláció egy matematikai struktúra, amely formálisan határozza meg a különböző objektumok tulajdonságait és kapcsolataikat. A kapcsolatokat általában a hivatkozott objektumok száma alapján osztályozzák... Wikipédia
HOZZÁÁLLÁS- a logikában olyasmi, ami a tulajdonsággal ellentétben nem egy különálló tárgyat, hanem egy párt, hármat stb. tételeket. A hagyományos logika nem vette figyelembe O.-t; a modern logikában az O. két vagy több változó propozíciós függvénye. Bináris... Filozófiai Enciklopédia
Preferencia kapcsolat- a fogyasztói elméletben ez a fogyasztó azon képességének formális leírása, hogy összehasonlítsa (kívánatos rendezés) különböző árukészleteket (fogyasztói készleteket). A preferenciakapcsolat leírásához nem szükséges mérni a kívánatosságot... ... Wikipédia
Hozzáállás (filozófiai)- Attitűd, az elemek elrendezésének jellegét kifejező filozófiai kategória egy bizonyos rendszerés kölcsönös függőségeik; egy személy érzelmi-akarati attitűdje valamihez, azaz pozíciójának kifejezése; különböző tárgyak mentális összehasonlítása... Nagy Szovjet Enciklopédia
hozzáállás- A RELATIONSHIP rendezett n ok egyedek halmaza (ahol n 1), azaz. kettes, hármas stb. Az n számot „localitásnak” vagy „aritásnak” nevezik O.-nak, és ennek megfelelően n helyi (n arno) O-ról beszélnek. Így például egy kettős O.-t... ... Ismeretelméleti és Tudományfilozófiai Enciklopédia
Hozzáállás- Az attitűd egy filozófiai kategória, amely egy bizonyos rendszer elemeinek elrendezésének jellegét és egymásrautaltságát fejezi ki; egy személy érzelmi-akarati attitűdje valamihez, azaz pozíciójának kifejezése; különböző gondolatok összehasonlítása.... Nagy Szovjet Enciklopédia
Egyenértékűségi osztály- Az ekvivalenciareláció () egy X halmazon egy bináris reláció, amelyre a következő feltételek teljesülnek: Reflexivitás: bármely a-ra X-ben, Szimmetria: ha, akkor, Tranzitivitás: ha... Wikipédia
Könyvek
- Pénzügyi döntések meghozatala komparatív bizonytalanság körülményei között: Monographia, Bayuk O.A.. A monográfiában egy új logikus döntéshozatali stratégia kerül kidolgozásra és elméletileg alátámasztva az összehasonlíthatatlan objektumok közötti választás során, sajátos preferencia- és...
Számos számítási feladatban nagy halmazokat vesznek fel és osztanak fel úgy, hogy az összes számunkra érdekes szituáció több helyesen kiválasztott példa segítségével tanulmányozható legyen.
1. definíció: Legyen A ¹ Æ és (A i ),i= olyan részhalmazok gyűjteménye, amelyekre A= . Ekkor ezeknek a részhalmazoknak a gyűjteményét nevezzük bevont készlet A.
Például (A, B) az AÈB borítása; (A, AÈB, B, C)-takaró AÈBÈC.
Megjegyzés: Általános esetben a lefedettség végtelen lehet. Konkrét tulajdonságok tanulmányozása szempontjából azonban ez a helyzet nem kelt lelkesedést.
2. definíció: Hasítással egy nem üres halmaz A lefedését úgy nevezzük, hogy ha i¹ j, akkor A i ÇA j =Æ.
Például (A, A’) egy partíció U.
(AÇB, AÇB’, A’ÇB, A’ÇB’) – partíció U,
(A\B, AÇB, B\A) – AÈB partíció.
A nem üres halmazok partícióját megszervezheti olyan relációk segítségével, amelyek egyenlőségi relációkként viselkednek számok vagy halmazok halmazán.
3. definíció: Egy halmaz bináris relációját nevezzük ekvivalencia reláció, ha reflexív, szimmetrikus és tranzitív.
Példák:
1. Az összes háromszög halmazán: ((x, y)| x és y területe azonos)
2. Az összes program halmazán: ((a, b)| a, b számítsa ki ugyanazt a függvényt egy adott gépen)
4. definíció: Legyen R egy ekvivalencia reláció az A és xОA halmazon. Az x által generált ekvivalenciaosztály az (y| xR y)=[x] R halmazt hívjuk.
5. definíció: Egy ekvivalenciaosztály bármely elemét hívjuk reprezentatív ez az osztály. Teljes képviselői rendszer képviselők halmazát hívják, minden osztályból egyet.
3. példa:
N – egész számok, s – fix elem. Tovább Z az összefüggés definiált: r s = ((x, y)| x-y=ns, nО Z). Hozzáállás összehasonlítások modulo s (jelölés: xºy(mod s)).
Könnyen ellenőrizhető, hogy a modulo s összehasonlítási reláció egy ekvivalencia reláció a halmazon Z.
Legyen például s=10. Akkor:
= {11,21,-9,10 976 631,.... }
= {66,226,-24,... }
Valójában ennek a relációnak csak 10 ekvivalenciaosztálya van, és a 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 számok jönnek létre. teljes képviselői rendszer. Az ezen az ekvivalenciareláción alapuló ekvivalenciaosztályokat nevezzük levonási osztályok modulo s.
6. definíció: Factor-set egy A halmazt egy R ekvivalenciarelációhoz képest az összes ekvivalenciaosztály halmazának nevezzük erre a relációra vonatkozóan, és A/R-nek jelöljük.
A maradék osztályok modulo s halmazát jelöljük Z s.
Bekövetkezik
Tétel (a particionálásról): Legyen R egy ekvivalenciareláció egy nem üres A halmazon. Ekkor az A/R hányadoshalmaz az A halmaz egy partíciója.
Bizonyíték:
"xОA(xО[x] R). Be kell bizonyítanunk, hogy az A halmaz minden eleme pontosan egy osztályba tartozik. Vagyis bebizonyítjuk, hogy ha az osztályoknak van legalább egy közös eleme, akkor egybeesnek. Legyen cО[ a] és cО [b], de akkor x R a, a R c, c R b Þ x R b ) Tehát [a] М [b] ] М [a].
Q.E.D.
A fordítva is igaz. Legyen S egy A halmaz partíciója és R s egy bináris reláció A-n, úgy, hogy: R=((x,y)ïx és y a partíció ugyanahhoz az eleméhez tartozik), akkor R-t hívjuk – az S partíció által meghatározott reláció.
Tétel (fordított): Az R reláció A-n, amelyet S partíciója határoz meg, egy ekvivalencia-reláció A-n, és A/R s = S. (függetlenül)
Feladatok:
1. Legyen A véges halmaz. Mely ekvivalenciarelációk adják a legnagyobb és a legkisebb számú ekvivalenciaosztályt.
2. Ha (A 1 , A 2 , ..., A n ) A és A véges partíciója, akkor .
Rendelési viszony.
Az egyenlőség fogalmából (például számok) adódik matematikai fogalom egyenértékűség. Az egyenlőtlenség fogalmából pedig egy másik típusú kapcsolat is keletkezik, amelyet rendi viszonyoknak neveznek.
1. definíció: Részleges rendelés az A halmazon egy bináris reláció, amely reflexív, antiszimmetrikus és tranzitív.
A részleges sorrend a £ és az R kapcsolat általánosítása. Bevezethetjük a fogalmat szigorú rend , a relációnak megfelelő< на R. Отношение строгого порядка - только транзитивно(оно еще и антирефлексивно).
Ha £ adott, akkor definiálhatjuk<: a
Azt a halmazt, amelyen a sorrendi relációt megadjuk, jelöljük
(X, £) (vagy (X,<), если порядок строгий).
2. definíció: Meghívjuk azt a halmazt, amelyen egy sorrendi reláció adott részben megrendelt.
Példa: A egy halmaz. ( P (A),Í), könnyen ellenőrizhető, hogy a kapcsolat Í rendelési reláció van P (A).
3. definíció: Az A-n lévő R rendű relációt nevezzük teljes ( lineáris ) sorrendben, ha " x, yÎA (xR y Ú yR x). Az (A, R) halmazt lineárisan rendezettnek nevezzük.
Példák:
1. arány £-hoz R egy teljes rend kapcsolat. És így ( R,£) - lineárisan rendezett.
2. és itt ( P (A),Í) nem lineárisan rendezett
3. x£y Û y x a készleten N nincs teljes rendben
4. definíció: hagyjuk (A, £) részben megrendelt készlet. Az AOA elemet hívják legkisebb/legnagyobb/ A-ban ha " xОA (a£ x) /x £ a /. A bОА elemet ún. minimum /maximum/ ha "xÎA (x£ a Þ x=a) /a £ x Þ a=x /.
Feladat: Bizonyítsuk be, hogy egy lineárisan rendezett halmaz esetében a legnagyobb (legkisebb) és maximális (minimális) elemek fogalma egybeesik. Mondjon példát egy részben rendezett halmazra, ahol nem esnek egybe!
A kapcsolatok összetétele
Legyenek adottak az A, B és C halmazok, valamint az A és B (azaz SÌA´B) és az R közötti összefüggések B és C között (RÌB´C). Definiáljunk egy új kapcsolatot A és C között a következőképpen:
1. definíció: Az összes olyan (x, y) pár halmaza, ahol létezik zÎB úgy, hogy (x, z)О S és (z, y)О R ún. kapcsolatok összetétele S és R. Jelölve: R o S . Így R o S Ì A´ C .
R oS = ((x, y)| $zÎB((x,z)ÎSÙ(z,y)ÎR)) vagy x R o Sy Û $zÎB(xSzÙzRy).
1. példa : Legyen A=(1, 2, 3), B=(1, 2, 3, 4, 5, 6), C=(3, 6, 9, 12), s =((1,2), (2 ,4), (3,6)), r=((1,3), (2,6), (3,9), (4,12)). Ekkor r o s=((1,6), (2,12)).
Illusztráljuk a helyzetet a képen:
2. példa : Legyen s és r kapcsolatok on N oly módon, hogy
S = ((x,x+1)ïxО N) és r = ((x 2 ,x)ïxО N). Ekkor D r = (x 2 ïxО N)=(1,4,9,16,25,...), és D s = N.
D r o s =(xïxО NÙ x+1=y 2 )=(3,8,15,24,...).
Abban az esetben, ha egy reláció egy halmazon van definiálva, kombinálható önmagával:
sos = s 2 = ((x,x+2)½xО N) és ror = r 2 = ((x 4 ,x)½xО N}.
Ezzel a jelöléssel definiálhatjuk a kapcsolat n-edik hatványát:
, ahol nО N, n>1.
Például a 2. példa relációihoz a következőket kapjuk:
,
A hasonlatot a szorzással szeretném kiegészíteni. Ehhez a következő természetes definíciót vezetjük be:
2. definíció: A bináris relációkat nevezzük egyenlő, ha részhalmazként egyenlőek, azaz R=S, ha"x,y((x,y)ÎRÛ(x,y)ÎS).
Nyilvánvaló, hogy a kapcsolatokat ugyanazokon a halmazokon kell meghatározni.
Tétel (kapcsolatok összetételének tulajdonságai): Bármely R, S, T bináris relációra a következő egyenlőségek érvényesek:
1. (RoS)oT = Ro(SoT)
2. (RoS) -1 = S -1 o R -1
Bizonyíték:
1) Tetszőleges x és y esetén:
x(RoS)oTy º $z(xTzÙ(zRoSy)) º $z$t(xTzÙ(zStÙtRy)) º $z$t((xTzÙzSt)ÙtRy) º $t(($z(xTzÙzSt)) ºtRy) $t((xSoTt)ÙtRy) º xRo(SoT)y.
2) x(RoS) -1 y º yRoSx º $z(ySzÙzRx) º $z(xR -1 zÙzS -1 y) º xS -1 vagy R -1 y.
Q.E.D.
Megjegyzés: ha R reláció az A halmazon, akkor világos, hogy I A vagyR=RoI A =R. Vagyis I A úgy viselkedik, mint egy számok szorzásakor. Teljes analógia azonban nem mondható. Mivel például a kommutativitásnak nincs helye az általános esetben, hiszen RoS definiálható, SoR viszont nem. Ahogy az R -1 vagy R=RoR -1 = I A egyenlőségnek sem mindig van értelme.
A kapcsolat lezárása
A lezárás fogalma alapvető matematikai fogalom, és a matematika legtöbb ágában használják. Szemléltessük ezt a fogalmat egy általános példával: vegyünk egy x 0 objektumot és egy P folyamatot, amely szekvenciálisan alkalmazva egy bizonyos halmazt generál, és így egy x 1 , x 2 , ..., x n , sorozatot definiál. .. így x 1 ÎP(x 0), x 2 ÎP(x 1),..., x n ÎP(x n -1),...
1. definíció: a P folyamat segítségével megszerezhető és x 0-val kezdődő sorozatok összes elemét tartalmazó halmazt hívjuk a folyamat lezárása P x 0-hoz viszonyítva .
Nyilvánvaló, hogy az eredmény az lesz, hogy egyesekre P n (x 0)-t találunk n. Ez n Nem tudjuk előre, ez magától a folyamattól függ. Sőt, ha az elemet vesszük y ettől a lezárástól, és alkalmazzuk rá az eljárást R, akkor nem kapunk semmi újat. Vagyis a készlet így nem bővíthető - zárt!
Példa : Vegyünk egy S négyzetet, amelyet ABCD-vel jelölünk, és tekintsük az r folyamatot, amely a négyzet óramutató járásával megegyező 90°-os elforgatásából áll:
|
|
|
|
|
Legyen egy A reláció definiálva valamilyen halmazon. Akkor:
2. definíció: Tranzitív zárás Az A relációt egy adott halmazon A + relációnak nevezzük:
Így egy nem tranzitív A relációból egy bizonyos halmazon tranzitív A + konstruálható.
Példák:
1. r - arány be N: r=((x, y)| y=x+1), akkor r + =((x, y)| x 2.s be K: s=((x, y)| x 3.t tovább K: t=((x, y)| x×y=1), akkor r + =((x, x)| x¹0) 4. Legyen L a londoni metróállomások halmaza; L=(a, b, c) egymást követő állomások. N=((x, y)| y x után következik. Ez azt jelenti, hogy (a, b), (b, c) ÎN; ezen kívül (a, a), (b, b), (c, c), (a, c) О N 2 . Ez azt jelenti, hogy N + =L´L Általánosságban elmondható, hogy a tranzitív lezárás nem reflexív (2. példa). Legyen A reláció X-en. Legyen A 0 =I X. 3. definíció: Reflexív zárás A* Az A relációkat relációnak nevezzük . Azaz .
Példák:
1. r*=((x, y)| x£y) 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\). $$ Legyen %%M%% Oroszország összes lakosának halmaza, %%R%% pedig az „ugyanabban a városban élni” ekvivalencia relá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. 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. Bármely %%a \in M%% elemre teljesül a $$ a \in M_a $$ feltétel Valójában a 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. 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. $$ 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 $$ A %%M%% halmaz összes ekvivalencia-osztályának uniója megegyezik a %%M%% halmazzal. $$ \bigcup_(a\in M)(M_a) = M. $$ 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: 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: A partíció meghatározásának minden feltétele teljesül. Ezért az ekvivalenciaosztályok a %%M%% halmaz partíciói. 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: De a következő aggregátumok nem partíciók: 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ű elemek osztályai és tulajdonságaik
Példa
Az ekvivalencia osztályok tulajdonságai
1. tulajdonság
2. tulajdonság
3. tulajdonság
4. tulajdonság
Egy halmaz felosztása
Példák