Részbenrendezett halmaz

Részbenrendezett halmaz Hasse-diagramja

A matematikában részbenrendezett halmaznak (vagy más néven parciálisan rendezett halmaznak) 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.

Definíció

Az $(A;\leq )$ párt részbenrendezett halmaznak nevezzük, ha $A$ tetszőleges halmaz, $\leq$ pedig $A$-n értelmezett részbenrendezés, azaz tetszőleges $a,b,c\in A$ elemekre teljesülnek a következők:

• $a\leq a$
• ha $a\leq b$ és $b\leq a$, akkor $a=b$
• ha $a\leq b$ és $b\leq c$, akkor $a\leq c$

Kiterjesztés, kompatibilitás, atommentesség, elágazó részbenrendezett halmazok

Legyen $(A;\leq )$ tetszőleges részbenrendezett halmaz és $a,b\in A$. Azt mondjuk, hogy b kiterjesztése a-nak, ha $b\leq a$, illetve valódi kiterjesztésről beszélünk, ha $b\leq a$ és $b\neq a$

Legyen $(A;\leq )$ tetszőleges részbenrendezett halmaz és $a,b\in A$. Akkor mondjuk, hogy az $a$ és $b$ elemek kompatibilisek, ha van közös kiterjesztésük, azaz van olyan $c\in A$ elem, amelyre $c\leq a$ és $c\leq b$ is teljesül. Ellenkező esetben inkompatibilis elemekről beszélünk.

Legyen $(A;\leq )$ tetszőleges részbenrendezett halmaz és $a\in A$. Az $a$ elemet atomnak nevezzük, ha az $a$ elemnek nincs valódi kiterjesztése. Az $(A;\leq )$ részbenrendezett halmazt atommentesnek nevezzük, ha nincs benne atom.

Az $(A;\leq )$ részbenrendezett halmazt elágazó részbenrendezett halmaznak nevezzük, ha tetszőleges $a,b\in A$ elemekhez létezik olyan $c\in A$ elem, hogy $c$ kompatibilis $a$-val és inkompatibilis $b$-vel.

Tulajdonságok

Legyen $(A;\leq )$ tetszőleges atommentes, elágazó részbenrendezett halmaz. Ekkor tetszőleges $a\in A$ elemhez létezik $b,c\in A$ elem úgy, hogy $b$ és $c$ egyaránt kiterjesztése $a$-nak, azonban $b$ és $c$ egymással inkompatibilis.

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.

Lásd még

• Kuratowski–Zorn-lemma
• Hausdorff–Birkhoff-tétel
• Háló
• Forszolás

Hivatkozások

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

Külső hivatkozások

• Partially Ordered Set a MathWorld oldalán
• Forszolás (jegyzet) Csirmaz László oldalán