Halmazrendszer

Halmazrendszeren a matematikában többféle, de sok tekintetben hasonló dolgot érthetünk:

A naiv halmazelméletben szokás halmazrendszer vagy halmazcsalád néven beszélni olyan halmazokról, melyeknek elemei mind halmazok; erre a kétértelműség fellépte miatt alkalmazzuk inkább szigorúan a halmazcsalád elnevezést;
Szűkebb értelemben vett halmazrendszeren (a szakirodalomban gyakran indexezett vagy indexelt halmazrendszer néven fordul elő) olyan „rendezett multihalmazt” érthetünk („rendezett” = az elemek sorrendje is számít;^[1] „multihalmaz” = az elemek ismétlődhetnek, többször is előfordulhatnak), melynek elemei is halmazok. Rövidebben, halmazrendszeren egyszerűen egy olyan elemrendszert (tkp. „vektort”) érthetünk, melynek elemei is halmazok.
A kombinatorikában használják a hipergráf szó helyett.

Definíció szerkesztés

Legyen $I$ tetszőleges halmaz, az ún. indexhalmaz (ez gyakran a pozitív egészek $\mathbb {N} ^{+}$ halmaza). Legyen továbbá $U$ másik tetszőleges halmaz, és jelölje részhalmazai halmazát, azaz hatványhalmazát $P(U)$ .

Ekkor valamely

f:I\to P(U)

függvényt az $U$ halmaz $I$ indexhalmaz feletti halmazrendszerének nevezzük, és így jelöljük:

(U_{i})_{i\in I}

Az $f(i)\in P(U)$ halmazt a rendszer $i$ indexhez tartozó taghalmazának (röviden i-edik tagnak vagy i-edik taghalmaznak) mondjuk, és leggyakrabban az $U_{i}$ jobb alsó indexes alakban írjuk. Tehát minden $i\in I$ -re $U_{i}\subseteq U$ . Helytelen egy kissé, de általában nem okoz félreértést az $R:=(U_{i})_{i\in I}$ rendszer egy $U_{i}$ tagja esetén az $U_{i}\in (U_{i})_{i\in I}$ , azaz az $U_{i}\in R$ jelölés használata.

A halmazrendszerek azonosíthatóak a hipergráfokkal (minden halmazrendszernek megfelel egy és csak egy hipergráf, és viszont).

Megjegyzések a definíciókról: összefüggések és eltérések szerkesztés

A halmazrendszer fogalma a halmazelmélet fogalmaira úgy alapítható precízen, ha függvényként (elemrendszerként) értelmezzük. E modellben az elemeknek – tag(halmaz)oknak – indexekből és taghalmazokból álló rendezett párok felelnek meg, ezért a taghalmazok „sorrendjére” nézve megkülönböztető erővel bír utóbbiaknak a különböző indexekkel való párosítása még akkor is, ha az indexhalmazon semmiféle rendezés, belső reláció nincs értelmezve. Ugyanezen ok, az eltérő indexek miatt ugyanazon taghalmaz „többször is előfordulhat”, nevezetesen ha $a,b\in I$ és $a\neq b$ , akkor $(a,A)$ és $(b,A)$ különböző, noha „ugyanazt a taghalmazt reprezentálja”.

A halmazcsalád és (indexelt) halmazrendszer fogalma tehát különbözik: a halmazcsalád „rendezetlen” halmazok egy halmaza, míg a halmazrendszer bonyolultabb struktúra: „rendezett” halmazok (konkrétan elem-halmaz-párosok) egy halmaza. A szakirodalomban e két terminus jelentése még ingadozó, sok szerző nemcsak egymástól eltérően használja a „halmazrendszer” kifejezést, de néhányan tudatában is vannak az eltéréseknek; ti. a szakkifejezések rögzítetlenségére kifejezetten fel is hívják a figyelmet.^[2]

Bár a szakirodalomban a „rendezett” halmazrendszerekre az „indexelt halmazrendszer” kifejezést is szokás alkalmazni – kifejezetten a halmazcsaládok megkülönböztetése miatt –, az elnevezés némileg félreérthető, ugyanis halmazcsaládot is lehet indexes alakba írni (ilyenkor a kerek zárójel helyett kapcsosat írunk: h $\{A_{i}\}_{i\in I}$ ). Az indexelt halmazcsaládok eo ipso halmazrendszerek (a definíció miatt), a kapcsos zárójel használata csak azt hangsúlyozza, hogy külön kikötjük a tagok ismételhetetlenségét (azaz az $f:I\to U$ indexelő függvény injektivitását).

A halmazrendszerek jelentősége szerkesztés

A halmazrendszerek igen hasznosak – persze az olyan halmazelméleti alkalmazásokon túl, mint a kiválasztási axióma formalizálása – a matematikai analízisben, mert már a valós számok halmazának bizonyos gyakori felépítési módjaihoz is sokszor van szükség végtelen sok halmazzal végzett műveletekre (unió, metszet). Az ilyesfajta alkalmazásokon kívül elsősorban a kombinatorika foglalkozik a halmazrendszerekkel, utóbbi esetben persze leginkább véges indexhalmazú és véges taghalmazokkal rendelkező rendszerek jönnek szóba.

Halmazműveletek szerkesztés

A halmazrendszerekkel különféle műveletek végezhetőek, például

Unió / Egyesítés: $\bigcup \left({\mathcal {R}}\right)=\bigcup _{i\in I}U_{i}=\left\{x\in {\mathcal {U}}\ {\mathcal {j}}\ \exists i\in I:x\in U_{i}\right\}$
Metszet: $\bigcap \left({\mathcal {R}}\right)=\bigcap _{i\in I}U_{i}=\left\{x\in {\mathcal {U}}\ {\mathcal {j}}\ \forall i\in I:x\in U_{i}\right\}$ .
Diszjunkt unió vagy szimmetrikus differencia: az unió definíciójában az egzisztenciális kvantort unicit egzisztenciális kvantorra ( $\exists !$ = „létezik pontosan egy … ”) kell cserélni;

Számos fogalom sokkal kényelmesebben és ugyanakkor precízebben leírható a második felfogásban definiált halmazrendszerek segítségével, mint pusztán halmazcsaládokra hagyatkozva.

Izomorfia szerkesztés

Legyen $A:=(A_{i})_{i\in I}$ és $B:=(B_{j})_{j\in J}$ két, az $I$ ill. $J$ indexhalmazok feletti halmazrendszer. Ekkor őket izomorfnak nevezzük, ha van az $\cup \!(A)$ és a $\cup \!(B)$ halmazok közt olyan $\varphi :\cup \!(A)\to \cup \!(B)$ bijekció, melyre igaz, hogy tetszőleges $a,\alpha \in \cup \!(A)$ -ra és $i\in I$ -re akkor és csak akkor igaz $a,\alpha \in A_{i}$ , ha $\varphi (a),\varphi (\alpha )\in \cup \!(B)$ -hez is található olyan $j\in J$ index, hogy $\varphi (a),\varphi (\alpha )\in B_{j}$ . Tehát ha van olyan bijekció, hogy az egy taghalmazba tartozó elemek képei is egy taghalmazba tartozzanak.

Másképp szólva (de ugyanazt mondva), az $A:=(A_{i})_{i\in I}$ és $B:=(B_{j})_{j\in J}$ két, az $I$ ill. $J$ indexhalmazok feletti halmazrendszert izomorfnak nevezzük, ha van olyan $\varphi :\cup \!(A)\to \cup \!(B)$ bijektív leképezés, hogy minden $i\in I$ -re $\varphi [A_{i}]:=\{b\in B\mid \exists a\in A_{i}:\varphi (a)=b\}=B_{j}$ legyen; és hasonló teljesül tetszőleges $j\in J$ esetén is. Röviden szólva, ha van olyan bijekció a rendszerek unióhalmazai közt, hogy az $A$ rendszer tetszőleges indexelt taghalmazának e függvény szerinti „képe” (relációmetszete) a $B$ rendszer egy taghalmaza legyen, és viszont: a $B$ rendszer egy taghalmazának e függvény szerinti képe az $A$ egy taghalmaza legyen.

További információk szerkesztés

Alice és Bob - 19. rész: Alice és Bob ideáljai

Jegyzetek szerkesztés

↑ A „rendezett” kifejezést itt tehát a naiv halmazelméletben alkalmazott módon használtuk, vö. „rendezett pár”, és nem a gyakoribb, analitikus jellegű értelemben: „rendezési relációval ellátott”.
↑ Hajnal 2. o.

Források szerkesztés

Maurer I. Gyula – Virág Imre: Bevezetés a struktúrák elméletébe. Kolozsvár-Napoca: Dacia. 1976.
↑ Hajnal: Hajnal Péter: Halmazrendszerek. Szeged: Polygon. 2002. = Polygon Jegyzettár, ISSN 1417-0590,

Kapcsolódó szócikkek szerkesztés

Halmazrendszerek kombinatorikus tulajdonságainak listája

[1] A „rendezett” kifejezést itt tehát a naiv halmazelméletben alkalmazott módon használtuk, vö. „rendezett pár”, és nem a gyakoribb, analitikus jellegű értelemben: „rendezési relációval ellátott”.

[2] Hajnal 2. o.

[1]

[2]