Seja
um alfabeto e sejam
e
subconjuntos de
. Mostre que
.
Passo 1
O enunciado trabalha com linguagens (subconjuntos de
) e pede para mostrar que o tamanho da linguagem concatenada
nunca ultrapassa o produto dos tamanhos de
e de
. Vamos usar dois fatos fundamentais de teoria de conjuntos e cardinalidades:
- Para toda função
, vale
- O cardinal do produto cartesiano satisfaz
Passo 2
Definimos a linguagem concatenada por
Agora considere a função de concatenação
Pela definição, a imagem de
é exatamente
:
Passo 3
Pelo fato geral de funções, temos
Passo 4
Pelo teorema do tamanho do produto cartesiano,
Passo 5
Combinando os resultados dos passos anteriores chega-se a