Seja S um conjunto de n números. Seja X o conjunto de todos os subconjuntos de S de tamanho k, e seja Y o conjunto de todas as k-uplas ordenadas (s1, s2, ldots, sk) tal que s1<s2<ldots<sk. Ou seja,
X & =s1, s2, ldots, sk>si in S e todos os si s são distintos , e Y & =(s1, s2, ldots, sk) mid si in S e s1, s2, ldots, sk ã
Defina uma bijeção f: X Y. Explique por que f é injetiva e sobrejetiva.

Passo 1

O enunciado define S como um conjunto com n elementos,
X como o conjunto de todos os subconjuntos de S com exatamente k elementos, e
Y como o conjunto de todas as tuplas ordenadas estritamente crescentes
l(s1,s2,dots,skr) com s1<s2<cdots<sk.
Queremos construir uma bijeção fcolon Xto Y e mostrar que ela é injetiva e sobrejetiva.

Passo 2

Definimos
fcolon Xto Y
de modo que, para cada subconjunto
A=a1,a2,dots,akin X,
ordenamos seus elementos em ordem crescente
t1<t2<cdots<tk,
e tomamos
f(A)=(t1,t2,dots,tk)in Y
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 A,Bin X e que
f(A)=f(B)
Então as tuplas ordenadas obtidas de A e de B coincidem termo a termo. Como cada uma dessas tuplas é a lista crescente dos elementos do subconjunto correspondente, segue-se que
A=B
Assim, não existem dois subconjuntos distintos em X que sejam enviados para a mesma tupla em Y. Logo, f é injetiva.

Passo 4

(Sobrejetividade)
Considere qualquer tupla
l(s1,s2,dots,skr)in Y.
Por definição, esses si são todos distintos e estão em ordem crescente.
Forme o subconjunto
A=s1,s2,dots,skin X
Ao aplicarmos f em A, como já estão em ordem crescente, obtemos
f(A)=(s1,s2,dots,sk)
Portanto, cada elemento de Y é imagem de algum elemento de X, e f é sobrejetiva.

Resposta

A bijeção fcolon Xto Y é
fl(s1,dots,skr)=(t1,dots,tk),
onde t1<cdots<tk é a ordenação crescente dos elementos de s1,dots,sk.
Ela é injetiva porque duas imagens iguais implicam subconjuntos iguais, e sobrejetiva porque toda tupla crescente (s1,dots,sk) vem do subconjunto s1,dots,sk.

Exercícios de Livros Relacionados