LogicaUniPR - Guida Interattiva

3.1 Relazioni Binarie: Mettere in Collegamento gli Elementi

Ricordi il prodotto cartesiano $A \times B$ dal Capitolo 2? Era l'insieme di tutte le possibili coppie ordinate $(a,b)$ dove $a \in A$ e $b \in B$. Una relazione binaria $R$ da un insieme $A$ a un insieme $B$ non è altro che un qualsiasi sottoinsieme di $A \times B$.

Formalmente: $R \subseteq A \times B$.

Se una coppia $(a,b)$ appartiene alla relazione $R$ (cioè $(a,b) \in R$), diciamo che "$a$ è in relazione $R$ con $b$" e possiamo anche scriverlo in modo più compatto come $aRb$. Se la coppia non appartiene alla relazione, scriviamo $a \not R b$.

Esempio: Siano $A = \{\text{Anna, Bruno, Carla}\}$ e $B = \{\text{Gatto, Cane}\}$. Definiamo una relazione $R_{possiede} \subseteq A \times B$ come "$x$ possiede $y$". Se Anna possiede un Gatto e Bruno possiede un Cane, allora:
$R_{possiede} = \{(\text{Anna, Gatto}), (\text{Bruno, Cane})\}$.
Quindi, $\text{Anna } R_{possiede} \text{ Gatto}$ è vero, ma $\text{Carla } R_{possiede} \text{ Cane}$ è falso (in questo esempio).

Molto spesso, siamo interessati a relazioni definite su un singolo insieme $A$. In questo caso, la relazione $R$ è un sottoinsieme di $A \times A$ (cioè $R \subseteq A \times A$). Questo significa che mettiamo in relazione elementi dello stesso insieme.

Esempio: Sia $A = \{1, 2, 3\}$. Definiamo la relazione $R_{minore} \subseteq A \times A$ come "$x$ è minore di $y$" (cioè $x < y$).
$R_{minore} = \{(1,2), (1,3), (2,3)\}$.
Quindi, $1 R_{minore} 2$ è vero, ma $2 R_{minore} 1$ è falso, e $3 R_{minore} 3$ è falso.

3.2 Proprietà Fondamentali delle Relazioni (su un Insieme $A$)

Quando una relazione $R$ è definita su un singolo insieme $A$ (cioè $R \subseteq A \times A$), possiamo analizzare alcune sue proprietà strutturali importanti. Queste proprietà ci aiutano a classificare le relazioni e a capirne il comportamento.

• 1. Riflessiva: Una relazione $R$ su $A$ è riflessiva se ogni elemento di $A$ è in relazione con se stesso.
  Formalmente: $\forall x \in A, (x,x) \in R$ (oppure $xRx$).
  Domanda chiave: "Ogni elemento è in relazione con sé stesso?"
  Esempio: La relazione "$\le$" (minore o uguale) sui numeri interi $\mathbb{Z}$ è riflessiva, perché per ogni intero $x$, $x \le x$ è vero. La relazione "$<$" (minore stretto) non è riflessiva, perché $x < x$ non è mai vero.
• 2. Simmetrica: Una relazione $R$ su $A$ è simmetrica se, ogni volta che $x$ è in relazione con $y$, allora anche $y$ è in relazione con $x$. La relazione "va in entrambe le direzioni".
  Formalmente: $\forall x, y \in A, (xRy \Rightarrow yRx)$.
  Domanda chiave: "Se c'è una freccia da $x$ a $y$, c'è sempre anche una freccia da $y$ a $x$?"
  Esempio: La relazione "essere sposato con" è simmetrica (se A è sposato con B, B è sposato con A). La relazione "essere genitore di" non è simmetrica.
• 3. Antisimmetrica: Una relazione $R$ su $A$ è antisimmetrica se, le uniche volte in cui $x$ è in relazione con $y$ e contemporaneamente $y$ è in relazione con $x$, è perché $x$ e $y$ sono in realtà lo stesso elemento. Non ci possono essere "frecce bidirezionali" tra elementi distinti.
  Formalmente: $\forall x, y \in A, ((xRy \wedge yRx) \Rightarrow x=y)$.
  Domanda chiave: "Se ci sono frecce in entrambe le direzioni tra $x$ e $y$, allora $x$ e $y$ sono la stessa cosa?"
  Esempio: La relazione "$\le$" sui numeri interi $\mathbb{Z}$ è antisimmetrica: se $x \le y$ e $y \le x$, allora deve essere $x=y$. La relazione "essere amico di" non è necessariamente antisimmetrica (due persone diverse possono essere amiche tra loro).
  Attenzione: Antisimmetrica non è il contrario di simmetrica! Una relazione può essere entrambe (es. l'uguaglianza), nessuna delle due, o solo una.
• 4. Transitiva: Una relazione $R$ su $A$ è transitiva se, ogni volta che $x$ è in relazione con $y$ e $y$ è in relazione con $z$, allora anche $x$ è in relazione con $z$. Se puoi andare da $x$ a $y$, e da $y$ a $z$, allora puoi andare direttamente da $x$ a $z$.
  Formalmente: $\forall x, y, z \in A, ((xRy \wedge yRz) \Rightarrow xRz)$.
  Domanda chiave: "Se c'è un percorso da $x$ a $z$ passando per $y$, c'è anche un collegamento diretto da $x$ a $z$?"
  Esempio: La relazione "$\le$" è transitiva: se $x \le y$ e $y \le z$, allora $x \le z$. La relazione "essere antenato di" è transitiva. La relazione "essere amico di" non è necessariamente transitiva.

3.3 Relazioni di Equivalenza: Raggruppare Elementi Simili

Una relazione $R$ su un insieme $A$ si dice relazione di equivalenza se soddisfa contemporaneamente tre proprietà:

1. È Riflessiva ($\forall x \in A, xRx$)
2. È Simmetrica ($\forall x,y \in A, xRy \Rightarrow yRx$)
3. È Transitiva ($\forall x,y,z \in A, (xRy \wedge yRz) \Rightarrow xRz$)

Le relazioni di equivalenza sono incredibilmente utili perché ci permettono di "raggruppare" elementi di un insieme che, rispetto a un certo criterio (definito dalla relazione), sono considerati "uguali" o "indistinguibili". Pensa all'idea di "avere lo stesso colore": tutti gli oggetti rossi sono equivalenti rispetto al colore rosso.

3.3.1 Classi di Equivalenza: I Gruppi di Elementi Simili

Se $R$ è una relazione di equivalenza su un insieme $A$, per ogni elemento $a \in A$, possiamo definire la sua **classe di equivalenza**. La classe di equivalenza di $a$, denotata con $[a]_R$ (o semplicemente $[a]$ se $R$ è chiara dal contesto), è l'insieme di tutti gli elementi $x \in A$ che sono in relazione $R$ con $a$.

Formalmente: $[a]_R = \{x \in A \mid aRx \}$. (A causa della simmetria, è equivalente a $\{x \in A \mid xRa\}$).

Esempio: Congruenza modulo 3 su $\mathbb{N}$
Sia $A = \mathbb{N} = \{0, 1, 2, 3, 4, 5, 6, \dots\}$.
Definiamo $xRy \iff x \pmod 3 = y \pmod 3$ (cioè $x$ e $y$ hanno lo stesso resto quando divisi per 3). Questa è una relazione di equivalenza.
Le classi di equivalenza sono:

• $[0]_R = \{0, 3, 6, 9, \dots\} = \{x \in \mathbb{N} \mid x \pmod 3 = 0\}$ (i multipli di 3)
• $[1]_R = \{1, 4, 7, 10, \dots\} = \{x \in \mathbb{N} \mid x \pmod 3 = 1\}$
• $[2]_R = \{2, 5, 8, 11, \dots\} = \{x \in \mathbb{N} \mid x \pmod 3 = 2\}$

3.3.2 Partizione e Insieme Quoziente

Le classi di equivalenza indotte da una relazione $R$ su $A$ hanno proprietà notevoli:

• Ogni elemento $a \in A$ appartiene alla propria classe di equivalenza ($a \in [a]$), grazie alla riflessività.
• Due classi di equivalenza $[a]$ e $[b]$ sono o completamente identiche ($[a]=[b]$) oppure completamente separate (disgiunte, $[a] \cap [b] = \emptyset$). Non possono sovrapporsi parzialmente. Questo accade se $aRb$.
• L'unione di tutte le classi di equivalenza distinte restituisce l'intero insieme $A$.

Queste proprietà significano che le classi di equivalenza formano una partizione di $A$: dividono $A$ in "fette" non sovrapposte che ricoprono tutto $A$. L'insieme che ha come elementi tutte queste classi di equivalenza distinte è chiamato insieme quoziente di $A$ rispetto a $R$, e si denota con $A/R$.

Continuando l'esempio della congruenza modulo 3:
$A/R = \{[0]_R, [1]_R, [2]_R\}$. L'insieme quoziente ha 3 elementi.

3.4 Relazioni d'Ordine: Confrontare e Ordinare

Un altro tipo fondamentale di relazione è la relazione d'ordine. Una relazione $R$ su un insieme $A$ è una relazione d'ordine (o semplicemente un **ordinamento**) se soddisfa le seguenti tre proprietà:

1. È Riflessiva ($\forall x \in A, xRx$)
2. È Antisimmetrica ($\forall x,y \in A, (xRy \wedge yRx) \Rightarrow x=y$)
3. È Transitiva ($\forall x,y,z \in A, (xRy \wedge yRz) \Rightarrow xRz$)

Un insieme $A$ munito di una relazione d'ordine $R$ si chiama **insieme ordinato** e si indica con la coppia $(A,R)$.

Esempio classico: La relazione "minore o uguale a" ($\le$) sull'insieme dei numeri naturali $\mathbb{N}$ è una relazione d'ordine.

• Riflessiva: $x \le x$ per ogni $x \in \mathbb{N}$. (Vero)
• Antisimmetrica: Se $x \le y$ e $y \le x$, allora $x=y$. (Vero)
• Transitiva: Se $x \le y$ e $y \le z$, allora $x \le z$. (Vero)

Esempio: Relazione di Divisibilità Sia $D_6 = \{1, 2, 3, 6\}$ l'insieme dei divisori di 6. La relazione "$x$ divide $y$" (scritta $x|y$) è una relazione d'ordine su $D_6$.

• Riflessiva: $x|x$ (es. $2|2$ perché $2=1 \cdot 2$). (Vero)
• Antisimmetrica: Se $x|y$ e $y|x$ (e $x,y \in D_6$, quindi positivi), allora $x=y$. (Vero)
• Transitiva: Se $x|y$ e $y|z$, allora $x|z$. (Vero)

3.4.1 Ordine Totale (o Lineare) vs. Ordine Parziale

Non tutti gli ordinamenti sono uguali. Alcuni ci permettono di confrontare qualsiasi coppia di elementi, altri no.

• Un ordinamento $R$ su $A$ è totale (o lineare) se per ogni coppia di elementi $x, y \in A$, vale sempre che $xRy$ oppure $yRx$. In pratica, puoi sempre dire se $x$ "viene prima o è uguale" a $y$, o viceversa.
  Esempio: $(\mathbb{N}, \le)$ è totalmente ordinato. Dati due numeri naturali qualsiasi, uno è sempre minore o uguale all'altro.
• Un ordinamento $R$ su $A$ è parziale se non è totale. Ciò significa che esistono almeno due elementi $x, y \in A$ tali per cui né $xRy$ né $yRx$ vale. Questi elementi sono detti inconfrontabili. Un insieme con un ordine parziale è spesso chiamato POSET (Partially Ordered Set).
  Esempio: $(D_6, |)$ è parzialmente ordinato. Ad esempio, $2$ e $3$ sono in $D_6$. $2$ non divide $3$, e $3$ non divide $2$. Quindi $2$ e $3$ sono inconfrontabili rispetto alla relazione di divisibilità in $D_6$.
• Esempio: La relazione di inclusione $\subseteq$ sull'insieme delle parti $\mathcal{P}(S)$ di un insieme $S$ con almeno due elementi è un ordine parziale. Se $S=\{a,b,c\}$, allora $\{a\}$ e $\{b\}$ sono inconfrontabili (nessuno dei due è sottoinsieme dell'altro).

3.4.2 Diagrammi di Hasse: Visualizzare gli Ordini Parziali

Per gli insiemi finiti parzialmente ordinati, i diagrammi di Hasse offrono una rappresentazione grafica intuitiva. Per costruirli:

1. Rappresenta ogni elemento dell'insieme con un punto (nodo).
2. Disponi i punti in modo che se $xRy$ (e $x \neq y$), allora $y$ sia disegnato più in alto di $x$.
3. Traccia un segmento (arco) da $x$ a $y$ solo se $xRy$ e non esiste un altro elemento $z$ (diverso da $x$ e $y$) tale che $xRz$ e $zRy$. In pratica, si disegnano solo le relazioni "dirette" o "immediate", omettendo quelle che si possono dedurre per transitività.
4. Non si disegnano gli anelli su ogni nodo (cioè le relazioni riflessive $xRx$).

Diagramma di Hasse per $(D_6, |)$:
$D_6 = \{1, 2, 3, 6\}$
Relazioni dirette: $1|2$, $1|3$, $2|6$, $3|6$.
(Omettiamo $1|6$ perché è implicata da $1|2$ e $2|6$, o da $1|3$ e $3|6$).

      6
     / \
    2   3
     \ /
      1
                        

3.4.3 Elementi Speciali in Insiemi Ordinati

In un insieme ordinato $(A,R)$, possiamo identificare alcuni elementi con proprietà particolari:

• Un elemento $m \in A$ è minimale se non c'è nessun altro elemento $x \in A$ (con $x \neq m$) che lo precede, cioè tale che $xRm$. Formalmente: $\forall x \in A, (xRm \Rightarrow x=m)$.
• Un elemento $M \in A$ è massimale se non c'è nessun altro elemento $x \in A$ (con $x \neq M$) che lo segue, cioè tale che $MRx$. Formalmente: $\forall x \in A, (MRx \Rightarrow x=M)$.
• Un elemento $m_0 \in A$ è il minimo (o elemento minimo) se precede (o è uguale a) tutti gli altri elementi dell'insieme. Formalmente: $\forall x \in A, m_0Rx$. Se esiste, il minimo è unico ed è anche l'unico elemento minimale.
• Un elemento $M_0 \in A$ è il massimo (o elemento massimo) se è preceduto da (o è uguale a) tutti gli altri elementi dell'insieme. Formalmente: $\forall x \in A, xRM_0$. Se esiste, il massimo è unico ed è anche l'unico elemento massimale.

Nota Bene:

• In un ordine parziale, possono esistere più elementi minimali e/o più elementi massimali.
• Se esiste un minimo, allora quello è l'unico elemento minimale.
• Se esiste un massimo, allora quello è l'unico elemento massimale.
• In un insieme totalmente ordinato, un elemento minimale è anche il minimo, e un elemento massimale è anche il massimo (se esistono).

Consideriamo $D=\{2,3,4,5,6\}$ con la relazione di divisibilità "$|$".
Minimali: $\{2, 3, 5\}$ (nessun altro elemento li divide, tranne 1 che non è in D).
Massimali: $\{4, 5, 6\}$ (non dividono nessun altro elemento in D).
Non c'è un minimo (es. 2 non divide 3). Non c'è un massimo (es. 4 non divide 6).

3.5 Esercizi del Capitolo 3