Halmazalgebra
A halmazalgebra vagy halmaztest (valószínűségszámításban szokásosabb kifejezéssel, eseményalgebra) a matematikai struktúrák egy fajtája, konkrétan egy egyszerű (nem-többszörös), egykomponensű topologikus ill. algebrai struktúra (mindkét tárgyalásmód lehetséges),[1] amely nem üres, és zárt az elemei[2] véges családjainak uniójára, metszetére és különbségére.
Definíciók
[szerkesztés]Legyen Ω tetszőleges halmaz, ennek részhalmazainak halmaza, vagyis hatványhalmaza, és legyen az Ω egy részhalmazai halmaza (egy Ω feletti halmazcsalád).
Az halmazt (szükség esetén az rendezett párt is[3]) az Ω halmaz feletti halmazalgebrának nevezzük, ha teljesülnek a következő tulajdonságok:
1. | nem üres, | azaz | |
2. | tartalmazza bármely eleme (Ω-ra vonatkozó) komplementerét, vagyis zárt a komplementerképzés műveletére; |
azaz | |
3. | tartalmazza bármely két eleme unióját, vagyis zárt az egyesítés műveletére, |
azaz |
A fogalom analogonja megfogalmazható az Ω feletti halmazrendszerek esetére is.
Zérus- és univerzum-zártság
[szerkesztés]Az 1. axióma helyettesíthető akár az " tartalmazza ∅-t" (az üres halmazt avagy a lehetetlen eseményt), akár az "A tartalmazza Ω-t" (az univerzális halmazt, avagy a biztos eseményt) tulajdonsággal, azaz az
vagy akár az
axiómákkal; hiszen ha nemüres, akkor tartalmaz egy T halmazt, akkor ennek T komplementerét is, ezeknek unióját is, ami maga Ω, ennek meg a komplementerét, ∅-t is. Fordítva, ha A tartalmazza akár az üres halmazt, akár Ω-t, akkor nem üres.
Különbségzártság
[szerkesztés]A 2. axióma helyettesíthető az " zárt a különbségképzésre" axiómával is, hiszen tetszőleges A,B⊆Ω halmazokra definíció szerint
ugyanakkor a De Morgan-azonosságokat, a kettős komplementerképzés (= helybenhagyás) és a disztributivitás törvényeit alkalmazva
,
ugyanakkor látható, hogy ha zárt az unió- és komplementerképzésre, akkor zárt az előzőek szerint a különbségképzéssel azonos műveletre is, fordítva, ha zárt a különbségképzésre, akkor az első axiómával ekvivalens Ω∈A segéd-axiómát is felhasználva, zárt az X* := Ω\X műveletre is, ami viszont a komplementerképzés.
További halmazelméleti tulajdonságok
[szerkesztés]Metszetképzésre való zártság
[szerkesztés]Könnyű belátni azt is, hogy
Tétel: a fenti axiómák teljesülése eredményeképp bármely halmaztest zárt a metszetképzésre, ugyanis a De Morgan-törvények egyszerű következményeképp
.
tehát ha A,B∈A; akkor a 2. axióma miatt A és B, a harmadik axióma miatt ezek uniója, és ismét a második miatt utóbbinak komplementere is A-beli.
Más, homonim értelemben ugyan, de a fenti címhez illik még a következő tétel is:
Tétel: Az Ω halmaz feletti halmazalgebrák tetszőleges nem üres rendszerének metszete is halmazalgebra.
Valóban, ha W halmazalgebrák halmaza, akkor a ∩W := {X∈P(Ω) | (∀W∈W):(X∈W)} halmazra teljesül, hogy nem üres, és zárt a komplementer- és unióképzésre. 1). nem üres, hiszen a tényezőknek két közös elemük is volt, mindegyiküknek, például ∅ és Ω; hiszen halmazalgebrák voltak. Továbbá 2). ∩W zárt a komplementerképzésre, hiszen ha M∈∩W, akkor M eleme volt minden W∈W-nek, de minden W halmazalgebra volt, azaz zárt a komplementerképzése, ergo minden W-nek az M komplementere is eleme volt, ergo a W-k metszetének is. 3). Hasonlóan, ∩W zárt az unióképzésre: ha U,V∈∩W, akkor U,V∈W minden W∈W-re, de W-k halmazalgebrák voltak, azaz U∪V∈W, ergo U∪V a metszetüknek is eleme. Összefoglalva 1.-2.-3.-t, a ∩W halmazcsalád egy halmazalgebra lesz.
„Univerzális” unió
[szerkesztés]Egyszerű, de fontos tulajdonság a következő: egy Ω feletti halmazalgebrának (mint halmazcsaládnak) uniója maga Ω:
Ennek az az egyszerű oka, hogy , így aztán az unió egyik tagja az univerzális halmaz, a többi – mind ennek részhalmaza – már nem ad ehhez semmilyen új elemet.
Generált algebra
[szerkesztés]Ad hoc általában nehéz egy halmazalgebrát elkészíteni, mondjuk ha veszünk néhány halmazt, és egy olyan halmazalgebrát akarunk, ami ezeket tartalmazza; különösen ha nem diszjunkt halmazokból indulunk ki, hiszen figyelni kell arra, hogy a tagok uniója, komplementere (ebből következően, a metszetük, különbségük) eleme legyen az algebrának. Szerencsére, bár általában nem olyan könnyű megmondani, hogy egy néhány halmazból építeni kezdett halmazalgebrának konkrétan mi az összes eleme, ennek ellenére mégis nyugodtan beszélhetünk olyan halmazalgebráról, ami tartalmazza az általunk kiválasztott halmazokat. Érvényes u.is:
Tétel: Legyen Ω tetszőleges halmaz, és G⊆P(Ω) az Ω részhalmazainak egy családja! Ekkor létezik olyan Ω feletti Ή(R) halmazalgebra, amelynek G minden eleme a tagja; és amely a legszűkebb (legkisebb) a ⊆ relációra nézve; azaz bármely más, az R elemeit elemként tartalmazó halmazalgebrának a részhalmaza.
Bizonyítás: Az biztos, hogy az Ω feletti teljes halmazalgebra (a P(Ω) család) halmazalgebra is, meg tartalmazza elemként az G összes elemét is, hiszen G⊆P(Ω) a feltételek szerint. Tehát azon halmazalgebrák W halmaza, amelyeknek G a részhalmaza, nem üres. Így lévén, képezzük a ∩W := {X∈P(Ω) | (∀W∈W):(X∈W)} halmazt. Ez nyilvánvalóan tartalmazni fogja G minden elemét, hiszen az összes W-re is igaz ez, tehát metszetükre is. Egy fentebbi tétel miatt továbbá ∩W, mint adott halmaz feletti halmazalgebrák egy rendszerének metszete, maga is az adott halmaz feletti halmazalgebra.
A fenti ∩W halmazalgebra legszűkebb is lesz abban az értelemben, hogy bármely, a G-t részhalmazként tartalmazó T halmazalgebrának a részhalmaza lesz. Hiszen T∈W a W definíciója szerint (W épp az R-tartalmazó halmazalgebrák halmaza), ezért érvényes ∩W = T∩(∩(W\{T}))⊆T, hiszen tetszőleges A,B halmazokra A∩B⊆A. ■ QED.
Kombinatorika
[szerkesztés]Véges Ω halmaz feletti halmazalgebra maximum 2|Ω| darab tagot tartalmazhat, hiszen ekkora a teljes halmazalgebra, vagyis a hatványhalmaz számossága. Nem feltétlenül kell ennyi elemet tartalmaznia (ld. a példákat). Az azonban igaz, hogy véges, nem üres halmaz feletti halmazalgebra számossága mindig kettő-hatvány (hogy páros, azt nagyon könnyű belátni, hiszen egy A taggal együtt annak – nem üres Ω esetén mindig különböző – komplementere is tag). Az is igaz, hogy tetszőleges véges Ω halmaz és bármely k≤|Ω| természetes szám esetén van 2k elemszámú halmazalgebra Ω felett, mégpedig pontosan annyi, ahány k elemű partíciója van az Ω halmaznak, (másodfajú Stirling-számok).[4] Mindennek bizonyítása az atom fogalmára hivatkozva történhet.
Összefüggés más struktúratípusokkal
[szerkesztés]Kapcsolat a halmazgyűrűkkel
[szerkesztés]Ha az 1. axiómát elhagyjuk, és a 3. axióma helyett a nála jóval gyengébb[5] metszet-zártság követelményét állítjuk fel, akkor a halmazgyűrű fogalmát kapjuk.
Kapcsolat a topologikus terekkel
[szerkesztés]Ha a 3. axióma helyett azt az erősebb követelményt állítjuk fel, hogy A zárt legyen tetszőleges (akár végtelen), de megszámlálható sok tagjának egyesítésére, akkor a Borel-féle halmaztest = σ-algebra fogalmát kapjuk. Ha további erősítést követelünk meg, nevezetesen: az unió legyen zárt az akármilyen végtelen családokra is, s egyúttal a 2. axiómát meggyengítjük, a különbségre zártság helyett csak a (véges) metszetre való zártságot követeljük meg, a topologikus tér fogalmát kapjuk.[6]
Kapcsolat a Boole-algebrákkal
[szerkesztés]A halmazalgebrák fontos szerepet játszanak egy általánosabb absztrakt algebrai struktúra, a Boole-algebrák elméletében. Ismeretes, hogy bármely B véges - általánosabban, bármely B komplett atomos - Boole-algebrához megadható olyan X halmaz, amelynek hatványhalmaza az unió-, metszet- és X-re vonatkozó komplementerképzés műveletével tekintve, az adott Boole-algebrával izomorf Boole-algebra lesz, szemléletesen szólva, „bármely Boole-algebra »igazából« egy hatványhalmaz-algebra” (hatványhalmaz-reprezentációs tétel, HRT). Ha a Boole-algebra nem komplett atomos, akkor egy hatványhalmaz helyett a Boole-algebra bizonyos ultrafiltereinek halmazalgebrája is izomorf B-vel; összességében tehát: bármely Boole-algebra izomorf egy halmazalgebrával (Stone-féle reprezentációs tétel, SRT). Az atom fogalma, ahogy a halmazalgebrák elméletében általában; kulcsszerepet játszik a HRT-ben is, sőt az SRT alapját is képezhetik az atomok viselkedésével kapcsolatos megfigyelések általánosításai, melyek elvezetnek az ultraszűrők alkalmazásához és ezáltal az SRT egy - bár nem az egyetlen lehetséges - bizonyításához.
Példák
[szerkesztés]- Tetszőleges nemüres Ω halmaz felett halmaztestet alkot a csak az üres és az univerzális halmazból álló kételemű {∅, Ω} halmaz, ez az Ω feletti minimális halmazalgebra.
- Tetszőleges nemüres Ω halmaz esetén a teljes Ω⊆P(Ω) halmaz is halmazalgebra, az Ω feletti teljes halmazalgebra. A minimális és a teljes halmazalgebrát összefoglaló néven az Ω feletti triviális halmazalgebráknak nevezzük.
- Tetszőleges Ω halmaz felett az egyelemű halmazokat tartalmazó Ω1 := { {ω} | ω∈Ω} =: {R ∈ P(Ω) | |R|=1} halmazrendszer által generált Ή(Ω1) halmazalgebra pontosan az Ω azon részhalmazait fogja tartalmazni, melyek vagy végesek, vagy komplementerük véges.[7] Ez csak véges Ω esetén lesz a teljes halmazalgebra, ha az alaphalmaz számossága akár csak megszámlálhatóra is növekszik (pl. N), a generált Ή(N1) halmazalgebra nem lesz a teljes hatványhalmaz. Például a prímek vagy a páros számok halmaza sem lesz mérhető, mivel e halmazok nem végesek, de komplementerük sem véges[8]
- Az Ω := {1,2,3,4,5,6} feletti egy halmazalgebra a {∅, {1,3,5}, {2,4,6}, Ω} halmaz. Valószínűségszámítási szempontból ez azért tanulságos példa, mert jelzi, hogy egy eseményalgebrának nem szükséges minden kimenetelt mint elemi eseményt (az Ω egyelemű halmazait) tartalmaznia (ha mindegyiket tartalmazza, akkor véges Ω esetében épp a teljes eseményalgebráról van szó). Ld. még atomhalmaz.
Lásd még
[szerkesztés]- Borel-féle halmaztest (σ-algebra)
- Topologikus tér
Jegyzetek
[szerkesztés]- ↑ Néha nevezik "halmazalgebrának" összefoglaló néven a halmazműveletekkel kapcsolatos algebrai, műveleti törvényszerűségeket is, de ezek lényegében a Boole-algebra törvényei.
- ↑ Ezeket általában „nyílt/mérhető halmazok”-nak nevezik.
- ↑ Az olyan analízis-központú művek, mint például Szőkefalvi-Nagy közismert Valós függvények és függvénysorok c. könyve, a halmaztesteket egyszerűen egy univerzumhalmaz bizonyos halmazcsaládjaként definiálják (IV. kiad. Tankönyvkiadó 1972; 21. o.); ily módon a halmaztestek szigorú, definitív értelemben nem matematikai struktúrák, mivel egy struktúra a tartóhalmazból és az algebrai műveletekből álló elemrendszer, a halmazcsaládos definíció viszont csak a tartóhalmazra (magára a halmazcsaládra) van tekintettel, de nem foglalja magába a műveleteket. Más szerzők viszont figyelembe veszik az algebrai szempontokat is, és a "halmaztest"-et mint algebrai struktúrát definiálják, ld. például Jeremy Alm: A Philosophical View of Representations in Boolean and Relation Algebra Archiválva 2006. szeptember 11-i dátummal a Wayback Machine-ben; (pdf; v. 2007. augusztus 2. 13:15). A különbségnek nincs számottevő gyakorlati jelentősége, a definíciók szempontjából viszont a tárgyalást nehezítő eltérést jelent.
- ↑ Megjegyezzük, ezek közt lehetnek algebrai értelemben izomorfak is, az ilyeneket nem tekintettük azonosnak.
- ↑ Ld. a [1] lábjegyzetet.
- ↑ Ez valóban gyengítés: könnyen mutatható olyan topologikus tér, amely metszet-zárt, de nem különbség-zárt, illetve - ami ezzel A\B = A∩B miatt ekvivalens - nem zárt a tartóhalmazra való komplementerképzésre. Legyen például Ω={a,b,c} és ''A'' = {∅, {a}, {a,b}}; ez (metszet-zárt) topologikus tér, de minthogy {b}={a,b}\{a} nem eleme, nem különbség-zárt (azaz nem halmazalgebra)
- ↑ A tétel bizonyítása szinte teljesen ugyanaz, mint a σ-algebrákra vonatkozó analóg tételé (azt és annak bizonyítását ld. itt: Generált σ-algebra/Az "elemi események" által generált algebra), csak az ottani "megszámlálható" kifejezés helyébe itt a "véges" szót kellene írni.
- ↑ Utóbbi megjegyzés bizonyításához elegendő megmutatni, hogy a véges és véges komplementerű részhalmazok tényleg egy halmazalgebrát alkotnak (ez triviálisan nem tartalmazza a prímek halmazát); tehát egy, a prímek halmazát tartalmazó halmazalgebra N felett nem lehet a generált algebra, hiszen akkor a legszűkebb lenne, holott A szűkebb.
Források
[szerkesztés]- Halmazalgebra alapok Archiválva 2016. március 4-i dátummal a Wayback Machine-ben
- Gyakoroló feladatok