Conjunt parcialment ordenat

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

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 complir:^[1]

• aRa (reflexivitat).
• Si aRb i bRa , llavors a = b (antisimetria).
• 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'anomena 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 a l'ordre parcial.

Exemples

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 a 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

En alguns contextos, l'ordre parcial anteriorment definit s'anomena no estricte o reflexiu, així doncs, un 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) | a ∈ X } és l'ordre parcial estricte corresponent. Anàlogament, tot ordre parcial estricte S té un no estricte corresponent, és a dir, S ∪ { (a, a) | a ∈ P }, 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.

Podeu consultar la seqüència corresponent al nombre d'ordres parcials en un conjunt de n elements a l'OEIS A001035.

Extensió lineal

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

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

Referències

1. Richard Johnsonbaugh. «3». A: Matemáticas discretas. 6. Pearson Educación, 2005, p. 121. ISBN 978-97-0260-637-6.