„Osztályfelbontás” változatai közötti eltérés

[ellenőrzött változat][ellenőrzött változat]
Tartalom törölve Tartalom hozzáadva
Legobot (vitalap | szerkesztései)
a Bot: 28 interwiki link migrálva a Wikidata d:q381060 adatába
Nincs szerkesztési összefoglaló
4. sor:
 
== 1. definíció ==
Legyen adott egy <math> U </math> [[halmaz]] (a továbbiakban ''univerzum(halmaz)).'' Ennek [[Halmaz#Részhalmaz|részhalmaz]]ainak halmazát <math>\mathcal{P} \left( U \right)</math>-val jelöljük, és az <math>\mathcal{U}</math> halmaz [[hatványhalmaz]]ának nevezzük. A <math>\mathcal{P} \left( U \right)</math> halmaz egy részhalmazát – tehát <math>U</math> néhány részhalmazának halmazát – az <math>U</math> feletti [[halmazcsalád]]nak nevezzük.
<math> \mathcal{P} \left( U \right) </math> -val jelöljük, és az <math> \mathcal{U} </math> halmaz [[Halmaz#Hatványhalmaz|hatványhalmaz]]ának nevezzük. A <math> \mathcal{P} \left( U \right) </math> halmaz egy részhalmazát – tehát <math> U </math> néhány részhalmazának halmazát – az <math> U </math> feletti [[halmazcsalád]]nak nevezzük.
 
Mármost az <math> U </math> egy '''''osztályfelbontás'''''a vagy '''''partíció'''''ja egy olyan <math> U </math> feletti halmazcsalád, azaz <math> U </math> részhalmazainak egy <math> P </math> halmaza, melynek elemei mint (rész)halmazok egyrészt
# nem üresek ( <math> \forall x \in P : x \ne \empty </math> ); másrészt
# páronként diszjunktak (<math> \forall x,y \in P : \left( x \cap y \ne \empty \Rightarrow x=y \right) </math> );
# egyesítésük kiadja az <math> U </math> univerzumhalmazt, azaz <math> \mathcal{U} </math> minden eleme előfordul valamelyik <math> P </math> -beli halmazban, ha elég sokáig keresgélünk <math> P </math> elemeinek elemei között ( <math> \bigcup_{x \in P} x = \bigcup {P} = U </math>, vagyis <math> \forall x \in U : \exist y \in P : x \in y </math> ).
 
== 2. definíció ==
16 ⟶ 15 sor:
Egy kicsit bonyolultabb, de sokkal hasznosabb definíció a halmazcsalád helyett a [[halmazrendszer]] fogalmára épít.
 
Legyen adott két <math> U, I </math> [[halmaz]]. Előbbi halmaz [[Halmaz#Részhalmaz|részhalmaz]]ai halmazát, azaz hatványhalmazát továbbra is <math>\mathcal{P} \left( U \right)</math>-val jelöljük. Valamely <math>f: I \mapsto \mathcal{P} (U) , f(i) := U_{i} \subseteq U</math> függvényt nevezünk lényegében az <math>U</math> halmaz <math>I</math> indexhalmaz feletti (vagy <math>U, I</math> feletti) [[halmazrendszer]]nek. Erre az <math>\left( U_{i} \right) _{i \in I}</math> jelölést alkalmazzuk.
<math> \mathcal{P} \left( U \right) </math> -val jelöljük. Valamely <math> f: I \mapsto \mathcal{P} (U) , f(i) := U_{i} \subseteq U </math> függvényt nevezünk lényegében az <math> U </math> halmaz <math> I </math> indexhalmaz feletti (vagy <math> U, I </math> feletti) [[halmazrendszer]]nek. Erre az <math> \left( U_{i} \right) _{i \in I} </math> jelölést alkalmazzuk.
 
Egy ilyen halmazrendszert <math> U </math> '''''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 ( <math> \forall i \in I : U_{i} \ne \empty </math> );
# páronként diszjunktak (<math> \forall i,j \in I : \left( U_{i} \cap U_{j} \ne \empty \Rightarrow i=j \right) </math> );
# egyesítésük kiadja az <math> U </math> univerzumhalmazt, azaz <math> \mathcal{U} </math> minden eleme előfordul valamelyik <math> U_{i} </math> taghalmazban, ha elég sokáig keresgélünk az indexek között ( <math> \bigcup_{i \in I} U_{i} = U </math>, vagyis <math> \forall x \in U : \exist i \in I : x \in U_{i} </math> ).
 
== Egyszerűbb példák ==
 
* Minden egyelemű halmaznak egyetlen partíciója létezik (tkp. saját maga – pontosabban az <math> \left\{ a \right\} </math> egyetlen partíciója <math> \left\{ \ \left\{ a \right\} \ \right\} </math>.
* 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.
 
== Alkalmazások ==
46 ⟶ 44 sor:
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ály]]ok 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ály''ai 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).
55 ⟶ 53 sor:
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ált'''''jainak mondjuk, más elnevezésben a relációt a partíció '''''mag'''''já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 <math> U </math> halmaz <math> I </math> indexhalmaz feletti <math> \mathfrak{p} = \left( U_{i} \right) _{i \in I} </math> osztályfelbontása, akkor az ehhez asszociált <math> \rho _{ \mathfrak{p} } \subseteq U \times U </math> bináris (kétváltozós) relációt a következőképp definiáljuk: <math> \rho _{ \mathfrak{p} } := \left\{ \left( x,y \right) \in U \times U \ \mathcal{j} \ \exist i \in I : \ x,y \in U_{i} \right\} </math>. E <math> \rho </math> relációt szokás <math> ass \left( \left( U \right) _{i \in I} \right) = ass \left( \mathfrak{p} \right)</math> -vel (ejtsd: „gót p asszociátja”asszociáltja”) vagy <math> U / \left( U \right) _{i \in I} = U / \mathfrak{p} </math> -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 <math> \rho </math> valóban reflexív, szimmetrikus és tranzitív, azaz ekvivalenciareláció.
* ha pedig adott egy <math> U </math> halmaz feletti <math> \rho \subseteq U \times U </math> bináris (kétváltozós) ekvivalenciareláció, akkor definiálhatjuk a következő ekvivalenciaosztályokat: <math> \forall x \in U : \ \bar{x} _{ \rho} := \left\{ y \in U \ \mathcal{j} \ x \rho y \right\} </math>. A különböző ekvivalenciaosztályok egy halmazt ([[halmazcsalád]]ot) alkotnak: <math> \mathfrak{P} := \left\{ z \in \mathcal{P} \left( U \right) \ \mathcal{j} \ \exist x \in U : \ z = \bar{x} _{ \rho } \right\} </math>, amely teljesíti a partíciókra vonatkozó három alapkövetelményt, így az osztályfelbontás [[Osztályfelbontás#1. definíció|egyik definíciója]] értelmében partíciója <math> U </math>-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 <math> U </math>-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).
69 ⟶ 67 sor:
 
[[Kép:PartitionLattice.svg|center|thumb|400px|Az {1,2,3,4} halmaz partícióinak hálódiagramja]]
 
=== 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.
 
például: 3 = 1 + 1 + 1 = 1 + 2
 
Így tehát <math>P\left( 3 \right) = 3</math>.
 
A partíciók száma meglehetősen gyorsan nő, ez azonban leírható aszimptotikusan, amit Ramanujan–Hardy-féle formulának nevezünk:
 
<math>P\left( n \right) = \frac{{1 + O\left( {n^{ - \frac{1}{2}} } \right)}}{{4n\sqrt 3 }}e^{\pi \sqrt {\frac{2}{3}n} }</math>
 
== Források ==
* 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
{{bevstruk}}