Capítulo 5

Cardinalidade

Contar um conjunto finito consiste em associar seus elementos aos números \(1,2,\ldots ,n\). A comparação por meio de funções também se aplica a conjuntos infinitos. Nesse caso, um conjunto pode ter a mesma cardinalidade que um subconjunto próprio, e dois conjuntos infinitos podem ter cardinalidades diferentes.

Neste capítulo, estudaremos essas comparações. Começaremos pelos conjuntos enumeráveis, que têm a mesma cardinalidade de \(\mathbb {N}\), e provaremos que \(\mathbb {Z}\) e \(\mathbb {Q}\) são enumeráveis. Em seguida, mostraremos que \(\mathbb {R}\) não é enumerável. O caso dos racionais permite distinguir duas noções: embora \(\mathbb {Q}\) seja denso em \(\mathbb {R}\), os dois conjuntos não têm a mesma cardinalidade.

Notação 5.1
Ao longo do texto,
\[ \mathbb {N}=\{ 1,2,3,\ldots \} , \qquad \mathbb {N}_0=\{ 0,1,2,\ldots \} , \]
e, para \(n\in \mathbb {N}\), escrevemos \([n]=\{ 1,2,\ldots ,n\} \).

5.1 Comparação de cardinalidades

Retomaremos as noções de função injetora, sobrejetora e bijetora, que serão usadas para comparar conjuntos.

Definição 5.2
Uma função \(f\colon A\to B\) associa a cada \(x\in A\) um único elemento \(f(x)\in B\). O conjunto \(A\) é o domínio e \(B\) é o contradomínio.

Definição 5.3
Seja \(f\colon A\to B\).

  1. Se \(E\subset A\), a imagem de \(E\) é

    \[ f(E)=\{ f(x):x\in E\} . \]

  2. Se \(F\subset B\), a pré-imagem de \(F\) é

    \[ f^{-1}(F)=\{ x\in A:f(x)\in F\} . \]

  3. A função é injetora se

    \[ f(x_1)=f(x_2)\ \Longrightarrow \ x_1=x_2; \]

    é sobrejetora se \(f(A)=B\); e é bijetora se é ao mesmo tempo injetora e sobrejetora.

Dois conjuntos têm a mesma cardinalidade quando seus elementos podem ser postos em correspondência um a um. A definição seguinte formaliza essa ideia.

Definição 5.4
Se existe uma bijeção \(f\colon A\to B\), dizemos que \(A\) e \(B\) têm a mesma cardinalidade, ou que são equipotentes, e escrevemos
\[ A\sim B. \]

Observação 5.5
A relação \(\sim \) é uma relação de equivalência: a identidade mostra que \(A\sim A\); a inversa de uma bijeção mostra a simetria; e a composição de bijeções mostra a transitividade.

Para comparar conjuntos que talvez não tenham a mesma cardinalidade, usaremos injeções.

Definição 5.6
Escrevemos
\[ A\preceq B \]
se existe uma função injetora \(A\to B\). Intuitivamente, isso significa que \(A\) cabe dentro de \(B\) sem identificar dois de seus elementos.

O resultado seguinte permite transformar duas comparações em sentidos opostos em uma bijeção. Ele será útil para comparar intervalos e a reta real.

Teorema 5.7 (Cantor–Bernstein)
Se existem injeções \(f\colon A\to B\) e \(g\colon B\to A\), então existe uma bijeção \(A\to B\). Em outras palavras,
\[ A\preceq B\quad \text{e}\quad B\preceq A \quad \Longrightarrow \quad A\sim B. \]

Demonstração ▼

Defina

\[ A_0=A\setminus g(B), \qquad A_{n+1}=g(f(A_n)), \qquad C=\bigcup _{n=0}^{\infty }A_n. \]

Construiremos \(h\colon A\to B\) por

\[ h(x)= \begin{cases} f(x),& x\in C,\\ g^{-1}(x),& x\notin C. \end{cases} \]

A segunda expressão faz sentido: se \(x\notin C\), então \(x\notin A_0\), logo \(x\in g(B)\); como \(g\) é injetora, existe um único \(g^{-1}(x)\).

A função \(h\) é injetora em cada uma das duas partes, pois \(f\) e \(g\) são injetoras. Além disso, suas imagens nessas duas partes não se misturam. De fato, se \(x\in C\) e \(h(x)=h(y)\) com \(y\notin C\), então \(f(x)=g^{-1}(y)\), e portanto

\[ y=g(f(x))\in g(f(C))\subset C, \]

contradição.

Resta provar a sobrejetividade. Seja \(b\in B\). Se \(g(b)\notin C\), então \(h(g(b))=b\). Se \(g(b)\in C\), não pode ocorrer \(g(b)\in A_0\); logo \(g(b)\in A_{n+1}=g(f(A_n))\) para algum \(n\). Pela injetividade de \(g\), existe \(x\in A_n\subset C\) tal que \(f(x)=b\), e então \(h(x)=b\). Portanto \(h\) é bijetora.

Definição 5.8
Para um conjunto \(A\), dizemos:

  1. \(A\) é finito se \(A\sim [n]\) para algum \(n\in \mathbb {N}\); o conjunto vazio também é considerado finito;

  2. \(A\) é infinito se não é finito;

  3. \(A\) é enumerável se \(A\sim \mathbb {N}\);

  4. \(A\) é no máximo enumerável se é finito ou enumerável;

  5. \(A\) é não enumerável se é infinito e não é enumerável.

Para conjuntos finitos, essa definição recupera a contagem usual. O exemplo seguinte mostra uma diferença entre o caso finito e o infinito.

Exemplo 5.9
O conjunto \(\mathbb {Z}\) é enumerável. Uma bijeção \(f\colon \mathbb {N}\to \mathbb {Z}\) é dada por
\[ f(n)= \begin{cases} \dfrac n2,& n\text{ par},\\[1mm] -\dfrac {n-1}{2},& n\text{ ímpar}. \end{cases} \]
Assim,
\[ 0,1,-1,2,-2,3,-3,\ldots \]
é uma enumeração dos inteiros.

Observação 5.10
Um conjunto finito nunca é equipotente a um subconjunto próprio. No caso infinito, isso pode acontecer: \(\mathbb {N}\subsetneq \mathbb {Z}\), mas \(\mathbb {N}\sim \mathbb {Z}\). Essa é a primeira indicação de que o tamanho de conjuntos infinitos não se comporta como a contagem finita.

Definição 5.11
Como já vimos, uma sequência em \(A\) é uma função \(\mathbb {N}\to A\). Portanto, dizer que \(A\) é enumerável equivale a dizer que seus elementos podem ser organizados como uma sequência
\[ a_1,a_2,a_3,\ldots \]
sem repetições e sem omissões.

Observação 5.12
Usaremos livremente a caracterização
\[ x\in \bigcup _{i\in I}E_i \quad \Longleftrightarrow \quad (\exists i\in I)\, x\in E_i, \]
e a versão análoga para interseções. As propriedades associativa, comutativa e distributiva de uniões e interseções seguem diretamente dessas equivalências.

5.2 O infinito enumerável

A propriedade de ser no máximo enumerável é preservada pela passagem a subconjuntos, por produtos finitos e por uniões enumeráveis. Estabeleceremos esses fatos antes de examinar conjuntos não enumeráveis.

Lema 5.13
Um conjunto \(S\) é no máximo enumerável se, e somente se, existe uma função injetora
\[ m\colon S\to \mathbb {N}. \]

Demonstração ▼

Se \(S\) é finito, basta numerar seus elementos por naturais distintos; se é enumerável, qualquer bijeção \(S\to \mathbb {N}\) é, em particular, injetora.

Reciprocamente, suponha que \(m\colon S\to \mathbb {N}\) seja injetora. Então \(S\sim m(S)\subset \mathbb {N}\). Se \(m(S)\) é finito, terminamos. Se é infinito, podemos enumerá-lo em ordem crescente: escolha

\[ n_1=\min m(S) \]

e, depois de escolhidos \(n_1\lt \cdots \lt n_k\), defina

\[ n_{k+1}=\min \bigl(m(S)\setminus \{ n_1,\ldots ,n_k\} \bigr). \]

O bom ordenamento de \(\mathbb {N}\) garante que o processo está bem definido, e todo elemento de \(m(S)\) aparece em algum estágio. Assim \(m(S)\sim \mathbb {N}\), e portanto \(S\) é enumerável.

Corolário 5.14
Todo subconjunto de um conjunto no máximo enumerável é no máximo enumerável.

Demonstração ▼

Se \(T\subset S\) e \(S\) admite uma injeção em \(\mathbb {N}\), basta restringi-la a \(T\).

Lema 5.15
Se \(S\neq \varnothing \) e existe uma função sobrejetora \(g\colon \mathbb {N}\to S\), então \(S\) é no máximo enumerável.

Demonstração ▼

Para cada \(s\in S\), o conjunto

\[ g^{-1}(\{ s\} )=\{ n\in \mathbb {N}:g(n)=s\} \]

é não vazio. Pelo bom ordenamento de \(\mathbb {N}\), ele possui um menor elemento. Defina

\[ m(s)=\min g^{-1}(\{ s\} ). \]

Se \(m(s_1)=m(s_2)=n\), então \(g(n)=s_1=s_2\). Logo \(m\colon S\to \mathbb {N}\) é injetora, e o lema anterior conclui a prova.

Teorema 5.16
Se \(\{ E_n\} _{n\in \mathbb {N}}\) é uma sequência de conjuntos enumeráveis, então

\begin{equation} \label{eq:S-uniao-En} S=\bigcup _{n=1}^{\infty }E_n \tag{5.1} \end{equation}

é no máximo enumerável. Se \(S\) é infinito, então é enumerável.

Demonstração ▼

Para cada \(n\), escolha uma sobrejeção \(\phi _n\colon \mathbb {N}\to E_n\), e escreva \(x_{nk}=\phi _n(k)\). Dispomos os termos em uma tabela infinita: Ilustração: O infinito enumerável Percorrendo as diagonais sucessivas, obtemos uma sobrejeção \(g\colon \mathbb {N}\to S\). Por exemplo,

\begin{align} \label{eq:diagonal} g(1)& =x_{11}, \tag{5.2}\\ g(2)& =x_{21},\quad g(3)=x_{12}, \tag{5.3}\\ g(4)& =x_{31},\quad g(5)=x_{22},\quad g(6)=x_{13},\quad \ldots \tag{5.4} \end{align}

Todo \(s\in S\) pertence a algum \(E_n\), logo é da forma \(x_{nk}\) para algum par \((n,k)\), e portanto aparece nesse percurso. Pelo Lema 5.15, \(S\) é no máximo enumerável. Se \(S\) é infinito, então é enumerável.

Corolário 5.17
Se \(A\) é no máximo enumerável e, para cada \(\alpha \in A\), o conjunto \(B_\alpha \) é no máximo enumerável, então
\[ \bigcup _{\alpha \in A}B_\alpha \]
é no máximo enumerável.

Demonstração ▼

Se \(A=\varnothing \), a união é vazia. Suponha \(A\neq \varnothing \). Como \(A\) é no máximo enumerável, existe uma sobrejeção \(\psi \colon \mathbb {N}\to A\): no caso finito, basta repetir elementos.

Para cada \(n\), ponha \(E_n=B_{\psi (n)}\). Descartemos as linhas vazias. Para cada \(E_n\neq \varnothing \), existe uma sobrejeção \(\phi _n\colon \mathbb {N}\to E_n\): se \(E_n\) é finito, repetimos seus elementos; se é enumerável, usamos uma enumeração. Percorrendo a tabela \(\phi _n(k)\) por diagonais, exatamente como na prova do Teorema 5.16, obtemos uma sobrejeção de \(\mathbb {N}\) sobre a união. Pelo Lema 5.15, essa união é no máximo enumerável.

Teorema 5.18
Se \(A\) é enumerável, então, para todo \(n\ge 1\), o conjunto \(A^n\) das \(n\)-uplas de elementos de \(A\) é enumerável.

Demonstração ▼

Para \(n=1\), não há o que provar. Suponha que \(A^{n-1}\) seja enumerável. Para cada \(b\in A^{n-1}\), o conjunto

\[ C_b=\{ (b,a):a\in A\} \]

é equipotente a \(A\), logo enumerável. Como

\[ A^n=\bigcup _{b\in A^{n-1}}C_b, \]

o resultado segue do teorema da união enumerável. A conclusão vem por indução.

5.3 Enumerabilidade e densidade dos racionais

A enumerabilidade dos racionais decorre da enumerabilidade dos inteiros e de seus produtos finitos.

Corolário 5.19
O conjunto \(\mathbb {Q}\) é enumerável.

Demonstração ▼

Como \(\mathbb {Z}\) é enumerável, \(\mathbb {Z}^2\) é enumerável. O subconjunto

\[ \mathbb {Z}\times (\mathbb {Z}\setminus \{ 0\} ) \]

é, portanto, no máximo enumerável. A aplicação

\[ (a,b)\longmapsto \frac ab \]

é sobrejetora sobre \(\mathbb {Q}\). Logo \(\mathbb {Q}\) é no máximo enumerável. Como é infinito, é enumerável.

A enumerabilidade não impede que um conjunto seja denso. No caso de \(\mathbb {Q}\), todo intervalo aberto não vazio da reta contém um de seus elementos.

Proposição 5.20 (Densidade dos racionais)
Entre dois números reais distintos existe um número racional. Equivalentemente, \(\mathbb {Q}\) é denso em \(\mathbb {R}\).

Demonstração ▼

Sejam \(a\lt b\). Pela propriedade arquimediana, escolha \(n\in \mathbb {N}\) tal que

\[ \frac1n\lt b-a. \]

Existe um inteiro \(m\) tal que

\[ m-1\le na\lt m. \]

Então

\[ a\lt \frac mn\le a+\frac1n\lt b. \]

Logo \(m/n\in \mathbb {Q}\cap (a,b)\).

Essa distinção será importante no capítulo seguinte: a densidade depende da topologia, enquanto a comparação de cardinalidades depende da existência de funções injetoras e bijetoras. Um subconjunto pode ser denso sem ter a mesma cardinalidade do espaço que o contém.

5.4 O teorema de Cantor

O teorema de Cantor fornece, a partir de qualquer conjunto, outro de cardinalidade estritamente maior: seu conjunto das partes.

Teorema 5.21 (Cantor)
Para todo conjunto \(A\), não existe sobrejeção
\[ f\colon A\to \mathcal P(A), \]
onde \(\mathcal P(A)\) é o conjunto de todos os subconjuntos de \(A\). Em particular,
\[ A\not\sim \mathcal P(A). \]

Demonstração ▼

Suponha que \(f\colon A\to \mathcal P(A)\) seja sobrejetora e defina

\[ D=\{ x\in A:x\notin f(x)\} . \]

Como \(D\subset A\), pela sobrejetividade existe \(d\in A\) tal que \(f(d)=D\). Mas então

\[ d\in D \quad \Longleftrightarrow \quad d\notin f(d)=D, \]

contradição.

A aplicação \(x\mapsto \{ x\} \) é uma injeção de \(A\) em \(\mathcal P(A)\). Assim, \(A\preceq \mathcal P(A)\), mas o teorema mostra que não existe bijeção entre os dois conjuntos: o conjunto das partes tem cardinalidade estritamente maior.

A ideia de diagonalização também pode ser aplicada às expansões decimais, como veremos na prova da não enumerabilidade de um intervalo real.

Teorema 5.22
O intervalo \([0,1]\) é não enumerável.

Demonstração ▼

Mostraremos primeiro que \([0,1)\) não é enumerável. Suponha, por absurdo, que seus elementos possam ser listados como

\[ x_1,x_2,x_3,\ldots . \]

Para cada \(n\), escolha a expansão decimal de \(x_n\) que não termina em uma cauda de algarismos \(9\):

\[ x_n=0.a_{n1}a_{n2}a_{n3}\ldots . \]

Essa convenção fornece uma representação para todo elemento de \([0,1)\).

Defina

\[ y=0.b_1b_2b_3\ldots \]

por

\[ b_n= \begin{cases} 1,& a_{nn}\neq 1,\\ 2,& a_{nn}=1. \end{cases} \]

Como todos os dígitos \(b_n\) pertencem a \(\{ 1,2\} \), temos \(y\in [0,1)\). Além disso, o \(n\)-ésimo dígito de \(y\) difere do \(n\)-ésimo dígito de \(x_n\). Logo \(y\neq x_n\) para todo \(n\), contradizendo a hipótese de que a lista continha todos os elementos de \([0,1)\).

Portanto \([0,1)\) é não enumerável. Se \([0,1]\) fosse enumerável, seu subconjunto \([0,1)\) seria no máximo enumerável pelo Corolário 5.14; como \([0,1)\) é infinito, seria enumerável, contradição. Logo \([0,1]\) é não enumerável.

Ilustração: O teorema de Cantor
Figura 5.1 Na diagonal escolhemos, em cada linha, o dígito que será alterado.

O argumento não depende da base decimal: construímos um objeto que difere do \(n\)-ésimo elemento de uma lista na \(n\)-ésima coordenada. Esse procedimento é chamado processo diagonal de Cantor.

5.5 A cardinalidade do contínuo

A não enumerabilidade de \([0,1]\) mostra que sua cardinalidade é maior que a de um conjunto enumerável. Veremos agora que todos os intervalos não degenerados da reta têm a mesma cardinalidade.

Teorema 5.23
Temos
\[ (0,1)\sim [0,1]\sim \mathbb {R}. \]

Demonstração ▼

A inclusão \((0,1)\hookrightarrow [0,1]\) é injetora. Por outro lado,

\[ f\colon [0,1]\to (0,1), \qquad f(x)=\frac{x+1}{3}, \]

é injetora. Pelo Teorema de Cantor–Bernstein, \((0,1)\sim [0,1]\).

Além disso,

\[ g\colon (0,1)\to \mathbb {R}, \qquad g(x)=\tan \bigl(\pi (x-1/2)\bigr), \]

é uma bijeção. Logo todos os três conjuntos são equipotentes.

A cardinalidade de \(\mathbb {R}\) é chamada cardinalidade do contínuo e é tradicionalmente denotada por \(\mathfrak c\).

Reunindo os resultados sobre os racionais e os reais, temos:

\[ \mathbb {Q}\text{ é enumerável e denso em }\mathbb {R}, \qquad \mathbb {R}\text{ tem cardinalidade }\mathfrak c. \]

A comparação de cardinalidades também permite demonstrar a existência de números transcendentes, sem construir um exemplo explícito.

Teorema 5.24
O conjunto dos números algébricos é enumerável.

Demonstração ▼

Para cada \(n\ge 0\), o conjunto dos polinômios

\[ a_0+a_1x+\cdots +a_nx^n, \qquad a_j\in \mathbb {Z}, \]

é no máximo enumerável, pois pode ser identificado com um subconjunto de \(\mathbb {Z}^{n+1}\). A união, sobre todos os graus, do conjunto de polinômios não nulos com coeficientes inteiros é, portanto, no máximo enumerável.

Cada polinômio não nulo possui apenas um número finito de raízes complexas. Logo o conjunto de todos os números algébricos é uma união enumerável de conjuntos finitos e, portanto, é no máximo enumerável. Como contém \(\mathbb {Q}\), é infinito; logo é enumerável.

Corolário 5.25
O conjunto dos números reais transcendentes é não enumerável.

Demonstração ▼

Se os transcendentes reais fossem no máximo enumeráveis, então \(\mathbb {R}\), sendo a união dos algébricos reais com os transcendentes reais, seria no máximo enumerável. Isso contradiz a não enumerabilidade de \([0,1]\subset \mathbb {R}\).

Os números algébricos, entre os quais está \(\sqrt2\), formam um conjunto enumerável. Já o conjunto dos reais transcendentes é não enumerável.

5.6 Exercícios

Exercício 5.1

Prove diretamente que o conjunto dos números pares é equipotente a \(\mathbb {N}\), e construa uma bijeção explícita.

Ver solução

Com a interpretação usada no gabarito original, seja \(P=\{ 2,4,6,\ldots \} \). A função

\[ f:\mathbb {N}\longrightarrow P,\qquad f(n)=2n, \]

é injetora, pois \(2m=2n\Rightarrow m=n\), e sobrejetora, pois todo elemento de \(P\) tem a forma \(2n\), com \(n\ge 1\). Logo \(P\sim \mathbb {N}\).

Se o conjunto pretendido incluir \(0\), use \(f(n)=2(n-1)\). Se incluir também os inteiros negativos, uma bijeção com \(2\mathbb {Z}\) é

\[ g(n)=\begin{cases} n,& n\text{ par},\\ -(n-1),& n\text{ ímpar},\end{cases} \]

que enumera \(0,2,-2,4,-4,\ldots \).

Exercício 5.2

Mostre que o conjunto de todos os subconjuntos finitos de \(\mathbb {N}\) é enumerável.

Ver solução

Seja \(\mathcal F\) a família dos subconjuntos finitos de \(\mathbb {N}\). Defina

\[ \Phi :\mathcal F\longrightarrow \mathbb {N}_0,\qquad \Phi (A)=\sum _{n\in A}2^{n-1}. \]

A soma vazia vale zero. Se \(A\ne B\), seja \(k\) o maior índice em que suas pertinências diferem. A contribuição \(2^{k-1}\) não pode ser cancelada pelos termos menores, cuja soma é \(2^{k-1}-1\). Portanto \(\Phi (A)\ne \Phi (B)\), e \(\Phi \) é injetora.

Assim, \(\mathcal F\) é no máximo enumerável. Como contém os infinitos conjuntos distintos \(\{ n\} \), é infinita e, portanto, enumerável.

Exercício 5.3

Prove que o conjunto de todas as sequências finitas de números racionais é enumerável.

Ver solução
O conjunto das sequências de comprimento \(m\) pode ser identificado com \(\mathbb {Q}^m\). Para \(m\ge 1\), esse conjunto é enumerável, por ser um produto finito de conjuntos enumeráveis. Para \(m=0\), há apenas a sequência vazia. Logo
\[ \bigcup _{m=0}^{\infty }\mathbb {Q}^m \]
é no máximo enumerável. Como contém as sequências de comprimento \(1\), que estão em bijeção com \(\mathbb {Q}\), é infinito e, portanto, enumerável.
Exercício 5.4

Mostre que \(\mathbb {Q}^n\) é enumerável para todo \(n\in \mathbb {N}\).

Ver solução
Como \(\mathbb {Q}\) é enumerável, o teorema sobre produtos finitos de conjuntos enumeráveis mostra que \(\mathbb {Q}^n\) é enumerável para cada \(n\ge 1\). Explicitamente, uma bijeção \(q:\mathbb {N}\to \mathbb {Q}\) induz
\[ (k_1,\ldots ,k_n)\longmapsto (q(k_1),\ldots ,q(k_n)), \]
que é uma bijeção \(\mathbb {N}^n\to \mathbb {Q}^n\). Como \(\mathbb {N}^n\) é enumerável, segue a conclusão.
Exercício 5.5

Mostre que o conjunto de todas as funções \(f\colon \mathbb {N}\to \{ 0,1\} \) não é enumerável. Relacione esse conjunto com \(\mathcal P(\mathbb {N})\).

Ver solução

Suponha que todas essas funções pudessem ser listadas como \(f_1,f_2,\ldots \). Defina

\[ g(n)=1-f_n(n). \]

Então \(g:\mathbb {N}\to \{ 0,1\} \), mas \(g(n)\ne f_n(n)\) para todo \(n\), de modo que \(g\) não aparece na lista. Isso é uma contradição.

A correspondência com \(\mathcal P(\mathbb {N})\) é a bijeção

\[ A\longmapsto \mathbf1_A, \]

cuja inversa envia \(f\) no conjunto \(\{ n\in \mathbb {N}:f(n)=1\} \). Assim, os dois conjuntos têm a mesma cardinalidade e não são enumeráveis.

Exercício 5.6

Prove que \(\mathcal P(\mathbb {N})\) tem a mesma cardinalidade que \([0,1]\). Sugestão: use expansões binárias com uma convenção que elimine a ambiguidade das caudas de \(1\)’s, ou use Cantor–Bernstein.

Ver solução

Construiremos injeções nos dois sentidos e aplicaremos Cantor–Bernstein. A primeira é

\[ \Phi :\mathcal P(\mathbb {N})\longrightarrow [0,1],\qquad \Phi (A)=\sum _{n\in A}\frac2{3^n}. \]

A série converge e sua soma pertence a \([0,1]\). Se \(A\ne B\) e \(k\) é o primeiro índice em que diferem, podemos supor \(k\in A\setminus B\). Então

\[ \Phi (A)-\Phi (B) \ge \frac2{3^k}-\sum _{n\gt k}\frac2{3^n} =\frac1{3^k}\gt 0. \]

Logo \(\Phi \) é injetora.

Para o outro sentido, escolha uma enumeração \((q_n)\) de \(\mathbb {Q}\cap [0,1]\) e defina

\[ \Psi :[0,1]\longrightarrow \mathcal P(\mathbb {N}),\qquad \Psi (t)=\{ n:q_n\lt t\} . \]

Se \(s\lt t\), a densidade dos racionais fornece \(q_n\in (s,t)\). Então \(n\in \Psi (t)\setminus \Psi (s)\), e \(\Psi \) é injetora. Pelo teorema de Cantor–Bernstein, \(\mathcal P(\mathbb {N})\sim [0,1]\).

Exercício 5.7

Mostre que todo intervalo aberto \((a,b)\), com \(a\lt b\), tem cardinalidade \(\mathfrak c\).

Ver solução
A função
\[ f:(0,1)\longrightarrow (a,b),\qquad f(x)=a+(b-a)x, \]
é bijetora, com inversa \(y\mapsto (y-a)/(b-a)\). Como \((0,1)\sim \mathbb {R}\), segue que \((a,b)\sim \mathbb {R}\). Portanto \((a,b)\) tem cardinalidade \(\mathfrak c\).
Exercício 5.8

Prove que o conjunto dos irracionais é não enumerável.

Ver solução
Seja \(I=\mathbb {R}\setminus \mathbb {Q}\). Se \(I\) fosse no máximo enumerável, a união \(\mathbb {R}=\mathbb {Q}\cup I\) também seria no máximo enumerável, pois \(\mathbb {Q}\) é enumerável. Isso contradiz a não enumerabilidade de \([0,1]\subset \mathbb {R}\). Logo \(I\) é não enumerável.
Exercício 5.9

Dê uma nova prova de que existem números reais transcendentes usando apenas os Teoremas 5.22 e 5.24.

Ver solução
Seja \(A\) o conjunto dos números algébricos, que é enumerável. Se todo real fosse algébrico, teríamos \([0,1]\subseteq A\). Todo subconjunto de um conjunto enumerável é no máximo enumerável, logo \([0,1]\) seria no máximo enumerável, uma contradição. Portanto existe um real que não é algébrico, isto é, um número real transcendente.
Exercício 5.10

Prove que, se \(A\) é infinito e no máximo enumerável, então \(A\sim \mathbb {N}\).

Ver solução
Pela definição adotada, ser no máximo enumerável significa ser finito ou admitir uma bijeção com \(\mathbb {N}\). Como \(A\) é infinito, a primeira possibilidade está excluída. Portanto \(A\sim \mathbb {N}\).