[skip-to-content]

Seção 5.3 Conjuntos Enumeráveis

Definição 5.3.1.

Um conjunto \(X\) é chamado enumerável quando é finito ou quando existe um bijeção \(f:\mathbb{N}\rightarrow X\text{.}\) Neste último caso, \(f\) é chamada uma enumeração dos elementos de \(X\text{.}\) Se escrevermos

\begin{equation*} f(1)=x_1, ~ f(2)=x_2, ~ \cdots, ~ f(n)=x_n, \cdots, \end{equation*}

então

\begin{equation*} X=\{x_1,x_2,\cdots, x_n,\cdots\}\text{.} \end{equation*}

Se \(X\) é finito, nada há para demonstrar. Caso contrário, enumeramos os elementos de \(X\) da seguinte maneira:

  • \(x_1 =\) menor elemento de \(X\text{,}\)
  • \(x_2 =\) menor elemento de \(X\setminus\{x_1\}\text{,}\)
  • \(x_3 =\) menor elemento de \(X\setminus\{x_1, x_2\}\text{,}\)
  • \(\displaystyle \vdots\)
  • \(x_{n+1} =\) menor elemento de \(X\setminus\{x_1, x_2, \ldots, x_n\}\text{.}\)
  • \(\displaystyle \vdots\)

Note que \(X\setminus\{x_1, x_2, \ldots, x_n\}\neq \varnothing\) para qualquer \(n\in \mathbb{N}\text{,}\) pois \(X\) é infinito, então \(X = \{x_1, x_2, \ldots, x_n, \ldots\}\text{.}\) Com efeito, se existisse algum elemento \(x\in X\) diferente de todos os \(x_n\text{,}\) teríamos \(x\in X\setminus\{x_1, x_2, \ldots, x_n\}\) para todo \(n\in \mathbb{N}\text{,}\) logo \(x\) seria um número natural maior do que todos os elementos do conjunto infinito \(\{x_1, x_2, \ldots, x_n, \ldots\}\text{,}\) contrariando o Corolário 5.1.12.

Como \(Y\) é enumerável, existe uma bijeção \(\varphi:Y\rightarrow \mathbb{N}\text{.}\) A função composta

\begin{equation*} \varphi\circ f:X\rightarrow \mathbb{N} \end{equation*}

é injetiva. Como \(\varphi\circ f(X)\subset \mathbb{N}\text{,}\) pelo Teorema 5.3.2, \(\varphi\circ f(X)\) é enumerável. Logo

\begin{equation*} \varphi\circ f:X\rightarrow \varphi\circ f(X) \end{equation*}

é uma bijeção. Portanto, \(X\) é enumerável.

No caso particular de \(X\subset Y\text{,}\) considere

\begin{equation*} f:X\rightarrow Y, \end{equation*}

tal que, \(f(x)=x\text{.}\) Assim, \(f\) é injetiva e \(Y\) é enumerável. Pelo que já foi provado \(X\) é enumerável.

Para cada \(y\in Y\) escolha um \(x\in X\) tal que \(f(x)=y\text{,}\) isto é possível, pois \(f\) é sobrejetiva. Defina uma função \(g:Y\rightarrow X\) tal que \(g(y)=x\text{,}\) para cada \(y\in Y\) com \(f(x)=y\text{.}\) Então, \(f(g(y))=y\) para todo \(y\in Y\text{.}\) Segue daí que \(g\) é injetiva, pois se \(g(y_1)= g(y_2)\text{,}\) então

\begin{equation*} y_1 = f(g(y_1)) = f(g(y_1))=y_2\text{.} \end{equation*}

Pelo Corolário 5.3.3, \(Y\) é enumerável.

Se \(X\) e \(Y\) são enumeráveis então existem bijeções

\begin{equation*} f:\mathbb{N}\rightarrow X ~\text{e}~ g:\mathbb{N}\rightarrow Y. \end{equation*}

Logo, \(\varphi:\mathbb{N}\times \mathbb{N}\rightarrow X\times Y\) dada por \(\varphi(m,n) = (f(m), g(n))\) é sobrejetiva. Basta provar que \(\mathbb{N}\times \mathbb{N}\) é enumerável. Para isto, considere a função \(\psi:\mathbb{N}\times \mathbb{N} \rightarrow \mathbb{N}\text{,}\) dada por \(\psi(m,n)=2^m\cdot 3^n\text{.}\) Pela unicidade da decomposição de um número em fatores primos, \(\psi\) é injetiva. Segue-se que \(\mathbb{N}\times \mathbb{N}\) é enumerável.

Dados \(X_1, X_2, \ldots, X_n, \ldots\) enumeráveis, existem sobrejeções

\begin{equation*} f_1:\mathbb{N}\rightarrow X_1, f_2:\mathbb{N}\rightarrow X_2, \ldots, f_n:\mathbb{N}\rightarrow X_n, \ldots\text{.} \end{equation*}

Tomando

\begin{equation*} X = \bigcup_{n=1}^{\infty}X_n, \end{equation*}

definimos a sobrejeção \(f:\mathbb{N}\times \mathbb{N}\rightarrow X\) pondo \(f(m,n)=f_n(m)\text{.}\)

O caso de uma reunião finita \(X = X_1\cup X_2\cup \cdots \cup X_n\) reduz-se ao anterior, pois \(X = X_1\cup X_2\cup \cdots \cup X_n\cup X_n\cup X_n\cup \cdots\text{.}\)

Exemplo 5.3.7.

O conjunto \(\mathbb{Z}\) dos números inteiros é enumerável.

Solução

A função \(f:\mathbb{N}\rightarrow \mathbb{Z}\) definida por

\begin{equation*} f(n)=\left\{ \begin{array}{ll} \dfrac{n-1}{2}, \amp \mbox{se} ~ n ~ \mbox{for ímpar}\\ \dfrac{-n}{2}, \amp \mbox{se} ~ n ~ \mbox{for par}\\ \end{array}, \right. \end{equation*}

é sobrejetiva e pelo Corolário 5.3.4 \(\mathbb{Z}\) é enumerável. De fato, temos dois casos.

Se \(m\in \mathbb{Z}\text{,}\) com \(m\geq 0\text{,}\) então \(2m+1\in \mathbb{N}\text{,}\) e

\begin{equation*} f(2m+1)=\frac{(2m+1)-1}{2}=m. \end{equation*}

Se \(m\in \mathbb{Z}\text{,}\) com \(m\lt 0\text{,}\) então \(-2m\in \mathbb{N}\text{,}\) e

\begin{equation*} f(-2m) = \frac{-(-2m)}{2}=m. \end{equation*}
Exemplo 5.3.8.

O conjunto \(\mathbb{Q}\) dos números racionais é enumerável.

Solução

Com efeito, denotando \(\mathbb{Z}^*=\mathbb{Z}-\{0\}\) e definindo

\begin{equation*} f:\mathbb{Z}\times \mathbb{Z}^*\rightarrow\mathbb{Q} \end{equation*}

por \(f(m,n)=\dfrac{m}{n}\text{.}\) Pelo Corolário 5.3.5 \(\mathbb{Z}\times \mathbb{Z}^*\) é enumerável e pelo Corolário 5.3.4, \(\mathbb{Q}\) é enumerável.