LogicaUniPR - Guida Interattiva

Svolgimento Dettagliato:

a) Dimostrare che $R$ è una relazione di equivalenza:

• Riflessiva: Dobbiamo verificare $\forall x \in \mathbb{Z}, xRx$.
  $xRx \iff x^2 = x^2$. Questa è un'identità, vera per ogni $x \in \mathbb{Z}$. Quindi $R$ è riflessiva.
• Simmetrica: Dobbiamo verificare $\forall x,y \in \mathbb{Z}, (xRy \Rightarrow yRx)$.
  Assumiamo $xRy$, cioè $x^2 = y^2$.
  Poiché l'uguaglianza è simmetrica, se $x^2 = y^2$, allora $y^2 = x^2$.
  Per definizione di $R$, $y^2 = x^2 \iff yRx$. Quindi $R$ è simmetrica.
• Transitiva: Dobbiamo verificare $\forall x,y,z \in \mathbb{Z}, ((xRy \wedge yRz) \Rightarrow xRz)$.
  Assumiamo $xRy$ e $yRz$.
  Questo significa $x^2 = y^2$ (da $xRy$) e $y^2 = z^2$ (da $yRz$).
  Per la transitività dell'uguaglianza, se $x^2 = y^2$ e $y^2 = z^2$, allora $x^2 = z^2$.
  Per definizione di $R$, $x^2 = z^2 \iff xRz$. Quindi $R$ è transitiva.

Poiché $R$ è riflessiva, simmetrica e transitiva, è una relazione di equivalenza.

b) Descrivere le classi di equivalenza:

• $[0]_R = \{x \in \mathbb{Z} \mid xR0\} = \{x \in \mathbb{Z} \mid x^2 = 0^2\} = \{x \in \mathbb{Z} \mid x^2 = 0\}$. L'unico intero il cui quadrato è 0 è 0 stesso. Quindi, $[0]_R = \{0\}$.
• $[1]_R = \{x \in \mathbb{Z} \mid xR1\} = \{x \in \mathbb{Z} \mid x^2 = 1^2\} = \{x \in \mathbb{Z} \mid x^2 = 1\}$. Gli interi il cui quadrato è 1 sono $1$ e $-1$. Quindi, $[1]_R = \{1, -1\}$.
• $[2]_R = \{x \in \mathbb{Z} \mid xR2\} = \{x \in \mathbb{Z} \mid x^2 = 2^2\} = \{x \in \mathbb{Z} \mid x^2 = 4\}$. Gli interi il cui quadrato è 4 sono $2$ e $-2$. Quindi, $[2]_R = \{2, -2\}$.

c) Numero di classi distinte e forma generale:

La classe $[0]_R = \{0\}$ è unica.

Per ogni $a \in \mathbb{Z}$ con $a \neq 0$, la classe di equivalenza $[a]_R = \{x \in \mathbb{Z} \mid x^2 = a^2\}$. Gli unici interi $x$ tali che $x^2 = a^2$ sono $x=a$ e $x=-a$.
Quindi, per $a \neq 0$, $[a]_R = \{a, -a\}$.
Notiamo che $[a]_R = [-a]_R$. Ad esempio, $[1]_R = \{-1, 1\}$ e $[-1]_R = \{-1, -(-1)\} = \{-1, 1\}$.
Le classi di equivalenza distinte sono quindi:
$[0]_R = \{0\}$
$[1]_R = \{1, -1\}$
$[2]_R = \{2, -2\}$
$[3]_R = \{3, -3\}$
... e così via per ogni numero naturale positivo.
C'è una classe per lo zero, e una classe per ogni coppia di interi opposti $\{n, -n\}$ dove $n \in \mathbb{N} \setminus \{0\}$.
Quindi, ci sono infinite classi di equivalenza distinte (una per ogni numero naturale, se consideriamo il rappresentante positivo o zero).
La forma generale di una classe $[a]_R$ per $a \neq 0$ è $\{a, -a\}$. Se $a=0$, è $\{0\}$.

Svolgimento Dettagliato:

$D_{20} = \{1, 2, 4, 5, 10, 20\}$.

a) $(\mathcal{P}(D_{20}), R')$ dove $X R' Y \iff |X| \le |Y|$.

• Riflessiva: $\forall X \in \mathcal{P}(D_{20}), |X| \le |X|$. Vero.
• Antisimmetrica: $\forall X,Y \in \mathcal{P}(D_{20}), (|X| \le |Y| \wedge |Y| \le |X|) \Rightarrow X=Y$?
  Se $|X| \le |Y|$ e $|Y| \le |X|$, allora $|X| = |Y|$. Ma questo non implica $X=Y$.
  Controesempio: Siano $X=\{1,2\}$ e $Y=\{1,4\}$. Entrambi sono in $\mathcal{P}(D_{20})$.
  $|X|=2$, $|Y|=2$. Quindi $|X| \le |Y|$ e $|Y| \le |X|$. Ma $X \neq Y$.
  La proprietà antisimmetrica fallisce. Quindi non è una relazione d'ordine.
• Transitiva: $\forall X,Y,Z \in \mathcal{P}(D_{20}), (|X| \le |Y| \wedge |Y| \le |Z|) \Rightarrow |X| \le |Z|$?
  Sì, questa è la proprietà transitiva dell'ordinamento $\le$ sui numeri naturali (le cardinalità). Vero.

Poiché l'antisimmetria fallisce, $R'$ non è una relazione d'ordine.

b) Dimostra che $(D_{20}, |)$ è un insieme parzialmente ordinato. È totalmente ordinato?

• Riflessiva: $\forall x \in D_{20}, x|x$. Vero ($x=1 \cdot x$).
• Antisimmetrica: $\forall x,y \in D_{20}, (x|y \wedge y|x) \Rightarrow x=y$.
  Se $x|y \implies y=k_1x$ e $y|x \implies x=k_2y$. Allora $x=(k_1k_2)x$. Poiché $x \neq 0$, $k_1k_2=1$. Essendo $x,y$ positivi, $k_1, k_2$ devono essere 1. Quindi $x=y$. Vero.
• Transitiva: $\forall x,y,z \in D_{20}, (x|y \wedge y|z) \Rightarrow x|z$.
  Se $y=k_1x$ e $z=k_2y$, allora $z=k_2(k_1x)=(k_1k_2)x$. Quindi $x|z$. Vero.

$(D_{20}, |)$ è una relazione d'ordine.
È totale? No. Ad esempio, $4 \in D_{20}$ e $5 \in D_{20}$. $4$ non divide $5$, e $5$ non divide $4$. Quindi $4$ e $5$ sono inconfrontabili. L'ordine è **parziale**.

c) Diagramma di Hasse per $(D_{20}, |)$:

                20
               /  \
              /    \
             4     10
             |   / |
             2     5
              \   /
                1
                                    

d) Elementi minimali, massimali, minimo e massimo:

• Elemento Minimale: $\{1\}$.
• Minimo: $1$.
• Elemento Massimale: $\{20\}$.
• Massimo: $20$.