Seja
um conjunto de
números. Seja
o conjunto de todos os subconjuntos de
de tamanho
, e seja
o conjunto de todas as
-uplas ordenadas
tal que
. Ou seja,
Defina uma bijeção
. Explique por que
é injetiva e sobrejetiva.
Passo 1
O enunciado define
como um conjunto com
elementos,
como o conjunto de todos os subconjuntos de
com exatamente
elementos, e
como o conjunto de todas as tuplas ordenadas estritamente crescentes
com
.
Queremos construir uma bijeção e mostrar que ela é injetiva e sobrejetiva.
Queremos construir uma bijeção
Passo 2
Definimos
de modo que, para cada subconjunto
,
ordenamos seus elementos em ordem crescente
ordenamos seus elementos em ordem crescente
e tomamos
Essa definição é bem-definida porque, num conjunto finito, existe exatamente uma forma de listar seus elementos em ordem estrita crescente.
Passo 3
(Injetividade)
Suponha que e que
Suponha que
Então as tuplas ordenadas obtidas de
e de
coincidem termo a termo. Como cada uma dessas tuplas é a lista crescente dos elementos do subconjunto correspondente, segue-se que
Assim, não existem dois subconjuntos distintos em
que sejam enviados para a mesma tupla em
. Logo,
é injetiva.
Passo 4
(Sobrejetividade)
Considere qualquer tupla
.
Por definição, esses são todos distintos e estão em ordem crescente.
Forme o subconjunto
Considere qualquer tupla
Por definição, esses
Forme o subconjunto
Ao aplicarmos
em
, como já estão em ordem crescente, obtemos
Portanto, cada elemento de
é imagem de algum elemento de
, e
é sobrejetiva.
Resposta
A bijeção
é
onde
é a ordenação crescente dos elementos de
.
Ela é injetiva porque duas imagens iguais implicam subconjuntos iguais, e sobrejetiva porque toda tupla crescente vem do subconjunto
.
Ela é injetiva porque duas imagens iguais implicam subconjuntos iguais, e sobrejetiva porque toda tupla crescente