Exercício 16.1 Seja \(A=\{1,2,\ldots,n\}\). Mostre que o conjunto \[
\mathcal P(A)=\{ X \mid X\subseteq A\}
\] está em bijeção com o conjunto das seqências \[
\{(a_1,a_2,\ldots,a_n) \mid a_i\in \{0,1\} \text{ para } i=1,2,\ldots,n \}
\] Deduza que \(\mathcal P(A)\) tem \(2^n\) elementos.
Exercício 16.2 Seja \(A\) um conjunto de cardinalidade qualquer.
- Construa uma bijeção entre \(\mathcal P(A)\) e o conjunto das funções de \(A\) em \(\{0,1\}\).
- Deduza que \(|\mathcal P(\N)|=|\R|\).
Exercício 16.3 Seja \(A\) um conjunto enumerável e seja \(B\) um subconjunto de \(A\). Mostre que \(B\) é enumerável ou finito.
Exercício 16.4 Seja \(A\) um conjunto infinito e seja \(a\) um elemento qualquer. Mostre que \(A\) está em bijeção com \(A\cup \{a\}\). Deduza que \(|A|=|A\cup \{a\}|\).
Exercício 16.5 Seja \(A\) um conjunto infinito e seja \(B\) um conjunto finito. Mostre que \(|A\cup B|=|A|\).
Exercício 16.6 Sejam \(A\) e \(B\) conjuntos finitos e assuma que \(|A|=m\) e \(|B|=n\). Mostre que \(|A\cup B|=m+n-|A\cap B|\).
Exercício 16.7 Sejam \(A\) e \(B\) conjuntos finitos e assuma que \(|A|=m\) e \(|B|=n\).
- Construa uma bijeção entre \(A\times B\) e o conjunto \(\{1,2,\ldots,m\cdot n\}\).
- Deduza que \(|A\times B|=m\cdot n\)
Exercício 16.8 Sejam \(A\) e \(B\) conjuntos finitos e assuma que \(|A|=m\) e \(|B|=n\). Mostre que \[
|\{f:A\to B \mid f \text{ é uma função}\}|=n^m.
\]
Exercício 16.9 Sejam \(A\) e \(B\) conjuntos infinitos enumeráveis. Mostre que \(A\cup B\) e \(A\times B\) são conjuntos infinitos enumeráveis.
Exercício 16.10 Quais dos seguintes conjuntos são infinitos enumeráveis? Justifique sua resposta.
- \(\{n\in \N \mid n\mbox{ é primo}\}\)
- \(\{r\in \Q\mid r\geq 0\}\)
- \(\{r\in \R\mid 0 < r < 1/10^{12}\}\)
- \(\C\)
- \(\{x\in\R\mid x^2=2^a3^b\mbox{ para alguns }a,b\in\N\}\)
Exercício 16.11 Construa bijeções entre os conjuntos no Lema Lema 15.1 para os quais não há uma bijeção explícita na prova do lema.
Exercício 16.12 Um número \(x\in \C\) chama-se algébrico se existem inteiros \(a_0,a_1,\ldots,a_n\), não todos nulos, tais que \[
a_nx^n+a_{n-1}x^{n-1}+\cdots + a_1x+a_0=0.
\] Caso contrário, \(x\) chama-se transcendental.
- Mostre que o conjunto dos números algébricos é enumerável.
- Deduza que o conjunto dos números transcendentais é não enumerável.