Delno urejena množica

Delno urejena množica (tudi poset iz angleškega izraza partially ordered set) je v matematiki in teoriji urejenosti pojem, ki posplošuje pojem urejenosti, zaporednosti in ureditve elementov v množici. Delno urejena množica (poset) je sestavljena iz množice, ki skupaj z binarno relacijo, pove kateri pari elementov iz množice so pred drugimi. Takšna vrsta relacije se imenuje delna urejenost.

Hassejev diagram množice vseh podmnožic treh elementov {x, y, z}, urejenih po vključenosti.

Definicija

Delni red je binarna relacija "≤" nad množico P, ki je refleksivna, antisimetrična in tranzitivna. To pomeni, da za vse a, b in c v P velja:

• a ≤ a (refleksivnost);
• če je a ≤ b in b ≤ a potem je tudi a = b (antisimetričnost);
• če je a ≤ b in b ≤ c potem je a ≤ c (tranzitivnost).

Zgledi

Običajni zgledi za delno urejene množice so:

• realna števila, ki so urejena po relaciji manjše kot ali enako oziroma z znakom ≤
• množica naravnih števil skupaj z relacijo deljivosti
• množica oglišč usmerjeni neciklični graf urejen po dosegljivosti
• množica podmnožic dane množice urejene po podmnožicah (glej sliko zgoraj)
• množica podprostorov vektorskih prostorov urejenih po vključenosti
• za delno urejeno množico P je prostor zaporednosti, ki vsebuje vsa zaporedja elementov iz P, kjer je zaporedje a pred zaporedjem b, če je vsak element iz a pred pripadajočim elementom iz b. To velja (a_n)_n∈ℕ ≤ (b_n)_n∈ℕ, če in samo, če je a_n ≤ b_n za vse n v ℕ
• za množico X in delno urejeno množico P, vsebuje funkcijski prostor vse funkcije od X do P, kjer je f ≤ g ,če in samo, če je f(x) ≤ g(x) za vse x v X
• ograja delno urejene množice je definirana s spremenljivim zaporedjem urejenih relacij a < b > c < d ...

Skrajni elementi

Obstoja nekaj opisov za pojme največji in najmanjši element v delno urejeni množici P:

• največji element in najmanjši element: Element g v P je največji element a v P, če za vsak element a v P velja g ≥ a. Element m v P je najmanjši element, če za vsak element a v P velja a ≥ m.
• maksimalni elementi in minimalni elementi: Element g v P je maksimalni element, če ni elementa a v P za katerega bi veljalo g ≤ a. Podobno je element m v P najmanjši element, če v P ni elementa a, za katerega bi veljalo a ≤ m. Kadar ima delno urejena množica največji element je ta edini maksimalni element. V vseh ostalih primerih je več kot eden maksimalni element. Podobo velja tudi za minimalne elemente.
• zgornje in spodnje meje: za podmnožico A množice P je element x iz P zgornja meja množice A, če za vsak a v P velja a ≤ x. Ni nujno, da je x v A, toda mora biti zgornja meja v A. Podobno je element x v P, spodnja meja množice A, če velja za vsak a v P a ≥ x. Največji element množice P je zgornja meja in najmanjši element je spodnja meja množice P.

Zunanje povezave

• Delno urejena množica na MathWorld (angleško)
• Delno urejene množice (angleško)
• Delno urejena množica v Encyclopedia of Mathematics (angleško)
• Delno urejena množica na WolframAlpha (angleško)