Esercizi strutture discrete
(dal Sussidiario di Algebra e Matematica Discreta)
Alberto Carraro
April 18, 2008
Exercise 1 (8.6, pag 58). Si dimostri che se a, b, c ∈ Z e M CD(a, n) = 1 allora ab ≡nac ⇒ a ≡n c
Solution 1.
ab ≡nac ⇐⇒ n | ab − ac
⇐⇒ n | (αa + βn)(ab − ac) , perch´e ∃α, β ∈ Z . αa + βn = 1,
⇐⇒ n | αa(ab − ac) + βn(ab − ac)
⇐⇒ n | αa2(b − c) , perch´e n | βn(ab − ac),
⇐⇒ n | (b − c) , vedi (∗),
⇐⇒ b ≡n c
(∗) Sicuramente n non divide a2, perch´e n ed a sono primi tra loro. Inoltre ora mostriamo che se α | n allora α = ±1. Assumiamo α | n. Allora esiste q ∈ Z tale che αq = n, da cui αa + βαq = 1. Quindi α(a + βq) = 1. Questo `e possibile sse α e (a + βq) sono entrambi uguali a 1 o −1.
Definition 0.0.1. Sia X un insieme. Un sottoinsieme x ⊆ X `e cofinito (rispetto ad X) sse X r x `e un insieme finito.
Exercise 2 (11.12, pag 82). Sia X un insieme infinito. Definiamo Pcof(X) = {x ∈ P(X) | x cofinito }.
Dimostrare che hPcof(X), ⊆i `e un reticolo distributivo non limitato.
Solution 2. Prima di tutto mostriamo che hPcof(X), ⊆i `e un reticolo. Per questo dobbiamo trovare le operazioni inf e sup adatte.
• Vogliamo mostrare che sup{x, y} = x∪y. Sicuramente x∪y `e il pi´u piccolo insieme che contiene x ed y. Mostriamo che x ∪ y `e cofinito:
X r (x ∪ y) = (X r x) r y
Siccome x `e cofinito, (X r x) `e finito e quindi lo `e anche (X r x) r y.
• Vogliamo mostrare che inf {x, y} = x∩y. Sicuramente x∩y `e il pi´u grande insieme contenuto in x ed y. Mostriamo che x ∩ y `e cofinito:
X r (x ∩ y) = (X r x) ∪ (X r y)
Siccome x ed y sono cofiniti, sia (X r x) che (X r y) sono finiti e quindi lo `e anche la loro unione.
Sappiamo bene che l’unione e l’intersezione godono della propriet´a distributiva.
Manca solo vedere che hPcof(X), ⊆i non `e limitato. Infatti non c’`e un minimo.
Non vi sono insiemi finiti in Pcof(X) e nessun insieme infinito pu`o essere minimo rispetto all’ordinamento ⊆.
1
