Seja V um alfabeto e sejam A e B subconjuntos de V^{*}. Mostre que |A B| \leq|A \| B|.

Passo 1

O enunciado trabalha com linguagens (subconjuntos de V^*) e pede para mostrar que o tamanho da linguagem concatenada AB nunca ultrapassa o produto dos tamanhos de A e de B. Vamos usar dois fatos fundamentais de teoria de conjuntos e cardinalidades:
  1. Para toda função f\colon X\to Y, vale
|\mathrm{Im}(f)|\le|X|.
  1. O cardinal do produto cartesiano satisfaz
|A\times B|=|A|\;|\!B|.

Passo 2

Definimos a linguagem concatenada por
AB=\{\,xy\mid x\in A,\;y\in B\}.
Agora considere a função de concatenação
f\colon A\times B\longrightarrow V^*,\quad f(x,y)=xy.
Pela definição, a imagem de f é exatamente AB:
\mathrm{Im}(f)=\{\,f(x,y)\mid(x,y)\in A\times B\} = AB.

Passo 3

Pelo fato geral de funções, temos
|AB| = |\mathrm{Im}(f)| \le |A\times B|.

Passo 4

Pelo teorema do tamanho do produto cartesiano,
|A\times B| = |A|\;|\!B|.

Passo 5

Combinando os resultados dos passos anteriores chega-se a
|AB| \le |A\times B| = |A|\;|\!B|.

Resposta

|AB|\le|A|\;|\!B|.

Exercícios de Livros Relacionados