Relazione d'ordine: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Tolto non sequitur |
m fix vari -parametri deprecati using AWB |
||
Riga 1:
In [[matematica]], più precisamente in [[teoria degli ordini]], una '''relazione d'ordine''' su di un [[insieme]] è una [[relazione binaria]] tra elementi appartenenti all'insieme che gode delle seguenti proprietà:
* [[Relazione riflessiva|riflessiva]]
* [[Relazione antisimmetrica|antisimmetrica]]
* [[Relazione transitiva|transitiva]].
Si definisce '''insieme parzialmente ordinato''' (oppure '''ordine''') 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 <math>\leq</math>, <math>\subseteq</math>, <math>\sqsubseteq</math> e <math>\preccurlyeq</math>.
In [[lingua inglese]] un insieme parzialmente ordinato è anche detto concisamente '''''poset''''' (''Partially Ordered Set''), e questo termine è usato gergalmente anche nella lingua italiana.
Riga 18:
ed in tal caso si scrive <math> xRy</math>.
Una relazione d'ordine <math>\le</math> è una relazione binaria tra elementi di un insieme <math>A</math> [[Relazione riflessiva|riflessiva]], [[Relazione antisimmetrica|antisimmetrica]] e [[Relazione transitiva|transitiva]].<ref>{{Cita|Reed, Simon|Pag. 3|reed}}</ref>
Esplicitamente, tale relazione soddisfa le seguenti proprietà:
Riga 28:
Le relazioni d'ordine si indicano spesso con i simboli <math>\leq</math>, <math>\subseteq</math>, <math>\sqsubseteq</math> e <math>\preccurlyeq</math>.
La coppia <math>(A,\leq)</math> costituita da un insieme e da una relazione d'ordine su di esso si dice ''insieme parzialmente ordinato'' o semplicemente ''ordine'', da non confondere con il termine più specifico [[insieme totalmente ordinato]].
=== Primi esempi ===
Riga 39:
<blockquote>Una relazione d'ordine è asimmetrica se e solo se è irriflessiva<ref name=":0" />.</blockquote>Benché le due definizioni siano distinte, il loro studio non presenta grosse differenze, in quanto tra le due classi di relazioni sussiste una corrispondenza biunivoca molto semplice.
Sia <math> A </math> un insieme e denotiamo con <math>\,\Delta(A)</math> la diagonale di <math>\,A\times A</math>, cioè <math>\ \Delta(A):= \{ (x,x) : x\in A \} </math>, allora ad ogni relazione d'ordine largo <math>(A, \leq)</math> è associata la relazione d'ordine stretto <math>(A,\leq
== Digrafo di un ordine ==
Riga 48:
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 in <math>\mathbb N \backslash \{0\}</math> 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 un ''ordine semplice'' o ''lineare'', oppure ''[[ordine totale
Il digrafo di un insieme totalmente ordinato si può rappresentare come un [[segmento]] o una [[retta]] o una [[semiretta]] su cui giacciono tutti i nodi (corrispondenti a tutti gli elementi dell'insieme).
Riga 58:
=== Esempio ===
Per l'insieme parzialmente ordinato della divisibilità, sono catene gli insiemi delle potenze positive di un numero primo e 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.
Riga 81:
Si definisce ''elemento massimo'' di <math>A</math> un <math>y \in A</math> tale che <math>\forall a \in A,\ a\leq y</math>.
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 di <math>A</math> si indicano rispettivamente come ''max'' <math>A</math> e ''min'' <math>A</math>.
Su ordini non semplici è utile definire altri due concetti: quello di elemento minimale e massimale.
Riga 99:
*[[Estremo superiore e estremo inferiore|estremo superiore]] di <math>S</math> il <math>\min M_S</math> ; quando esiste è indicato con <math>{sup}\; S</math>;
*[[Estremo superiore e estremo inferiore|estremo inferiore]] di <math>S</math> il <math>\max m_S</math>; quando esiste è indicato con <math>{inf}\; S</math>
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.
| |||