Conjunt parcialment ordenat

De Viquipèdia
Jump to navigation Jump to search
Relació homogèniaRelació reflexivaRelació no reflexivaConjunt preordenatRelació de dependènciaConjunt parcialment ordenatRelació d'equivalènciaOrdre totalRelacions homogènies.jpg
Quant a la imatge

En matemàtiques, especialment en teoria de l'ordre, un conjunt parcialment ordenat (o Poset, de l'anglès partially ordered 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 els uns amb els altres tots els elements del conjunt, Tot i així, això pot ocórrer en alguns casos (en altres paraules, l'ordre total és un cas particular de l'ordre parcial).

Definició formal[modifica]

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]

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 qualsevol dels enters. Aquest ordre és també total.
  • El conjunt de naturals ordenat per la relació de divisibilitat.
  • El conjunt de subconjunts d'un conjunt donat (és a dir, el seu conjunt de parts) ordenat per inclusió.
  • El conjunt de subespais d'un espai vectorial ordenat per inclusió.

Ordres parcials estrictes i no estrictes[modifica]

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]

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

Extensió lineal[modifica]

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]

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