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
A_1\times A_2=\bigcup_{a\in A_1} \big(\{a\}\times A_2\big)
como união disjunta de |A_1|=m_1 conjuntos, cada um com m_2 elementos. Assim o número total de elementos é a soma de m_2 repetida m_1 vezes, isto é
|A_1\times A_2|= \underbrace{m_2 + m_2 + \cdots + m_2}_{m_1\\ \text{vezes}} = m_1\cdot m_2.
Isso prova o caso k=2. (Intuitivamente: para cada uma das m_1 escolhas da primeira coordenada há m_2 escolhas da segunda, total m_1m_2.)

Passo 5

Exemplo rápido para fixar a ideia (sem rigores formais, só para intuição): se A_1=\{x,y\} ( m_1=2) e A_2=\{1,2,3\} ( m_2=3), então
A_1\times A_2=\{(x,1),(x,2),(x,3),(y,1),(y,2),(y,3)\},
que tem 6=2\cdot 3 elementos. Bom para ver a lógica “escolhe primeiro elemento, depois escolhe segundo”.

Passo 6

Passo indutivo: assumir verdadeiro para k-1 e provar para k.
Indução: suponha que, para algum k\ge 2, o produto cartesiano de k-1 conjuntos finitos satisfaça
\left|\prod_{i=1}^{k-1} A_i\right| = m_1\cdot m_2\cdots m_{k-1}.
Considere então o produto com mais um fator:
\prod_{i=1}^{k} A_i = \Big(\prod_{i=1}^{k-1} A_i\Big)\times A_k.
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,
\left|\prod_{i=1}^{k} A_i\right| = \left|\prod_{i=1}^{k-1} A_i\right|\cdot |A_k| = \big(m_1\cdot m_2\cdots m_{k-1}\big)\cdot m_k.
Multiplicar é associativo, portanto
\left|\prod_{i=1}^{k} A_i\right| = m_1\cdot m_2\cdots m_{k-1}\cdot m_k = \prod_{i=1}^{k} m_i.
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.

Exercícios relacionados