Részbenrendezett halmaz

A Wikipédiából, a szabad enciklopédiából
(Részbenrendezés szócikkből átirányítva)
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ó[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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

Példák[szerkesztés | forrásszöveg szerkesztése]

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

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

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

  • 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ók[szerkesztés | forrásszöveg szerkesztése]