Differenza tra relazione d'ordine totale e parziale
Salve a tutti, sto avendo un po' di problemi a capire il concetto di relazione d'ordine e soprattutto, quello di relazione d'ordine totale.
Per quello che ho capito io, una relazione $\R$ è un sottoinsieme del prodotto cartesiano di due insiemi $AxB$.
Se $(a,b) in R $ con $a in A$ e $b in B$ allora si dice che $a$ è in relazione $R$ con $b$ ($a R b$).
Una relazione d'ordine è una relazione che viene definita su un insieme $A$ (ovvero $R sube A x A$ con $A != phi$), indicata come $(A,<=)$ e che ha le seguenti proprietà:
1)riflessiva se $R(x,x) AA x in A$ ovvero $ x <= x$
2)antisimmetrics se $R(x,y)$ e $R(y,x) => x = y$ $AA x,y in A$ ovvero $x <= y$ e $y <= x => x = y$
3)transitiva se $R(x,y)$ e $R(y,z) => R(x,z)$ ovvero $x <= y$ e $ y <= z => x <= z$
Ad esempio $(NN,<=)$ potrebbe essere definita come $EE l in NN: x+l = y$ ( specifico che per me 0 fa parte di $NN$)
$NNxNN = {(0,0),(0,1),(0,2),(0,3)....(1,0),(1,1),(1,2),(1,3)...(2,0),(2,1),(2,2)...} $ è il prodotto cartesiano di $NNxNN$
$R sube NNxNN = {(0,0),(0,1),(0,2),(0,3)....(1,1),(1,2),(1,3),(1,4),...(2,2),(2,3),(2,4)....(3,3), (3,4),(3,5)...(100,100),(100,101)...}$
è il sottoinsieme $R$ di $NNxNN$ ovvero la nostra relazione.
Si può verificare che è di ordine perché le 3 proprietà che la contraddistinguono sono verificate:
1,2) riflessiva e antisimmetrica: per $l = 0$ e se $ x=0 => y=0$ e quindi è vero che $0<=0$ e quindi $xRx$ ma anche $x<=y$ e $y<=x => x=y$ e quindi $xRy$ e $yRx$.
sempre per $ l = 0, x=1 => y=1$ e quindi è vero che $1<=1$ e così via...
3) transitiva se $l = 1$ e $x = 1 => y = 2$ e $x <= y$, se $l = 2$ e $x = 2 => y =4$. In questo caso $xRy$ e $yRz$
perché $1<=2$ e $2<=4$. Si nota però anche $xRz$ perché $1<=4$ è una coppia di $R sube NNxNN$ che si può trovare con $x = 1$ e $l = 3$.
(Se ci sono degli errori nel mio ragionamento es: magari ho inteso male $R(x,x)$ vi prego, ditemelo
)
Fino a qui penso di aver capito che cos'è una relazione d'ordine ma, non riesco a capire la differenza tra una normale relazione d'ordine (definita anche come parziale) ed una totale.
Una relazione d'ordine totale ha come aggiunta alla definizione precedente che $AA x,y in X, x<=y$ e $y<=x$.
Ma non è già così in "automatico"? Voglio dire, se ho delle coppie di valori $(x,y)$, se $x$ non è $>= y$ allora $y>=x$ per forza, no?
Ringrazio in anticipo per la risposta e spero di essermi fatto capire a dovere.
Buona serata a tutti.
Per quello che ho capito io, una relazione $\R$ è un sottoinsieme del prodotto cartesiano di due insiemi $AxB$.
Se $(a,b) in R $ con $a in A$ e $b in B$ allora si dice che $a$ è in relazione $R$ con $b$ ($a R b$).
Una relazione d'ordine è una relazione che viene definita su un insieme $A$ (ovvero $R sube A x A$ con $A != phi$), indicata come $(A,<=)$ e che ha le seguenti proprietà:
1)riflessiva se $R(x,x) AA x in A$ ovvero $ x <= x$
2)antisimmetrics se $R(x,y)$ e $R(y,x) => x = y$ $AA x,y in A$ ovvero $x <= y$ e $y <= x => x = y$
3)transitiva se $R(x,y)$ e $R(y,z) => R(x,z)$ ovvero $x <= y$ e $ y <= z => x <= z$
Ad esempio $(NN,<=)$ potrebbe essere definita come $EE l in NN: x+l = y$ ( specifico che per me 0 fa parte di $NN$)
$NNxNN = {(0,0),(0,1),(0,2),(0,3)....(1,0),(1,1),(1,2),(1,3)...(2,0),(2,1),(2,2)...} $ è il prodotto cartesiano di $NNxNN$
$R sube NNxNN = {(0,0),(0,1),(0,2),(0,3)....(1,1),(1,2),(1,3),(1,4),...(2,2),(2,3),(2,4)....(3,3), (3,4),(3,5)...(100,100),(100,101)...}$
è il sottoinsieme $R$ di $NNxNN$ ovvero la nostra relazione.
Si può verificare che è di ordine perché le 3 proprietà che la contraddistinguono sono verificate:
1,2) riflessiva e antisimmetrica: per $l = 0$ e se $ x=0 => y=0$ e quindi è vero che $0<=0$ e quindi $xRx$ ma anche $x<=y$ e $y<=x => x=y$ e quindi $xRy$ e $yRx$.
sempre per $ l = 0, x=1 => y=1$ e quindi è vero che $1<=1$ e così via...
3) transitiva se $l = 1$ e $x = 1 => y = 2$ e $x <= y$, se $l = 2$ e $x = 2 => y =4$. In questo caso $xRy$ e $yRz$
perché $1<=2$ e $2<=4$. Si nota però anche $xRz$ perché $1<=4$ è una coppia di $R sube NNxNN$ che si può trovare con $x = 1$ e $l = 3$.
(Se ci sono degli errori nel mio ragionamento es: magari ho inteso male $R(x,x)$ vi prego, ditemelo
)Fino a qui penso di aver capito che cos'è una relazione d'ordine ma, non riesco a capire la differenza tra una normale relazione d'ordine (definita anche come parziale) ed una totale.
Una relazione d'ordine totale ha come aggiunta alla definizione precedente che $AA x,y in X, x<=y$ e $y<=x$.
Ma non è già così in "automatico"? Voglio dire, se ho delle coppie di valori $(x,y)$, se $x$ non è $>= y$ allora $y>=x$ per forza, no?
Ringrazio in anticipo per la risposta e spero di essermi fatto capire a dovere.
Buona serata a tutti.
Risposte
Una relazione d'ordine totale ha come aggiunta alla definizione precedente che $∀x,y∈X,x≤y$ e $y≤x$.
E' un OR non un AND: $∀x,y∈X,x≤y$ o $y≤x$. Non devono valere entrambe, se $x≤y$ non è detto che $y≤x$.
Ma non è già così in "automatico"? Voglio dire, se ho delle coppie di valori $(x,y)$, se $x$ non è $≥y$ allora $y≥x$ per forza, no?
Non devi pensare alla relazione maggiore/minore di. $(X, ≤)$ indica una generica relazione d'ordine indicata con $≤$.
Come hai scritto una relazione d'ordine $R$ è una relazione riflessiva, antisimmetrica e transitiva (e un insieme con tale relazione è detto parzialmente ordinato). Se alla relazione d'ordine $R$ aggiungi che ogni coppia di elementi è confrontabile rispetto a $R$, allora la relazione diventa di ordine totale.
Due elementi $x, y in X$ sono confrontabili rispetto alla relazione $R$ se $(x, y) in R$ o $(y, x) in R$ (che è equivalente a dire $x≤y$ o $y≤x$ come scritto sopra).
Come esempio di relazione d'ordine non totale considera la divisibilità in $N\\{0}$: $(N\\{0}, |) = {(x, y) in R <=> x|y}$
E' una relazione d'ordine perchè valgono le 3 proprietà, ma non è totale perchè se prendi ad esempio i numeri $3, 5 in N\\{0}$ non sono confrontabili rispetto ad $R$ perchè 3 non divide 5 e 5 non divide 3.
P.S. Non credo che questa sia la sezione giusta, è più un argomento riguardante l'algebra.
Grazie mille per la tua risposta, penso di aver capito ora 
.
In pratica una relazione d'ordine è totale se posso confrontare tra di loro tutti gli elementi di $X$ e quindi $R sube NNxNN$ e $NNxNN sube R$?
Il mio esempio di prima era una relazione d'ordine parziale allora, in quanto non potevo confrontare le coppie $(1,0),(2,0),(2,1)...$ perché non fanno parte di $R$ giusto?
Se io definisco $(NN, <=)$ come $x in RR$ e $y in RR$ questa è una relazione ma non d'ordine perché non rispetta la proprietà antisimmetrica giusto?
Potresti farmi un esempio di relazione d'ordine totale?
Per quanto riguarda la sezione, chiedo scusa se ho postato in Analisi Matematica ma, nella dispensa di Analisi del mio prof. questi argomenti sono trattati e pensavo che facessero parte della materia. Algebra ce l'ho il secondo semestre (quindi penso che avrò l'occasione di ripetere un po' di cose
), comunque se è un problema posso chiedere di fare spostare la discussione.
.In pratica una relazione d'ordine è totale se posso confrontare tra di loro tutti gli elementi di $X$ e quindi $R sube NNxNN$ e $NNxNN sube R$?
Il mio esempio di prima era una relazione d'ordine parziale allora, in quanto non potevo confrontare le coppie $(1,0),(2,0),(2,1)...$ perché non fanno parte di $R$ giusto?
Se io definisco $(NN, <=)$ come $x in RR$ e $y in RR$ questa è una relazione ma non d'ordine perché non rispetta la proprietà antisimmetrica giusto?
Potresti farmi un esempio di relazione d'ordine totale?
Per quanto riguarda la sezione, chiedo scusa se ho postato in Analisi Matematica ma, nella dispensa di Analisi del mio prof. questi argomenti sono trattati e pensavo che facessero parte della materia. Algebra ce l'ho il secondo semestre (quindi penso che avrò l'occasione di ripetere un po' di cose
), comunque se è un problema posso chiedere di fare spostare la discussione.
"feiv":
In pratica una relazione d'ordine è totale se posso confrontare tra di loro tutti gli elementi di $X$ e quindi $R sube NNxNN$ e $NNxNN sube R$?
No, qui per forza sto sbagliando perché deve essere confrontabile (nel caso del tuo esempio) solamente la coppia $(3,5)$ e non $(5,3)$ perché $5<=3$ è falso.
Up. Vi chiedo scusa ma, vorrei riuscire a capire bene questa cosa. Spero di non disturbare troppo!
Detto formalmente, una relazione \(\mathcal{R}\) è totale in $A$ se per ogni paio di elementi $a,b\in A$ si ha:
\[
(a,b)\in \mathcal{R}\quad \text{oppure}\quad (b,a)\in \mathcal{R}\; ,
\]
(con disgiunzione non esclusiva, nel senso che anche entrambe le coppie $(a,b)$ e $(b,a)$ possono stare in \(\mathcal{R}\)).
Informalmente, dire che una relazione \(\mathbb{R}\) è totale in \(A\) significa poter sempre stabilire per ogni paio di elementi $a,b\in A$ se \(a\mathcal{R} b\) oppure se \(b\mathcal{R} a\).
Se \(\mathcal{R}\) è d'ordine, la totalità equivale al cosiddetto Principio di Tricotomia, nel senso che \(\mathcal{R}\) è totale se e solo se per ogni paio di elementi $a,b\in A$, vale una ed una soltanto delle condizioni:
\[
\begin{split}
a&=b\\
a\neq b &\text{ e } a\mathcal{R} b\\
a\neq b &\text{ e } b\mathcal{R} a\; .
\end{split}
\]
Usando le notazioni canoniche, una relazione d'ordine \(\mathcal{R}=\leq\) induce una relazione d'ordine stretto \(<\) in \(A\) attraverso la definizione:
\[
a
ed il Principio di Tricotomia si può scrivere dicendo che \(\leq \) è totale se e solo se per ogni paio di elementi $a,b\in A$ vale una ed una soltanto delle seguenti proposizioni:
\[
\begin{split}
a&=b\\
a &< b\\
b &< a\; .
\end{split}
\]
\[
(a,b)\in \mathcal{R}\quad \text{oppure}\quad (b,a)\in \mathcal{R}\; ,
\]
(con disgiunzione non esclusiva, nel senso che anche entrambe le coppie $(a,b)$ e $(b,a)$ possono stare in \(\mathcal{R}\)).
Informalmente, dire che una relazione \(\mathbb{R}\) è totale in \(A\) significa poter sempre stabilire per ogni paio di elementi $a,b\in A$ se \(a\mathcal{R} b\) oppure se \(b\mathcal{R} a\).
Se \(\mathcal{R}\) è d'ordine, la totalità equivale al cosiddetto Principio di Tricotomia, nel senso che \(\mathcal{R}\) è totale se e solo se per ogni paio di elementi $a,b\in A$, vale una ed una soltanto delle condizioni:
\[
\begin{split}
a&=b\\
a\neq b &\text{ e } a\mathcal{R} b\\
a\neq b &\text{ e } b\mathcal{R} a\; .
\end{split}
\]
Usando le notazioni canoniche, una relazione d'ordine \(\mathcal{R}=\leq\) induce una relazione d'ordine stretto \(<\) in \(A\) attraverso la definizione:
\[
a
ed il Principio di Tricotomia si può scrivere dicendo che \(\leq \) è totale se e solo se per ogni paio di elementi $a,b\in A$ vale una ed una soltanto delle seguenti proposizioni:
\[
\begin{split}
a&=b\\
a &< b\\
b &< a\; .
\end{split}
\]
Grazie mille gugo sei stato gentilissimo!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo