Osztályfelbontás

(Osztályozás (matematika) szócikkből átirányítva)
Ez a közzétett változat, ellenőrizve: 2023. november 13.

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.

Egy U halmaz felbontásának Venn-diagramja

1. definíció

szerkesztés

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

  1. nem üresek ( ); másrészt
  2. páronként diszjunktak ( );
  3. egyesítésük kiadja az   univerzumhalmazt, azaz   minden eleme előfordul valamelyik  -beli halmazban:  , vagyis  .

2. definíció

szerkesztés

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:

  1. nem üresek ( );
  2. páronként diszjunktak ( );
  3. 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

szerkesztés
  • 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

szerkesztés

Elemi matematika

szerkesztés

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

szerkesztés

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).

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

További információk

szerkesztés
  • Hajnal András – Hamburger Péter: Halmazelmélet, Nemzeti Tankönyvkiadó, Bp., 1983. ISBN 963-18-5998-3.
  • Szendrei Ágnes, Diszkrét matematika, Polygon, JATE Bolyai Intézet, Szeged, 1996
  • Maurer Gyula, Virág Imre. Bevezetés a struktúrák elméletébe. Kolozsvár: Dacia könyvkiadó (1976)