Halmazrendszer

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

1. 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;
2. 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.
3. A kombinatorikában használják a hipergráf szó helyett.

Definíció

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

Ekkor valamely

$${\displaystyle f:I\to P(U)}$$

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

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

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

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 ${\displaystyle a,b\in I}$ és ${\displaystyle a\neq b}$, akkor ${\displaystyle (a,A)}$és ${\displaystyle (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${\displaystyle \{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 ${\displaystyle f:I\to U}$ indexelő függvény injektivitását).

A halmazrendszerek jelentősége

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

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

• Unió / Egyesítés: ${\displaystyle \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: ${\displaystyle \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 (${\displaystyle \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

Legyen ${\displaystyle A:=(A_{i})_{i\in I}}$ és ${\displaystyle B:=(B_{j})_{j\in J}}$ két, az ${\displaystyle I}$ ill. ${\displaystyle J}$ indexhalmazok feletti halmazrendszer. Ekkor őket izomorfnak nevezzük, ha van az ${\displaystyle \cup \!(A)}$ és a ${\displaystyle \cup \!(B)}$ halmazok közt olyan ${\displaystyle \varphi :\cup \!(A)\to \cup \!(B)}$ bijekció, melyre igaz, hogy tetszőleges ${\displaystyle a,\alpha \in \cup \!(A)}$-ra és ${\displaystyle i\in I}$-re akkor és csak akkor igaz ${\displaystyle a,\alpha \in A_{i}}$, ha ${\displaystyle \varphi (a),\varphi (\alpha )\in \cup \!(B)}$-hez is található olyan ${\displaystyle j\in J}$ index, hogy ${\displaystyle \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 ${\displaystyle A:=(A_{i})_{i\in I}}$ és ${\displaystyle B:=(B_{j})_{j\in J}}$ két, az ${\displaystyle I}$ ill. ${\displaystyle J}$ indexhalmazok feletti halmazrendszert izomorfnak nevezzük, ha van olyan ${\displaystyle \varphi :\cup \!(A)\to \cup \!(B)}$ bijektív leképezés, hogy minden ${\displaystyle i\in I}$-re ${\displaystyle \varphi [A_{i}]:=\{b\in B\mid \exists a\in A_{i}:\varphi (a)=b\}=B_{j}}$ legyen; és hasonló teljesül tetszőleges ${\displaystyle j\in J}$ esetén is. Röviden szólva, ha van olyan bijekció a rendszerek unióhalmazai közt, hogy az ${\displaystyle A}$ rendszer tetszőleges indexelt taghalmazának e függvény szerinti „képe” (relációmetszete) a ${\displaystyle B}$ rendszer egy taghalmaza legyen, és viszont: a ${\displaystyle B}$ rendszer egy taghalmazának e függvény szerinti képe az ${\displaystyle A}$ egy taghalmaza legyen.

További információk

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

Jegyzetek

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.

Források

• 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

• Halmazrendszerek kombinatorikus tulajdonságainak listája