LogicaUniPR - Guida Interattiva

Definizione di Relazione Binaria

Una relazione binaria $R$ da un insieme $A$ a un insieme $B$ è un sottoinsieme del prodotto cartesiano $A \times B$. Cioè, $R \subseteq A \times B$. Se $(x,y) \in R$, diciamo che $x$ è in relazione $R$ con $y$, e possiamo scrivere $xRy$.

Spesso consideriamo relazioni su un singolo insieme $A$, ovvero $R \subseteq A \times A$.

Esempio: Sia $A = \{a, g, e, l\}$ e $B = \{b\}$. Se $R(x,y) \iff$ "$x$ è una vocale e $y$ è una consonante", allora la relazione $R$ (vista come insieme di coppie) è $C = \{(a,b), (e,b)\}$. Se $R'$ è definita su $A \times A$ come $R'(x,y) \iff$ "$x$ è una vocale e $y$ è una consonante", allora $C' = \{(a,g), (a,l), (e,g), (e,l)\}$.

Proprietà delle Relazioni (su un insieme $A$)

Una relazione $R \subseteq A \times A$ può avere le seguenti proprietà:

• Riflessiva: Ogni elemento è in relazione con se stesso.
  $\forall x \in A: (x,x) \in R$ (o $xRx$).
  Esempio: La relazione "$=$" (uguaglianza) è riflessiva. La relazione "divide" ($|$) su $\mathbb{N} \setminus \{0\}$ è riflessiva ($x|x$ perché $x = 1 \cdot x$).
• Simmetrica: Se $x$ è in relazione con $y$, allora $y$ è in relazione con $x$.
  $\forall x,y \in A: (xRy \Rightarrow yRx)$.
  Esempio: La relazione "$=$" è simmetrica. La relazione "essere compagno di banco di" è simmetrica.
• Antisimmetrica: Se $x$ è in relazione con $y$ e $y$ è in relazione con $x$, allora $x$ e $y$ devono essere lo stesso elemento.
  $\forall x,y \in A: ((xRy \wedge yRx) \Rightarrow x=y)$.
  Esempio: La relazione "$\le$" (minore o uguale) sui numeri reali è antisimmetrica. La relazione "divide" ($|$) sui numeri naturali positivi è antisimmetrica (se $x|y$ e $y|x$, e $x,y > 0$, allora $x=y$).
• Transitiva: Se $x$ è in relazione con $y$ e $y$ è in relazione con $z$, allora $x$ è in relazione con $z$.
  $\forall x,y,z \in A: ((xRy \wedge yRz) \Rightarrow xRz)$.
  Esempio: Le relazioni "$=$", "$\le$", "$<$", "|" sono transitive.

Relazioni di Equivalenza

Una relazione $R$ su un insieme $A$ è una **relazione di equivalenza** se è:

1. Riflessiva
2. Simmetrica
3. Transitiva

Le relazioni di equivalenza raggruppano elementi "simili" o "indistinguibili" rispetto a una certa caratteristica.

Classi di Equivalenza

Se $R$ è una relazione di equivalenza su $A$, per ogni elemento $x \in A$, la **classe di equivalenza** di $x$, denotata con $[x]_R$ o semplicemente $[x]$, è l'insieme di tutti gli elementi $y \in A$ che sono in relazione con $x$:
$[x]_R = \{ y \in A \mid xRy \}$.

Le classi di equivalenza formano una **partizione** dell'insieme $A$, il che significa che:

• Ogni elemento di $A$ appartiene ad almeno una classe di equivalenza (infatti $x \in [x]$ per la riflessività).
• Due classi di equivalenza o sono identiche o sono disgiunte (non hanno elementi in comune). Cioè, se $[x] \cap [y] \neq \emptyset$, allora $[x] = [y]$.
• L'unione di tutte le classi di equivalenza distinte restituisce l'intero insieme $A$.

L'insieme di tutte le classi di equivalenza è chiamato **insieme quoziente** $A/R$.

Esempio 1 (Uguaglianza): La relazione $R(x,y) \iff x=y$ su un insieme $A$ è una relazione di equivalenza. Ogni classe di equivalenza $[x]$ contiene solo l'elemento $x$ stesso, cioè $[x] = \{x\}$.

Esempio 2 (Congruenza modulo $n$): Sia $R$ su $\mathbb{N}$ definita da $xRy \iff x \pmod{n} = y \pmod{n}$ (cioè $x$ e $y$ hanno lo stesso resto nella divisione per $n$). Questa è una relazione di equivalenza. Le classi di equivalenza sono $n$: $[0], [1], \dots, [n-1]$. Per esempio, se $n=10$, le classi sono 10, e la classe $[3]$ contiene $\{3, 13, 23, \dots\}$.

Esempio 3 (Equipotenza tra insiemi): La relazione $R(A,B) \iff |A|=|B|$ (A e B hanno la stessa cardinalità, cioè esiste una funzione biunivoca tra A e B) è una relazione di equivalenza sull'insieme di tutti gli insiemi. Le classi di equivalenza raggruppano tutti gli insiemi con lo stesso "numero" di elementi (finiti o infiniti).

Relazioni d'Ordine

Una relazione $R$ su un insieme $A$ è una **relazione d'ordine** (o ordinamento) se è:

1. Riflessiva
2. Antisimmetrica
3. Transitiva

Un insieme $A$ con una relazione d'ordine $R$ è detto **insieme ordinato**, e si indica con $(A, R)$.

Ordine Totale vs. Ordine Parziale

• Un ordinamento $R$ su $A$ è **totale** (o lineare) se per ogni coppia di elementi $x,y \in A$, si ha che $xRy$ oppure $yRx$ (cioè, tutti gli elementi sono confrontabili).
  Esempio: $(\mathbb{N}, \le)$ è totalmente ordinato.
• Un ordinamento $R$ su $A$ è **parziale** se non è totale, cioè esistono almeno due elementi $x,y \in A$ tali per cui né $xRy$ né $yRx$ (non sono confrontabili). Un insieme parzialmente ordinato è detto anche **POSET**.
  Esempio: La relazione "divide" ($|$) sull'insieme $D_{12} = \{1,2,3,4,6,12\}$ è un ordine parziale (es. 2 non divide 3, e 3 non divide 2).
  Esempio: La relazione di inclusione ($\subseteq$) sull'insieme delle parti $\mathcal{P}(S)$ di un insieme $S$ (con $|S| \ge 2$) è un ordine parziale.

Diagrammi di Hasse

Per insiemi finiti parzialmente ordinati, si possono usare i **diagrammi di Hasse** per una rappresentazione grafica. Si omettono gli archi riflessivi e quelli deducibili per transitività, e si posizionano gli elementi "superiori" più in alto.

Esempio ($D_{12}, |$):
Il diagramma di Hasse per $D_{12}=\{1,2,3,4,6,12\}$ con la relazione di divisibilità mostra 1 in basso, collegato a 2 e 3. Il 2 è collegato a 4 e 6. Il 3 è collegato a 6. Sia 4 che 6 sono collegati a 12.

      12
     /  \
    4    6
   /    / \
  2    /   3
   \  /   /
    \/   /
     1
                        

Elementi Minimali, Massimali, Minimo e Massimo

In un insieme ordinato $(A,R)$:

• $m \in A$ è **minimale** se non c'è nessun $x \in A$ (con $x \ne m$) tale che $xRm$.
• $M \in A$ è **massimale** se non c'è nessun $x \in A$ (con $x \ne M$) tale che $MRx$.
• $m_0 \in A$ è il **minimo** se $m_0Rx$ per ogni $x \in A$. Se esiste, è unico ed è l'unico minimale.
• $M_0 \in A$ è il **massimo** se $xRM_0$ per ogni $x \in A$. Se esiste, è unico ed è l'unico massimale.

In $(D_{12}, |)$: 1 è il minimo (e unico minimale). 12 è il massimo (e unico massimale).
In $(\mathcal{P}(\{a,b\}), \subseteq)$: $\emptyset$ è il minimo. $\{a,b\}$ è il massimo.
Considera $D=\{2,3,4,5,6\}$ con la relazione di divisibilità. Minimali: 2, 3, 5. Massimali: 4, 6, 5. Non ci sono minimo né massimo.