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
então
Teorema 5.3.2.
Todo subconjunto \(X\subset\mathbb{N}\) é enumerável.
Demonstração.
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.
Corolário 5.3.3.
Seja \(f:X\rightarrow Y\) injetiva. Se \(Y\) é enumerável então \(X\) também é. Em particular, todo subconjunto de um conjunto enumerável é enumerável.
Demonstração.
Como \(Y\) é enumerável, existe uma bijeção \(\varphi:Y\rightarrow \mathbb{N}\text{.}\) A função composta
é injetiva. Como \(\varphi\circ f(X)\subset \mathbb{N}\text{,}\) pelo Teorema 5.3.2, \(\varphi\circ f(X)\) é enumerável. Logo
é uma bijeção. Portanto, \(X\) é enumerável.
No caso particular de \(X\subset Y\text{,}\) considere
tal que, \(f(x)=x\text{.}\) Assim, \(f\) é injetiva e \(Y\) é enumerável. Pelo que já foi provado \(X\) é enumerável.
Corolário 5.3.4.
Seja \(f:X\rightarrow Y\) sobrejetiva. Se \(X\) é enumerável então \(Y\) é enumerável.
Demonstração.
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
Pelo Corolário 5.3.3, \(Y\) é enumerável.
Corolário 5.3.5.
O produto cartesiano de dois conjuntos enumeráveis é um conjunto enumerável.
Demonstração.
Se \(X\) e \(Y\) são enumeráveis então existem bijeções
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.
Corolário 5.3.6.
A reunião de uma família enumerável de conjuntos enumeráveis é enumerável.
Demonstração.
Dados \(X_1, X_2, \ldots, X_n, \ldots\) enumeráveis, existem sobrejeções
Tomando
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çãoA função \(f:\mathbb{N}\rightarrow \mathbb{Z}\) definida por
é 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
Se \(m\in \mathbb{Z}\text{,}\) com \(m\lt 0\text{,}\) então \(-2m\in \mathbb{N}\text{,}\) e
Exemplo 5.3.8.
O conjunto \(\mathbb{Q}\) dos números racionais é enumerável.
SoluçãoCom efeito, denotando \(\mathbb{Z}^*=\mathbb{Z}-\{0\}\) e definindo
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.