Sejam
conjuntos enumeráveis. Prove que
é enumerável.
Passo 1
Então, a gente tem um problema envolvendo conjuntos enumeráveis. Especificamente, temos
, que são conjuntos enumeráveis, e queremos provar que o produto cartesiano desses conjuntos, ou seja,
, também é enumerável. Para resolver isso, vamos precisar entender o que significa um conjunto ser enumerável e como construir uma lista que consiga listar todos os elementos desse produto cartesiano.
Passo 2
Primeiro, vamos lembrar o que é um conjunto enumerável. Um conjunto é enumerável se conseguimos colocar seus elementos em uma sequência, como uma lista infinita:
. Isso significa que conseguimos contar os elementos, mesmo que haja infinitos.
Passo 3
Agora, o que é um produto cartesiano? O produto cartesiano de vários conjuntos, como
, consiste em todas as tuplas
onde cada
pertence ao conjunto
. Por exemplo, se temos dois conjuntos, o produto cartesiano seria todas as combinações possíveis de pares
.
Passo 4
Como queremos provar que esse produto cartesiano é enumerável, vamos usar uma técnica conhecida como contagem por passos múltiplos ou intercalamento. A ideia é que, se cada conjunto
é enumerável, podemos listar todas as possíveis combinações das tuplas de forma a não deixar nenhum elemento de fora.
Passo 5
Para visualizar isso, imagine que cada conjunto
tem seus elementos listados como
. Então, uma tupla no produto cartesiano seria
,
, e assim por diante.
Passo 6
Podemos construir uma lista que percorre todas essas tuplas de forma organizada. Uma maneira de fazer isso é ordenar as tuplas pela soma dos índices, ou usando alguma outra regra que garanta que cada tupla seja eventualmente listada. Como há apenas um número finito de conjuntos (
), essa ordenação é possível e não deixa passar nenhuma tupla.
Passo 7
Assim, conseguimos criar uma sequência infinita que inclui todas as tuplas do produto cartesiano, sem repetir nenhuma e sem deixar nenhuma de fora. Isso mostra que o produto cartesiano
é, de fato, enumerável.
Resposta
Portanto, provamos que o produto cartesiano de
conjuntos enumeráveis é também enumerável.