Prodotto cartesiano, relazione

Dati $S, T \subseteq X$ il prodotto cartesiano $S \times T = \{ (x,y)| x \in S \land y \in T \}$ è l’insieme delle coppie ordinate

Per insiemi finiti con $|A| = n$ e $|B| = m$ si ha $|A \times B| = |A| \cdot |B|$

Una relazione tra $S$ e $T$ è un sottoinsieme di $S \times T$

Tipi di relazione

• relazione riflessiva: $xRx$
• relazione simmetrica: $xRy \Rightarrow yRx$
• relazione antisimmetrica: $xRy, yRx \Rightarrow x = y$
• relazione transitiva: $xRy, yRz \Rightarrow xRz$
• relazione d’ordine: RAT
• relazione d’equivalenza: RST
• applicazione: $\forall x \in S , \exist! y \in T:xRy$
• successione: $\forall x \in \mathbb N , \exist! y \in T:xRy$
• relazione totale: $\forall (x,y) \in S\times T$ $xRy$
• relazione vuota: $R = \emptyset$
• relazione opposta: $(x,y) \in R^{op} \Leftrightarrow (y,x) \in R$
• relazione n-aria: $R \subseteq S \times S \times .. \times S$