Osztályfelbontás

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.

1. definíció 
Legyen adott egy  halmaz (a továbbiakban univerzum(halmaz)). Ennek részhalmazainak halmazát -val jelöljük, és az  halmaz hatványhalmazának nevezzük. A  halmaz egy részhalmazát – tehát  néhány részhalmazának halmazát – az  feletti halmazcsaládnak nevezzük.

Mármost az  egy osztályfelbontása vagy partíciója egy olyan  feletti halmazcsalád, azaz  részhalmazainak egy  halmaza, melynek elemei mint (rész)halmazok egyrészt
 nem üresek (); másrészt
 páronként diszjunktak ();
 egyesítésük kiadja az  univerzumhalmazt, azaz  minden eleme előfordul valamelyik -beli halmazban: , vagyis .

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  halmaz. Előbbi halmaz részhalmazai halmazát, azaz hatványhalmazát továbbra is -val jelöljük. Valamely  függvényt nevezünk lényegében az  halmaz  indexhalmaz feletti (vagy  feletti) halmazrendszernek. Erre az  jelölést alkalmazzuk.

Egy ilyen halmazrendszert  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 ();
 páronként diszjunktak ();
 egyesítésük kiadja az  univerzumhalmazt, azaz  minden eleme előfordul valamelyik  taghalmazban, ha elég sokáig keresgélünk az indexek között (, vagyis ).

Egyszerűbb példák 

 Minden egyelemű halmaznak egyetlen partíciója létezik (tkp. saját maga – pontosabban az  egyetlen partíciója .
 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}} nem 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ása A-nak, 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.

Alkalmazások

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: például 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ályt „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).

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 elemi matematikai példákból is sejthető – szoros kapcsolatban van az ekvivalenciareláció – az egyszerre reflexív, tranzitív és szimmetrikus 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  halmaz  indexhalmaz feletti  osztályfelbontása, akkor az ehhez asszociált  bináris (kétváltozós) relációt a következőképp definiáljuk: . E  relációt szokás -vel (ejtsd: „gót p asszociáltja”) vagy -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  halmaz feletti  bináris (kétváltozós) ekvivalenciareláció, akkor definiálhatjuk a következő ekvivalenciaosztályokat: . A különböző ekvivalenciaosztályok egy halmazt (halmazcsaládot) alkotnak: , 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 -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 -nak.

Az ekvivalenciarelációk pedig rendkívül fontosak a matematikában (például 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).

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.

További információk 
 Alice és Bob - 13. rész: Alice és Bob eladósodik

Források 
 Hajnal András – Hamburger Péter: Halmazelmélet, Nemzeti Tankönyvkiadó, Bp., 1983. .
 Szendrei Ágnes, Diszkrét matematika, Polygon, JATE Bolyai Intézet, Szeged, 1996

Halmazelmélet