Set parzialmente ordinato

In matematica , un insieme parzialmente ordinato (a volte chiamato poset dall'inglese parzialmente ordinato ) formalizza e generalizza la nozione intuitiva di ordine o disposizione tra gli elementi di un insieme . Un insieme parzialmente ordinato è un insieme dotato di una relazione d'ordine che indica che per alcune coppie di elementi, uno è più piccolo dell'altro. Tutti gli elementi non sono necessariamente confrontabili, a differenza del caso di un set provvisto di un ordine totale .

Se l'insieme è finito, abbiamo una rappresentazione grafica dell'insieme parzialmente ordinato, il diagramma di Hasse , che può rendere più facile lavorarci sopra. Se l'insieme è infinito, possiamo disegnare parte del suo diagramma di Hasse.

Definizione ed esempi

Definizione

Un ordine (o ordine parziale) è una relazione binaria su un insieme P che è riflessivo , antisimmetrico e transitivo . Si nota ≤.

I tre assiomi precedenti vengono riscritti:

a ≤ a (riflessività).
Se a ≤ b e b ≤ a , allora a = b (antisimmetria).
Se a ≤ b e b ≤ c , allora a ≤ c (transitività).

Quindi non è necessariamente un ordine totale .

Esempi

L'insieme degli interi naturali, provvisto di divisibilità, è un insieme infinito parzialmente ordinato.
Un insieme di persone con la relazione di discendenza genealogica è un insieme parzialmente ordinato. Ad esempio, due sorelle sono inferiori alla madre ma non sono paragonabili tra loro.
L' insieme di parti di un dato insieme , fornito con l'inclusione, forma un insieme parzialmente ordinato. Se l'insieme dato è finito, il suo insieme di parti è finito (più precisamente , abbiamo ). La figura seguente rappresenta il diagramma di Hasse di un set con 3 elementi. $\ # A = n$ $\ #P (A) = 2 ^ {n}$

Per prendere un caso concreto (anzi, isomorfo ) dell'esempio precedente, un insieme di persone dotate della relazione può donare sangue per formare un insieme parzialmente ordinato secondo i sistemi ABO e Rhesus . Gli elementi x , y , e z nell'esempio precedente più generale essendo istanziati dal antigeni A, B, e D (Rh +) dell'individuo. Ad esempio, un individuo del gruppo O + può dare a un destinatario del gruppo B +, ma nessuno dei due può dare o ricevere da un individuo del gruppo A-.
L'insieme dei numeri complessi forniti nella seguente relazione ordine parzialmente ordinato: . $a + ib <a '+ ib' \ Leftrightarrow \ left \ {{\ begin {matrix} a <a '\\ b <b' \ end {matrix}} \ right.$

Ad esempio, non possiamo confrontare 1 e i . Questo ordine non è compatibile con la struttura del corpo di . $\ mathbb {C}$

L'insieme delle funzioni di in , fornito con la relazione d'ordine si , è un insieme infinito parzialmente ordinato. Intuitivamente, una funzione è più piccola di un'altra se la sua curva è sempre al di sotto dell'altra curva. Possiamo generalizzare questo esempio alle funzioni di un insieme X in un insieme parzialmente ordinato P. $\ mathbb {R}$ $\ mathbb {R}$ $f <g$ $\ forall x, f (x) <g (x)$
L'insieme delle partizioni di un dato insieme è parzialmente ordinato, con l'ordine dato dal perfezionamento delle partizioni: per definizione, una partizione è più fine di un'altra se divide le parti dell'altra in parti più piccole.
Possiamo fornire l'insieme di polinomi con n variabili con una relazione di ordine parziale. Iniziamo confrontando i monomi con n variabili tramite l' ordine lessicografico indotto da (questo ordine lessicografico è totale). Confrontiamo due polinomi e dicendo che è strettamente più piccolo di se qualsiasi monomio diverso da zero di è strettamente più piccolo di qualsiasi monomio diverso da zero di . Questa relazione d'ordine sui polinomi è parziale. $R [X_ {1}, ..., X_ {n}]$ $1 <X_ {1} <X_ {2} <... <X_ {n}$ $P$ $Q$ $P$ $Q$ $P$ $Q$

Specificità di insiemi parzialmente ordinati

Elemento più grande , elemento massimo e limite superiore

Sia P un insieme parzialmente ordinato:

Un elemento a di P è un elemento maggiore se per qualsiasi elemento b di P, b ≤ a. Un set parzialmente ordinato può avere solo un elemento più grande.

Un elemento a di P è un elemento massimale se non esiste un elemento b di P tale che b> a. Se P ha un elemento più grande, è l'elemento massimo unico di P.

Per un sottoinsieme A di P, l'elemento x di P è un limite superiore di A se a ≤ x per qualsiasi elemento a di A. x non appartiene necessariamente ad A. L'elemento più grande di P, s 'che esiste, è un limite superiore di P.

Esempio : considera l'insieme di interi positivi, ordinati per divisione. 1 è l'elemento più piccolo. D'altra parte, questo set non ha un elemento più grande. Se ora escludessimo l'elemento 1, l'insieme parzialmente ordinato non avrebbe più un elemento più piccolo ma un'infinità di elementi minimi: i numeri primi .

Se E è un insieme parzialmente ordinato, non esiste necessariamente un elemento più grande. Se E è un insieme finito parzialmente ordinato, conterrà almeno un elemento massimale. Se E è un insieme induttivo infinito, possiamo usare il lemma di Zorn per avere l'esistenza di un elemento massimale.

Alcune condizioni sugli elementi più grandi e sugli elementi più piccoli di un insieme parzialmente ordinato portano alla definizione di un reticolo .

Con lo stesso ragionamento otteniamo l'elemento più piccolo, gli elementi minimi e il limite inferiore.

Comparabilità

Se a ≤ b o a b, allora aeb sono comparabili. Nel diagramma di Hasse sopra, {x} e {x, y, z} sono comparabili, mentre {x} e {y} non lo sono. Un ordine parziale in cui qualsiasi coppia di elementi è confrontabile è chiamato ordine totale e l'insieme è chiamato stringa . Un insieme in cui non è possibile trovare una coppia comparabile è chiamato anticatena (ad esempio l'insieme {{x}, {y }, {z}} nella figura sopra) $\ geq$

Recupero

Diciamo che un elemento a è ricoperto da un elemento b, che si scrive a <: b, se a è strettamente minore di be non c'è elemento c interposto tra i due. Ad esempio, {x} è coperto da {x, z} nella figura sopra ma non da {x, y, z}.

Collegamenti con complessi simpliciali

Una classe importante di complessi simpliciali proviene da insiemi parzialmente ordinati finiti. Definiamo il complesso di ordine D (P) di un insieme finito parzialmente ordinato P come l'insieme di catene di P. Il complesso di ordine è banalmente un complesso simpliciale.

Lo studio dell'insieme parzialmente ordinato fornisce informazioni sul suo complesso d'ordine, e quindi è interessante studiare un complesso simpliciale come complesso d'ordine di un insieme parzialmente ordinato.

Operazione su set parzialmente ordinati

Prodotto cartesiano parzialmente ordinato insieme

Al fine di eliminare la molteplicità delle possibili relazioni d'ordine durante un insieme parzialmente ordinato, possiamo definire tre diverse regole:

L' ordine lessicografico ( un , b ) ≤ ( c , d ) se un < c o ( a = c e b ≤ d );
L' ordine moltiplicativo : ( a , b ) ≤ ( c , d ) se a ≤ c e b ≤ d ;
La chiusura riflessiva del prodotto diretto : ( a , b ) ≤ ( c , d ) se ( un < c e b < d ) o ( a = c e b = d ).

Tutte queste regole si applicano anche ai prodotti di più di due set parzialmente ordinati.

Finitezza locale

Un insieme parzialmente ordinato E si dice localmente finito se per tutti l'intervallo è finito. Questa ipotesi consente di generalizzare la formula di inversione di Möbius . $x, y \ in E$ $[x, y]$

Riferimenti

(en) Richard P. Stanley , Enumerative Combinatorics , vol. 1 [ dettaglio delle edizioni ] ( presentazione online )

Vedi anche