Relazione d'ordine: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
→Segmenti iniziali e finali: corrette formule |
Elementi massimali e minimali spostati |
||
Riga 42:
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à).
Line 61 ⟶ 62:
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.
==Intervalli e intervalli stretti==
Line 71 ⟶ 73:
*'''intervallo stretto''' di <math>a</math> e <math>b</math> l'insieme <math>\, ]a,b[=\{x\in A|a < x < b\}=[a,b] - \{a,b\}</math>.
==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>.▼
== 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]].▼
=== 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).▼
==Maggiorante e minorante==
Sia <math>(A,\leq)</math> un ordine (poset) e
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
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:▼
:<math>\min\{a,b\}=\mathbf{1}_{\mathbb{R}^-}(a-b) \cdot (a-b)+b</math>▼
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.
Si dice che <math>m</math> è l''''elemento minimo''' di <math>
[[Dualità (teoria degli ordini)|Dualmente]] si definisce '''elemento massimo''' di <math>
L'elemento di massimo e l'elemento di minimo di <math>
*<math>m</math> si dice
*<math>M</math> sarà invece un
In generale, massimo ed elemento massimale ''non'' sono la stessa cosa. Si pensi a <math>\{2,3,4,5,6\}</math> fornito della relazione di divisibilità. 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>M_S=\{x\in A\,|\,{x}\;{e'}\;{maggiorante}\;{di} \; S \}</math>;
Line 121 ⟶ 115:
Allora un elemento <math>x\in A</math> si dice:
*'''[[Estremo superiore e estremo inferiore|estremo superiore]]''' di <math>S</math> (indicato con <math>{sup}\; S</math>)
*'''[[Estremo superiore e estremo inferiore|estremo inferiore]]''' di <math>S</math> (indicato con <math>{inf}\; 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>.
▲== 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]].
▲=== 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 140 ⟶ 152:
<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>.
▲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:
▲:<math>\min\{a,b\}=\mathbf{1}_{\mathbb{R}^-}(a-b) \cdot (a-b)+b</math>
▲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]].
== Note ==
| |||