Halmazalgebra

E szócikk egy matematikai struktúrafajtáról szól. A halmazokkal kapcsolatos műveleti törvényszerűségeket a halmazelmélet c. szócikk tárgyalja.

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), amely nem üres, és zárt az elemei véges családjainak uniójára, metszetére és különbségére.

Definíciók

Legyen Ω tetszőleges halmaz, ${\mathcal {P}}(\Omega )$ ennek részhalmazainak halmaza, vagyis hatványhalmaza, és legyen ${\mathcal {A}}\subseteq {\mathcal {P}}(\Omega )$ az Ω egy részhalmazai halmaza (egy Ω feletti halmazcsalád).

Az ${\mathcal {A}}$ halmazt (szükség esetén az $(\Omega ,{\mathcal {A}})$ rendezett párt is) az Ω halmaz feletti halmazalgebrának nevezzük, ha teljesülnek a következő tulajdonságok:

1.	${\mathcal {A}}$ nem üres,	azaz	${\mathcal {A}}\neq \varnothing$
2.	${\mathcal {A}}$ tartalmazza bármely eleme (Ω-ra vonatkozó) komplementerét, vagyis zárt a komplementerképzés műveletére;	azaz	$A\in {\mathcal {A}}\Rightarrow {\bar {A}}\in {\mathcal {A}}$
3.	${\mathcal {A}}$ tartalmazza bármely két eleme unióját, vagyis zárt az egyesítés műveletére,	azaz	$A,B\in {\mathcal {A}}\Rightarrow A\cup B\in {\mathcal {A}}$

A fogalom analogonja megfogalmazható az Ω feletti halmazrendszerek esetére is.

Zérus- és univerzum-zártság

Az 1. axióma helyettesíthető akár az "${\mathcal {A}}$ 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

$\varnothing \in {\mathcal {A}}$

vagy akár az

$\Omega \in {\mathcal {A}}$

axiómákkal; hiszen ha ${\mathcal {A}}$ 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

A 2. axióma helyettesíthető az "${\mathcal {A}}$ zárt a különbségképzésre" $(A,B\in {\mathcal {A}}\Rightarrow A\setminus B\in {\mathcal {A}})$ axiómával is, hiszen tetszőleges A,B⊆Ω halmazokra definíció szerint

$A-B=A\cap {\overline {B}}$,

ugyanakkor a De Morgan-azonosságokat, a kettős komplementerképzés (= helybenhagyás) és a disztributivitás törvényeit alkalmazva

${\overline {B\cup {\overline {A\cup B}}}}$ $=$ ${\overline {B}}\cap {\overline {\overline {A\cup B}}}$ $=$ ${\overline {B}}\cap (A\cup B)$ $=$ $\left({\overline {B}}\cap A\right)\cup \left({\overline {B}}\cap B\right)$ $=$ $\left({\overline {B}}\cap A\right)\cup \emptyset$ $=$ ${\overline {B}}\cap A$ $=$ $A\cap {\overline {B}}$ $=$

$A-B$,

ugyanakkor látható, hogy ha ${\mathcal {A}}$ zárt az unió- és komplementerképzésre, akkor zárt az előzőek szerint a különbségképzéssel azonos ${\overline {B\cup {\overline {A\cup B}}}}$ 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

Metszetképzésre való zártság

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

$A\cap B={\overline {{\overline {A}}\cup {\overline {B}}}}$,

.

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ó

Egyszerű, de fontos tulajdonság a következő: egy Ω feletti ${\mathcal {A}}$ halmazalgebrának (mint halmazcsaládnak) uniója maga Ω:

$\bigcup _{A\in {\mathcal {A}}}{\mathcal {A}}=\Omega$

Ennek az az egyszerű oka, hogy $\Omega \in {\mathcal {A}}$, í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

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

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 2^k elemszámú halmazalgebra Ω felett, mégpedig pontosan annyi, ahány k elemű partíciója van az Ω halmaznak, $\left\{{\begin{matrix}n\\k\end{matrix}}\right\}={\frac {1}{k!}}\sum _{j=1}^{k}(-1)^{k-j}{k \choose j}j^{n}$ (másodfajú Stirling-számok). Mindennek bizonyítása az atom fogalmára hivatkozva történhet.

Összefüggés más struktúratípusokkal

Kapcsolat a halmazgyűrűkkel

Ha az 1. axiómát elhagyjuk, és a 3. axióma helyett a nála jóval gyengébb metszet-zártság követelményét állítjuk fel, akkor a halmazgyűrű fogalmát kapjuk.

Kapcsolat a topologikus terekkel

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.

Kapcsolat a Boole-algebrákkal

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

1. 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.
2. 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.
3. Tetszőleges Ω halmaz felett az egyelemű halmazokat tartalmazó $\Omega _{\mathbf {1} }:=\{\{\omega \}|\omega \in \Omega \}=:\{R\in P(\Omega )||R|=\mathbf {1} \}$ halmazrendszer által generált Ή(Ω₁) halmazalgebra pontosan az Ω azon részhalmazait fogja tartalmazni, melyek vagy végesek, vagy komplementerük véges. 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 Ή(N₁) 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
4. Az $\Omega :=\{1,2,3,4,5,6\}$ feletti egy halmazalgebra a $\{\emptyset ,\{1,3,5\},\{2,4,6\},\Omega \}$ 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

• Σ-algebra (Borel-féle halmaztest)
• Topologikus tér

Források

• Halmazalgebra alapok Archiválva 2016. március 4-i dátummal a Wayback Machine-ben
• Gyakoroló feladatok