Relazione d'ordine

Inmatematica, più precisamente inteoria degli ordini, unarelazione d'ordinedi uninsiemeè unarelazione binariatra elementi appartenenti all'insieme che gode delle seguenti proprietà:
Si definisceinsieme parzialmente ordinato(oppureordine) la coppia costituita da un insieme e da una relazione d'ordine su di esso. Le relazioni d'ordine si indicano spesso con i simboli≤{\displaystyle \leq },⊆{\displaystyle \subseteq },⊑{\displaystyle \sqsubseteq }e≼{\displaystyle \preccurlyeq }.
Inlingua ingleseun insieme parzialmente ordinato è anche detto concisamenteposet(Partially Ordered Set), e questo termine è usato gergalmente anche nella lingua italiana.
Dati dueinsiemiA{\displaystyle A}eB{\displaystyle B}, il loroprodotto cartesianoè l'insieme dellecoppie ordinatedefinito nel modo seguente:
Si definiscerelazione binariasu un insiemeA{\displaystyle A}un sottoinsiemeR{\displaystyle R}del prodotto cartesianoA×A{\displaystyle A\times A}.Due elementix{\displaystyle x}ey{\displaystyle y}sono messi in relazione daR{\displaystyle R}se:
e in tal caso si scrivexRy{\displaystyle xRy}.
Una relazione d'ordine≤{\displaystyle \leq }è una relazione binaria tra elementi di un insiemeA{\displaystyle A}riflessiva,antisimmetricaetransitiva.
Esplicitamente, tale relazione soddisfa le seguenti proprietà:
Le relazioni d'ordine si indicano spesso con i simboli≤{\displaystyle \leq },⊆{\displaystyle \subseteq },⊑{\displaystyle \sqsubseteq }e≼{\displaystyle \preccurlyeq }.
La coppia(A,≤){\displaystyle (A,\leq )}costituita da un insieme e da una relazione d'ordine su di esso si diceinsieme parzialmente ordinatoo semplicementeordine, da non confondere con il termine più specificoinsieme totalmente ordinato.
Esempi ben noti di insiemi parzialmente ordinati sono:
Una qualunque famiglia di insiemi munita della relazione di inclusioneaRb⇔a⊆b{\displaystyle aRb\Leftrightarrow a\subseteq b}(cioèa{\displaystyle a}èsottoinsiemedib{\displaystyle b})
Se la relazione≤{\displaystyle \leq }soddisfa la proprietà riflessiva e transitiva (ma non necessariamente la proprietà antisimmetrica), si dice che induce unpreordinamento.In tal caso, si hanno elementi dell'insieme equivalenti dal punto di vista della relazione (ossia vale sia chea≤b{\displaystyle a\leq b}sia cheb≤a{\displaystyle b\leq a}) pur essendo distinti,a≠b{\displaystyle a\neq b}.
Tale preordinamento è detto esseretotaleolinearese per ogni coppiaa,b{\displaystyle a,b}si può stabilire se valgaa≤b{\displaystyle a\leq b},b≤a{\displaystyle b\leq a}o entrambe, così che tutte le coppie di elementi siano confrontabili; altrimenti si parla di preordinamentoparziale.
Alcuni autoridefiniscono relazione d'ordine "stretto" una relazione(A,<){\displaystyle (A,<)}che soddisfi le proprietàantiriflessiva,antisimmetricaetransitiva(o, equivalentemente e più concisamente, le proprietàasimmetricaetransitiva), e quindi chiamano relazione d'ordine "largo" la relazione d'ordine(A,≤){\displaystyle (A,\leq )}. L'ordine stretto mira a concentrarsi sullaasimmetriadella relazione, non considerando la riflessività.
Benché le due definizioni siano distinte, il loro studio non presenta grosse differenze, in quanto tra le due classi di relazioni sussiste unacorrispondenza biunivocamolto semplice.
SiaA{\displaystyle A}un insieme e denotiamo conΔ(A){\displaystyle \Delta (A)}la diagonale diA×A{\displaystyle A\times A}, cioèΔ(A):={(x,x):x∈A}{\displaystyle \Delta (A):=\{(x,x):x\in A\}}, allora ad ogni relazione d'ordine largo(A,≤){\displaystyle (A,\leq )}è associata la relazione d'ordine stretto(A,≤)∖Δ(A){\displaystyle (A,\leq )\setminus \Delta (A)}; viceversa ad ogni relazione d'ordine stretto(A,<){\displaystyle (A,<)}è associata la relazione d'ordine largo(A,<)∪Δ(A){\displaystyle (A,<)\cup \Delta (A)}.
Se l'insiemeA{\displaystyle A}è finito onumerabilela relazione d'ordine si può rappresentare visivamente mediante undigrafo(risp. finito o numerabile) i cui nodi sono gli elementi diA{\displaystyle A}e tale che due nodia{\displaystyle a}eb{\displaystyle b}sono connessi da unarcose e solo sea≤b{\displaystyle a\leq b}e non ci sono elementi intermedi tra di loro (cioè non esiste nessunc≠a,b{\displaystyle c\neq a,b}tale chea≤c{\displaystyle a\leq c}ec≤b{\displaystyle c\leq b}). Il grafo di una relazione d'ordine non può averecicli, mentre può avere piùcomponenti connessee da ogni suo nodo può entrare ed uscire qualsiasi numero di archi. Se il grafo è numerabile, da un nodo possono entrare o uscire infiniti archi (questo è il caso della relazione di divisibilità).
Due elementia{\displaystyle a}eb{\displaystyle b}di un insieme parzialmente ordinato(A,≤){\displaystyle (A,\leq )}si diconoconfrontabilise accade chea≤b{\displaystyle a\leq b}oppure cheb≤a{\displaystyle b\leq a}.
In generale, due elementi di una relazione d'ordine parziale possono non essere confrontabili, cioè non sono necessariamente in relazione fra di loro. Ad esempio inN∖{0}{\displaystyle \mathbb {N} \backslash \{0\}}munito della relazione di divisibilità, gli elementi 2 e 3 non sono in relazione perché nessuno dei due è divisore dell'altro.
Un insieme si dice unordine sempliceolineare, oppureordine totalese per ognia,b∈A{\displaystyle a,b\in A},a{\displaystyle a}eb{\displaystyle b}sono confrontabili (ossia valea≤b{\displaystyle a\leq b}oppureb≤a{\displaystyle b\leq a}).
Il digrafo di un insieme totalmente ordinato si può rappresentare come unsegmentoo unarettao unasemirettasu cui giacciono tutti i nodi (corrispondenti a tutti gli elementi dell'insieme).
Sia un ordine(A,≤){\displaystyle (A,\leq )}, si dicecatenaogni sottoinsiemeY⊆A{\displaystyle Y\subseteq A}tale che la relazione d'ordine ridotta aY{\displaystyle Y}costituisce unordine semplice.
Si dice inveceanticatenadell'insieme parzialmente ordinato(A,≤){\displaystyle (A,\leq )}un sottoinsiemeY⊆A{\displaystyle Y\subseteq A}i cui elementi sono mutuamente inconfrontabili. Una anticatena dell'insieme parzialmente ordinato delle divisibilità è fornita dall'insieme dei numeri primi.
Per l'insieme parzialmente ordinato della divisibilità, sono catene gli insiemi delle potenze positive di unnumero primoe più in generale i sottoinsiemi ottenuti con un processo che inizia considerando un intero positivo e prosegue aggiungendo ad ogni passo un multiplo dell'intero aggiunto in precedenza. Si possono considerare catene finite o infinite; il processo precedente può essere finito o illimitato.
Sia(A,≤){\displaystyle (A,\leq )}un insieme parzialmente ordinato (poset) e∅≠S⊆A{\displaystyle \varnothing \neq S\subseteq A}. Allora si dice che un elementoy∈A{\displaystyle y\in A}è unmaggiorantediS{\displaystyle S}sex≤y{\displaystyle x\leq y}per ognix∈S{\displaystyle x\in S}.
Analogamente, in modo duale, un elementoy∈A{\displaystyle y\in A}si definisce unminorantedi un insiemeS{\displaystyle S}sey≤x{\displaystyle y\leq x}per ognix∈S{\displaystyle x\in S}.
SeS{\displaystyle S}ammette almeno un maggiorante (minorante), allora si dice cheS{\displaystyle S}è un sottoinsieme limitato superiormente (inferiormente).
Un sottoinsieme che possiede sia maggioranti che minoranti si dicelimitato d'ordine.
Se l'insiemeS{\displaystyle S}è un insieme numerico con cardinalità maggiore di uno (|S|>1{\displaystyle |S|>1}), allora scegliendo un suo sottoinsiemeS2⊆S{\displaystyle S_{2}\subseteq S}con cardinalità uguale a 2 (|S2|=2{\displaystyle |S_{2}|=2}), si può definire il minimo tra i due soli elementi,a{\displaystyle a}eb{\displaystyle b}con la seguente relazione:
Il massimo tra i due elementi si trova invece con la seguente espressione:
dove con1{\displaystyle \mathbf {1} }si è indicata lafunzione indicatrice.
Sia(A,≤){\displaystyle (A,\leq )}un ordine. Si dice chem{\displaystyle m}è l'elemento minimodiA{\displaystyle A}sem≤a{\displaystyle m\leq a}per ognia∈A{\displaystyle a\in A}.
Si definisceelemento massimodiA{\displaystyle A}uny∈A{\displaystyle y\in A}tale chea≤y{\displaystyle a\leq y}per ognia∈A{\displaystyle a\in A}.
Vi sono ordinamenti per cui non esiste l'elemento minimo (rispettivamente, massimo); si mostra facilmente che se esiste un elemento minimo (rispettivamente, massimo) esso è unico. Quando esistono, l'elemento massimo e l'elemento minimo diA{\displaystyle A}si indicano rispettivamente comemaxA{\displaystyle \max A}eminA{\displaystyle \min A}.
Su ordini non semplici è utile definire altri due concetti: quello di elemento minimale e massimale.
In generale, massimo ed elemento massimale non corrispondono allo stesso elemento. Si consideri come esempio l'insieme{2,3,4,5,6}{\displaystyle \{2,3,4,5,6\}}fornito della relazione di divisibilità: esso non ammette né massimo né minimo, ma per esempio 3 è un elemento minimale, poichéx∣3{\displaystyle x\mid 3}è soddisfatto solo perx=3{\displaystyle x=3}. Si presti attenzione inoltre che l'elemento 3 non può essere massimale. Se così fosse, allora 3 non dividerebbe nessun altro elemento dell'insieme, ma3∣6{\displaystyle 3\mid 6}che dimostra l'assurdità della asserzione dato che3≠6{\displaystyle 3\neq 6}. Addirittura 5 è sia elemento massimale che minimale, poiché non è in relazione con nessun altro elemento dell'insieme diverso da se stesso. Dall'esempio è facile intuire che le due definizioni (massimo ed elemento massimale; minimo e elemento minimale) coincidono in presenza di un ordine semplice.
Sia(A,≤){\displaystyle (A,\leq )}un ordine e sia∅≠S⊆A{\displaystyle \varnothing \neq S\subseteq A}. Definiamo:
Allora si definiscono:
Osserviamo che, dato un sottoinsieme, non è detto che esso ammetta un minimo o un massimo, e dunque non è detto che esistano gli estremi superiori e inferiori.
Sia(A,≤){\displaystyle (A,\leq )}un insieme ordinato e un sottoinsiemeS⊆A{\displaystyle S\subseteq A}, alloraS{\displaystyle S}è detto:
In altre parole, gli elementi diS{\displaystyle S}non ammettono (rispettivamente) minimo o massimo al di fuori daS{\displaystyle S}.
Una relazione d'ordine su un insiemeA{\displaystyle A}si dice "ben fondata" obuon ordinamentose ogni sottoinsiemeY⊆A{\displaystyle Y\subseteq A}non vuoto è dotato di minimo.
Un tipico esempio dibuon ordinamentoè quello che stabilisce la relazione d'ordine standard sull'insiemeN{\displaystyle \mathbb {N} }dei numeri naturali. L'affermazione che i naturali sono un insieme ben ordinato, ossia che ogni sottoinsiemeX{\displaystyle X}diN{\displaystyle \mathbb {N} }ha un minimo viene talvolta chiamataprincipio del buon ordinamentoe si può dimostrare essere equivalente alprincipio di induzione.
Ilteorema del buon ordinamento(da non confondere con ilprincipio del buon ordinamento) asserisce che su ogni insieme non vuoto può essere definita una relazione d'ordine ben fondata (o buon ordinamento). Tale enunciato è equivalente all'assioma della scelta(cioè assumendolo vero si può dimostrare l'assioma della scelta e viceversa).
Ilprodotto cartesianodi due insiemi parzialmente ordinati può essere munito anch'esso di un ordine in più modi:
Se i due ordini sono semplici, lo è anche l'ordine lessicografico, ma non necessariamente gli altri due.
Siano(A,≤){\displaystyle (A,\leq )}e(P,≼){\displaystyle (P,\preccurlyeq )}due ordini e siaf:A→P{\displaystyle f\colon A\to P}.