Question

Seja A = {1, . . . , n}. Mostre que há uma bijeção entre P(A) e o produto {0, 1}^n
.
(Construa a bijeção.)

Answer 1

Explicação passo a passo:

Seja $f:~P(A)\to \{0,\,1\}^n,\,n\in\mathbb{N}^*$ uma função definida da seguinte forma:

Dado $X\in P(A),$ definimos

    $\displaystyle f(X):=(y_1,\,y_2,\,\ldots,\,y_n)$

tal que, para todo $i\in\{1,\,2,\,\ldots,\,n\}=A,$ temos

    $y_i=\left\{\begin{array}{ll}0,&\mathrm{se,\,e~somente~se~} i\not\in X\\ 1,&\mathrm{se,\,e~somente~se~} i\in X\\ \end{array}\right.$

    $\displaystyle\Longleftrightarrow\quad f(X)=\underset{i\in X~\Leftrightarrow~y_i=1}{\underset{i\not\in X~\Leftrightarrow~y_i=0}{\prod_{i\in A}}}\{y_i\}$

Obs.: O símbolo $\displaystyle\prod$ denota produto cartesiano.

Definindo desta forma, em particular, temos

    $f(\varnothing)=\{0\}^n=\underbrace{(0,\,0,\,\ldots,\,0)}_{n\mathrm{~coordenadas}}\\\\\\ f(A)=\{1\}^n=\underbrace{(1,\,1,\,\ldots,\,1)}_{n\mathrm{~coordenadas}}$

Resta-nos mostrar agora que $f$ da forma que está definida é uma bijeção de $P(A)$ em $\{0,\,1\}^n.$

• Mostrando que $f$ é injetora.

Sejam $X,\,Y\in P(A),$ tais que $f(X)=f(Y)=(y_1,\,y_2,\,\ldots,\,y_n).$

Logo, para todo $i\in A,$

    $y_i=\begin{cases}0,&\mathrm{se~}i\not\in X\overset{f(X)=f(Y)}{\qquad{\Longleftrightarrow}\qquad}i\not\in Y\\\\ 1,&\mathrm{se~}i\in X\overset{f(X)=f(Y)}{\qquad{\Longleftrightarrow}\qquad}i\in Y\end{cases}$

    $\Longrightarrow\quad X\subset Y\mathrm{~~e~~}Y\subset X.$

Logo, $X$ e $Y$ possuem exatamente os mesmos elementos, isto é,

    $\Longleftrightarrow\quad X=Y\quad\Longrightarrow\quad f\mathrm{~\acute{e}~injetora.}\qquad\square$

• Mostrando que $f$ é sobrejetora.

Dado $(y_1,\,y_2,\,\ldots,\,y_n)\in\{0,\,1\}^n,$ existe $X\in P(A)$ tal que

    $\displaystyle f(X)=(y_1,\,y_2,\,\ldots,\,y_n).$

A saber, os elementos de $X$ serão todos os naturais $i\in A,$ tais que $y_i=1:$

    $\displaystyle X=\underset{y_i=1}{\bigcup_{i\in A}} \{i\}.$

Portanto, $f$ é bijeção.          $\blacksquare$

Dúvidas? Comente.

Bons estudos!