Produto cartesiano

---

O produto cartesiano entre dois conjuntos $A$ e $B$, denotado como $A\times B$, é o conjunto de todos os pares ordenados $(a,b)$, onde $a$ pertence ao conjunto $A$ e $b$ pertence ao conjunto $B$.

Formalmente, podemos definir como:

$$A\times B=\{(a,b)\mid a\in A,b\in B\}$$

Exemplo com dois conjuntos

Sejam os conjuntos:

$$A=\{2,4\},B=\{2,3,5\}$$

O produto cartesiano entre $A$ e $B$ resulta no conjunto:

$$A\times B=\{(2,2),(2,3),(2,5),(4,2),(4,3),(4,5)\}$$

O número de elementos de $A\times B$ é dado pelo produto do número de elementos de $A$ e $B$:

$$|A\times B|=|A|\cdot |B|$$

Neste caso:

$$|A\times B|=2\cdot 3=6$$

Generalizando

O produto cartesiano pode ser estendido para mais de dois conjuntos:

$$A\times B\times C\times \cdots \times Z$$

Cada elemento do produto cartesiano será uma tuplade $n$ posições $(a,b,c,...,z)$, onde cada elemento pertence ao respectivo conjunto.

Exemplo com três conjuntos:

Seja $C=\{1,2\}$, então:

$$A\times B\times C=\{(2,2,1),(2,2,2),(2,3,1),(2,3,2),(2,5,1),(2,5,2),(4,2,1),(4,2,2),(4,3,1),(4,3,2),(4,5,1),(4,5,2)\}$$

E o número total de elementos será:

$$|A\times B\times C|=|A|\cdot |B|\cdot |C|$$

Se substituirmos os valores:

$$|A\times B\times C|=2\cdot 3\cdot 2=12$$

NOTE

O conceito de produto cartesiano é amplamente utilizado em bancos de dados relacionais na operação de CROSS JOIN.

Referências

---

Linguagens Formais e Autômatos - Tópicos preliminares