Verificare se un ordinamento è totale
Salve ragazzi ho la segunte relazione d'ordine in $NxN$
$(a,b) sigma (c,d) <=> a <= c and b <= d$
Adesso devo dimostrare se l'ordinamento è totale, quindi:
$AA(x,y),(h,k) in NxN, (x,y) sigma (h,k) or (h,k) sigma (x,y)$
Direi che è d'ordine ma come lo dimostro?
Grazie anticipatamente
$(a,b) sigma (c,d) <=> a <= c and b <= d$
Adesso devo dimostrare se l'ordinamento è totale, quindi:
$AA(x,y),(h,k) in NxN, (x,y) sigma (h,k) or (h,k) sigma (x,y)$
Direi che è d'ordine ma come lo dimostro?
Grazie anticipatamente
Risposte
Proprietà Riflessiva:
[tex](a,b)\sigma(a,b) \Leftrightarrow (a \leq a \land b \leq b)[/tex]
Proprietà Antisimmetrica:
[tex](a,b)\sigma(c,d) \land (c,d)\sigma(a,b) \Rightarrow (a,b)=(c,d)[/tex]
[tex](a,b)\sigma(c,d) \Leftrightarrow (a \leq c \land b \leq d)[/tex]
[tex](c,d)\sigma(a,b) \Leftrightarrow (c \leq a \land d \leq b)[/tex]
Allora [tex](a \leq c \land b \leq d) \land (c \leq a \land d \leq b) \Rightarrow (a \leq c \leq a) \land (b \leq d \leq b) \Leftrightarrow (a,b)=(c,d)[/tex]
Proprietà Transitiva:
[tex](a,b)\sigma(c,d) \land (c,d)\sigma(e,f) \Rightarrow (a,b)\sigma(e,f)[/tex]
[tex](a,b)\sigma(c,d) \Leftrightarrow (a \leq c \land b \leq d)[/tex]
[tex](c,d)\sigma(e,f) \Leftrightarrow (c \leq e \land d \leq f)[/tex]
Allora [tex](a \leq c \land b \leq d) \land (c \leq e \land d \leq f) \Rightarrow (a \leq c \leq e) \land (b \leq d \leq f) \Leftrightarrow (a,b)\sigma(e,f)[/tex]
Proprietà Totale:
[tex](a,b)\sigma(c,d) \lor (c,d)\sigma(a,b)[/tex]
[tex](a,b)\sigma(c,d) \Leftrightarrow (a \leq c \land b \leq d)[/tex]
[tex](c,d)\sigma(a,b) \Leftrightarrow (c \leq a \land d \leq b)[/tex]
In questo caso l'operatore [tex]\lor[/tex] ci dice che questa asserzione è vera quando uno dei due disgiunti è vero o sono entrambi veri, ma in quest'ultimo caso, per la proprietà Antisimmetrica, sarebbero uguali.
Spero sia tutto corretto....
[tex](a,b)\sigma(a,b) \Leftrightarrow (a \leq a \land b \leq b)[/tex]
Proprietà Antisimmetrica:
[tex](a,b)\sigma(c,d) \land (c,d)\sigma(a,b) \Rightarrow (a,b)=(c,d)[/tex]
[tex](a,b)\sigma(c,d) \Leftrightarrow (a \leq c \land b \leq d)[/tex]
[tex](c,d)\sigma(a,b) \Leftrightarrow (c \leq a \land d \leq b)[/tex]
Allora [tex](a \leq c \land b \leq d) \land (c \leq a \land d \leq b) \Rightarrow (a \leq c \leq a) \land (b \leq d \leq b) \Leftrightarrow (a,b)=(c,d)[/tex]
Proprietà Transitiva:
[tex](a,b)\sigma(c,d) \land (c,d)\sigma(e,f) \Rightarrow (a,b)\sigma(e,f)[/tex]
[tex](a,b)\sigma(c,d) \Leftrightarrow (a \leq c \land b \leq d)[/tex]
[tex](c,d)\sigma(e,f) \Leftrightarrow (c \leq e \land d \leq f)[/tex]
Allora [tex](a \leq c \land b \leq d) \land (c \leq e \land d \leq f) \Rightarrow (a \leq c \leq e) \land (b \leq d \leq f) \Leftrightarrow (a,b)\sigma(e,f)[/tex]
Proprietà Totale:
[tex](a,b)\sigma(c,d) \lor (c,d)\sigma(a,b)[/tex]
[tex](a,b)\sigma(c,d) \Leftrightarrow (a \leq c \land b \leq d)[/tex]
[tex](c,d)\sigma(a,b) \Leftrightarrow (c \leq a \land d \leq b)[/tex]
In questo caso l'operatore [tex]\lor[/tex] ci dice che questa asserzione è vera quando uno dei due disgiunti è vero o sono entrambi veri, ma in quest'ultimo caso, per la proprietà Antisimmetrica, sarebbero uguali.
Spero sia tutto corretto....
Salve GundamRX91,
potevi fare a meno della riflessività, vedi qui, visto che la disgiunzione è inclusiva
..
Cordiali saluti
potevi fare a meno della riflessività, vedi qui, visto che la disgiunzione è inclusiva
.. Cordiali saluti
IN questo caso non è totale: poichè ho un controesempio .
Presi $(3,7)$ e $(5,5)$
$(3,7)$ non è in relazione con $(5,5)$ e
$(5,5)$ non è in relazione con $(3,7)$
Presi $(3,7)$ e $(5,5)$
$(3,7)$ non è in relazione con $(5,5)$ e
$(5,5)$ non è in relazione con $(3,7)$
Scusa ma la relazione d'ordine non è un sottoinsieme del prodotto cartesiano [tex]\sigma \subseteq \mathbb{N} \times \mathbb{N}[/tex] ? Quindi [tex]\sigma[/tex] non dovrebbe contenere solo le coppie ordinate che soddisfano la condizione [tex](a,b)\sigma(c,d) \Leftrightarrow a \le c \land b \le d[/tex] ?
"GundamRX91":
Scusa ma la relazione d'ordine non è un sottoinsieme del prodotto cartesiano [tex]\sigma \subseteq \mathbb{N} \times \mathbb{N}[/tex] ? Quindi [tex]\sigma[/tex] non dovrebbe contenere solo le coppie ordinate che soddisfano la condizione [tex](a,b)\sigma(c,d) \Leftrightarrow a \le c \land b \le d[/tex] ?
La relazione e' su $\NN\timesNN$ e quindi sara' un sottoinsieme di $(\NN\times\NN)\times(\NN\times\NN)$. Esattamente il sottoinsieme contenente le coppie di coppie in cui la prima e' in relazione con la seconda; ovvero l'insieme delle quaterne tali che la coppia formate dalle prime due componenti e' in relazione con quella formata dalla terza e dalla quarta componente.
Comunque, in definitiva, vi trovate con me che quella relazione non è totale? ( vi trovate col mio controesempio ?? ).
"gaten":
Comunque, in definitiva, vi trovate con me che quella relazione non è totale? ( vi trovate col mio controesempio ?? ).
ovvio
Grazie 
"Valerio Capraro":
[quote="GundamRX91"]Scusa ma la relazione d'ordine non è un sottoinsieme del prodotto cartesiano [tex]\sigma \subseteq \mathbb{N} \times \mathbb{N}[/tex] ? Quindi [tex]\sigma[/tex] non dovrebbe contenere solo le coppie ordinate che soddisfano la condizione [tex](a,b)\sigma(c,d) \Leftrightarrow a \le c \land b \le d[/tex] ?
La relazione e' su $\NN\timesNN$ e quindi sara' un sottoinsieme di $(\NN\times\NN)\times(\NN\times\NN)$. Esattamente il sottoinsieme contenente le coppie di coppie in cui la prima e' in relazione con la seconda; ovvero l'insieme delle quaterne tali che la coppia formate dalle prime due componenti e' in relazione con quella formata dalla terza e dalla quarta componente.[/quote]
Certo, è vero; [tex]\sigma \subseteq (\mathbb{N} \times \mathbb{N}) \times (\mathbb{N} \times \mathbb{N})[/tex].
Scusate
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo