Exercício - Bijeção - Matemática Discreta 2021 2

Ex. 6. Seja A = \{1, \ldots , n\}. Mostre que há uma bijeção entre \mathcal{P}(A) e o produto \{0,1\}^n. (Construa a bijeção.) Atividade Matemática Discreta *Todas as questões de cálculos foram conferidas por software antes da entrega. Seguindo a sugestão dada, vamos mostrar que existe uma bijeção entre os conjuntos construindo a bijeção. Primeiramente, vamos entender como são os conjuntos. 𝒫(𝐴) é o conjunto das partes de 𝐴, ou seja, é o conjunto formato por todos os subconjuntos possíveis de elementos de 𝐴. Um elemento genérico 𝐴𝑘 ∈ 𝒫(𝐴) é um conjunto formado por elementos de 𝐴 (podendo inclusive ser o conjunto vazio) O conjunto {0; 1}𝑛 é formado por todas as n-uplas da forma 𝑥 = (𝑥1; 𝑥2; 𝑥3; … ; 𝑥𝑛) tais que 𝑥𝑖 ∈ {0; 1}. Seja 𝐴𝑘 ∈ 𝒫(𝐴). Podemos criar a partir desse elemento um vetor 𝑥 = (𝑥1; 𝑥2; … ; 𝑥𝑛) tal que 𝑥𝑖 = 1 se 𝑖 ∈ 𝐴𝑘, e 𝑥𝑖 = 0 se 𝑖 ∉ 𝐴𝑘. Por exemplo, se 𝑛 = 5, temos que 𝐴 = {1; 2; 3; 4; 5} O elemento {2; 4; 5} ∈ 𝒫(𝐴) será associado ao vetor 𝑥 = (0; 1; 0; 1; 1) ∈ {0; 1}𝑛 O elemento {1; 5} ∈ 𝒫(𝐴) será associado ao vetor 𝑥 = (1; 0; 0; 0; 1) ∈ {0; 1}𝑛 O elemento ∅ ∈ 𝒫(𝐴) será associado ao vetor 𝑥 = (0; 0; 0; 0; 0) ∈ {0; 1}𝑛 Para todo elemento em 𝒫(𝐴), podemos associar um vetor 𝑥 ∈ {0; 1}𝑛 Seja 𝑓: 𝒫(𝐴) → {0; 1}𝑛 a função que toma 𝐴𝑘 ∈ 𝒫(𝐴), e faz a associação descrita acima, ou seja 𝑓(𝐴𝑘) = (𝑥1; 𝑥2; … 𝑥𝑛), onde 𝑥𝑖 = 1 se 𝑖 ∈ 𝐴𝑘 e 𝑥𝑖 = 0 se 𝑖 ∉ 𝐴𝑘. Vamos provar que 𝑓 é uma bijeção. Ela será injetora, pois se 𝐴𝑘1 ≠ 𝐴𝑘2, então existirá ao menos um elemento distinto entre 𝐴𝑘1 e 𝐴𝑘2 (podendo haver mais de um. Digamos que esse elemento distinto esteja na i-ésima coordenada. Então 𝑓(𝐴𝑘1) e 𝑓(𝐴𝑘2) serão diferentes nessa coordenada. Provando que se 𝐴𝑘1 ≠ 𝐴𝑘2, então 𝑓(𝐴𝑘1) ≠ 𝑓(𝐴𝑘2), e que a função 𝑓 é injetora. Essa função será bijetora também, pois para todo 𝑥 ∈ {0; 1}𝑛, sempre existirá 𝐴𝑘 ∈ 𝒫(𝐴) tal que 𝑓(𝐴𝑘) = 𝑥. No caso, será o elemento 𝐴𝑘 = {𝑖 | 𝑥𝑖 = 1} Dessa forma provamos que existe ao menos uma bijeção 𝑓, construída e apresentada, entre os conjuntos dados.