„Részbenrendezett halmaz” 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
Syp (vitalap | szerkesztései) |
Syp (vitalap | szerkesztései) |
||
27. sor:
== Tulajdonságok ==
Legyen <math>(A; \leq)</math> tetszőleges atommentes, elágazó részbenrendezett halmaz. Ekkor tetszőleges <math>a \in A</math> elemhez létezik <math>b, c \in A</math> elem úgy, hogy <math>b</math> és <math>c</math> egyaránt kiterjesztése <math>a</math>-nak, azonban <math>b</math> és <math>c</math> egymással inkompatibilis.<ref>Lásd: Csirmaz László: Forszolás (jegyzet)</ref>
== 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észhalmaz]]a 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étel|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 ==
| |||