Questão 12 \operatorname{Sejam} A_{1}, A_{2}, \ldots, A_{k}, conjuntos finitos com m_{1}, m_{2}, \ldots, m_{k} elementos, respectivamente. Mostre que o produto cartesiano \prod_{i=1}^{k} A_{i} é finito e possui m_{1} \cdot m_{2} \cdots m_{k} elementos.
Passo 1
O enunciado dá os conjuntos finitos A_{1},A_{2},\dots,A_{k} e os números inteiros positivos m_{1},m_{2},\dots,m_{k} tais que, para cada i, o conjunto A_{i} tem exatamente m_{i} elementos. Ou seja:
|A_i| = m_i\quad\text{para }i=1,\dots,k.
O que se pede:
Mostrar que o produto cartesiano \displaystyle\prod_{i=1}^{k} A_{i} é finito.
Mostrar que \displaystyle\prod_{i=1}^{k} A_{i} possui exatamente m_{1}\cdot m_{2}\cdots m_{k} elementos.
Passo 2
Primeiro, vamos lembrar direitinho o que é o produto cartesiano e o que significa “possuir n elementos”.
Definição do produto cartesiano: \displaystyle\prod_{i=1}^{k} A_{i} é o conjunto de tuplas ordenadas de comprimento k cujas coordenadas vêm dos conjuntos correspondentes. Formalmente,
\prod_{i=1}^{k} A_{i}=\{(a_{1},a_{2},\dots,a_{k}) \mid a_{i}\in A_{i}\text{ para todo }i\}.
Definição de conjunto finito e cardinalidade: dizer que um conjunto X é finito e tem n elementos significa que existe uma bijeção entre X e o conjunto \{1,2,\dots,n\}. Em notação, |X|=n.
Intuição sobre multiplicação: a igualdade m_1\cdot m_2 representa “m_2 somado a si mesmo m_1 vezes”. Vamos usar que, se um conjunto é união disjunta de m_1 partes, cada uma com m_2 elementos, então o conjunto todo tem m_1\cdot m_2 elementos (soma repetida).
Passo 3
Base simples k=1. Se k=1, então
\prod_{i=1}^{1} A_i = A_1,
que é finito por hipótese e tem |A_1|=m_1 elementos. Assim o enunciado é verdadeiro para k=1.
Passo 4
Caso k=2. Mostramos explicitamente que A_1\times A_2 é finito e que |A_1\times A_2|=m_1\cdot m_2.
Para cada elemento a\in A_1 considere o subconjunto
\{a\}\times A_2 = \{(a,b)\mid b\in A_2\}.
Esse subconjunto tem exatamente |A_2|=m_2 elementos, porque a primeira coordenada é fixada em a e a segunda percorre todos os m_2 elementos de A_2.
Observe que, se a e a' são distintos em A_1, então \{a\}\times A_2 e \{a'\}\times A_2 são disjuntos (duas tuplas com primeira coordenada diferente não podem ser iguais). Portanto podemos escrever
Pelo passo anterior (o caso em que temos apenas dois fatores), aplicado às duas partes \prod_{i=1}^{k-1} A_i e A_k, temos que o número de elementos do produto é o produto dos números de elementos de cada fator. Ou seja,
Como produto de números finitos é finito, segue que \prod_{i=1}^{k} A_i é finito.
Passo 7
Conclusão: pelo princípio da indução matemática, o resultado vale para todo k\ge 1. Ou seja, para quaisquer conjuntos finitos A_1,\dots,A_k com |A_i|=m_i vale que \prod_{i=1}^{k} A_i é finito e tem exatamente \prod_{i=1}^{k} m_i elementos.
Resposta
\displaystyle\prod_{i=1}^{k} A_{i} é finito e possui \displaystyle\prod_{i=1}^{k} m_{i} elementos.