Ordine totale o reticolo?

[folli88]

Ciao a tutti!
Ho la seguente relazione $ rho $ su $ ZZ xx NN $ :

$ (a,b) rho (c,d) $ quando $ a < c $ oppure $ a = c $ e $ d | b $

devo verificare se la relazione è un ordine totale oppure un reticolo.
Non sono riuscito a capire come dimostrare la totalità della relazione per quanto riguarda l'ordine totale. Invece per la dimostrazione delle proprietà riflessiva, antisimmetrica e transitiva nessun problema.

Qualcuno è in grado di aiutarmi?

[mistake89]

Beh devi chiederti se tutte le coppie possibili in $ZZ \times NN$ sono effettivamente confrontabili...

Ti basta trovare una coppia non confrontabile per far cadere la possibilità di ordine totale. Guarda bene la relazione!

[folli88]

aaaah..allora non avevo interpretato correttamente la definizione!

quindi ad esempio basta che c sia minore di a ed è dimostrato che non è una relazione d'ordine totale?

[folli88]

up

[Lord K]

Secondo te sono confrontabili [tex](1,2), (1,3)[/tex]?

[folli88]

no perché d non divide b...ok dovrei aver capito. Perché sia totale prendendo coppie qualsiasi la relazione deve essere sempre valida. Per quanto riguarda il reticolo?

Secondo la definizione l'insieme deve avere estremo inferiore ed estremo superiore, quindi se esiste un minimo e un massimo, no? Però a rigor di logica non mi sembra corretto dato che da come è scritto o è un ordine totale o un reticolo.

[Lord K]

Allora la definizione di reticolo (io lo chiamerò lattice) cita: un reticolo è un insieme parzialmente ordinato entro il quale esistono, dati due elementi qualsiasi [tex]x,y[/tex], un elemento [tex]s[/tex] detto supremum tale che [tex]x \leq s[/tex] e [tex]y \leq s[/tex] ed un elemento [tex]i[/tex] detto infimum tale che [tex]i \leq x[/tex] e [tex]i \leq y[/tex].

In altre parole, sia [tex](L, \leq)[/tex] un insieme parzialmente ordinato, siano [tex]x,y \in L[/tex] esistono le funzioni [tex]\vee, \wedge[/tex] tali che quale che sia la scelta di [tex]x,y \in L[/tex]:

[tex]x \leq x \vee y[/tex] ed anche [tex]y \leq x \vee y[/tex]
[tex]x \wedge y \leq x[/tex] ed anche [tex]x \wedge y \leq y[/tex]

e tali che valgono le proprietà:

Commutativa: [tex]a \vee b = b \vee a[/tex], [tex]a \wedge b = b \wedge a[/tex]
Associativa: [tex]a \wedge (b \wedge c) = (a \wedge b) \wedge c[/tex], [tex]a \vee (b \vee c) = (a \vee b) \vee c[/tex]
Leggi di assorbimento: [tex]a \vee (a \wedge b)=a[/tex], [tex]a \wedge (a \vee b)=a[/tex]

Usualmente il lattice si indica come [tex](L,\leq, \vee, \wedge)[/tex]

[folli88]

Oddio, ho letto male anche questa definizione. Avevo capito che l'insieme della relazione doveva avere estremo superiore ed estremo inferiore, e non un suo sottoinsieme composto da due elementi. Quindi (non vorrei esprimermi male!) un insieme è un reticolo se non è limitato superiormente ed inferiormente?