Delno urejena množica

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Hassejev diagram množice vseh podmnožic treh elementov {x, y, z}, urejenih po vključenosti.

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.

Definicija[uredi | uredi kodo]

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[uredi | uredi kodo]

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 (an)n∈ℕ ≤ (bn)n∈ℕ, če in samo, če je an ≤ bn 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 fg ,č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[uredi | uredi kodo]

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 a ≥ m. 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 največji element, če ni elementa p v P za katerega bi veljalo a>g. 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 največji element. V vseh ostalih primerih je več kot eden največji element. Podobo velja tudi za najmanjše 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ša meja je spodnja meja množice P.

Zunanje povezave[uredi | uredi kodo]