Osztályfelbontás

A Wikipédiából, a szabad lexikonból.

Ez a szócikk a matematikai partícióról szól. További jelentéséhez lásd: Partíció.

Egy U halmaz felbontásának
Venn-diagramja

Az osztályfelbontás vagy osztályozás (idegen szóval partíció) halmazelméleti fogalom, mely a matematika minden területén előfordul, és rendkívül hasznos.

[szerkesztés] 1. definíció

Legyen adott egy $U$ halmaz (a továbbiakban univerzum(halmaz)). Ennek részhalmazainak halmazát $\mathcal{P} \left( U \right)$ -val jelöljük, és az $\mathcal{U}$ halmaz hatványhalmazának nevezzük. A $\mathcal{P} \left( U \right)$ halmaz egy részhalmazát – tehát $U$ néhány részhalmazának halmazát – az $U$ feletti halmazcsaládnak nevezzük.

Mármost az $U$ egy osztályfelbontása vagy partíciója egy olyan $U$ feletti halmazcsalád, azaz $U$ részhalmazainak egy $P$ halmaza, melynek elemei mint (rész)halmazok egyrészt

nem üresek ( $\forall x \in P : x \ne \empty$ ); másrészt
páronként diszjunktak ( $\forall x,y \in P : \left( x \cap y \ne \empty \Rightarrow x=y \right)$ );
egyesítésük kiadja az $U$ univerzumhalmazt, azaz $\mathcal{U}$ minden eleme valamelyik előfordul valamelyik $P$ -beli halmazban, ha elég sokáig keresgélünk $P$ elemeinak elemei között ( $\bigcup_{x \in P} x = \bigcup {P} = U$ , vagyis $\forall x \in U : \exist y \in P : x \in y$ ).

[szerkesztés] 2. definíció

Egy kicsit bonyolultabb, de sokkal hasznosabb definíció a halmazcsalád helyett a halmazrendszer fogalmára épít.

Legyen adott két $U, I$ halmaz. Előbbi halmaz részhalmazai halmazát, azaz hatványhalmazát továbbra is $\mathcal{P} \left( U \right)$ -val jelöljük. Valamely $f: I \mapsto \mathcal{P} (U) , f(i) := U_{i} \subseteq U$ függvényt nevezünk lényegében az $U$ halmaz $I$ indexhalmaz feletti (vagy $U, I$ feletti) halmazrendszernek. Erre az $\left( U_{i} \right) _{i \in I}$ jelölést alkalmazzuk.

Egy ilyen halmazrendszert $U$ osztályfelbontásának vagy partíciójának nevezünk, ha (ugyanazok a tulajdonságok, mint fent) teljesülnek, azaz a rendszer tagjai:

nem üresek ( $\forall i \in I : U_{i} \ne \empty$ );
páronként diszjunktak ( $\forall i,j \in I : \left( U_{i} \cap U_{j} \ne \empty \Rightarrow i=j \right)$ );
egyesítésük kiadja az $U$ univerzumhalmazt, azaz $\mathcal{U}$ minden eleme valamelyik előfordul valamelyik $U i$ taghalmazban, ha elég sokáig keresgélünk az indexek között ( $\bigcup_{i \in I} U_{i} = U$ , vagyis $\forall x \in U : \exist i \in I : x \in U_{i}$ ).

[szerkesztés] Egyszerűbb példák

Minden egyelemű halmaznak egyetlen partíciója létezik (tkp. saját maga – pontosabban az $\left\{ a \right\}$ egyetlen partíciója $\left\{ \ \left\{ a \right\} \ \right\}$ .
Az üres halmaznak egyetlen partíciója van, saját maga (minden eleme páronként diszjunkt és nemüres, mivel egy eleme sincs, és elemeinek egyesítése azon x elemek halmaza, melyhez van olyan üres halmazbeli taghalmaz, amelynek x eleme, de ilyen tag nincs, mert az üres halmaznak nincs semmilyen eleme, így olyan se, ami taghalmaz lehetne; így az egyesítésnek nincs x eleme, tehát tényleg üres).
Az emberek halmaza (eltekintve a genetikai, ivari kromoszomális eltéréseket hordozóktól) két csoportra osztható: férfiakra és nőkre. E csoportok egy kételemű halmazt alkotnak, az emberek nem szerinti partícióját, osztályfelbontását, ennek tagjai a genetikailag „férfiak” és „nők” halmazai;
Bármely nem üres U halmaznak tetszőleges valódi részhalmaza és ennek komplementere az U egy osztályfelbontását alkotja;
Az A := { 1, 2, 3 } halmaznak ötféle osztályfelbontása van:
- { {1}, {2}, {3} }, rövidebben jelölve 1/2/3.
- { {1, 2}, {3} }, rövidebben jelölve 12/3.
- { {1, 3}, {2} }, rövidebben jelölve 13/2.
- { {1}, {2, 3} }, rövidebben jelölve 1/23.
- { {1, 2, 3} }, rövidebben jelölve 123.
Jegyezzük meg:
- { {}, {1,3}, {2} } nem partíciója A-nak (sem), mert egy tagja üres;
- { {1,2}, {2, 3} } sem osztályfelbontás, mert a 2 elem több tagban is előfordul, így a tagok nem mind diszjunktak;
- { {1}, {2} } sem jó osztályfelbontás, mert a 3-t egyik tag sem tartalmazza, így ezek uniója nem adja ki A-t, eme kételemű halmaz a B = {1, 2} halmaznak osztályfelbontása.

[szerkesztés] Alkalmazások

[szerkesztés] Elemi matematika

Szemléletesen egy partíciót egyszerűen úgy képzelhetjük el, hogy az univerzumhalmazt „szétszedjük” kisebb, elkülönült halmazokra. E fogalom nagyon fontos: pl. a maradékosztályok adott modulus szerint az egész számok halmazát particionálják (minden egész szám egy és csak egyféle maradékot ad adott egész modulussal osztva). Az elemi matematikában három fontos példa is van osztályfelbontásra:

az egész számok egy adott m nem nulla egész számmal (modulussal) osztva az ún. maradékosztályok halmazaira bomlanak (egy osztályba az azonos maradékot adók tartoznak);
azonkívül az ismétléses permutációk halmaza valójában felfoghatóak a hagyományos permutációk bizonyos ún. ekvivalenciaosztályai halmazának..
az adott egyenessel párhuzamos egyenesek is egy-egy párhuzamossági osztályt alkotnak, egy-egy osztáyt „iránynak” is nevezhetnénk. A projektív geometriában az ideális („végtelen távoli”) pontok misztikus fogalma ily módon precízen definiálható: egy-egy ideális pont legyen egy-egy irány, azaz egyenessereg. A projektív síkot úgy kapjuk, hogy az euklideszi síkhoz hozzáunionáljuk az irányok vagy ideális pontok halmazát (az „ideális egyenest”): máris kész a projektív sík.

Mindhárom partíció speciális tulajdonsága, hogy az (ekvivalencia)osztályok mindkét esetben mind azonos számosságúak (ez nem követelmény egyébként tetszőleges partícióra).

[szerkesztés] Az osztályozás és az ekvivalenciarelációk

A partíciófogalom fontosságát az is mutatja, hogy – amint az már az elemei matematikai példákból is sejthető – szoros kapcsolatban van az ekvivalenciareláció – az egyszerre reflexív, tranzitív és szimetrikus relációk – fogalmával.

Minden partíció meghatároz egy ekvivalenciarelációt, és viszont (a partíciót és a relációt egymás asszociáltjainak mondjuk, más elnevezésben a relációt a partíció magjának, míg a partíciót a reláció faktorának). Két elem akkor álljon relációban, ha a partíció azonos osztályába esnek, fordítva pedig az adott elemmel relációban lévő elemek halmaza, mint a reláció alaphalmazának egy részhalmaza, valójában felfogható, mint az alaphalmaz partíciójának egy tagja, osztálya.

Formálisan:

ha adott egy $U$ halmaz $I$ indexhalmaz feletti $\mathfrak{p} = \left( U_{i} \right) _{i \in I}$ osztályfelbontása, akkor az ehhez asszociált $\rho _{ \mathfrak{p} } \subseteq U \times U$ bináris (kétváltozós) relációt a következőképp definiáljuk: $\rho _{ \mathfrak{p} } := \left\{ \left( x,y \right) \in U \times U \ \mathcal{j} \ \exist i \in I : \ x,y \in U_{i} \right\}$ . E $ρ$ relációt szokás $ass \left( \left( U \right) _{i \in I} \right) = ass \left( \mathfrak{p} \right)$ -vel (ejtsd: „gót p asszociátja”) vagy $U / \left( U \right) _{i \in I} = U / \mathfrak{p}$ -vel (ejtsd: „U faktor(izáltja) gót p(-vel)”) jelölni. A partícióra vonatkozó három követelményből következik, hogy $ρ$ valóban reflexív, szimmetrikus és tranzitív, azaz ekvivalenciareláció.
ha pedig adott egy $U$ halmaz feletti $\rho \subseteq U \times U$ bináris (kétváltozós) ekvivalenciareláció, akkor definiálhatjuk a következő ekvivalenciaosztályokat: $\forall x \in U : \ \bar{x} _{ \rho} := \left\{ y \in U \ \mathcal{j} \ x \rho y \right\}$ . A különböző ekvivalenciaosztályok egy halmazt (halmazcsaládot) alkotnak: $\mathfrak{P} := \left\{ z \in \mathcal{P} \left( U \right) \ \mathcal{j} \ \exist x \in U : \ z = \bar{x} _{ \rho } \right\}$ , amely teljesíti a partíciókra vonatkozó három alapkövetelményt, így az osztályfelbontás egyik definíciója értelmében partíciója $U$ -nak. A kiválasztási axióma biztosítja, hogy létezik egy halmazrendszer, létezik egy megfelelő indexhalmaz, melyekre az ekvivalenciaosztályok rendszere mint halmazrendszer is partíciója $U$ -nak.

Az ekvivalenciarelációk pedig rendkívül fontosak a matematikában (pl. a halmazok számosság szerinti ekvivalenciája, az euklideszi és projektív geometriában a párhuzamosság, algebrai vagy egyéb struktúrák izomorfiája, a moduláris számelmélet kongruenciarelációi, a csoportelmélet mellékosztályok szerinti partíciói, azonos nyelvet elfogadó véges automaták stb. mind-mind egy egy matematikai elmélet alapját jelentik).

[szerkesztés] Rendezés

Egy halmaz összes partíciója hálót alkot, azaz rendezhető (a rendezési reláció a „finomítás”: egy partíció „finomabb”, mint egy másik, ha előbbi minden tagja része az utóbbi valamely tagjának). Ez a tény például a legegyszerűbb integrálfogalmak felépítésében (Riemann-integrál, Darboux-integrál) kap fontos szerepet, természetesen a halmazelméleten kívül.

Az {1,2,3,4} halmaz partícióinak hálódiagramja

[szerkesztés] Számelméleti partíció

Egy pozitív egész szám partícióinak a számán azt a számot értjük, amely megadja, hogy az adott szám hány különböző módon írható fel pozitív egészek összegeként, itt az egytagú összeg is megengedett, a tagok sorrendje nem számít.

pl.: 3 = 1 + 1 + 1 = 1 + 2

Így tehát $P\left( 3 \right) = 3$ .

A partíciók száma meglehetősen gyorsan nő, ez azonban leírható aszimptotikusan, amit Ramanujan - Hardy féle formulának nevezünk:

$P\left( n \right) = \frac{{1 + O\left( {n^{ - \frac{1}{2}} } \right)}}{{4n\sqrt 3 }}e^{\pi \sqrt {\frac{2}{3}n} }$

[szerkesztés] Források

Hajnal András–Hamburger Péter: Halmazelmélet. Nemzeti Tankönyvkiadó, Bp., 1983. ISBN 963-18-5998-3 .
Maurer Gyula–Virág Imre: Bevezetés a struktúrák elméletébe. Dacia könyvkiadó, Kolozsvár/Cluj-Napoca, 1976.