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

Ekkor valamely

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

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

( U i ) i ∈ I {\displaystyle (U_{i})_{i\in I}}

Az f ( i ) ∈ P ( U ) {\displaystyle f(i)\in P(U)} halmazt a rendszer i {\displaystyle i} indexhez tartozó taghalmazának (röviden i-edik tagnak vagy i-edik taghalmaznak) mondjuk, és leggyakrabban az U i {\displaystyle U_{i}} jobb alsó indexes alakban írjuk. Tehát minden i ∈ I {\displaystyle i\in I} -re U i ⊆ U {\displaystyle U_{i}\subseteq U} . Helytelen egy kissé, de általában nem okoz félreértést az R := ( U i ) i ∈ I {\displaystyle R:=(U_{i})_{i\in I}} rendszer egy U i {\displaystyle U_{i}} tagja esetén az U i ∈ ( U i ) i ∈ I {\displaystyle U_{i}\in (U_{i})_{i\in I}} , azaz az U i ∈ R {\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 a , b ∈ I {\displaystyle a,b\in I} és a ≠ b {\displaystyle a\neq b} , akkor ( a , A ) {\displaystyle (a,A)} és ( b , A ) {\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 { A i } i ∈ I {\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 f : I → U {\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: ⋃ ( R ) = ⋃ i ∈ I U i = { x ∈ U   j   ∃ i ∈ I : x ∈ U i } {\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: ⋂ ( R ) = ⋂ i ∈ I U i = { x ∈ U   j   ∀ i ∈ I : x ∈ U i } {\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 A := ( A i ) i ∈ I {\displaystyle A:=(A_{i})_{i\in I}} és B := ( B j ) j ∈ J {\displaystyle B:=(B_{j})_{j\in J}} két, az I {\displaystyle I} ill. J {\displaystyle J} indexhalmazok feletti halmazrendszer. Ekkor őket izomorfnak nevezzük, ha van az ∪ ( A ) {\displaystyle \cup \!(A)} és a ∪ ( B ) {\displaystyle \cup \!(B)} halmazok közt olyan φ : ∪ ( A ) → ∪ ( B ) {\displaystyle \varphi :\cup \!(A)\to \cup \!(B)} bijekció, melyre igaz, hogy tetszőleges a , α ∈ ∪ ( A ) {\displaystyle a,\alpha \in \cup \!(A)} -ra és i ∈ I {\displaystyle i\in I} -re akkor és csak akkor igaz a , α ∈ A i {\displaystyle a,\alpha \in A_{i}} , ha φ ( a ) , φ ( α ) ∈ ∪ ( B ) {\displaystyle \varphi (a),\varphi (\alpha )\in \cup \!(B)} -hez is található olyan j ∈ J {\displaystyle j\in J} index, hogy φ ( a ) , φ ( α ) ∈ B j {\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 A := ( A i ) i ∈ I {\displaystyle A:=(A_{i})_{i\in I}} és B := ( B j ) j ∈ J {\displaystyle B:=(B_{j})_{j\in J}} két, az I {\displaystyle I} ill. J {\displaystyle J} indexhalmazok feletti halmazrendszert izomorfnak nevezzük, ha van olyan φ : ∪ ( A ) → ∪ ( B ) {\displaystyle \varphi :\cup \!(A)\to \cup \!(B)} bijektív leképezés, hogy minden i ∈ I {\displaystyle i\in I} -re φ [ A i ] := { b ∈ B ∣ ∃ a ∈ A i : φ ( a ) = b } = B j {\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 j ∈ J {\displaystyle j\in J} esetén is. Röviden szólva, ha van olyan bijekció a rendszerek unióhalmazai közt, hogy az A {\displaystyle A} rendszer tetszőleges indexelt taghalmazának e függvény szerinti „képe” (relációmetszete) a B {\displaystyle B} rendszer egy taghalmaza legyen, és viszont: a B {\displaystyle B} rendszer egy taghalmazának e függvény szerinti képe az A {\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