Főmenü megnyitása
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 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.

Tartalomjegyzék

DefinícióSzerkesztés

Az   párt részbenrendezett halmaznak nevezzük, ha   tetszőleges halmaz,   pedig  -n értelmezett részbenrendezés, azaz tetszőleges   elemekre teljesülnek a következők:

  •  
  • ha   és  , akkor  
  • ha   és  , akkor  

Gyenge és erős részbenrendezésSzerkeszté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 halmazokSzerkesztés

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ágokSzerkesztés

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.[1]

Szélessége és magasságaSzerkesztés

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ákSzerkesztés

Lásd mégSzerkesztés

JegyzetekSzerkesztés

  1. Lásd: Csirmaz László: Forszolás (jegyzet)

HivatkozásokSzerkesztés

  • Csirmaz László: Forszolás (jegyzet)
  • Rédei László: Algebra I., Akadémiai Kiadó, Budapest (1954)
  • Szász Gábor: Bevezetés a hálóelméletbe, Akadémiai Kiadó, Budapest (1959)
  • Szendrei Ágnes, Diszkrét matematika, Polygon, JATE Bolyai Intézet, Szeged (1994)

További információkSzerkesztés