bélyegkép|jobbra|Részbenrendezett halmaz Hasse-diagramja A matematikában részbenrendezett halmaznak (vagy más néven parciálisan rendezett halmaznak (angolul partially ordered set vagy poset) nevezünk egy halmazt, ha definiálva van a halmaz elemein egy részbenrendezés (vagy más néven parciális rendezés), azaz egy reflexív, antiszimmetrikus, tranzitív kétváltozós reláció. Részbenrendezett halmazok esetében tehát nem követeljük meg, hogy az alaphalmaz bármely két eleme összehasonlítható legyen, mint a rendezett halmazoknál.
Részbenrendezett halmaz rendezett részhalmazának neve lánc, az olyan részhalmazé pedig, amelyben semelyik két elem sem hasonlítható össze, antilánc.
Részbenrendezett halmazok ábrázolására általában Hasse-diagramot használunk.
Definíció Az párt részbenrendezett halmaznak nevezzük, ha nemüres halmaz, pedig -n értelmezett részbenrendezés, azaz tetszőleges elemekre teljesülnek a következők: reflexív: , antiszimmetrikus: ha és , akkor , tranzitív: ha és , akkor .
Gyenge és erős részbenrendezés Bizonyos kontextusokban a fent definiált reflexív, antiszimmetrikus, tranzitív részbenrendezést („≤”) gyenge részbenrendezésnek nevezik, és definiálják a szigorú részbenrendezést („<”), ami antiszimmetrikus, tranzitív, de irreflexív.
Kiterjesztés, kompatibilitás, atommentesség, elágazó részbenrendezett halmazok
Legyen tetszőleges részbenrendezett halmaz és . Azt mondjuk, hogy b kiterjesztése a-nak, ha , illetve valódi kiterjesztésről beszélünk, ha és
Legyen tetszőleges részbenrendezett halmaz és . Akkor mondjuk, hogy az és elemek kompatibilisek, ha van közös kiterjesztésük, azaz van olyan elem, amelyre és is teljesül. Ellenkező esetben inkompatibilis elemekről beszélünk.
Legyen tetszőleges részbenrendezett halmaz és . Az elemet atomnak nevezzük, ha az elemnek nincs valódi kiterjesztése. Az részbenrendezett halmazt atommentesnek nevezzük, ha nincs benne atom.
Az részbenrendezett halmazt elágazó részbenrendezett halmaznak nevezzük, ha tetszőleges elemekhez létezik olyan elem, hogy kompatibilis -val és inkompatibilis -vel.
Tulajdonságok Legyen tetszőleges atommentes, elágazó részbenrendezett halmaz. Ekkor tetszőleges elemhez létezik elem úgy, hogy és egyaránt kiterjesztése -nak, azonban és egymással inkompatibilis.Lásd: Csirmaz László: Forszolás (jegyzet)
Szélessége és magassága Egy részbenrendezett halmaz magassága megegyezik a maximális lánc számosságával. A Dilworth-tétel duálisa kimondja, hogy bármely véges magasságú részbenrendezett halmaznál a magasság megegyezik azzal a számmal, ahány antiláncra lehet bontani a részbenrendezett halmazt minimálisan.
Maximális antilánc alatt olyan antiláncot értünk, ami nem valódi részhalmaza egyetlen más antiláncnak sem. A maximális antilánc számossága nagyobb vagy egyenlő bármely más antilánc számosságánál. A részbenrendezett halmaz szélessége megegyezik maximális antiláncának számosságával. Mivel bármely antilánc legfeljebb egyetlen közös elemet tartalmaz egy lánccal, ha a halmazt fel tudjuk osztani k láncra, akkor a részbenrendezett halmaz szélességének legfeljebb k-nak kell lennie. Dilworth tétele kimondja, hogy ezt a határt minden esetben el is lehet érni: mindig létezik olyan antilánc, és a halmaz elemeinek olyan láncokra bontása, hogy a láncok száma megegyezik az antilánc elemeinek számával, ami szintén megegyezik a részbenrendezett halmaz szélességével.
Példák A természetes számok halmazán értelmezett oszthatóság reláció részbenrendezés. Definíció szerint minden rendezett halmaz részbenrendezett.
Kapcsolódó szócikkek Kuratowski–Zorn-lemma Hausdorff–Birkhoff-tétel Háló Forszolás
Jegyzetek
Irodalom Csirmaz László: Forszolás (jegyzet) Rédei László: Algebra I. (Akadémiai, 1954) Szász Gábor: Bevezetés a hálóelméletbe, (Akadémiai, 1959) Szendrei Ágnes: Diszkrét matematika (Polygon–JATE Bolyai Intézet, Szeged, 1994) Czédli Gábor: Hálóelmélet (JATEPress, Szeged, 1999)
További információk Alice és Bob - 12. rész: Alice és Bob rendet tesz Alice és Bob - 15. rész: Alice és Bob az absztrakció útján Alice és Bob - 19. rész: Alice és Bob ideáljai Partially Ordered Set a MathWorld oldalán Forszolás (jegyzet) Csirmaz László oldalán
Kategória:Hálóelmélet Kategória:Relációkalkulus