cap6 enumerabilidade

Prévia do material em texto

Capítulo 6
Enumerabilidade
No capítulo anterior, vimos uma propriedade que distingue o corpo ordenado dos números
racionais do corpo ordenado dos números reais: R é completo, enquanto Q não é.
Neste novo capítulo investigaremos mais uma propriedade que distingue os racionais dos
reais.
Lembremos que no primeiro capítulo, vimos como que o conjunto dos números naturais
é aquele cujos elementos são usados para enumerar. Nesse sentido, nos perguntamos quais
conjuntos que podem ser enumerados.
Dizemos que um conjunto X não vazio é dito enumerável se acontece uma das duas possi-
bilidades:
- X é finito;
- X é infinito e existe uma bijeção entre N e X.
Mostrar que um conjunto é ou não enumerável depende da investigação da finitude e, caso
necessário, da função bijetiva.
Neste curso, duas vertentes serão utilizadas. Na primeira delas, veremos esta estrutura
citada anteriormente. Na segunda, buscaremos mostrar que um conjunto é ou não enumerável
a partir de proposições que facilitem o trabalho.
Inicialmente, vejamos alguns exemplos.
Exemplo 1. Mostre que o conjunto X1 = {a,b, c,d} é enumerável.
Como X1 é finito, então segue da definição que ele é enumerável.
Exemplo 2. Mostre que o conjunto X2 dos números pares a partir do 6 é enumerável.
Precisamos mostrar que X2 é finito ou que é infinito e admite uma bijeção entre N e ele.
Claramente, ele não é finito.
Então buscamos uma bijeção entre N e X2 através de operações que transformem um con-
junto no outro.
X2 −→ 6 8 10 12 14 16 . . .
| | | | | |
3 4 5 6 7 8 . . .
| | | | | |
N −→ 1 2 3 4 5 6 . . .
32
Para o nosso problema, tanto faz encontrar uma bijeção entre N e X2 ou entre X2 e N.
Importa apenas explicitar alguma das duas.
Ao observarmos a tabela, temos que, dado um elemento x de X2, primeiramente dividimos
ele por 2 e depois subtraímos essa mesma quantidade. Logo, uma das bijeções desejadas é
f : X2 → N tal que f(x) = (x/2) − 2.
Caso estivéssemos em busca da função bijetiva que parte de N até X2, já não precisaríamos
mais de tanto trabalho. Basta utilizar a mesma tabela, só que na ordem contrária: partindo de
N, primeiramente somamos dois e, em seguida, dobramos este valor. Portanto, a inversa da f
acima seria g : N→ X2 tal que g(n) = 2(n+ 2).
Resta mostrar que essas funções são bijetivas. Para mostrar que f é injetiva, suponha que
existam x1 e x2 tais que f(x1) = f(x2). Logo,
f(x1) =
x1
2
− 2 =
x2
2
− 2 = f(x2) =⇒ x1 = x2.
Para f ser sobrejetiva, resta mostrar que, para todo n em N, ele é atingido por alguém do
domínio. De fato, como já construímos uma “inversa” para ela, vemos que o número natural
n é atingido pelo elemento 2(n + 2) em X2. Assim, todo número em N é imagem de algum
elemento do domínio.
Portanto, f é injetiva e sobrejetiva, ou seja, bijetiva.
Exemplo 3. Mostre que o conjunto X3 dos quadrados dos naturais pares é enumerável.
A construção segue o mesmo padrão. Primeiramente, identificamos uma associação entre
os elementos desse conjunto e os naturais.
X3 −→ 4 16 36 64 100 144 . . .
| | | | | |
2 4 6 8 10 12 . . .
| | | | | |
N −→ 1 2 3 4 5 6 . . .
Com isto, conseguimos duas funções (potencialmente bijetivas). As funções f : X3 → N tal
que f(x) =
√
x/2 e g : N→ X3 tal que g(n) = (2n)2 são as candidatas.
Exercício 6.1. Mostre que essas funções f e g acima são bijetivas.
Exercício 6.2. Obtenha uma enumeração de N em cada um dos conjuntos abaixo, mostrando que
cada função é uma bijeção.
a) C1 = {n ∈ N : n é divisível por 2 e não por 4}.
b) C2 = {m ∈ N : m é um múltiplo ímpar de 3}.
c) C3 = {nn
n
}n∈N.
d) C4 = {m ∈ N : m é um natural ímpar que é um quadrado perfeito }.
A partir de agora veremos uma sequência de proposições que facilitarão na hora de mostrar
se um conjunto é ou não é enumerável. Na maioria das vezes é possível concluir sem conseguir
exibir a enumeração!
Proposição 1. Um conjunto X não vazio de números naturais é finito se e somente se ele é limitado
superiormente.
Demonstração: (⇒) Se é finito, então X = {x1, x2, . . . , xn}, sendo xi ∈ N para todo i. Ao
tomarmos a soma de todos os termos, temos o número y = x1 + x2 + . . . + xn que é maior
33
que todos elementos de X, ou seja, serve como uma cota superior para o conjunto. Logo, X é
limitado superiormente.
(⇐) Se X é limitado superiormente, então existe algum natural y tal que xi 6 y, para todo
xi ∈ X. Assim, X deve ser um subconjunto de {1, 2, . . . ,y}, já que X ⊆ N.
Usaremos esta proposição para demonstrar um resultado bastante interessante, o qual co-
mentaremos posteriormente.
Proposição 2. Todo subconjunto X dos números naturais é enumerável.
Demonstração: Temos duas opções para X: ou ele é um conjunto finito ou ele é um conjunto
infinito. Caso seja finito, então ele é enumerável por definição. Se ele for infinito, consideramos
a função ϕ : N→ X tal que ϕ(x) = xn de modo que:
x1 é o menor elemento de X.
x2 é o menor elemento de X \ {x1}.
x3 é o menor elemento de X \ {x1, x2}.
x4 é o menor elemento de X \ {x1, x2, x3}.
...
Xn+1 é o menor elemento de X \ {x1, x2, x3, . . . , xn}.
O Princípio da Boa Ordem nos garante que cada um desses menores elementos podem ser
tomados, já que “todo subconjunto não vazio dos naturais admite um elemento minimal”.
Note que esta função é construída indutivamente, já que é necessário o passo atual para
construir o seguinte. Ainda mais: com isto, temos que x1 < x2 < . . . < xn < . . ., o que já nos
garante que esta função é injetiva!
Para mostrar que ϕ é sobrejetiva, suponha que existe elemento x de X tal que ϕ(x) = xn 6= x
para todo n. Isto significa que x > xn para todo n ∈ N; caso contrário, se houvesse j tal que
x < xj, então xj não seria o menor elemento a ser escolhido daquela vez.
Por outro lado, ter que x > xn nos garante uma contradição, já que, pela Proposição 1, um
subconjunto não vazio de naturais é finito e, por hipótese, temos X infinito.
A contradição ocorre devido à suposição da existência de tal x que não é imagem de alguém
do domínio de ϕ. Assim, esta função é obrigatoriamente sobrejetiva e, consequentemente, é
bijetiva.
Note que esta última proposição traz um resultado que muda um pouco a nossa forma de
lidar com a enumerabilidade. Todo subconjunto não vazio dos naturais é enumerável, mesmo
que aparentemente não haja padrão nos termos da sequência.
Por exemplo, até hoje não é conhecida nenhuma expressão que determine a sequência de
números naturais primos. Por outro lado, como formam um subconjunto não vazio de N, são
enumeráveis devido à Proposição 2.
Com um pouco mais de trabalho, é possível estender esta Proposição para subconjuntos de
conjuntos enumeráveis.
Proposição 3. Sejam X, Y conjuntos tais que X ⊆ Y. Se Y for enumerável, então X é enumerável.
Demonstração: Começamos do mesmo modo. Há duas possibilidades para X, ser finito ou
infinito. Se for finito, então é enumerável por definição. Se X for infinito, então necessariamente
Y deve ser infinito (como pode caber um conjunto infinito dentro de outro finito?).
Como Y é infinito e é enumerável, existe função f1 bijeção entre N e Y. Lembre também que
X ⊆ Y implica a existência da função inclusão g1, que faz g(x) = x para todo x ∈ X.
34
Resta agora mostrar que a função h1 := f1 ◦ g1 é bijetiva. Entretanto, isto geralmente não
é verdade! A inclusão é injetiva e a enumeração é bijetiva; portanto, a composição é injetiva.
O que falha geralmente é a sobrejetividade. Para entender porque isso acontece, imagine que
vários elementos de Y foram enumerados e ganharam rótulos. Todos os rótulos utilizados para
os elementos de Y\X serão desprezados no momento em que tentarmos construir a enumeração
para os elementos de X, o que significa que nem todos naturais serão utilizados na enumeração
e h1 não será sobrejetiva.
O esquema a seguir, baseado num exemplo, mostra melhor esta ideia.
Y −→ y1 y2 y3 y4 y5 y6 y7 y8 y9. . .
| | | | | | | | |
1 2 3 4 5 6 7 8 9 . . .
1 3 7 8
| | | | . . .
X −→ y1 y3 y7 y8 . . .
Apesar da composição não ser suficientemente boa, existe um procedimento padrão para
construir tal função sobrejetiva.
Segundo o esquema acima, nem todos rótulos foram utilizados. Considere o conjunto h1(X)
como sendo os rótulos dos elementos de X através da enumeração de Y (no exemplo acima,
seria o conjunto {1, 3, 7, 8, . . .}. Note que, por serem rótulos, são um subconjunto de N. No
diagrama de Venn acima, fica mais fácil de ver que h1(X) ⊆ N.
Da Proposição anterior, temos que h1(X) deve ser enumerável e, como não é finito - já que
h1 é injetiva e X é infinito -, existe bijeção f : h1(X)→ N.
Por outro lado, a restrição do contradomínio de h1 produz uma nova função, agora bijetiva
(pois mantemos a lei de associação e o domínio): h : X→ h1(X) tal que h(x) = h1(x).
Tomando a composição F := f ◦ h que liga X a N, temos uma composição de bijeções.
Portanto, F é uma bijeção enter X e N, o que mostra que X é enumerável.
35
Até agora, a única forma de mostrar que um conjunto é enumerável é exibir uma bijeção
entre ele e N ou que ele é finito. A próxima proposição reduz um pouco a preocupação em
encontrar a função bijetiva.
Proposição 4. São equivalentes:
i) X é enumerável;
ii) Existe função sobrejetiva de N em X;
iii) Existe função injetiva de X em N.
Demonstração: Comecemos mostrando que [i =⇒ ii].
Por hipótese, X é enumerável. Portanto, X é finito ou X é infinito e existe bijeção entre N e
X. Se X for infinito, esta função citada é sobrejetiva, o que satisfaz a condição.
O caso mais complexo é se X for finito. Considere X = {x1, x2, . . . , xn}. Defina f : N→ X de
modo que f(i) = xi se 1 6 i 6 n.
Observe que todos xi são atingidos pelos naturais 1, 2, . . . ,n, o que já nos garante a condição
de sobrejeção. Para os demais inteiros, basta combiná-los a quaisquer elementos de X, já que
só falta “completar” a associação para obtermos uma função. Por exemplo, podemos fazer
f(i) = x1 se i > n.
[ii =⇒ iii]: Esta parte da demonstração é válida para quaisquer funções e não é exata-
mente um problema envolvendo enumerabilidade.
Seja f uma função sobrejetiva de N em X. Para cada elementos x de X, considere sua
imagem inversa, conjunto dos elementos n de N tal que f(n) = x.
f−1({x}) = {n ∈ N : f(n) = x}
Como f é sobrejetiva, a imagem inversa associada a todo elemento x de X é não vazia. Pelo
Axioma da Escolha, podemos tomar qualquer nx ∈ f−1({x}) e criar uma função g : X → N tal
que g(x) = nx.
Resta agora mostrar que g é injetiva. Suponha que existam x1 e x2 em X tais que g(x1) =
g(x2) = n. Da definição de g, temos que n ∈ f−1({x1}) e n ∈ f−1({x2}), ou seja, f(n) = x1 e
f(n) = x2. Mas como f é uma função, a única possibilidade é a que x1 = x2. Logo, g é injetiva.
36
[iii =⇒ i]: Suponha agora que exista uma função injetiva f de X em N. Analisemos as duas
possibilidades para a quantidade de elementos de X.
Se o conjunto for finito, automaticamente será enumerável por definição. Se for infinito,
precisamos exibir a bijeção.
A princípio, a função f da hipótese é a principal candidata, já que já é injetiva. Infelizmente,
a sobrejeção falha em geral. Mas o argumento a ser utilizado é o mesmo da demonstração da
Proposição 3.
O conjunto f(X) = {n ∈ N : n = f(x)} é um subconjunto dos naturais (portanto, enumerável)
e admitem uma correspondência biunívoca com os elementos de x, já que f é injetiva. Logo, a
função g : X→ f(X) tal que g(x) = f(x) é uma bijeção desejada.
Estas proposições demonstradas até agora serão a base para mostrar que alguns dos conjun-
tos numéricos são enumeráveis.
Proposição 5. O conjunto dos inteiros é enumerável.
Demonstração: Um dos pensamentos mais comuns é de que Z contém “o dobro” dos ele-
mentos de N. Agora veremos que, na verdade, os dois possuem mesma quantidade de elemen-
tos.
Uma função construída de forma alternada resolve nosso problema:
Fazemos, portanto, as seguintes associações de números inteiros aos naturais:
0→ 1 1→ 2
−1→ 3 2→ 4
−2→ 5 3→ 6
−3→ 7 4→ 8
. . . . . .
Formalizamos isto em uma função definida em duas partes:
f(x) =
{
2x, se x ∈ N
−2x+ 1, se x ∈ Z \ N.
Resta mostrar que esta função é bijetiva. A f é sobrejetiva pois todos os naturais são pares
ou ímpares. Os números naturais pares são atingidos pelos números inteiros positivos e pelo
zero; os naturais ímpares são atingidos pelos inteiros negativos.
Suponha agora que existam dois inteiros x1 e x2 tais que f(x1) = f(x2). Note que, necessari-
amente, os dois devem ter mesmo sinal. Caso contrário, a imagem desses números deveria ser
par e ímpar simultaneamente.
37
Se x1 e x2 são positivos, então, aplicando a função, temos 2x1 = 2x2 e, consequentemente,
x1 = x2. Caso ocorra x1 6 0 e x2 6 0, acontece −2x1 + 1 = −2x2 + 1, o que implica x1 = x2.
Portanto, a f citada é bijetiva.
Proposição 6. O conjunto dos números racionais é enumerável.
Demonstração: Primeiramente, devemos relembrar como definimos os números racionais.
A enumeração que encontraremos está atrelada àquele procedimento.
Considere A = {(m,n) ∈ (Z\{0})×Z}. Este conjunto admite enumeração derivada da figura
acima, que copia o procedimento que adotamos para os números inteiros: a enumeração segue
alguma ordem de proximidade com a origem do eixo ou plano cartesiano.
Neste caso, a ordem de enumeração seria:
(1, 0) (1, 1) (−1, 1) (−1, 0) (−1,−1) (1,−1) (2,−1) (2, 0) (2, 1) (2, 2) . . .
l l l l l l l l l l
1 2 3 4 5 6 7 8 9 10 . . .
Devido ao comportamento dessa bijeção, não existe uma forma ótima de escrever quem é o
par ordenado associado a um número natural escolhido. Demonstraremos que Q é enumerável
mesmo sem conhecer explicitamente a bijeção.
Caso consideremos apenas a condição da construção de números racionais, os pares orde-
nados (1, 1) e (2, 2), por exemplo, dariam origem aos mesmos racionais, embora admitissem
rótulos 2 e 10, considerando a enumeração de A. Buscamos uma bijeção entre os naturais e os
racionais, independendo da forma que escrevemos este número.
Para resolver este problema, consideramos uma forma de escrever Q sem repetir nenhuma
das frações:
Q = {(m,n) ∈ A : MDC(|m|, |n|) = 1}.
Com isto, todo r em Q é escrito de forma única. Por outro lado, isto implica que Q ⊂ A. Mas
como A é enumerável, segue da Proposição 3 que o conjunto dos racionais é enumerável.
38
Mostrar que o conjunto dos reais não é enumerável é um pouco mais complicado. Faremos
duas demonstrações nesse material. A primeira abordagem é a que utiliza uma ferramenta
bastante interessante, que é o Teorema dos Intervalos Compactos Encaixados (um intervalo é
compacto se é limitado e fechado).
Proposição 7 (Teorema dos intervalos compactos encaixados). Dada sequência de intervalos
[a1,b1] ⊃ [a2,b2] ⊃ . . . ⊃ [an,bn] ⊃ . . . ,
então tem-se que
∞⋂
i=1
[ai,bi] 6= ∅.
Demonstração: Observemos o que acontece na sequência dos ai. Como cada intervalo está
contido no próximo, segue que ai < ai+1 para todo i ∈ N e podemos escrever
a1 < a2 < . . . < an < . . .
Por outro lado, essa sequência de números reais é limitada. Qualquer um dos termos bk
serve como cota superior. Caso isto não fosse verdade, existiria algum j,k ∈ N tal que aj > bk;
mas isto contradiz o fato de que os intervalos são da forma [ai,bi].
Temos, portanto, uma sequência limitada de números reais. O Axioma do supremo nos diz
que toda sequência limitada de números reais admite supremo. Denotemos por x o supremo do
conjunto {ai}i∈N.
Por hipótese, para todo i ∈ N valem x > ai (pois x é supremo dos termos ai) e x 6 bi
(porque x é a menor das cotas superiores). Assim, concluímos que x ∈ [ai,bi] para todo i
natural.
Uma das demonstrações possíveis de que R não é enumerável segue do Teorema dos Inter-
valos Compactos Encaixados (TICE). A proposição a seguir será demonstrada de duas formasdiferentes.
Proposição 8. O conjunto dos números reais não é enumerável.
Demonstração 1: (Via TICE) De acordo com a Proposição 4, basta mostrar que não pode
existir função sobrejetiva de N em R.
Suponha que exista função f : N→ R sobrejetiva. Escrevamos f(i) = xi, com i ∈ N.
Para cada xi, construímos um intervalo [ai,bi] de modo que xi 6∈ [ai,bi] e que ocorra
[ai,bi] ⊃ [ai+1,bi+1]. O esquema abaixo mostra uma possível organização dos passos i = 1, 2
e 3.
Do Teorema dos Intervalos Compactos Encaixados, temos que existe x ∈ R tal que x pertence
a todos [ai,bi], sendo i natural.
Por hipótese, f é sobrejetiva. Logo, existe j ∈ N tal que f(j) = xj = x. Observemos a
consequência disto acontecer quando consideramos a construção dos intervalos: xj 6∈ [aj,bj] e
x ∈ [aj,bj], o que gera uma contradição.
Esta contradição decorre da suposição de que f−1({x}) 6= ∅. Devido a isto, nenhuma função
f de N a R pode ser sobrejetiva. Da proposição 4, R não é enumerável.
39
Demonstração 2: (Construção da Diagonal de Cantor) O objetivo desta demonstração é
utilizar a demonstração de que o intervalo ]0, 1[ não é enumerável e, a partir disso, concluir a
não enumerabilidade do conjunto dos reais.
Suponha, por contradição, que o intervalo seja enumerável e considere f(i) = xi uma enu-
meração. Nesta enumeração, toda vez que um número tiver expansão decimal finita (racional),
considere a versão em que a expansão é infinita e periódica. Por exemplo, ao invés de escrever
0, 234, tomamos 0, 233999 . . .
A partir dos números escolhidos por f, construímos um novo número x a partir da i-ésima
casa decimal de xi (para todo i natural) da seguinte forma:
• Se a i-ésima casa decimal de xi for 1, então a i-ésima casa decimal de x é 2.
• Se a i-ésima casa decimal de xi não for 1, então a i-ésima casa decimal de x é 1.
Exemplo:
x1 → 0, 1 7 6 9 0 5 0 2 4 2 . . .
x2 → 0, 9 5 8 5 3 5 8 6 2 7 . . .
x3 → 0, 6 8 6 8 6 4 6 0 7 5 . . .
x4 → 0, 8 8 8 8 8 8 8 8 8 8 . . .
x5 → 0, 1 2 3 4 5 6 7 8 9 0 . . .
x6 → 0, 8 5 0 6 4 1 9 9 4 8 . . .
x7 → 0, 3 4 3 5 5 3 2 5 5 2 . . .
x8 → 0, 1 6 9 0 5 3 7 9 4 2 . . .
x9 → 0, 4 6 3 5 2 4 7 9 1 3 . . .
x10 → 0, 3 3 3 4 4 4 2 2 2 1 . . .
...
Da enumeração acima, o número construído é x = 0, 2111121122 . . .
O x criado participa em algum ponto da enumeração? Não. Caso participasse, x = xk
para algum k natural. Da construção de x, temos que a k-ésima casa decimal desse número é
diferente da k-ésima cada decimal de xk, o que gera um absurdo.
Portanto, não existe função sobrejetiva de N em ]0, 1[, o que implica (Proposição 4) que este
intervalo não é enumerável.
Claramente, ]0, 1[⊂ R. Caso o conjunto dos números reais fosse enumerável, todo subcon-
junto dele (inclusive o intervalo) seriam enumeráveis, o que contradiz a demonstração acima.
Logo, R não pode ser enumerável.
Exercício 6.3. Mostre que todo conjunto infinito contém um subconjunto enumerável.
Exercício 6.4. Encontre uma decomposição N = X1 ∪ x2 ∪ . . . ∪ Xn ∪ . . . tal que os conjuntos
X1,X2, . . . ,Xn, . . . sejam dois a dois disjuntos.
Exercício 6.5. Sabemos que Q é um conjunto enumerável. Portanto, o conjunto
A =
{
n
n+ 1
: n ∈ N
}
é enumerável e finito.
a) Considere a aplicação f : N→ A tal que f(n) = nn+1 . Mostre que f é injetiva e sobrejetiva.
b) Determine a bijeção inversa g : A→ N da função f.
c) Considere B = {1, 2} ∪ A. Explique porque B é enumerável e defina uma bijeção de N sobre
B.
40