Versione delle 16:30, 21 giu 2016 modifica Ruthven (discussione \| contributi) Check user, Amministratori 109 292 modifiche →‎Intervalli e intervalli stretti: rimossa sezione ← Differenza precedente		Versione delle 16:42, 21 giu 2016 modifica annulla Ruthven (discussione \| contributi) Check user, Amministratori 109 292 modifiche unione con Ordine (matematica) eseguita Etichetta: Modifica visuale Differenza successiva →
Riga 1: ~~{{U\|Ordine (matematica)\|matematica\|ottobre 2015}}{{WIP\|Ruthven\|unione con [[Ordine (matematica)]]}}~~ 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]] Line 18 ⟶ 16: :<math>(x,y) \in R \ </math> 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> Line 34 ⟶ 32: === Primi esempi === Esempi ben noti di insiemi parzialmente ordinati sono: * gli insiemi numerici <math>\mathbb N</math>, <math>\mathbb {Z}</math>, <math>\mathbb Q</math>, <math>\mathbb R</math> muniti della relazione d'ordine totale standard <math>a R b \Leftrightarrow a \leq b</math>, * l'insieme <math>\mathbb N \backslash \{0\}</math> munito della relazione di [[divisibilità]] <math>a R b \Leftrightarrow a \| b</math> (cioè <math>a</math> è un [[divisore]] di <math>b</math>) Una qualunque famiglia di insiemi munita della relazione di inclusione <math>a R b \Leftrightarrow a \subseteq b</math> (cioè <math>a</math> è [[sottoinsieme]] di <math>b</math>)<h2>Ordine largo e ordine stretto</h2>Alcuni autori<ref name=":0">{{Cita libro\|autore=Vincenzo Aversa\|titolo=Metodi quantitativi delle decisioni. Algebra ed analisi elementare in una selezione di problemi di scelta\|collana=Manuali per l'università\|anno=2000\|editore=Liguori Editore\|città=\|pp=12-15\|ISBN=9788820731649}}</ref> definiscono [[relazione d'ordine]] ~~'''~~"stretto~~'''~~" una relazione <math> (A, <) </math> che soddisfi le proprietà [[Relazione antiriflessiva\|irriflessiva]], [[Relazione antisimmetrica\|antisimmetrica]] e [[Relazione transitiva\|transitiva]] (o, equivalentemente e più concisamente, le proprietà [[Relazione asimmetrica\|asimmetrica]] e [[Relazione transitiva\|transitiva]]), e quindi chiamano relazione d'ordine ~~'''~~"largo~~'''~~" la relazione d'ordine <math> (A, \leq) </math>. L'ordine stretto mira a concentrarsi sulla [[Relazione simmetrica\|asimmetria]] della relazione, non considerando la riflessività. === Proposizione === <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 ) \setminus (\Delta(A)))</math>; viceversa ad ogni relazione d'ordine stretto <math>(A,<)</math> è associata la relazione d'ordine largo <math>(A, \; (<)\; \cup \; (\Delta(A)))</math>. == Digrafo di un ordine == [[File:Divisibility_graph.png\|miniatura\|Grafo della relazione di divisibilità]]Se l'insieme <math>A</math> è finito o [[Insieme numerabile\|numerabile]] la relazione d'ordine si può rappresentare visivamente mediante un [[Digrafo (matematica)\|digrafo]] (risp. finito o numerabile) i cui nodi sono gli elementi di <math>A</math> e tale che due nodi <math>a</math> e <math>b</math> sono connessi da un [[Grafo\|arco]] se e solo se <math>a \leq b</math> e non ci sono elementi intermedi tra di loro (cioè non esiste nessun <math>c\ne a,b</math> tale che <math>a \leq c</math> e <math>c \leq b</math>). Il grafo di una relazione d'ordine non può avere [[Grafo\|cicli]], mentre può avere più [[Grafo#Connettività\|componenti connesse]] e 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à). ==Ordini semplici, lineari e totali== Due elementi <math>a</math> e <math>b</math> di un insieme parzialmente ordinato <math>\,(A,\leq)\, </math> si dicono '''confrontabili''' se accade che <math>a \leq b</math> oppure che <math>b \leq a</math>. 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]]\|''ordine totale'']] se per ogni <math>a,b \in A</math> , <math>a</math> e <math display="inline">b</math> sono confrontabili (ossia vale <math>a \leq b</math> oppure <math>b \leq a</math>). 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). Line 63 ⟶ 61: 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. == Maggiorante e minorante ==▼ Sia <math>(A,\leq)</math> un ordine (poset) e <math>\empty \neq S \subseteq O</math>. Allora si dice che un elemento <math>y\in A</math> è un ~~'''~~[[Maggiorante e minorante\|~~maggiorante]]~~''maggiorante'']] di <math>S</math> se <math>\forall x \in S,\ x\leq y</math>.▼ Analogamente, in modo [[duale]], un elemento <math>y\in A</math> si definisce un ~~'''~~[[Maggiorante e minorante\|''minorante'']]~~'''~~ di un insieme <math>S</math> se <math>\forall x \in S,\ y\leq x</math>.▼ ▲==Maggiorante e minorante== ~~Sia <math>(A,\leq)</math> un ordine (poset) e <math>\empty \neq S \subseteq O</math>. Allora:~~ ▲si dice che un elemento <math>y\in A</math> è un '''[[Maggiorante e minorante\|maggiorante]]''' di <math>S</math> se <math>\forall x \in S,\ x\leq y</math>. ▲Analogamente, in modo [[duale]], un elemento <math>y\in A</math> si definisce un '''[[Maggiorante e minorante\|minorante]]''' di un insieme <math>S</math> se <math>\forall x \in S,\ y\leq x</math>. Se <math>S</math> ammette almeno un maggiorante (minorante) allora si dice che <math>S</math> è un sottoinsieme limitato superiormente (inferiormente). Un sottoinsieme che possiede sia maggioranti che minoranti si dice '''limitato d'ordine'''. Se l'insieme <math>S</math> è un insieme numerico con cardinalità maggiore di uno (<math>\|S\|>1</math>) allora scegliendo un suo sottoinsieme <math>S_2 \subseteq S</math> con cardinalità pari a 2 (<math>\|S_2\|=2</math>), si può definire il minimo tra i due soli elementi, <math>a</math> e <math>b</math> con la seguente relazione: Line 79 ⟶ 74: Il massimo tra i due elementi si trova invece con la seguente espressione :<math>\max\{a,b\}=\mathbf{1}_{\mathbb{R}^+}(a-b) \cdot (a-b)+b</math> Dove con <math>\mathbf{1} </math> si è indicata la [[funzione indicatrice]]. ==Elementi massimali e minimali==▼ ~~Sia <math>(A,\leq)</math> un ordine.~~ ▲===Elementi massimali e minimali=== Sia <math>(A,\leq)</math> un ordine. Si dice che <math>m</math> è l''''elemento minimo''' di <math>A</math> se esiste un <math>x \in A</math> tale che <math>\forall a \in A,\ x\leq a</math>. ~~[[Dualità (teoria degli ordini)\|Dualmente]] si~~Ssi definisce '''elemento massimo''' di <math>A</math> un <math>y \in A</math> tale che <math>\forall a \in A,\ a\leq y</math>. L'elemento di massimo e l'elemento di minimo di <math>A</math> si indicano rispettivamente come ''max'' <math>A</math> e ''min'' <math>A</math>. Line 94 ⟶ 87: <math>M</math> sarà invece un ''elemento massimale'' se <math> a \in A,\ M \leq a \; \Rightarrow \; a = M </math>. In generale, massimo ed elemento massimale ''non'' ~~sono~~corrispondono laallo ~~stessa~~stesso ~~cosa~~elemento. Si ~~pensi~~consideri acome esempio l'insieme <math>\{2,3,4,5,6\}</math> fornito della relazione di divisibilità.: ~~Esso~~esso non ammette né massimo né minimo, ma per esempio 3 è un elemento minimale, poiché <math>x\|3</math> è soddisfatto solo per <math>x=3</math>. Si presti attenzione inoltre che l'elemento 3 non può essere massimale. Se così fosse, allora 3 non dividerebbe nessun altro elemento dell'insieme, ma <math>3\|6</math> che dimostra l'assurdità della asserzione dato che <math>3\ne6</math>. 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. ===Estremo superiore ed inferiore=== Sia <math>(A,\leq)</math> un ordine e sia <math>\empty \neq S \subseteq A</math>. Definiamo: Line 103 ⟶ 96: <math>m_s=\{x\in A\,\|\,{x}\;{e'}\;{minorante}\; {di} \; S \}</math>. Allora un elemento <math>x\in A</math> si ~~dice~~dicef: ~~'''~~[[Estremo superiore e estremo inferiore\|estremo superiore]]~~'''~~ di <math>S</math> (indicato con <math>{sup}\; S</math>) <math>\min M_S</math>; ~~'''~~[[Estremo superiore e estremo inferiore\|estremo inferiore]]~~'''~~ di <math>S</math> (indicato con <math>{inf}\; S</math>) <math>\max m_S</math>. Osserviamo che, dato un sottoinsieme, non è detto che esso ammetta un minimo o un massimo. ===Segmenti iniziali e finali=== Sia <math>(A,\leq)</math> un insieme ordinato e un sottoinsieme <math>S\subseteq A</math>, allora <math>S</math> è detto: '''segmento iniziale''' di <math>A</math>, se dati due elementi <math>x \in S</math> e <math>y \in A</math>, si ha che <math>y \leq x \Rightarrow y \in S</math>; '''segmento finale''' di <math>A</math>, se analogamente <math>x \leq y \Rightarrow y \in S</math>. In altre parole, gli elementi si <math>S</math> non ammettono (rispettivamente) minimo o massimo al di fuori da <math>S</math>. Line 119 ⟶ 112: == Ordinamenti ben fondati == Una relazione d'ordine su un insieme <math>A</math> si dice ~~'''~~"ben fondata~~'''~~" o ~~'''~~[[buon ordinamento]]~~'''~~ se ogni sottoinsieme <math>Y </math> <math> \subseteq</math> <math> A</math> non vuoto è dotato di minimo, ossia esiste un elemento <math>a \in A</math> tale che <math>a \le x \quad \forall x \in A.</math> Un tipico esempio di ''buon ordinamento'' è quello che stabilisce la relazione d'ordine standard sull'insieme <math>\mathbb N</math> dei numeri naturali. L'affermazione che i naturali sono un insieme ben ordinato, ovvero che ogni sottoinsieme <math>X</math> di <math>\mathbb N</math> ha un minimo viene talvolta chiamata [[Principio del buon ordinamento]] e si può dimostrare essere equivalente al [[Principio di induzione]]. Line 125 ⟶ 118: === Il teorema del buon ordinamento === Il ~~'''~~[[teorema del buon ordinamento]]~~'''~~ (da non confondere con il [[principio 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). == Prodotto cartesiano di ordini == Line 135 ⟶ 128: secondo la relazione <math>(a_1, b_1) \leq (a_2, b_2)</math> se <math>a_1 < a_2 \wedge b_1 < b_2</math> o <math>a_1=a_2 \wedge b_1= b_2</math><!-- Particolare importanza assumono in matematica le '''[[Ordine_totale\|relazioni d'ordine totali]]''', relazioni tali che due elementi qualsiasi ''a'' e ''b'' risultano '''confrontabili''', cioè deve essere <math>\,a R b</math> o <math>\,b R a</math>. Una relazione d'ordine non necessariamente totale si dice invece '''parziale'''. -->Se i due ordini sono semplici, lo è anche l'ordine lessicografico, ma non necessariamente gli altri due. == Funzioni ~~monotone,~~e ~~antitone~~relazioni d'ordine == Siano <math>(OA, \leq)</math> e <math>(P,\preccurlyeq)</math> due ordini e sia <math>f \colon OA \to P</math>. <math>f</math> si dice '''monotona''' se <math>x \leq y \Rightarrow f(x) \preccurlyeq f(y)</math> per ogni x,y in <math>P</math>. <math>f</math> si dice '''antitona''' se <math>x \le y \Rightarrow f(x) \succcurlyeq f(y)</math> per ogni x,y in <math>P</math>. == Note == Line 151 ⟶ 144: * [[Insieme totalmente ordinato]] * [[Relazione d'ordine reticolare]] e [[reticolo (matematica)]] * [[Insieme ordinato graduato]] * [[Ordine denso]] * [[Arborescenza]], o albero con radice * [[Teoria dei grafi]] * [[Inversione di Moebius-Rota]] * [[Relazione di equivalenza]] * [[Preordine]]

Relazione d'ordine: differenze tra le versioni