Conjunt parcialment ordenat

De Viquipèdia
Dreceres ràpides: navegació, cerca
Relació homogènia Relació reflexiva Relació no reflexiva Conjunt preordenat Relació de dependència Conjunt parcialment ordenat Relació d'equivalència Ordre totalRelacions homogènies.jpg
Quant a la imatge

En matemàtiques, especialment en teoria de l'ordre, un conjunt parcialment ordenat (o Poset , l'anglès p artially o rdered set ) és un conjunt equipat amb una relació binària d'ordre parcial. Aquesta formalitza el concepte intuïtiu d'ordre, seqüència, o arranjament dels elements del conjunt. Un tal ordre no necessàriament ha de ser total, és a dir, no es necessita que es puguin comparar uns amb altres tots els elements del conjunt, Tot i així, això pot ocórrer en alguns casos (en altres paraules, el ordre total és un cas particular de l'ordre parcial).

Definició formal[modifica | modifica el codi]

Un ordre parcial és una relació binària R sobre un conjunt X que és reflexiva, antisimètrica, i transitiva, és a dir, per a qualssevol a , b , i c en X s'ha de:

  • aRa (reflexivitat).
  • Si aRb i bRa , llavors a = b (antisimetría).
  • Si aRb i BRC , llavors aRc (transitivitat).

Un conjunt amb un ordre parcial s'anomena conjunt parcialment ordenat o Poset . De vegades s'usa l'expressió conjunt ordenat per a un parcialment ordenat, sempre que quedi clar que no es farà referència a altres classes d'ordre. En particular, a un conjunt totalment ordenat també l'hi crida ordenat a seques, especialment en camps on aquests són més comuns que els parcialment ordenats.

Usualment s'usa la notació de "≤" en lloc de "R" per l'ordre parcial.

Exemples[modifica | modifica el codi]

Conjunt dels subconjunts de{x, y, z}, ordenat per inclusió.

Alguns dels exemples més coneguts són els següents:

  • El conjunt dels naturals amb el seu ordre usual (la relació "menor o igual"). Aquest ordre és més un ordre total.
  • El conjunt dels enters amb el seu ordre usual. Aquest ordre és també total.
  • Un subconjunt finit{1, 2,..., n }dels naturals. Aquest ordre és també total.
  • El conjunt de naturals ordenat per la relació de divisibilitat.

Ordres parcials estrictes i no estrictes[modifica | modifica el codi]

En alguns contextos, l'ordre parcial anteriorment definit s'anomena no estricte o reflexiu , així doncs, uns ordre parcial estricte o irreflexiu és una relació binària que és irreflexiva i transitiva, i per tant asimètrica. De forma equivalent, asimètrica (i per tant irreflexiva) i transitiva.

És a dir, per a qualssevol a , b , i c en X s'ha de:

  • ¬ ( ara ) (irreflexives).
  • Si aRb , llavors ¬ ( bra ) (asimetria).
  • Si aRb i BRC , llavors arc (transitivitat).

Si R és un ordre parcial no estricte, llavors S = R -{( a , a )| aX }és l'ordre parcial estricte corresponent. Anàlogament, tot ordre parcial estricte S té un no estricte corresponent, és a dir, S ∪{( a , a )| aP }, o la "clausura reflexiva" de R .

Els ordres parcials estrictes són útils perquè es corresponen més directament amb els grafs acíclics dirigits: tot ordre parcial estricte és un GAD, i la clausura transitiva d'un GAD és, a més d'un ordre parcial estricte, un GAD en si mateixa.

Nombre d'ordres parcials[modifica | modifica el codi]

La seqüència [1] de la OEIS dóna el nombre d'ordres parcials en un conjunt de n elements.

Extensió lineal[modifica | modifica el codi]

Un ordre total T és una extensió lineal d'un ordre parcial P si, sempre que xPy , s'ha de xTy .

Esquema de temes relacionats[modifica | modifica el codi]

Teoria de l'ordre
Ben ordenat
Ordre total
Parcialment ordenat
preordenat
Relació reflexiva
Relació transitiva
Relació antisimètrica
Relació total
Relació ben fonamentada