[A/L] (2021/22) Relazioni - Esercizio 15

[matypist]

[LuginiAndrea]

Facile notare come $R$ non sia un ordine totale in quanto non vale $9R30, 30R9, 27R30, 30R27$.
Definiamo $R^* = aRb \Longleftrightarrow aRb \vee a \leq b$
Possiamo vedere che vale la riflessività, in quanto valeva per $R$ ed inoltre ogni $a \leq a \forall a \in A$
Vale inolte l'antisimmetria, in quanto valeva in $R$ e $\forall a, b \in A, a \leq b, b \leq a \Longrightarrow b = a$
Vale la transitività: se un numero è divisibile senza resto per un altro, vuol dire che dato $D_a$ l'insieme dei fattori primi di $a$
$aRb \Longrightarrow D_a \subseteq D_b, bRc \Longrightarrow D_b \subseteq D_c$, quindi $D_a \subseteq D_b \subseteq D_c \Longleftrightarrow D_a \subseteq D_c$. Inoltre, se $a \leq b \leq c \Longrightarrow a \leq c$

Dimostriamolo con le coppie: $9 \leq 30 \Longrightarrow 9 R^* 30$, $27 \leq 30 \Longrightarrow 27 R^* 30$
Le coppie che valevano per $R$ valgono anche per $R^*$

[CiottoloMaggico]

R è una relazione di ordine parziale, in quanto:

1. Soddisfa la proprietà riflessiva: per ogni a in A esiste aRa, ogni numero può essere diviso per se stesso.
2. Soddisfa l'anti-simmetricità: per ogni a,b in A se esiste aRb e bRa allora a = b, poichè se aRb vuol dire che a >= b quindi non può valere bRa a meno che a = b
3. Soddisfa la transitività: se esiste aRb e bRc => aRc, in quanto se aRb e bRc => c è uno dei divisori di a
4. Non soddisfa la totalità: per via dell'esistenza di coppie di incomparabili

Quindi possiamo procedere estendendo la relazione ad un'ordine totale come segue: