Halmazrendszer

A Wikipédiából, a szabad enciklopédiából

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, de e szokás szerencsére eltűnőben van, mert a sokkal megfelelõbb „hipergráf” terminus kiszorítja.

Definíció[szerkesztés | forrásszöveg szerkesztése]

Legyen I tetszőleges halmaz, az ún. indexhalmaz (ez gyakran a pozitív egészek 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 → P(U)

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

(Ui)i∈I.

Az f(i)∈P(U) halmazt a rendszer i indexhez tartozó taghalmazának (röviden i-edik tagnak vagy i-edik taghalmaznak) mondjuk, és leggyakrabban az Ui bal alsó indexes alakban írjuk. Tehát minden i∈I-re UiU. Helytelen egy kissé, de általában nem okoz félreértést az R := (Ui)i∈I rendszer egy Ui tagja esetén az Ui∈(Ui)i∈I, azaz az UiR 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 | forrásszöveg szerkesztése]

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 is a≠b, akkor az (a,A), (b,A) pár 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: {Ai}i∈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 indexelő függvény injektivitását).

A halmazrendszerek jelentősége[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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} \ \exist 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 ( \exist ! = „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 | forrásszöveg szerkesztése]

Legyen A := (Ai)i∈I és B := (Bj)j∈J két, az I ill. J indexhalmazok feletti halmazrendszer. Ekkor őket izomorfnak nevezzük, ha van az ∪(A) és a ∪(B) halmazok közt olyan φ:∪(A)→∪(B) bijekció, melyre igaz, hogy tetszőleges a,α∈∪(A)-ra és i∈I-re akkor és csak akkor igaz a,α∈Ai, ha φ(a),φ(α)∈∪(B)-hez is található olyan j∈J index, hogy φ(a),φ(α)∈Bj. 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 := (Ai)i∈I és B := (Bj)j∈J két, az I ill. J indexhalmazok feletti halmazrendszert izomorfnak nevezzük, ha van olyan φ:∪(A)→∪(B) bijektív leképezés, hogy minden i∈I-re φ[Ai] := {b∈B | ∃a∈Ai : φ(a)=b} = Bj legyen; és hasonló teljesül tetszőleges j∈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.

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  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 Péter: Halmazrendszerek. Polygon jegyzettár, Polygon kiadó, Szeged, 2002.; 2. old. ISSN 1417-0590.

Szakirodalom[szerkesztés | forrásszöveg szerkesztése]

  • Maurer I. Gyula - Virág Imre: Bevezetés a struktúrák elméletébe. Dacia Kiadó, Kolozsvár-Napoca, 1976.
  • Hajnal Péter: Halmazrendszerek. Polygon jegyzettár, Polygon kiadó, Szeged, 2002.; ISSN 1417-0590.