Capítulo 5 - Cardinalidade de um conjunto
Neste capítulo abordaremos o problema da cardinalidade de um conjunto. Definiremos o que se entende por
conjunto finito, infinito, contável e numerável, deduziremos critérios que nos permitem estabelecer se um
conjunto é de um desses tipos e mostraremos que existem conjuntos não contáveis.
Algumas demonstrações de resultados serão incluídas apenas no fim do capítulo, num anexo ao
mesmo: tal será o caso quer de certas demonstrações demasiado técnicas (e que não ilustram nenhuma
técnica nova, relevante), quer de outras demonstrações, que apesar de não serem demasiado técnicas, se
reportam a resultados que não são essenciais em relação ao fio condutor deste capítulo.
Obélix, qual dos conjuntos
tem mais elementos:
ou
Essa até eu sei:
o primeiro
(pois tem mais o 0)
{ 0 , 1, 2, 3, 4, 5, .... }
{ 1, 2, 3, 4, 5, .... } ?
Mas os Matemáticos
dizem que os dois
conjuntos têm o mesmo
número de elementos !
São malucos
esses
Matemáticos !
Vamos mas é
caçar romanos !
Secção 1: Cardinal de um conjunto, conjuntos finitos e infinitos: motivação.
Como referimos no capítulo 2, informalmente, o cardinal de um conjunto (finito) A (que representaremos
por #(A), ou #A) é o número de elementos de A. Daí decorre que se A ⊆ B então #A ≤ #B, e se A ⊂ B,
então A tem menos elementos do que B, pelo que #A < #B.
No entanto, como então referimos, algumas destas ideias acerca da cardinalidade de um conjunto,
aparentemente tão evidentes, nem sempre são verdadeiras quando consideramos conjuntos infinitos.
Quando passamos ao infinito, muitas das nossas intuições falham. Por exemplo, apesar do conjunto dos
naturais estar estritamente contido no conjunto dos inteiros, diz-se que os dois conjuntos têm a mesma
cardinalidade. Para percebermos porquê, torna-se necessário clarificar (o que se entende por conjunto
infinito e) qual o significado a dar à noção de número de elementos de um conjunto infinito e o que
significa dois conjuntos infinitos terem o mesmo número de elementos (ou a mesma cardinalidade). A isso
procuraremos responder nesta secção, ainda que sem aprofundar muito o tópico em causa.
139
Comecemos por procurar analisar o significado de contar o número de elementos de um conjunto.
Comecemos por um conjunto finito (intuitivamente falando, pois ainda não se deu uma definição de
conjunto finito, em geral). Pensemos, por exemplo, em conjuntos tão distintos como um rebanho
(conjunto) de cabras, o conjunto das letras "a", "b", "c" e "d", ou o conjunto de bolas que estão dentro de
um saco. E procuremos abstrair qual o procedimento genérico que seguimos quando queremos contar o
número de elementos desses conjuntos.
Podemos dizer que genericamente procedemos como se segue: extraímos (retiramos) um elemento desse
conjunto e associamos-lhe o número 1, extraímos um elemento do conjunto restante e associamos-lhe o
número 2, e assim sucessivamente até se esgotarem os elementos do conjunto a contar.
Assim, a contagem do número de elementos do conjunto (por exemplo) {"a", "b", "c", "d"} passa por
um procedimento do tipo:
(extrair um elemento, p.ex.:) "a" ---------------> (associar-lhe o número) 1
(extrair um elemento do conjunto restante {"b", "c", "d"}, p.ex.:) "b" ---------------> 2
(extrair um elemento do conjunto restante {"c", "d"}, p.ex.:) "c" ---------------> 3
(extrair um elemento do conjunto restante {"d"}:) "d" ---------------> 4
não há qualquer elemento restante, pelo que o processo pára, e dizemos que
{"a", "b", "c", "d"} tem 4 elementos.
a
1
b
2
c
3
d
4
{"a", "b", "c", "d"}
Repare-se que a ordem com que vamos extraindo os elementos do conjunto em contagem é irrelevante.
O procedimento a seguir levaria ao mesmo número de elementos:
(extrair um elemento, p.ex.:) "b" ---------------> (associar-lhe o número) 1
(extrair um elemento do conjunto restante {"a", "c", "d"}, p.ex.:) "d" ---------------> 2
(extrair um elemento do conjunto restante {"a", "c"}, p.ex.:) "c" ---------------> 3
(extrair um elemento do conjunto restante {"a"}:) "a" ---------------> 4
não há qualquer elemento restante, pelo que o processo pára, e dizemos que
{"a", "b", "c", "d"} tem 4 elementos.
a
1
b
2
c
3
d
4
140
Generalizando e abstraindo, podemos dizer que um conjunto A tem n elementos (com n>0) se podemos
estabelecer uma correspondência de um para um entre os elementos de A e os números 1, ..., n, isto é, em
linguagem matemática, se podemos estabelecer uma bijecção entre A e o conjunto dos números {1, ..., n}.
Por outro lado, um conjunto tem 0 elementos se e só se for o conjunto vazio. Mas, como só se pode
estabelecer uma bijecção entre um conjunto A e o conjunto vazio, se (e só se) A também for vazio,
podemos generalizar a definição anterior, para qualquer natural n, e dizer, uniformemente, que #(A) = n sse
podemos estabelecer uma bijecção entre A e o conjunto dos números {1, ..., n} (interpretando {1,...,n}
como sendo o conjunto vazio, se n for igual a 0) 1:
Definição (de conjunto finito e infinito e de cardinal de um conjunto finito):
a) Dado um natural n, diremos que um conjunto A tem n elementos, ou que A tem cardinal n, sse
podemos estabelecer uma bijecção entre A e o conjunto dos números {1, ..., n}.
Escreve-se #A = n para designar que A tem n elementos.
Em vez de dizer que A tem cardinal n também se diz, com o mesmo sentido, que A tem potência n.
b) Diremos que um conjunto A é finito sse existe algum natural n tal que #A = n
c) Um conjunto que não é finito diz-se infinito.
∇
Um dos problemas em aplicar o procedimento de contagem acima descrito a conjuntos infinitos é que
este procedimento não teria fim, pelo que não poderíamos dizer qual o número dos seus elementos (para
além de, naturalmente, precisarmos de outros números, para além dos naturais, para caracterizarmos o
número de elementos dos conjuntos infinitos; mas não nos preocupemos com isso: abstrair novas
"entidades" nunca foi um grande problema para os matemáticos).
Temos assim de procurar um outro caminho. Em vez de pensarmos qual o número de elementos (o
cardinal) de um dado conjunto, procuremos primeiro caracterizar quando é que dois conjuntos têm o mesmo
número de elementos (o mesmo cardinal).
Se pensarmos em conjuntos finitos, facilmente concluímos que dois conjuntos (finitos) A e B têm o
mesmo número de elementos se (e só se) podemos pôr os seus elementos em correspondência de um para
um, i.e. se é possível estabelecer uma bijecção entre esses conjuntos.
a
❤
b
▼
c
■
d
●
A
B
1 Na próxima secção mostrar-se-á que esta definição não é problemática.
141
Consideremos esta definição para quaisquer conjuntos A e B, finitos ou infinitos, e analisemos quais as
consequências da sua extensão aos conjuntos infinitos:
Definição (de conjuntos com o mesmo cardinal – conjuntos equipotentes):
Diremos que um conjunto A tem o mesmo número de elementos que um conjunto B, ou que A tem o
mesmo cardinal que B, sse existe uma bijecção entre A e B.
Em vez de dizer que A é equicardinal a B (significando que A tem o mesmo cardinal que B) também se
diz, com o mesmo sentido, que A é equipotente a B, e costuma escrever-se
A~B
para denotar que A é equipotente B (com o mesmo fim, poderá também escrever-se #A = #B 2).
∇
Definindo conjunto finito como anteriormente, pode verificar-se3 que um conjunto finito satisfaz as
duas propriedades intuivamente associadas ao cardinal de um conjunto:
i) se A ⊆ B então #A ≤ #B, e
ii) se A ⊂ B, então #A < #B (e, portanto, #A ≠ #B)
O que se passa quando consideramos conjuntos infinitos ?
Como veremos, (i) mantém-se, mas ii) nem sempre.
Embora ainda não tenhamos definido o que significa #A≤#B, ou #A<#B, quando estamos em presença
de conjuntos infinitos (o que só abordaremos na secção 3), podemos desde já ilustrar que ii) nem sempre se
verifica, mostrando que existem conjuntos infinitos A e B para os quais #A = #B, apesar de A ⊂ B.
Consideremos, como um primeiro exemplo, os conjuntos |N0 = {0, 1, 2, 3,, ...} e |N1 = {1, 2, 3,, ...}.
A primeira intuição diz-nos que |N0 deve ter um cardinal superior a |N1, pois |N0 tem mais um
elemento que |N1 (o zero).
Mas |N1 pode ser obtido de |N0 simplesmente "mudando os nomes" dos elementos de |N0: "adicionando
1 a cada elemento de |N0". Portanto, devemos concluir que ambos os conjuntos têm o mesmo número de
elementos. Dito de outra forma, a aplicação f: |N0 → |N1, dada por f(n)=n+1, é uma bijecção, e a existência
de uma bijecção entre dois conjuntos A e B significa (intuitivamente) que podemos ver os elementos de
um conjunto como uma mera mudança "de nome" (uma "re-etiquetação") dos elementos do outro. Nesta
perspectiva, já faz sentido, intuitivamente, dizer que dois conjuntos A e B (finitos ou infinitos) têm o
mesmo número de elementos (o mesmo cardinal), se é possível estabelecer uma bijecção entre eles.
2 No caso dos conjuntos finitos, em que definimos o cardinal destes conjuntos associando-lhes um número (tal como fazemos
intuitivamente), ter-se-á (como mostraremos à frente) que #A = #B sse A~B, como seria necessário para que essa definição de
cardinal e esta definição 2 fizessem sentido. No caso dos conjuntos infinitos, não nos preocuparemos aqui em associar números
aos seus cardinais. De qualquer modo, permitiremos, mesmo nesses casos, que se continue a poder escrever #A = #B para
designar que A e B têm o mesmo cardinal; mas, de acordo com esta definição 2, tal deverá ser entendido como significando
apenas que os conjuntos são equipotentes (i.e. que é possível definir uma bijecção entre eles.)
3 Ainda que com algum trabalho técnico (ver à frente).
142
Observação (|N0 tem o mesmo número de elementos que |N1):
A ideia de que |N1 pode ser obtido de |N0 simplesmente "mudando os nomes" dos elementos de |N0 talvez
seja mais fácil de intuir, se se vir (ou se representar) |N0 como o conjunto (por exemplo)
{ _ , _| , _||, _|||, ...}
4
e |N1 como o conjunto
{_| , _||, _|||, _||||, ...}
Então, é fácil de constatar que se se acrescentar um traço | a (esta "designação" de) cada elemento de |N0, se
obtém |N1 !
E, se virmos as coisas por esta perspectiva, então |N0 tem o mesmo número de elementos que |N1, e é
precisamente a isso que nos conduz a definição 2 anterior !
∇
Temos então, aceitando a definição 2 anterior, que existem conjuntos que têm o mesmo número de
elementos (o mesmo cardinal) que uma sua parte própria !
Ora, pode provar-se (como faremos) que é mesmo essa propriedade "estranha" que separa os conjuntos
finitos dos infinitos, pelo que até poderíamos considerar a seguinte definição de conjunto infinito (tendo-se
que um conjunto é finito sse não é infinito):
Definição alternativa de conjunto infinito:
Um conjunto A é infinito sse é equipotente a (tem o mesmo cardinal que) uma sua parte própria.
∇
Para terminar esta nossa introdução, sublinhe-se que nós não chegámos a definir a que é igual o
cardinal de um conjunto infinito. Tal pode ser feito, mas não o faremos neste texto. Aqui, no que respeita
aos conjuntos infinitos, limitar-nos-emos a comparar a ordem de grandeza dos seus cardinais.
Antes, porém, iremos praticar um pouco os conceitos introduzidos, formular e demonstrar alguns
resultados necessários (alguns deles já referidos, mas ainda não demonstrados), assim como mostrar que a
definição intuitiva (dada atrás) de cardinal de um conjunto finito não é problemática.
Secção 2: Conjuntos equipotentes. Conjuntos finitos e infinitos.
Comecemos por recordar a definição de conjuntos equipotentes5, ou equicardinais (i.e. com o mesmo
cardinal), e por "praticar" um pouco essa definição.
4 Formalmente, quando dizemos que podemos ver, ou representar, |N como o conjunto {_ , _| , _||, _|||, ...}, o que estamos a
0
dizer é que podemos estabelecer uma bijecção entre os dois conjuntos.
5 Nesta secção serão recordadas e “trabalhadas” as (duas primeiras) definições enunciadas na secção anterior. A sua
apresentação nesta secção será contudo efectuada pela ordem inversa da qual foram apresentadas na secção 1.
143
Definição 1 (Definição já enunciada na secção 1)
Diz-se que um conjunto A é equipotente a um conjunto B, o que se pode denotar escrevendo A ~ B, sse
existe uma bijecção entre A e B.
∇
Antes de prosseguir, e de vermos vários exemplos de conjuntos equipotentes, enunciemos algumas
propriedades imediatas desta relação de equipotência:
Teorema 1:
Quaisquer que sejam os conjuntos A, B e C:
a) A ~ A
b) Se A ~ B então B ~ A
c) Se A ~ B e B ~ C então A ~ C
Demonstração:
a) Imediato uma vez que idA é uma bijecção de A em A.
b) Sai do teorema 4.5.1 (i.e. teorema 1 da secção 5 do capítulo 4).
c) Sai da alínea c) do teorema 4.5.2.
∇
De posse da definição anterior, é então fácil verificarmos porque é que se diz, por exemplo, que o
conjunto dos naturais tem a mesma cardinalidade que o conjunto dos inteiros:
Exemplo 1:
Para mostrarmos que os conjuntos |N0 e
Z
têm a mesma cardinalidade basta mostrar que existe uma
bijecção entre esses conjuntos.
Ora, se existe uma bijecção entre |N0 e Z , também existe uma bijecção entre
Z
e |N0, e vice-versa.
Assim, basta-nos exibir uma bijecção num desses sentidos. Qual? Aquele em que for mais simples de
exibir tal bijecção!
Ora, a aplicação (por exemplo)6 f : Z → |N0, dada por f(x) = -2x se x≤0, e f(x) = 2x-1 se x>0, é uma
bijecção. Temos, portanto, o nosso problema resolvido.
∇
Vejamos mais alguns exemplos de conjuntos equipotentes.
Exemplo 2:
Qualquer intervalo de reais [a,b], com (a,b∈|R e) a<b, é equipotente ao intervalo [0,1], uma vez que a
aplicação g : [0,1] → [a,b], definida por
6 Que corresponde à seguinte correspondência:
|N0 :
0
1
2
3
4
5
6
...
Z:
0
1
-1
2
-2
3
-3
...
144
g(x) = a + (b-a) x
(∀x∈[0,1])
é uma bijecção.
∇
Exemplo 3:
O conjunto dos reais |R é equipotente ao intervalo ]0,+∞[, uma vez que a função exponencial7 ex é uma
bijecção entre |R e ]0,+∞[.
∇
Exemplo 4:
Suponha-se, agora, que se quer mostrar que o intervalo ]0 , 1[ é equipotente ao intervalo [0 , 1].
Para o fazer, uma primeira hipótese é encontrar directamente uma bijecção entre esses dois conjuntos,
como se fez nos exemplos anteriores.
Uma segunda hipótese consiste em tirar partido do teorema de Cantor - Schröder - Bernstein (teorema
4.5.7), e mostrar simplesmente que existem injecções "nos dois sentidos" (entre os dois conjuntos), o que
normalmente é mais simples de fazer do que explicitar uma bijecção.
Vamos, neste exemplo, seguir esta segunda alternativa:
É imediato que existe uma injecção entre ]0,1[ e [0,1]: basta considerar a função de inclusão
inc:]0,1[→[0,1], com inc(x)=x (∀x∈]0,1[).
No sentido inverso, a aplicação (por exemplo) g:[0,1]→]0,1[ dada por8
g(x) = x + 1
2 4
(∀ x∈]0,1[)
constitui uma injecção, como é fácil de verificar.
∇
Exemplo 5:
Mostremos agora que o conjunto dos reais |R é equipotente ao intervalo ]0 , 1[.
Tal como no exemplo anterior, recorrendo ao teorema de Cantor - Schröder - Bernstein, basta-nos
encontrar injecções nos dois sentidos, entre os dois conjuntos.
Como ]0,1[ ⊆ |R, a função de inclusão de ]0,1[ em |R constitui uma injecção de ]0,1[ em |R.
Procuremos agora uma injecção de |R em ]0,1[:
No exemplo 3, já explicitámos uma injecção (aliás, mesmo uma bijecção) entre |R e |R+ (=]0,+∞[): a
função exponencial f: |R → |R+, com f(x) = ex (∀x∈|R). Por outro lado, a aplicação g: |R+ → ]0,1[, definida
por g(x) = 1
x +1
(∀x∈|R+) é também uma injecção. Logo g o f é uma injecção entre |R e ]0,1[.
∇
7 Ou, mais precisamente, utilizando a notação lambda, a função λx.ex (recorde a observação 2 da secção 1 do capítulo 4
anterior).
8 A função λx. x reduz, bijectivamente, o intervalo [0,1] ao intervalo [0, 1 ]. Como nós querremos uma injecção entre [0,1] e
2
2
1
1
]0,1[, há que transladar o resultado assim obtido de uma quantidade positiva inferior a
(p.ex. de ).
2
4
€
€
145
€
€
Tendo sido definido o que se entende por dois conjuntos terem a mesma cardinalidade, poderíamos
procurar abordar o problema da definição do cardinal de um conjunto de uma forma abstracta, como sendo
aquela "propriedade" que caracteriza todos os conjuntos que lhe são equipotentes: o facto dos seus
elementos poderem ser postos em correspondência de um para um, independentemente da sua natureza.
Naturalmente, dá-nos jeito poder concretizar um pouco esse conceito ou propriedade abstracta,
associando p.ex. um "número" a cada uma dessas classes de conjuntos equipotentes, ou a um particular
conjunto representante de cada uma dessas classes. E é precisamente isso o que fizemos no caso dos
conjuntos finitos, como se recordará seguir.
Uma estratégia análoga pode também ser seguida para os conjuntos infinitos, obrigando à introdução de
novos tipos de números9, podendo definir-se uma aritmética dos chamados números cardinais.
Aqui, no entanto, como já referimos, no que respeita aos conjuntos infinitos, limitar-nos-emos a
comparar a ordem de grandeza dos seus cardinais.
Antes, porém, iremos rever a definição de cardinal de um conjunto finito10, mostrando que ela não é
problemática, e formular e demonstrar alguns resultados.
Notação:
Qualquer que seja o natural n, Jn = {k∈|N0: 1 ≤ k ≤ n} (isto é, J0 = ∅ e, se n>0, Jn = {1, ..., n}).
∇
Definição 2 (Definição já enunciada na secção 1)
a) Dado um natural n, dizemos que um conjunto A tem cardinal (ou potência) n (i.e. #A = n) sse11 A ~ Jn
b) Dizemos que um conjunto A é finito sse ∃n∈|No A ~ Jn (i.e., por a), sse ∃n∈|No #A = n)
c) Um conjunto que não é finito diz-se infinito.
∇
Repare-se que para que a definição 2-a) não seja problemática, é preciso que se prove que não é possível
A ser equipotente simultaneamente a Jn e a Jk com n≠k. Atendendo ao teorema 1 anterior, tal ficará
provado se demonstrarmos que se n≠k então Jn não é equipotente a Jk, o que, por sua vez, ficará provado se
demonstrarmos que nenhum conjunto Jn é equipotente a uma sua parte própria. Apesar de tal resultado
parecer intuitivamente evidente, a sua demonstração não é imediata e poderá ser omitida pelos menos
interessados, pois não é essencial para os fins aqui em vista (pelo que será incluída apenas no anexo a este
9 Por exemplo, o cardinal do conjunto dos naturais é designado de "alefe-zero" e representado pelo símbolo ℵ , e o cardinal do
0
conjunto dos reais é designado da potência do contínuo e representado por um c gótico.
10 Introduzindo uma outra notação para se referir o conjunto dos naturais positivos menores ou iguais a n (≥0), de modo a evitar
utilizar a notação {1,...,n}, também quando n=0.
11 Em vez de dizer que um conjunto A tem n elementos sse conseguimos estabelecer uma bijecção entre esse conjunto A e o
conjunto {1,...,n} dos naturais positivos menores ou iguais a n (=∅, se n=0), podemos antes dizer, alternativamente e de forma
equivalente, como fazem vários autores, que um conjunto A tem n elementos sse conseguimos estabelecer uma bijecção entre
esse conjunto A e o conjunto {0,...,n-1} dos naturais menores que n.
146
capítulo, que se encontra no fim deste). Como veremos, este resultado12 vai-nos permitir obter um critério
(teorema 3) que nos permitirá estabelecer que um certo conjunto A é infinito, sem necessidade de ter de
provar que A não é equipotente a qualquer Jn (n≥0).
Lema 1
13:
Qualquer que seja o natural n, o conjunto Jn não é equipotente a uma sua parte própria.
Demonstração: Ver anexo a este capítulo, no fim do capítulo.
∇
Usando o lema anterior, pode então provar-se o resultado a seguir, indispensável (como referimos atrás)
para que a definição 1 não seja problemática.
Teorema 2:
a) Se um conjunto A é equipotente a Jn (n≥0) e a Jk (k≥0), então n=k.
b) Um conjunto finito é equipotente a um único conjunto Jn (n≥0).
c) Se A e B são finitos e se n = #A e k = #B, então: n = k sse A ~ B
Demonstração:
a) Suponha-se que A é equipotente a Jn (n≥0) e a Jk (k≥0). Então, pelo teorema 1, Jn é equipotente a Jk.
Mas, pelo lema 1 anterior, tal implica que terá de se ter n = k (pois se n < k então Jn ⊂ Jk, e se k < n
então Jk ⊂ Jn).
b) Que um conjunto finito é equipotente a algum conjunto Jn decorre da própria definição de conjunto
finito. Que um conjunto finito não pode ser equipotente a mais do que um conjuto Jn decorre da alínea a).
c) Suponha-se que A ~ Jn e B ~ Jk.
Se n=k, então A ~ Jn e B ~ Jn, e portanto, pelo teorema 1, A ~ B.
Reciprocamente, se A ~ B, então, pelo teorema 1, Jn ~ Jk e, tal como na demonstração da alínea a), se
conclui que n = k.
∇
O lema 1 anterior pode generalizar-se, sem grande dificuldade, como se segue:
Teorema 3 (corolário do lema 1):
Nenhum conjunto finito é equipotente a uma sua parte própria.
Demonstração:
Suponha-se, por absurdo, que existe um conjunto finito A que é equipotente a uma sua parte própria B.
12 Que designaremos de lema (sobre esta terminologia, que aliás já é bem conhecida dos alunos, veja-se a nota de rodapé 6 do
capítulo 2).
13 Este resultado (com esta ou outra formulação equivalente) é por vezes conhecido como o "teorema dos cacifos", em virtude
da seguinte interpretação (veja-se p.ex. [41], pág. 114): se distribuirmos n objectos por menos de n cacifos, um dos cacifos (pelo
menos) receberá mais do que um objecto. Este resultado é conhecido na literatura inglesa como o "Pigeonhole Principle".
147
Então, como A é finito, existe um natural n tal que A ~ Jn, pelo que existe uma bijecção f: A → Jn.
Por outro lado, como estamos a supor que A ~ B, existe uma bijecção g: A → B.
Isto é, existem as seguintes bijecções:
f-1
A
Jn
g
B
A
f
Jn
Constatados estes factos, procuremos então chegar a uma contradição. Existem várias maneiras de o
fazer. A ideia da demonstração a seguir, consiste em "completar" o primeiro dos (dois) diagramas de
cima14 com novas bijecções:
f-1
A
Jn
g
h
B
C
f1
de modo a nos conduzir (pelo lema 1) à contradição desejada (para o que terá de se ter C ⊂ Jn).
Vejamos como tal pode ser feito (e que é simples).
Seja C = f[B] e f1: B → C definida por ∀x∈B f1(x) = f(x). Note-se que como f está definida em A e
B⊆A (pois B ⊂ A), f1 está bem definida. Por outro lado, é imediato que f1 é injectiva (pois f também o é)
e que f1 também é sobrejectiva (pois f1[B] = f[B] = C).
Seja h a aplicação h: Jn → C definida por h = f1 º g º f-1 (veja-se o diagrama anterior). É imediato quue
h é uma bijecção, pois f1, g e f-1 também o são.
Resta-nos mostrar que C⊂Jn. Ora, como f:A→Jn é uma bijecção e B⊂A, conclui-se que C = f[B] ⊂ Jn.
Mas então existe uma bijecção (h) entre Jn e uma sua parte própria, o que entra em contradição com o
lema 1 (já demonstrado).
∇
O resultado anterior fornece-nos um critério simples que nos permite demonstrar que um dado conjunto
é infinito: basta demonstrar que ele é equipotente a uma sua parte própria15.
14 Obtendo um diagrama comutativo, usando a terminologia introduzida na observação 4 no fim do capítulo anterior.
15 Adiante veremos que essa condição é não só suficiente para um conjunto ser infinito, mas também necessária. Refira-se,
aliás, que alguns autores introduzem a definição de conjunto infinito precisamente como sendo um conjunto que é equipotente a
uma sua parte própria (definindo conjunto finito como um conjunto que não satisfaz essa propriedade).
148
Usando este critério podemos concluir desde já que existem conjuntos infinitos: pelo exemplo 1, o
conjunto
Z
dos inteiros é infinito (e, pelo exemplo 3, o conjunto dos reais |R é também infinito).
Igualmente podemos usar este critério para demonstrar directamente, muito facilmente, que o conjunto dos
naturais |N0 também é infinito.
Exemplo 6:
O conjunto |N0 é infinito.
Demonstração:
Atentendo ao resultado anterior basta demonstrar que |N0 é equipotente a uma sua parte própria. Mas tal é
imediato, pois (como já referimos na secção 1 e) como é bem conhecido, a aplicaçãos : |N0 → |N1 dada por
∀x∈|No s(x) = x+1, é uma bijecção.
∇
O resultado a seguir (que decorre directamente da definição de conjunto finito e infinito) fornece-nos
outros critérios para poder concluir que um certo conjunto é finito, ou infinito.
Teorema 4 :
a) Se B é finito e A ~ B, então A é finito.
b) Se B é infinito e A ~ B, então A é infinito.
Demonstração:
a) Se B é finito então existe um natural n tal que B ~ Jn, pelo que existe uma bijecção f: B → Jn. Se A é
equipotente a B, então existe uma bijecção g: A → B. Mas então, pelo teorema 4.5.2-c), f º g: A → Jn
é uma bijecção. Logo A é finito.
b) Suponha-se que B é infinito e A ~ B e que, por absurdo, A era finito. Então, pela alínea a) (uma vez
que se A ~ B então, pelo teorema 1-b), B ~ A) , B também seria finito (o que contradiz B ser infinito).
∇
Usando este teorema, é imediato concluir que |N1 é infinito (uma vez que já vimos que |N0 é infinito e
que |N0 ~ |N1: exemplo 6 acima). Vejamos um outro exemplo de aplicação deste resultado:
Exemplo 7:
Como já vimos que o conjunto dos naturais é infinito, pelo teorema anterior, para mostrar que o conjunto
dos naturais pares também é infinito, basta mostrar que ele é equipotente ao conjunto dos naturais.
Mas tal é imediato, pois (designando por Pares o conjunto dos naturais pares {0, 2, 4, 6, ...}) é bem
conhecido que a aplicação f : |N0 → Pares dada por f(x) = 2x é uma bijecção.
∇
Exercícios:
1. Demonstre que o conjunto dos naturais pares é equipotente ao conjunto dos naturais ímpares.
2. O conjunto dos naturais ímpares é finito ou infinito ? justifique.
3. Demonstre que se A é um conjunto finito, então A∪{b} também o é (qualquer que seja o elemento b).
∇
149
Secção 3: Comparação de cardinais.
Já definimos conjuntos finitos e infinitos, assim como já caracterizámos quando é que dois conjuntos
(finitos ou infinitos) têm a mesma cardinalidade. (E já vimos que existem conjuntos infinitos.)
Como mostrámos, no caso dos conjuntos infinitos, um conjunto com menos elementos do que outro,
pode ter a mesma cardinalidade ("o mesmo número de elementos") que este: basta pensar no conjunto dos
naturais e no dos inteiros. À luz destes resultados "estranhos" podemos questionar-nos se será que todos os
conjuntos infinitos têm a mesma cardinalidade e, se tal não se passar (como intuitivamente deve ser o
caso16), como se podem comparar os cardinais de conjuntos infinitos não equipotentes. Para isso é
necessário que se defina um critério, justificado, que nos permita comparar a grandeza (em termos de
cardinalidade) de diferentes conjuntos infinitos, e dizer quando é que um conjunto (finito ou infinito) tem
menor cardinalidade que outro conjunto (critério esse que, naturalmente, se deverá comportar para os
conjuntos finitos da forma usual).
Dissemos atrás que, intuitivamente, podemos dizer que dois conjuntos A e B têm o mesmo número de
elementos se podemos pôr os seus elementos em correspondência de um para um, i.e. se é possível
estabelecer uma bijecção entre esses conjuntos.
Usando um raciocínio análogo, podemos dizer que um conjunto A tem um menor número de
elementos que um conjunto B se a cada elemento de A podemos fazer corresponder (injectivamente) um
elemento de B, mas não conseguimos fazer essa correspondência esgotando todos os elementos de B.
A
a
❤
b
▼
c
■
B
●
#A < #B
Tal conduz-nos à definição:
Definição:
a) Dados dois conjuntos A e B, diremos que a potência (ou cardinalidade) de A é inferior à de B, o que se
pode denotar escrevendo A
p B, sse se verificarem as duas condições seguintes:
i) existe uma aplicação injectiva de A em B
ii) não existe nenhuma aplicação bijectiva de A em B
b) Dados dois conjuntos A e B, diremos que a potência (ou cardinalidade) de A é inferior ou igual à de B,
o que se pode denotar escrevendo A p
~ B, sse existe uma aplicação injectiva de A em B.
∇
16 Mas já vimos que a intuição nos pode atraiçoar quando trabalhamos com os conjuntos infinitos !
150
Observação:
a) De acordo com a definição anterior, tem-se:
A
p B ⇔ A p~ B ∧ A ~/ B
b) Por outro lado, pelo último teorema enunciado no capítulo anterior (teorema 4.5.7 - teorema de
Cantor-Schröder-Bernstein), é imediato que a condição ii) da alínea a) dessa definição pode ser substituída
por "não existe nenhuma aplicação injectiva de B em A". Logo:
A
p B ⇔ A p~ B ∧ B p/ A
~
∇
Terminologia:
Quando A p
~ B também se diz que A é dominado por B.
∇
Facilmente se demonstra o seguinte resultado (usando o teorema de Cantor-Schröder-Bernstein para c)),
o que se deixa como exercício:
Teorema 1:
Quaisquer que sejam os conjuntos A, B e C:
a) Se A ~ B, então A p B
~
pA
~
c) Se A p B e B p A, então A ~ B
~
~
d) Se A p B e B p C, então A p C
~
~
~
p
e) A ~ B sse A p B ∨ A ~ B
b) A
∇
O próximo resultado estabelece a relação existente entre ⊆ e
p.
~
Como seria intuitivamente necessário, se A tem menos elementos ou os mesmos elementos que B,
então o número de elementos de A é menor ou igual que o número de elementos de B. Isto é, se A ⊆ B
então A
p B (alínea a) a seguir).
~
No entanto, se A tem menos elementos que B, então só se garante que o número de elementos de A é
menor que o número de elementos de B, se B for finito. Isto é, no caso de conjuntos infinitos, de A ⊂ B
não se pode concluir que A
p B, pois pode ter-se A ~ B (como se verifica p.ex. com |N0 e Z: recorde-se o
exemplo 1 da secção anterior).
Teorema 2:
a) Se A ⊆ B então A
b) A
pB
~
p B sse existe B1 ⊆ B tal que A ~ B1
~
151
Demonstração:
a) Imediato, pois se A ⊆ B então podemos considerar a função de inclusão de A em B (veja-se a definição
1-b) da secção 2 do capítulo 4), a qual é trivialmente uma injecção.
b) ⇒:
Suponha-se que A
p B. Então (por definição de p ) existe uma injecção f: A → B.
~
~
Mas então, restringindo o seu conjunto de chegada ao seu contra-domínio f[A] (= cod(f)), obtemos uma
bijecção entre A e uma parte de B. Mais precisamente, a função g:A→f[A], dada por ∀x∈A g(x)=f(x), é
uma bijecção e f[A] (= cod(f)) ⊆ B.
f
A
B
g
A
f[A] ( ⊆ B )
⇐:
Reciprocamente, suponha-se que existe B1 ⊆ B tal que A ~ B1. Então (por definição de ~) existe uma
bijecção f:A → B1.
Mas então, se estendermos o conjunto de chegada de f a B, obtemos uma injecção entre A e B. Mais
precisamente, a função g:A→B, dada por ∀x∈A g(x)=f(x), é uma injecção.
f
A
B1
g
A
B ( = B1 ∪ (B-B1) )
∇
Na secção anterior dissemos que dois conjuntos A e B tinham o mesmo cardinal (eram equipotentes)
sse podíamos estabelecer uma bijecção entre eles, o que denotámos escrevendo A ~ B, e mostrámos que tal
definição se comportava, como esperávamos, no caso dos conjuntos finitos (em que definimos
explicitamente a que era igual o seu cardinal, atribuindo-lhe um número), i.e. mostrámos que
Se A e B são finitos, então #A = #B sse A ~ B
Nesta secção introduzimos outros critérios para comparar conjuntos, quanto à sua cardinalidade,
definindo quando é que se diz que a cardinalidade (ou potência) de A é inferior à de B, o que denotámos
escrevendo A
p B, e quando é que se diz que a cardinalidade (ou potência) de A é inferior ou igual à de B,
o que denotámos escrevendo A p
~ B.
Naturalmente, no caso dos conjuntos finitos, tais definições têm (também) de coincidir com a usual
comparação dos seus cardinais. Tal é estabelecido no resultado a seguir e demonstrado em anexo.
Teorema 3:
Se A e B são finitos e se n = #(A) e k = #(B), então:
pB
~
b) n < k sse A p B
a) n ≤ k sse A
152
Demonstração: Ver anexo a este capítulo, no fim do capítulo.
∇
Assim, no caso dos conjuntos finitos, como seria necessário (para a interpretação dada a
escrever A
p e p~ ),
p B (resp. A p B) é equivalente a escrever #A ≤ #B (resp. #A < #B).
~
No caso dos conjuntos infinitos, como já referimos, não nos preocupámos em definir aqui exactamente
a que era igual o cardinal de um conjunto infinito, limitando-nos a comparar as suas "ordens de grandeza".
No entanto, poderemos também escrever #A≤#B (resp. #A<#B), mesmo quando os conjuntos (ou algum
dos conjuntos) A e B são infinitos: tal será visto como significando (apenas) que A p B (resp. A p B).
~
Exercícios:
1. Demonstre o teorema 1.
p B então C p B
~
~
3. Demonstre que se C ~ B e A p B então A p C
~
~
4. Demonstre que se C ~ A e A p B então C p B
2. Demonstre que se C ~ A e A
p B então A p C
Demonstre que se A ~ C e B ~ D, então A p B sse C p D
~
~
Demonstre que se A p B e B p C então A p C
~
Demonstre que se A p B e B p C então A p C
~
Demonstre que se A p B, então existe B1 ⊂ B tal que A ~ B1
5. Demonstre que se C ~ B e A
6.
7.
8.
9.
10. Demonstre que se B é finito, então A
p B sse existe B1 ⊂ B tal que A ~ B1
∇
Secção 4: Existência de um conjunto infinito "menor ou igual" que todos os outros
e caracterização alternativa dos conjuntos infinitos
A situação em que nos encontramos é a seguinte:
• Já sabemos como comparar a ordem de grandeza dos cardinais de quaisquer dois conjuntos !
• No que respeita aos conjuntos finitos, as definições dadas estão de acordo com a nossa intuição e com o
que estamos habituados (pelo que não aprofundaremos muito mais a questão da cardinalidade dos
conjuntos finitos) !
• No que respeita aos conjuntos infinitos, já vimos que se mantêm algumas das nossas intuições (p.ex.:
A ⊆ B ⇒ #A ≤ #B), mas não todas (p.ex.: A ⊂ B ⇒
/ #A < #B 17) !
€
17 Isto é, existem conjuntos infinitos A e B tais que A ⊂ B e #A
</
infinitos A e B tais que A ⊂ B e #A < #B: recorde-se o significado de
€
€
153
#B (embora possam também existir, e existem, conjuntos
⇒
/
na secção 2 do capítulo 1).
• Já dispomos de alguns critérios relativamente simples que nos permitem concluir que certos conjuntos
são infinitos (p.ex. para deteminar que A é infinito é suficiente mostrar que ele é equipotente a uma sua
parte própria, ou que ele é equipotente a um outro conjunto que já sabemos que é infinito) !
Mas, no que respeita aos conjuntos infinitos, existem ainda muitas questões interessantes a que não demos
resposta. Por exemplo:
i) Será que todos os conjuntos infinitos têm o mesmo cardinal ?
ii) Será que quaisquer dois conjuntos infinitos são comparáveis por intermédio da relação
(Como se passa com os conjuntos finitos.)
p?
~
iii) Será que existe um conjunto infinito que é "menor ou igual" (em termos de cardinal) que todos os
outros ?
No que respeita à questão i), à partida a intuição dir-nos-ia que existem conjuntos infinitos com maior
número de elementos que outros conjuntos infinitos. Mas, como já salientámos, a intuição pode enganarnos quando trabalhamos com o infinito. Deixaremos esta questão para o fim (para a secção 6).
No que respeita à questão ii), aceitando o axioma da escolha pode provar-se que a resposta é afirmativa,
mas não faremos aqui tal prova (o leitor interessado pode consultar p.ex. [41], págs. 142 a 145).
Finalmente, no que respeita à questão iii), se a resposta for positiva, então o principal candidato é
intuitivamente o conjunto |N1 (ou qualquer outro conjunto que lhe seja equipotente, i.e. que tenha o
mesmo cardinal que |N1), uma vez que todo o Jn={1,...,n} é finito e |N1 é infinito.
Nesta secção iremos responder à questão iii), esboçando (já a seguir) a demonstração de que |N1 é
efectivamente "menor ou igual" (em termos de cardinal) que todos os conjuntos infinitos.
Iremos igualmente, nesta secção, alargar o conjunto de critérios que dispomos para determinar se um
conjunto é infinito (ou não). Em particular, mostraremos que para um conjunto ser infinito, não só é
suficiente que ele seja equipotente a uma sua parte própria, como também é necessário (pelo que é essa
propriedade que distingue, na sua essência, os conjuntos finitos e infinitos).
Teorema 1:
Qualquer que seja o conjunto infinito A, |N1
pA
~
Demonstração:
Suponha-se que A é infinito. Pretendemos mostrar que existe uma injecção f : |N1 → A.
A ideia informal é simples:
•
define-se f(1) como sendo um qualquer elemento (que designaremos por) a1 de A
(como A é infinito, A é diferente do ∅);
•
define-se f(2) como sendo um qualquer elemento a1 de A-{a1} (= A-{f(1)})
(A-{a1}≠∅: caso contrário, A={a1}, o que não se pode verificar pois A é infinito e {a1} é finito);
•
define-se f(3) como sendo um qualquer elemento a3 de A-{a1, a2}
•
e assim sucessivamente.
154
A título meramente ilustrativo, vejamos como se pode concretizar mais rigorosamente esta ideia18:
Considere-se o conjunto, ou família19, das partes não vazias de A. Pelo axioma da escolha, dada uma
qualquer família de conjuntos não vazios é sempre possível escolher um elemento de cada conjunto da
família (de modo a obter uma família formada por um elemento de cada um desses conjuntos). Assim,
existe uma função s (de escolha) que aplica o conjunto das partes não vazias de A em A e que satisfaz
∀∅≠B⊆ A s(B)∈B.
Usando essa função de escolha pode definir-se uma aplicação H: |N1 → ℘(A), por recursão (ou
recorrência) 20, como se segue:
H(1) = { s(A) }
H(n+1) = H(n) ∪ { s(A-H(n)) } , qualquer que seja n≥1
Demonstra-se facilmente, por indução finita, que, qualquer que seja n≥1, H(n) ⊆ H(n+1) e H(n) é finito
(pelo que A-H(n)≠∅).
Finalmente define-se a aplicação f : |N1 → A desejada, como se segue:
∀n≥1 f(n) = s(A-H(n))
Que f é injectiva pode ver-se como se segue:
Sejam k ≠ n. Suponha-se que k < n (o caso k > n é análogo). Então ou k+1 < n ou k+1 = n. Logo
f(k) = s(A-H(k)) ∈ H(k+1) ⊆ H(n). Mas f(n) = s(A-H(n)) ∈ A-H(n). Logo f(k) ∈ H(n) e f(n) ∉ H(n), pelo
que f(k) ≠ f(n) (c.q.d.)
∇
O teorema anterior tem várias implicações e, em particular, permite-nos obter uma outra caracterização
equivalente de conjunto infinito: pelo teorema 3 da secção 2, já sabemos que um conjunto ser equipotente
a uma sua parte própria é uma condição suficiente para ser infinito; que tal é também uma condição
necessária decorre do teorema anterior, como se mostra a seguir.
Teorema 2:
Um conjunto A é infinito sse é equipotente a uma sua parte própria.
Demonstração:
⇐:
Teorema 3 da secção 2.
⇒:
Suponha-se que A é infinito. Então, pelo teorema 1 anterior, existe uma injecção f : |N1 → A.
18 Veja-se o livro já citado de Franco de Oliveira [41], págs. 139 a 141 e 152, para perceber bem a importância do axioma da
escolha nesta demonstração.
19 Como se referiu na nota de rodapé 48 do capítulo anterior, qualquer conjunto pode ser visto como uma família.
20 Note-se que podemos ver H(n+1) como sendo igual a T(H(n)), com T uma aplicação T:℘(A)→℘(A) assim definida:
∀ B⊂ A T(B) = B ∪ {s(A-B)} e T(A) é um qualquer subconjunto de A que é irrelevante para os fins aqui em vista.
Num capítulo à frente voltaremos a abordar este tipo de definição de função por recursão.
155
Defina-se a seguinte função g: A → B, onde B = A - {f(1)} (pelo que B é uma parte própria de A):
g(x) = x, se x ∉ f[|N1] (i.e. se x não pertence ao contradomínio de f)
∀n≥1 g( f(n) ) = f(n+1)
A
g
B = A - {f(1)}
x
|N1
f
f[|N1]
1
2
3
...
x
g
f(1)
f(2)
f(3)
...
f(2)
f(3)
f(4)
...
Resta-nos mostrar que g é uma bijecção, o que não é difícil e é feito a seguir:
•
g é sobrejectiva:
g[A] = g[f[|N1]∪(A- f[|N1])] = g[f[|N1] ] ∪ g[(A- f[|N1])] = {f(2), f(3), ...} ∪ (A- f[|N1]) = B
(c.q.d.)
•
g é injectiva:
- Suponha-se que x ≠ y e x,y∈(A-f[|N1]).
Então (por definição de g) tem-se g(x) = x ≠ y = g(y).
Logo g(x) ≠ g(y) (c.q.d.)
- Suponha-se que x ≠ y e x,y∈f[|N1]. Então:
Então (por definição de f[|N1]) existem n,k∈|N1 tais que x = f(n) e y = f(k) e (como x≠y e f
é uma função) n≠k.
Mas então, como f é injectiva, g(x) = g(f(n)) = f(n+1) ≠ f(k+1) = g(f(k)) = g(y)
Logo g(x) ≠ g(y) (c.q.d.)
- Suponha-se, finalmente, que x ≠ y, x∈f[|N1] e y∈A-f[|N1] (o caso em que x ≠ y, y∈f[|N1] e
x∈A-f[|N1] é análogo).
Então (por definição de f[|N1]) existe n∈|N1 tal que x = f(n). E (por definição de g) tem-se
g(x) = g(f(n)) = f(n+1) ∈ f[|N1] e g(y) = y ∈ A-f[|N1]
Logo g(x) ≠ g(y) (c.q.d.)
∇
E, a partir deste resultado, podemos estabelecer outros critérios úteis para poder concluir que um certo
conjunto é finito, ou infinito (critérios esses que estão de acordo com a nossa intuição).
Teorema 3:
a) Se B é infinito e B ⊆ A, então A é infinito.
b) Se B é finito e A ⊆ B, então A é finito.
Demonstração:
a) Suponha-se que B é infinito e B ⊆ A.
156
Pelo resultado anterior, existem D e f tais que D ⊂ B e f : B → D é uma bijecção.
Pelo mesmo resultado, teremos provado o que pretendemos, se mostrarmos que existe uma bijecção
entre A e uma sua parte própria.
Seja E = D ∪ (A-B) (que é uma parte própria de A, uma vez que D é uma parte própria de B) e definase g : A → E como se segue:
∀x∈B g(x) = f(x) e ∀x∈(A-B) g(x) = x
E = D∪ (A-B)
A
x
x
B
g
x
D
f(x)
Resta-nos mostrar que g é uma bijecção. Tal demonstração (que é análoga e até mais simples que a
prova da “bijectividade” da aplicação g na demonstração anterior) é feita a seguir:
• Como f[B]=D (pois f:B→D é sobrejectiva), g[A] = g[B] ∪ g[A-B] = f[B]∪(A-B) = D∪(A-B) = E,
pelo que g é sobrejectiva.
• Que g é injectiva, pode ver-se como se segue:
-
se x ≠ y e x,y∈A-B, então g(x) = x ≠ y = g(y)
-
se x ≠ y e x,y∈B, então g(x) = f(x) ≠ f(y) = g(y)
(usando o facto de f ser injectiva)
-
se x ≠ y e x∈B e y∈A-B, então g(x) = f(x) ≠ y = g(y)
(pois f[B]=D⊂B, pelo que f[B]∩(A-B)=∅, e f(x)∈f[B] e y∈A-B)
Logo g é bijectiva (c.q.d.)
b) Decorre de a): se, por absurdo, se tivesse B é finito, A ⊆ B e A infinito, então, por a), ter-se-ia B
infinito e B finito (contradição).
∇
Exemplo 1:
Já vimos que o conjunto dos naturais é infinito. Usando o teorema anterior podemos portanto concluir,
por exemplo, que é infinito o conjuntos dos racionais. (Usando este teorema podemos igualmente concluir
que são infinitos os conjuntos dos inteiros e dos reais, o que já tinhamos verificado por outro caminho, na
secção 2).
∇
O resultado a seguir estende quer o resultado anterior (uma vez que “se A ⊆ B então B p
~ A”, pelo
teorema 2-a) da secção 3), quer o teorema 4 da secção 2 (uma vez que “se A ~ B então B p
~ A” , pelo
teorema 1-a) da secção 3).
157
Teorema 4 (generalização do teorema 3 anterior e do teorema 4 da secção 2):
a) Se B é finito e A p
~ B, então A é finito.
b) Se B é infinito e B p
~ A, então A é infinito.
Demonstração:
a) Suponha-se que B é finito e A p
~ B. Então, por b) do teorema 2 da secção 3, existe B1 ⊆ B tal que
A~B1. Logo, pelo teorema 3-b) anterior, B1 é finito e, pelo teorema 4-a) da secção 2, A também é
finito.
b) Sai de a).
∇
Exemplo 2:
Suponha-se que A é infinito e que B é um conjunto qualquer, não vazio. Usando o teorema anterior
podemos facilmente concluir que AxB também é infinito:
como B≠∅, existe pelo menos um elemento b em B e a aplicação f: A → AxB, dada por
∀x∈A f(x) = (x,b)
é obviamente injectiva.
Como casos particulares tem-se, por exemplo, que |N02 é infinito.
∇
Exercícios:
1. Seja B um conjunto qualquer. Se A é infinito, o que pode concluir sobre A∪B ? (Justifique.)
2. Se for finito (pelo menos) um dos conjuntos A e B, o que pode concluir sobre A∩B ? (Justifique.)
∇
Secção 5: Conjuntos contáveis e numeráveis.
Pelo teorema 1 da secção anterior, sabemos que:
•
Todo o conjunto infinito é "maior ou igual" (em termos de cardinalidade) que |N1.
E, reciprocamente, como já sabemos que |N1 é infinito, pelo teorema 4-b) da secção anterior, temos que:
•
Todo o conjunto que é "maior ou igual" que |N1 é infinito.
No "outro sentido" 21, provaremos já a seguir que se tem a seguinte situação:
•
Todo o conjunto finito é "menor" (em termos de cardinalidade) que |N1
22
(e portanto, naturalmente, também "menor" que qualquer outro conjunto que seja equipotente a
|N1: ver exercício 5 da secção 3).
21 Pelo que acabámos de afirmar, já sabemos que os conjuntos "menores" que |N não podem ser infinitos e, portanto, são
1
finitos; e já sabemos, igualmente, que se A é finito, então A não é "maior ou igual" que |N1 , mas tal não nos garante, apenas com
o que já provámos, que A seja "menor" que |N1 , pois nós não provámos (apesar de tal se verificar) que quaisquer dois conjuntos
são comparáveis quanto ao seu cardinal.
22 Deste modo, como todo o conjunto infinito é "maior ou igual" que |N , (pelo exercício 8 da secção 3) podemos concluir, como
1
seria intuitivamente necessário, que todo o conjunto finito é
p
que qualquer conjunto infinito.
158
e, "vice-versa" (reciprocamente), todo o conjunto que é "menor" que |N1 é finito.
(e, portanto, todo o conjunto que é "menor ou igual" que |N1 é finito ou equipotente a |N1, e vice-versa).
Teorema 1:
p |N1 sse A é finito.
b) A p |N1 sse (A é finito ou A é equipotente a |N1).
~
a) A
Demonstração:
a) ⇐:
Suponha-se que A é finito.
Então A é equipotente a algum Jn (n≥0). E, como Jn ⊆ |N1, pelo teorema 2-b) da secção 3, A p |N1.
~
Mas A é finito e |N1 infinito, pelo que não podem ser equipotentes (teorema 4-b) da secção 2). Logo
A p |N1.
⇒:
Suponha-se, por absurdo, que A
p |N1 e A é infinito.
p |N1, tem-se A p |N1. Como A é infinito, |N1 p A. Mas A p |N1 e |N1 p A implica (pelo
~
~
~
~
teorema de Cantor-Schröder-Bernstein) que A ~ |N1, o que contradiz A p |N1.
b) Sai de a): A p |N1 sse (A p |N1 ou A ~ |N1) sse (A é finito ou A ~ |N1).
~
Como A
∇
Temos assim, portanto, que na "ordenação dos conjuntos pelo número dos seus elementos" podemos
distinguir três tipos de conjuntos: os conjuntos "menores" (no sentido de com menor cardinal) que |N1 - os
conjuntos finitos; os conjuntos "iguais" a (no sentido de com o mesmo cardinal que) |N1; e os eventuais23
restantes conjuntos, que serão necessariamente "maiores" (no sentido de com maior cardinal) que |N1.
A importância (em Matemática e em Computação) dos dois primeiros tipos de conjuntos justifica que
lhes demos um nome genérico e que nos debrucemos um pouco mais sobre eles.
Definição 1
24:
a) Diz-se que um conjunto A é numerável sse A ~ |N1 (i.e. sse A é equipotente a |N1).
b) Diz-se que um conjunto A é contável sse A é finito ou numerável.
∇
Teorema 1 (re-enunciado de acordo com a terminologia acabada de introduzir):
p |N1 sse A é finito.
b) A p |N1 sse A é contável.
~
a) A
∇
23 Dizemos aqui eventuais, pois ainda não provámos que exista algum conjunto com cardinal maior que o de |N .
1
24 Nesta definição seguimos a terminologia usada por Campos Ferreira. Outros autores, como Franco de Oliveira, na pág. 157
do livro [41], chamam de infinito numerável aos conjuntos que são equipotentes a |N0 , e dizem que um conjunto é numerável sse
é finito ou infinito numerável.
159
Como referimos, a importância (em Matemática e em Computação) dos conjuntos contáveis e
numeráveis justifica que nos debrucemos um pouco mais sobre eles. Em particular, é importante
dispormos de critérios práticos que nos permitam verificar se um determinado conjunto é numerável, ou
contável. O próximo teorema é útil para esse fim.
Teorema 2:
Se A ≠ ∅, então A é contável sse existe uma sobrejecção g : |N1 → A
Demonstração:
Suponha-se que A ≠ ∅. Então:
A é contável
sse (teorema 1)
A
p |N1
~
sse (definição de
p)
~
existe uma injecção f : A → |N1
sse (teorema 4.5.6)
existe uma sobrejecção g : |N1 → A
∇
Usando este teorema podemos facilmente estabelecer alguns critérios práticos úteis para os fins em
vista, como se mostra a seguir.
Teorema 3 (Critérios práticos):
a) Um conjunto (não vazio25) é contável
sse
podemos enumerar (numa sucessão1) todos os seus elementos (eventualmente com repetições26),
i.e. sse podemos dispor todos os seus elementos numa sucessão:
a1, a2, a3, ...
b) Um conjunto é numerável
sse
podemos enumerar todos os seus elementos sem repetições (numa sucessão1).
c) Um conjunto infinito é numerável
sse
podemos enumerar todos os seus elementos (eventualmente com repetições27).
25 O conjunto vazio é finito e portanto contável.
26 Repetições que ocorrerão, necessariamente, se o conjunto for finito.
27 Isto é, se já sabemos que um dado conjunto é infinito, então, para concluir que ele é numerável, basta-nos mostrar que
podemos enumerar todos os seus elementos numa sucessão (mais precisamente, numa sucessão1 ), sem nos preocuparmos em
tirar dessa enumeração eventuais repetições de elementos que nela ocorram.
160
Demonstração:
a) Uma sucessão1 de elementos de A é (ver secção 4 do capítulo 4) uma aplicação g:|N1→A
Assim, uma enumeração de todos os elementos de A pode ser vista como uma aplicação g:|N1→A que
é sobrejectiva (identificando-se ai com g(i)).
Logo, o critério indicado decorre do teorema 2 anterior.
b) A é numerável
sse
existe g:|N1→A bijectiva
sse
existe g:|N1→A sobrejectiva e injectiva
sse
existe uma sucessão1 de todos os elementos de A (g(1), g(2), ...) sem repetições
c) Imediato, por a), pois um conjunto infinito é numerável sse é contável.
∇
Vejamos alguns exemplos de aplicação destes critérios.
Mais precisamente, vamos considerar alguns conjuntos importantes de números, que conhecemos bem,
e utilizar os critérios práticos anteriores para mostrar que esses conjuntos (ao contrário do que
eventualmente poderíamos estar à espera) são numeráveis (i.e. têm o mesmo cardinal que |N1) 28.
Comecemos a nossa pequena digressão pelo conjunto dos inteiros.
Apesar de intuitivamente "sem contar com o zero, haver duas vezes mais inteiros que inteiros
positivos", o conjunto dos inteiros é numerável (como aliás já sabemos):
Exemplo 1:
É imediato que Z é numerável (pois já vimos que Z ~ |N0 e que |N0 ~ |N1, pelo que Z ~ |N1). Mas vejamos
como poderíamos mostrar que Z é numerável, usando o critério b) (do teorem 3) anterior.
De acordo com esse critério, para verificar que Z é numerável, basta mostrarmos como poderíamos
enumerar, sem repetições, todos os inteiros.
Há várias maneiras como tal pode ser feito. A ideia essencial é simples e interessante, como se mostra
a seguir.
Ora, Z é formado pelos inteiros positivos (i.e. |N1 - conjunto numerável), pelo zero e pelos inteiros
negativos (conjunto obviamente também numerável).
"Dobremos Z, pelo zero, como se fosse uma folha de papel:"
28 Os critérios práticos anteriores poderão ser usados para mostrar que um dado conjunto infinito é numerável, se for esse o
caso. Caso o conjunto em questão não seja numerável, temos de procurar outro caminho para provar esse facto (o que será
discutido na próxima secção).
161
. . . -4 , -3, -2, -1, 0, 1, 2, 3, 4, . . .
1
2
3
4
...
-1
-2
-3
-4
...
0
A partir daqui é fácil vislumbrar uma das (possíveis) maneiras por que podemos enumerar os inteiros:
começa-se pelo 0, e depois vai-se buscar, alternadamente, um elemento ao conjunto de cima (conjunto dos
inteiros positivos) e ao conjunto de baixo (conjunto dos ineiros negativos), seguindo a forma como eles
estão enumerados nesses conjuntos:
1
2
3
4
...
-1
-2
-3
-4
...
0
Obtém-se, deste modo, a seguinte enumeração dos inteiros:
0 , 1, -1, 2, -2, 3, -3, ....
que corresponde a estabelecer a seguinte bijecção entre |N1 e Z:
Z:
0
1
-1
2
-2
3
-3
...
|N1:
1
2
3
4
5
6
7
...
Naturalmente, fizemos apenas o esboço da prova (que para muitos efeitos será suficiente). A prova
rigorosa exigiria que mostrássemos que estavamos mesmo em presença de uma enumeração de todos os
inteiros, sem repetições, isto é, no fundo, que identificássemos a "regra" (a aplicação) g:|N1→Z que
"gera" tal sucessão29 e mostrássemos que se tratava de uma bijecção.
Iremos aqui, em geral, limitar-nos a efectuar o esboço da prova, neste sentido indicado.
∇
Nota (Z versus |N1):
O conjunto Z tem o mesmo número de elementos que |N1: podemos estabelecer uma bijecção entre os dois
conjuntos. Tal significa (como já referimos) que podemos passar dos inteiros para os inteiros positivos
simplesmente mudando as suas designação; mas esses elementos estão dispostos (ordenados) de forma
diferente nos dois conjuntos, o que lhes dá diferentes propriedades (por exemplo, não há um primeiro
inteiro, etc.).
29 Dada no caso por: g(n) = - (n DIV 2), se n é ímpar, e g(n) = n DIV 2, se n é par, onde DIV denota a operação que nos dá o
quociente da divisão inteira.
162
Quando pensamos em conjuntos, como Z ou |N1, não pensamos apenas nos seus elementos, mas em
toda a "estrutura" que está implicitamente associada a estes. Neste sentido, os conjuntos
Z
e |N1 são
essencialmente distintos. Estes aspectos serão abordados no próximo capítulo.
∇
Exemplo 2:
Será que Q (o conjunto dos racionais) é numerável ?
Como entre cada dois racionais há uma infinidade de racionais30, não é nada óbvio que a resposta seja
sim. No entanto, tal é o caso, como se mostrará no exemplo 3.
Para já, ilustremos apenas como se pode mostrar que
Q+
(o conjunto dos racionais positivos) é
numerável (esboçando a respectiva prova).
Como já sabemos que
Q+
é infinito (pois |N1 ⊆ Q + e |N1 é infinito), podemos aplicar o critério c)
anterior (teorema 3 -c)) e mostrar que Q+ é numerável, mostrando que conseguimos enumerar todos os seus
elementos, eventualmente com repetições, numa sucessão (ou seja, não temos de nos preocupar em retirar
da sucessão eventuais elementos repetidos).
Ora, sabemos que cada elemento de
Q+
é representável por uma "fracção" m , com m e n inteiros
n
positivos (aliás de infinitas maneiras distintas: p.ex. 2 = 2 = 4 = ...). Assim, basta-nos enumerar todas
1
essas "fracções" m (todos esses pares (m,n)).
2
n
Tal pode ser feito seguindo o esquema proposto por Cantor, considerando uma matriz/tabela infinita,
tendo como índices das linhas e das colunas os inteiros positivos, e percorrendo os elementos da tabela
como se ilustra a seguir (seguindo as setas, onde se percorre a matriz pelas diagonais: diagonalização):
1
2
3
4
...
1
1
1
2
1
3
1
4
1
...
2
1
2
2
2
3
2
...
...
3
1
3
2
3
...
...
...
4
1
4
...
...
...
...
...
...
...
...
...
...
30 Por exemplo: 2, .... , 2 + 1 ,
4
2 + 1 , 2 + 1 , 3 ( = 2 + 1 = 2 + (3 - 2) )
3
2
163
Percorrendo todos os elementos da tabela seguindo as setas indicadas obtém-se:
1 , 2 , 1 , 1 , 2 , 3 , 4 , 3 , 2 , 1 , ...
1
1
2
3
2
1
1
2
3
4
Tal corresponde a dispor todas as fracções da forma seguinte:
• Começa-se pelas fracções m para a qual a soma m+n é a menor possível (i.e. 2).
n
Tem-se apenas a fracção:
1
1
• a seguir dispõem-se as fracções m tais que m+n = 3 :
n
2
1
e 1 (a ordem porque dispomos estas fracções não é relevante)
2
• a seguir dispõem-se as fracções m tais que m+n = 4 :
n
1 , 2 e 3 (a ordem porque dispomos estas fracções não é relevante)
3
2
1
• e assim sucessivamente.
∇
Exemplo 3:
Mostremos agora que Q é numerável.
De forma análoga à usada no exemplo 2, podemos mostrar que Q- (o conjunto dos racionais negativos)
também é numerável (aliás, sabendo já que Q+ é numerável, é trivial que
que a aplicação f: Q+ →
E sabendo que
Q
+
Q
e
Q
-
também o é, pois é imediato
-
, dada por f(x) = -x, é uma bijecção).
Q
-
são numeráveis, podemos então mostrar que se podem enumerar todos os
racionais, seguindo uma estratégica idêntica à usada no exemplo 1 para enumerar todos os inteiros, como
se ilustra a seguir.
Como que Q+ e Q - são numeráveis, existem enumerações (até sem repetições):
Mas
Q
f(1)
f(2)
f(3) ...
de Q+
(i.e. existe f:|N1→ Q+ bijectiva)
g(1)
g(2) g(3) ...
de Q-
(i.e. existe g:|N1→ Q- bijectiva)
= Q- ∪ {0} ∪ Q+. Logo31 podemos enumerar os racionais como se segue:
f(1)
f(2)
f(3)
f(4)
...
g(1)
g(2)
g(3)
g(4)
...
0
Isto é, tem-se a seguinte enumeração de Q :
31 Como Q = Q - ∪ {0} ∪ Q +, uma vez verificado que Q - e Q + são numeráveis, pode concluir-se que Q
também o é,
recorrendo directamente ao resultado a seguir, cuja demonstração (no caso 3) se baseia, precisamente, numa técnica de
enumeração da união análoga à ilustrada neste exemplo.
164
0
f(1)
g(1)
f(2)
g(2) ...
=
=
=
=
=
...
h(1)
h(2)
h(3)
h(4)
h(5)
...
que corresponde à aplicação h:|N1→Q dada por
h(1) = 0
h(2n) = f(n), qualquer que seja n≥1
h(2n+1) = g(n), qualquer que seja n≥1
aplicação que é bijectiva (o que se deixa como exercício provar).
∇
Nos exemplos anteriores aplicámos os critérios atrás para mostrar que certos conjuntos concretos eram
numeráveis. Podemos também usar esses criérios para deduzir resultados genéricos sobre conjuntos
numeráveis.
A seguir, a técnica do exemplo anterior é adaptada para provar que a união de dois conjuntos
numeráveis é numerável.
Teorema 4:
A união de um conjunto numerável com um conjunto contável é numerável.
Demonstração:
Suponha-se que A é numerável e que B é contável.
Como A é numerável existe uma bijecção f:|N1→ A (que enumera todos os elementos de A, sem
repetições).
Caso 1: B=∅
Então A∪B = A é numerável
Caso 2: B é finito, não vazio.
Então existem n≥1 e elementos b1, ..., bn tais que B={b1, ..., bn}, tendo-se que
b1 , ... , bn , f(1) , f(2) , ...
constitui uma enumeração de todos os elementos de A∪B.
E embora tal enumeração possa ter repetições, pois A e B podem ter elementos em comum, como
A∪B é infinito (exercício 1 da secção 4), tal não é impeditivo a que se conclua que A∪B é numerável
(basta usar o critério/alínea c) do teorema 3).
Caso 3: B é numerável.
Então existe uma bijecção g:|N1→B (que enumera todos os elementos de B, sem repetições).
Logo
f(1) g(1) f(2) g(2) ...
constitui uma enumeração de todos os elementos de A∪B.
Tal como no caso anterior, esta enumeração pode ter repetições, mas tal não é impeditivo a que se
conclua que A∪B é numerável
∇
165
O resultado anterior pode generalizar-se facilmente (por indução finita) como se mostra a seguir:
Teorema 5:
Se A1, ..., An são n(≥2) conjuntos contáveis, e pelo menos um dos A1, ..., An é numerável, então a sua
n
união ( U Ai ) é numerável.
i =1
Demonstração:
Seja P(n) a asserção
"Quaisquer que sejam os n conjuntos A1, ..., An, se todos são contáveis e pelo menos um deles é
n
numerável, então
U
Ai é numerável"
i =1
e demonstremos, por indução em n(≥2), que
∀n≥2 P(n) (naturalmente, tem-se mesmo, ∀n≥1 P(n))
Base: verifica-se P(2)
Dem: Teorema 4 anterior.
Passo de indução: Seja n≥2 qualquer.
HI: verifica-se P(n)
Tese de indução: verifica-se P(n+1)
Dem:
Sejam A1 ,..., An+1, n+1 quaisquer conjuntos, todos contáveis e em que pelo menos um deles é
numerável.
Designe-se por B1, ..., Bn, n desses n+1 conjuntos, de modo a incluir um conjunto numerável em B1,
..., Bn, e designe-se por Bn+1 o conjunto restante (p.ex. se A1 é numerável, então pode escolher-se
Bi =Ai , para i=1,...,n+1; caso contrário, pode escolher-se Bi =Ai+1, para i=1,...,n e Bn+1=A1).
n
Por HI,
U
n +1
Bi é numerável. E portanto, pela base,
i =1
U
i =1
n
Ai = ( U Bi ) ∪ Bn+1 é numerável (c.q.d.)
i =1
∇
O resultado anterior pode ainda generalizar-se como em a) a seguir (a sua demonstração já é, contudo,
um pouco mais complexa, e será deixada para o anexo, incluído no fim deste capítulo):
Teorema 6:
a) Se B é um conjunto numerável de conjuntos contáveis, em que pelo menos um deles é numerável
(podendo ser todos numeráveis, ou não), então ∪B é numerável.
b) Se B é um conjunto numerável de conjuntos contáveis, disjuntos dois a dois, não vazios, então
∪B é
numerável.
Demonstração: Ver anexo a este capítulo, no fim do capítulo.
∇
166
Termina-se esta introdução aos conjuntos numeráveis, enunciando e demonstrando mais dois resultados
sobre estes conjuntos (cuja demonsração também é deixada para o anexo).
Teorema 7:
Se A é numerável, então o conjunto formado por todos os subconjuntos finitos de A é numerável.
Demonstração: Ver anexo a este capítulo, no fim do capítulo.
∇
Teorema 8
32:
Se A é numerável, então o conjunto de todas as sequências, não vazias, de elementos de A é numerável 33.
Demonstração: Ver anexo a este capítulo, no fim do capítulo.
∇
Exercícios:
1. Demonstre que se A e B são numeráveis, então existe uma bijecção entre A e B.
2. Demonstre que um subconjunto infinito de um conjunto numerável, é numerável.
3. Esboce a demonstração de que |N1 x |N1 é numerável.
4. Sabendo que f: |N1 → A e g: |N1 → B são bijecções, e que A e B são dois conjuntos disjuntos, defina
uma bijecção h: |N1 → A∪B.
5. Será que (|N1 x |N1) ∪ Z é numerável ? Justifique.
∇
Secção 6: Conjuntos não contáveis
Ainda não respondemos à questão i) que formulámos no início da secção 4:
"Será que todos os conjuntos infinitos têm o mesmo cardinal ?".
E, neste momento, apesar da intuição nos dizer que há conjuntos infinitos "muito maiores" que |N1,
começamos a poder questionar-nos se não se verificará mesmo que todos os conjuntos infinitos são
32 Este resultado é importante no estudo das linguagens, na medida em que ele nos diz que se o alfabeto da linguagem for
numerável, então o conjunto de todas as sequências de símbolos do alfabeto também o é. Logo, como as frases de uma
linguagem são sequências de símbolos do alfabeto,
embora em geral nem todas as sequências de símbolos sejam frases
(admissíveis), o conjunto de todas as frases está contido no conjunto anterior e, portanto, é contável (em qualquer caso
interessante, numerável).
33 Recorde-se que, de acordo com a nossa terminologia, uma sequência é finita (às "sequências infinitas" chamámos sucessões).
Por outro lado, é imediato que se o conjunto de todas as sequências, não vazias, de elementos de A é numerável, então o
conjunto de todas as sequências de elementos de A também é numerável
167
numeráveis34 (repare-se que até o conjunto dos racionais é numerável, apesar de entre quaisquer dois
racionais existir uma infinidade de racionais35).
Nesta secção, e para terminar esta nossa introdução ao tópico da cardinalidade, mostraremos que, de
facto, existem conjuntos não contáveis.
A demonstração de que existem conjuntos não contáveis utiliza o (importante) método da diagonal,
cuja ideia passamos a explicar.
Ideia do método da diagonal:
Suponha-se que se quer mostrar que uma certa colecção de entidades, de certo género (conjuntos, funções,
etc.) não é contável.
Supõe-se, por absurdo, que é contável. Então sabemos que se pode enumerar todos os seus
elementos36. Seja χ 1, χ 2, ... uma tal enumeração.
Então procura-se construir um objecto χ desse género, que é diferente de todos os objectos χ n, n≥1
(levando-nos à contradição desejada), de acordo com a seguinte ideia:
Fazer "χ e χn diferir em n" (i.e. nalguma propriedade relacionada com n)
1
2
3
...
χ1
χ2
χ3
...
...
A interpretação do que significa fazer "χ e χn diferir em n" depende naturalmente do género de entidades
com que estamos a trabalhar. Por exemplo:
34 Repare-se que se se verificasse que todos os conjuntos infinitos eram numeráveis, então todos eles seriam equipotentes, pelo
que não teria tido qualquer interesse introduzir as relações de comparação p e p (uma vez que para comparar a
~
cardinalidade de conjuntos finitos, basta-nos comparar os seus cardinais recorrendo às usuais relações de < e ≤ entre naturais).
35 É claro que, considerando apenas os conjuntos de números que conhecemos bem, ainda nos falta averiguar o que se passa
com o conjunto dos reais. Ainda há a esperança que ele possa ser o "contra-exemplo" (à afirmação de que "todos os conjuntos
infinitos são numeráveis") que estamos à procura. Como veremos, |R é de facto um dos conjuntos que são não numeráveis.
36 Se se estiver a tentar provar apenas que não é numerável, então pode supor-se por absurdo que é numerável, pelo que se
sabe que se pode enumerar todos os seus elementos sem repetições. Se só se estiver a assumir, por absurdo, que é contável
(como acima), então não podemos garantir que nessa enumeração de todos os elementos não haja repetições, mas tal é
irrelevante para o método. Refira-se, aliás, que este método é usado normalmente para provar que um dado conjunto infinito não
é numerável (é demasiado grande para ser numerável) e, para um conjunto infinito, ser numerável é equivalente a ser contável.
168
• Se estivermos a trabalhar com funções (i.e. se as nossas entidades forem funções), a interpretação
natural é fazer χ(n) tomar um valor diferente de χn(n) 37;
• Se estivermos a trabalhar com conjuntos (i.e. se as nossas entidades forem conjuntos ), a expressão "χ
diferir de χn em n" surge naturalmente associada à "pertença" de n ao conjunto χ a definir.
Os exemplos a seguir ajudar-nos-ão a concretizar esta ideia.
Teorema 1 / Exemplo 1:
O conjunto ℘(|N1) (das partes de |N1) não é contável.
Demonstração:
Se ℘(|N1) fosse contável, então poderíamos enumerar todos os seus elementos (que, no caso, são
conjuntos). Seja
A1 , A2 , A3 , ...
uma tal enumeração.
1
2
3
...
A1
A2
A3
...
...
Defina-se então B ⊆ |N1 como se segue:
∀n≥1 (n ∈ B sse n ∉ An).
É imediato que: ∀n≥1 B ≠ An.
Mas B∈℘(|N1).
Logo, A1 , A2 , A3 , ... não pode constituir uma enumeração de todos os conjuntos em ℘(|N1).
∇
Podemos portanto, desde já, concluir que existem conjuntos não contáveis !
Antes de vermos outros exemplos de aplicação do método da diagonal, saliente-se que o resultado
anterior pode ser generalizado. De facto, o que de essencial é estabelecido no resultado anterior é que38
|N1 ~/ ℘(|N1). Ora, pode provar-se que a propriedade anterior (“de um conjunto não ser equipotente ao
37 Note-se que isso pode ser feito de modo a garantir que χ satisfaz outros requisitos.
38 Pois é fácil verificar que |N p ℘(|N ) (demonstre!), e portanto
1
℘(|N1 )
p
~
~
|N1 sse ℘(|N1 )
1
~ |N1
(i.e. ℘(|N1 ) é contável sse é numerável)
169
conjunto das suas partes”) não é um exclusivo do conjunto |N1, verificando-se para qualquer conjunto. Tal
é estabelecido no (importante) teorema 2 abaixo.
Para melhor percebermos a demonstração desse teorema, iremos em seguida “re-visitar” a demonstração
do teorema anterior, reformulando-a de modo a torná-la facilmente generalizável.
Reformulação da demonstração do teorema 1 anterior:
No teorema 1 pretendíamos provar que ℘(|N1) não era contável.
• Supusemos então, por absurdo, que ℘(|N1) era contável, o que garantia a existência de uma enumeração
A1 , A2 , A3 , ...
de todos os elementos de ℘(|N1) (i.e. de todos os subconjuntos de |N1).
Isto é, dito de outra maneira, existia uma aplicação f:|N1 → ℘(|N1) que era sobrejectiva (com An = f(n)).
• Para obter a contradição desejada, a estratégia foi a de tentar mostrar que existia B∈℘(|N1) tal que
∀n≥1B≠An, o que entraria em contradição com o facto de A1, A2,... ser uma enumeração de todos os
elementos de ℘(|N1).
Dito de outra forma, a ideia foi mostrar que existia B∈℘(|N1) tal que ∀n∈|N1(B≠f(n)), o que implicaria
que B∉f[|N1], entrando em contradição com o facto de f:|N1→℘(|N1) ser sobrejectiva.
• E, para a construção de B, considerou-se que B era o subconjunto de |N1 assim definido:
∀n≥1 (n ∈ B sse n ∉ An)
i.e.
∀n∈|N1 (n ∈ B sse n ∉ f(n))
(o que garantia que, qualquer que seja n∈|N1, B≠f(n),
pois B e f(n) divergiam pelo menos em relação à “inclusão” do valor n)
Dito de outra forma, definiu-se B como se segue:
B = {n∈|N1: n ∉ f(n)}
∇
Teorema 2 (Cantor):
Qualquer que seja o conjunto A:
a) A
~/ ℘(A)
b) A
p
℘(A)
Demonstração:
a) Suponha-se, por absurdo, que existia uma bijecção
f : A →℘(A)
e mostremos que
existe B ∈ ℘(A) tal que B ∉ f[A] (= contra-domínio de f)
o que é uma contradição, pois f é (por hipótese) sobrejectiva.
Seja B = {x∈A: x ∉ f(x)}.
Tem-se B ⊆ A e, portanto, B ∈ ℘(A).
Por outro lado, ∀x∈A (x∈B ⇔ x∉f(x)). Logo ∀x∈A B ≠ f(x).
E, portanto, B ∉ f[A] (c.q.d.)
170
b) É imediato que g : A →℘(A), dado por ∀x∈A g(x) = {x}, é uma injecção.
p ℘(A).
~
Mas, por a), A ~/ ℘(A).
Logo A
Portanto A
p
℘(A).
∇
Este resultado permite-nos concluir que não há um um cardinal maior (por
f ) que todos os outros !
Para terminar este tópico, vejamos mais alguns exemplos de aplicação do método da diagonal.
Exemplo 2:
O conjunto das aplicações de |N1 em |N1 não é contável.
Demonstração:
Se o conjunto das aplicações de |N1 em |N1 fosse contável, seria possível enumerar todas as aplicações de
|N1 em |N1.
Seja
f1 , f2 , f3 , ...
uma possível enumeração de tal conjunto.
Assim, se conseguirmos construir uma aplicação f: |N1 → |N1 que seja diferente de f1 , f2 , f3 , ...,
obtemos a contradição desejada.
Para a construção de f: |N1 → |N1 o método da diagonal diz-nos que devemos definir f de modo que f
seja diferente de fn em n (para cada n≥1):
1
2
3
...
f1
f1(1)
f1(2)
f1(3)
...
f2
f2(1)
f2(2)
f2(3)
...
f3
f3(1)
f3(2)
f3(3)
...
...
...
...
...
...
Ora, a maneira natural de fazer f diferente de fn em n, é definir f(n) de modo a ter-se f(n) ≠ fn(n) (para
cada n≥1).
Uma hipótese (muito simples) consiste em definir:
∀n≥1 f(n) = fn(n)+1
Facilmente se constata que ∀n≥1 f ≠ fn, como se pretendia.
∇
171
A demonstração do próximo (importante) resultado constitui mais uma ilustração do método da
diagonal.
Teorema 3 / Exemplo 3:
O conjunto |R (dos reais) não é contável.
Esboço da demonstração:
Designe-se por uma dízima infinita própria, uma dízima da forma
y0 , y1 y2 y3 ...
em que:
i) y0 ∈ Z
ii) yi ∈ {0, ..., 9}, para todo o i≥1
iii) e não existe k ∈ |N1 tal que yi = 0, para todo o i≥k.
Ora, não só se tem que toda a dízima infinita própria representa um número real, como se pode provar
que todo o real pode ser representado por uma dízima infinita própria.
Por exemplo:
Π = 3,14159... ; -3 = -2,9999... ; 0,46 = 0,4599999... ; 23 = 22,9999...
39
; etc.
Pode ainda provar-se que uma tal representação é única.
Sabendo isto, podemos mostrar que |R não é contável, recorrendo ao método da diagonal:
Se |R fosse contável, seria então possível enumerar todas as dízimas infinitas próprias acima referidas.
Seja
x1
=
x10 , x11 x12 x13 ...
x2
=
x20 , x21 x22 x23 ...
x3
=
x30 , x31 x32 x33 ...
...
...
...
uma tal enumeração
Se conseguirmos definir uma dízima infinita própria z, que seja diferente de x1, x2, ..., teremos obtido
a contradição desejada.
Usemos o método da diagonal para construir tal dízima (fazendo z diferir de xn no dígito que está na
posição n, para cada n≥1 40):
Considere-se, por exemplo, a dízima infinita própria
z = z0 , z1 z2 z3 ...
assim definida:
z0 = 0
e, qualquer que seja n≥1:
39 Por exemplo:
22,99999... = 22 + 9 * 0,1 + 9 * 0,01 + 9 * 0,001 + ... =
+∞
22 +
∑
i=1
9(
1 i
1
) = 22 + 9
10
10
+∞
∑( 101 )
i= 0
1 10
1
= 22 + 9
= 23
10 9
10 1− 1
10
1
i =
22 + 9
40 Há apenas que ter cuidado em garantir que se obtém uma dízima infinita própria! As condições i) e ii) não levantam
€
quaisquer €
problemas (para z€
€ qualquer inteiro, por exemplo 0); uma maneira de garantir a conndição iii)
0 podemos escolher uma
consiste em definir todos os dígitos zn (n≥1) como sendo diferentes de zero.
172
zn = 1, se xnn ≠ 1
zn = 2, se xnn = 1
É imediato que z é uma dízima infinita própria (z0 ∈ Z, zi ∈ {0, ..., 9}, para todo o i≥1, e não existe
k ∈ |N1 tal que zi = 0, para todo o i≥k).
E ∀n≥1 (z ≠ xn), uma vez que ∀n≥1 (zn ≠ xnn).
∇
Exemplo 4:
Qualquer intervalo de reais [a,b] (com a<b) não é contável.
Demonstração:
Para provar este resultado não ncessitamos de recorrer ao método da diagonal, já que ele sai directamente do
resultado anterior, uma vez que [a,b] ~ |R (ver exemplos 2, 4 e 5 da secção 2).
∇
Observações (finais):
1) Pode provar-se que |R ~ ℘(|N1)
2) À potência (ou cardinalidade) de |R (ou de qualquer conjunto que lhe seja equipotente) é costume chamar
a potência do contínuo.
3) A hipótese do contínuo consiste na seguinte conjectura:
não existe qualquer conjunto S tal que #|N1 < #S < #|R
isto é:
não existe qualquer conjunto S tal que |N1
p
S
p
|R
4) Como já se referiu (teorema 2 - teorema de Cantor), não há um cardinal maior (por
f ) que todos os
outros:
"Qualquer que seja o conjunto A, A
p
℘(A)"
5) A hipótese generalizada do contínuo consiste na conjectura seguinte:
Qualquer que seja o conjunto infinito B,
não existe qualquer conjunto S tal que
B
p
S
p
℘(B)
(Se atendermos a que se disse em 1) que se pode provar que |R ~ ℘(|N1), facilmente se percebe porque é
que esta hipótese é uma generalização da hipótese do contínuo.)
De acordo com esta hipótese, e numa linguagem informal, podemos dizer que os cardinais dos
conjuntos infinitos "aumentam aos saltos": primeiro temos o cardinal de |N1, daí passamos para o
cardinal de ℘(|N1), daí para o cardinal de ℘(℘(|N1)), e assim sucessivamente.
Não se conseguiu provar que esta hipótese seja verdadeira, ou falsa. Gödel (em 1940) provou que a
hipótese generalizada do contínuo não é inconsistente com os usuais axiomas da teoria dos conjuntos.
Coen (em 1963) provou que esta hipótese é independente dos outros axiomas da teoria dos conjuntos.
Para saber mais sobre este tópico consulte-se p.ex. o livro (já várias vezes aqui referido) [41]
∇
173
Exercícios:
1. Demonstre que o conjunto das aplicações de Z em Z não é contável.
2. Demonstre que o conjunto das funções parciais de |N1 em |N1 não é contável.
∇
Exercício final:
Obélix, ainda achas
que os Matemáticos
são loucos ?
Nem pensar! Já apanhei a
ideia. Quando se come
muitos, muitos javalis, mais
um, menos um, tanto faz.
Por favor, mais um javali!
Será que o Obélix tem razão ?
∇
174
Anexo: Demonstração de alguns resultados deste capítulo
• Demonstração do lema 1 da Secção 2
Lema 1:
Qualquer que seja o natural n, o conjunto Jn não é equipotente a uma sua parte própria.
Demonstração:
Suponha-se que existia um natural n tal que Jn era equipotente a uma sua parte própria B.
Tal significava que existia uma bijecção g: Jn → B.
Mas então a aplicação g1: Jn → Jn assim definida ∀x∈Jn g1(x) = g(x), seria injectiva, mas não sobrejectiva
(uma vez que B era uma parte própria de Jn).
Logo, teremos demonstrado o teorema, se provarmos que:
toda a injecção f : Jn → Jn é sobrejectiva.
Mais precisamente, designemos por C(n) a condição
" qualquer injecção entre Jn e Jn é sobrejectiva"
e provemos por indução finita ("em n") que todo o natural n satisfaz C(n) (i.e. que C(n) é verdadeira
qualquer que seja o natural n).
Base (da indução): C(0) é verdadeira
Dem.:
Como J0 = ∅, a única injecção entre J0 e J0 (aliás, a única aplicação de J0 em J0) é a aplicação vazia
em J0, a qual é necessariamente sobrejectiva, pois tem como contradomínio o conjunto ∅ (= J0).
Passo de indução:
Seja n∈|N0 qualquer. Queremos provar que C(n) ⇒ C(n+1)
Suponha-se que se verifica C(n) (hipótese de indução - HI)
Queremos provar que se verifica C(n+1) (tese da indução)
Dem.:
Seja f : Jn+1 → Jn+1 uma qualquer injecção. Pretendemos provar (tese actual) que cod(f) = Jn+1.
Vamos definir, a partir de f, uma função g : Jn+1 → Jn+1, também injectiva, que satisfaz: ∀x∈Jng(x)∈Jn, e
que é sobrejectiva sse f o for. (Note-se que Jn+1 = Jn ∪ {n+1}.)
Caso 1: ∀x∈Jn f(x)∈Jn. (Se n+1=1, estaremos necessariamente neste caso, pois J0=∅.)
Defina-se g = f.
Caso 2: Suponha-se agora que existe j∈Jn tal que f(j) = n+1 (note-se que não só não poderá existir mais
do que um j∈Jn tal que f(j)=n+1, como existindo um então f(n+1) será diferente de n+1, pois f é
injectiva).
Defina-se então g : Jn+1 → Jn+1 (i.e. g : {1,...,n+1} → {1,...,n+1}) como se segue:
175
g(i)
=
f(i), se i≠j e i≠n+1
=
f(n+1), se i = j
( i.e. g(j) = f(n+1) )
=
f(j), se i = n+1
( i.e. g(n+1) = f(j) = n+1)
Isto é, g coincide com f, com excepção de que troca os valores que f atribui a j e a n+1.
Em qualquer dos casos, é imediato que g é injectiva (em virtude de f o ser). Mais ainda, se g for
sobrejectiva, então f também terá de o ser (também em qualquer um dos dois casos). Assim, daqui em
diante podemos esquecer f e provar apenas que g é sobrejectiva ("nova tese").
Considere-se a aplicação g1 : Jn → Jn definida como se segue: ∀x∈Jn g1(x) = g(x).
É imediato que g é uma injecção (pois "na prática" g1 não é mais do que a restrição de g a Jn
41).
Mas então, pela hipótese de indução, g1 é necessariamente sobrejectiva.
E portanto, como g1 coincide com g em Jn, todo o elemento de Jn é imagem por g de algum elemento
de Jn. Logo, como g é injectiva, g(n+1)∉J n. Pelo que se terá de ter g(n+1) = n+1. Conclui-se,
portanto, que g é sobrejectiva (c.q.d.)
∇
• Demonstração do teorema 3 da Secção 3
O teorema 3 da secção 3 estabelece que
"se A e B são finitos, então: i) #A ≤ #B sse A
p B, e ii) #A < #B sse A p B"
~
Vejamos uma das maneiras de demonstrar este resultado.
Comecemos por demonstrar o lema seguinte:
Lema:
Qualquer que seja o natural n, tem-se (asserção designada na demonstração por P(n)):
"qualquer que seja o conjunto B, se B ⊂ Jn, então B é finito e #(B) < n"
Demonstração:
Provemos o resultado por indução "em n":
Base (da indução): P(0) é verdadeira
Dem.:
Como J0 = ∅, não existe qualquer conjunto estritamente contido em J0, pelo que o resultado é
(vacuosamente) verdadeiro.
Passo de indução:
Seja n∈|N0 qualquer. Queremos provar que P(n) ⇒ P(n+1)
Suponha-se que se verifica P(n) (hipótese de indução - HI)
Queremos provar que se verifica P(n+1) (tese da indução)
176
Dem.:
Seja B um qualquer conjunto estritamente contido em Jn+1 (i.e. B ⊂ Jn+1).
Queremos provar que B é finito e #(B) < n+1.
Consideremos os seguintes casos possíveis (alternativos):
Caso 1: B = Jn.
Então B ~ Jn, pelo que B é finito e #(B) = n < n+1.
Caso 2: B ⊂ Jn.
Então, por HI, B é finito e #(B) < n. Logo #(B) < n+1.
Caso 3: n+1 ∈ B.
Ora, como B ⊂ Jn+1 e Jn+1 = Jn ∪ {n+1}, tem-se então:
B = B ∩ Jn+1 = B ∩ (Jn ∪ {n+1}) = (B ∩ Jn) ∪ (B ∩ {n+1}) = (B ∩ Jn) ∪ {n+1}
Mas (B ∩ Jn) ⊂ Jn
(como (B ∩ Jn) ⊆ Jn, se não se verficasse (B ∩ Jn) ⊂ Jn era porque B ∩ Jn = Jn; mas então
B = (B ∩ Jn) ∪ {n+1} = Jn ∪ {n+1} = Jn+1, o que contradiz a assumpção de que B ⊂ Jn+1).
Logo, por HI, (B ∩ Jn) é finito e existe k < n tal que #(B ∩ Jn) = k.
Isto é, existe uma bijecção f: B ∩ Jn → Jk,
Considere-se então a função g : B → Jk+1, assim definida:
g(n+1) = k+1 e ∀x∈(B ∩ Jn) g(x) = f(x)
(note-se que g está bem definida: como B = (B∩Jn)∪{n+1} e n+1∉(B ∩ Jn), podemos
atribuir a g(n+1) o valor que quisermos do conjunto de chegada Jk+1=Jk∪{k+1}).
Como f é uma bijecção entre B∩Jn e Jk, Jk+1 = Jk∪{k+1} e k+1∉Jk, é imediato que g é uma
bijecção.
Mas então B é finito e #(B) = k+1 < n+1 (c.q.d.)
∇
A partir deste lema facilmente se deduz o seguinte resultado:
Corolário:
Se B é finito e A ⊂ B, então A é finito e #A < #B
Demonstração:
Suponha-se que B é finito e A ⊂ B.
Como B é finito, existe um natural n tal que #(B) = n.
Isto é B~Jn, ou seja, existe uma bijecção f: B → Jn.
Restrinja-se o conjunto de partida de f a A e o seu conjunto de chegada a f[A]; isto é, mais precisamente,
considere-se a função g: A → f[A] dada por ∀x∈A g(x) = f(x).
É imediato que g é uma bijecção, pelo que A ~ f[A].
41 A única diferença entre g1 e a função restrição de g a J reside em o conjunto de chegada de g1 ser também J , e não J .
n
n
n+1
177
Por outro lado, como A ⊂ B e f é injectiva, f[A] ⊂ f[B] (=Jn). Logo f[A] ⊂ Jn e portanto, pelo lema
anterior, f[A] é finito e #(f[A]) < n.
Logo (pelos teoremas 4-a) e 2-c) da secção 2):
A é finito e #(A) = #(f[A]) < n = #(B)
(c.q.d.)
∇
Refira-se a propósito, num breve parêntese, que deste corolário (juntamente com o teorema 2-b) da secção
3) facilmente se retiram os seguintes outros critérios para poder concluir que um certo conjunto é finito,
ou infinito:
Resultado (outros critérios para determinar se um conjunto é finito ou infinto):
a) Se B é finito e A ⊆ B, então A é finito (e #A ≤ #B).
b) Se A é infinito e A ⊆ B, então B é infinito.
p B, então A é finito.
~
d) Se A é infinito e A p B, então B é infinito.
~
c) Se B é finito e A
Demonstração:
a) Imediato (pelo corolário).
b) Decorre de a):
se, por absurdo, se tivesse A infinito, A ⊆ B e B finito, então, por a), ter-se-ia A infinito e A finito
(contradição).
c) Suponha-se que B é finito e A
p B.
~
Então, por b) do teorema 2 da secção 3, existe B1 ⊆ B tal que A~B1.
Logo, pela alínea a), B1 é finito e, pelo teorema 4-a) da secção 2, A também é finito.
d) Sai de c).
∇
Estes critérios foram também demonstrados neste capítulo (na secção 4), mas sem recurso ao lema atrás,
utilizando antes outros resultados.
E, usando o corolário atrás, pode deduzir-se o resultado desejado:
Resultado (teorema 3 da secção 3):
Se A e B são finitos e se n = #(A) e k = #(B), então:
pB
~
b) n < k sse A p B
a) n ≤ k sse A
Demonstração:
a) Sejam A e B finitos e n = #(A) e k = #(B).
a-i) Suponha-se que n≤k.
178
Então Jn ⊆ Jk, pelo que podemos definir a função de inclusão de Jn em Jk:
inc : Jn → Jk, com ∀x∈Jn inc(x) = x
Por outro lado, como n = #(A) e k = #(B), existem bijecções f : A → Jn e g : B → Jk,
Mas então a aplicação h: A → B, definida por h = g-1 º inc º f (veja-se o diagrama a seguir).
f
A
Jn
h
inc
B
g-1
Jk
é injectiva (porquê?). Logo A
pB
~
(como pretendíamos).
a-ii) Suponha-se que A
p B.
~
Então, por b) do teorema 2 da secção 3, existe B1 ⊆ B tal que A ~ B1.
Logo, pelo corolário acima (ou directamente pelo critério a) anterior que decorre desse corolário),
#B1 ≤ #B.
Mas então, pelo teorema 2-c) da secção 2, #A = #B1 ≤ #B
(c.q.d.)
b) Sai da alínea a) e do teorema 2-c) da secção 2, uma vez que
n<k ⇔ n≤k ∧ n≠k
e (ver observação na secção 3)
A
p B ⇔ A p B ∧ A ~/ B
~
∇
• Demonstração do teorema 6 da Secção 5
Teorema 6:
a) Se B é um conjunto numerável de conjuntos contáveis, em que pelo menos um deles é numerável
(podendo ser todos numeráveis, ou não), então ∪B é numerável.
b) Se B é um conjunto numerável de conjuntos contáveis, disjuntos dois a dois, não vazios, então
∪B é
numerável.
Demonstração:
a) Como há pelo menos um conjunto numerável (e portanto infinito) em B , chamemos-lhe A, então
∪B é infinito (pois A ⊆ ∪B).
179
Logo, para provar que
elementos de
∪B
∪B
é numerável, basta-nos mostrar que é possível enumerar todos os
(eventualmente com repetições), isto é, basta-nos mostrar que existe uma
sobrejecção h: |N1 → ∪ B.
Como B é um conjunto numerável, é possível enumerar (mesmo sem repetições, embora isso não seja
essencial para o que se segue), numa sucessão1, todos os seus elementos (que são conjuntos). Seja
A1 , A2 , A3, ...
tal enumeração.
Tem-se portanto que ∪B =
U
An.
n ≥1
Como cada An (n≥1) é contável, existe (para cada n≥1) uma sobrejecção fn:|N1→An (se designarmos
fn(k) por ank, então: a11, a12, a13, ... constitui uma enumeração de A1; a21, a22, a23, ... constitui uma
enumeração de A2; e assim sucessivamente).
Defina-se g : |N1 x |N1 →
U
An como se segue:
n ≥1
∀n,k≥1 g(n,k) = fn(k) (isto é ank , usando a designação acima referida)
Pode provar-se que g é sobrejectiva (faça-o).
Finalmente, pode mostrar-se que existe a sobrejecção h:|N1→
U
An pretendida, como se segue:
n ≥1
Como |N1 ~ |N1 x |N1 (demonstre, usando uma técnica análoga à do exemplo 2 da secção 5), existe uma
bijecção j: |N1 → |N1 x |N1.
Mas então h = g o j: |N1→
U
An é uma sobrejecção (como se pretendia obter).
n ≥1
b) Suponha-se que B é um conjunto numerável de conjuntos contáveis, disjuntos dois a dois, não vazios.
Se existir em B algum conjunto numerável, então ∪B é numerável, por a).
Logo podemos supor que todos os conjuntos em B são finitos (não vazios).
Seja A1 , A2 , A3, ... uma enumeração, sem repetições, de todos os elementos de B (cuja existência
decorre de B ser numerável).
Defina-se f : |N1 →
U
An, como se segue:
n ≥1
qualquer que seja i≥1, f(i) é um elemento (qualquer) de Ai (por hipótese, Ai ≠ ∅).
É imediato que f é injectiva, pois os conjuntos em B são disjuntos, dois a dois (e a enumeração
considerada é sem repetições).
Logo |N1
p U An, e portanto U An é infinito.
~ n ≥1
n ≥1
180
Assim, se provarmos que
U
An é contável, teremos provado que
n ≥1
U
An é numerável, como
n ≥1
pretendemos.
Seja n≥1 qualquer.
Como An é finito, existem k≥1 elementos distintos x1,...,xk tais que An={x1,...,xk}.
Defina-se Bn={x1, ..., xk, k+1, k+2, k+3, ...}.
É fácil verificar que Bn é numerável. Logo, por a),
U
Bn é numerável.
n ≥1
Mas
U
An ⊆
n ≥1
U
Bn. Logo
n ≥1
U
An é contável (justifique!)
n ≥1
(c.q.d.)
∇
• Demonstração do teorema 7 da Secção 5
Teorema 7:
Se A é numerável, então o conjunto formado por todos os subconjuntos finitos de A é numerável.
Demonstração:
Suponha-se que A é numerável e seja B = {B: B⊆A e B é finito}. Queremos provar que B é numerável.
É imediato que A p B (pois h: A → B, definida por ∀x∈A h(x) = {x}, é uma injecção). Logo B é infinito.
~
Assim, se mostrarmos que B
p |N1 (i.e. se mostrarmos que existe uma injecção de B em |N1), então
~
temos que B é contável (pelo teorema 1 da secção 5) e, portanto, numerável.
Como A é numerável existe uma bijecção f : |N1 → A.
Defina-se g : B → |N1 como se segue:
Qualquer que seja B∈B:
g(B) = produto dos primos pn com n ∈ f-1[B] (note-se f-1[B] = {f-1(x): x∈B} ⊆ |N1)
onde pi (i≥1) designa o i-ésimo número primo: p1 = 2, p2 = 3, p3 = 5, ...
Se B1 ≠ B2 (com B1, B2 ∈B), então f-1[B1] ≠ f-1[B2] (pois f é bijectiva) e, como duas sequências
diferentes de números primos têm produtos distintos, g(B1) ≠ g(B2). Logo g é injectiva (c.q.d.)
∇
• Demonstração do teorema 8 da Secção 5
Teorema 8:
Se A é numerável, então o conjunto de todas as sequências, não vazias, de elementos de A é numerável.
181
Demonstração (parte da demonstração é análoga à demonstração anterior):
Suponha-se que A é numerável e seja S o conjunto formado por todas as sequências, não vazias, de
elementos de A. Queremos provar que S é numerável.
É imediato que A p S (pois h: A → S, definida por ∀x∈A h(x) = (x), é uma injecção). Logo S é infinito.
~
Assim, se mostrarmos que S
p |N1 (i.e. se mostrarmos que existe uma injecção de S em |N1), então
~
temos que S é contável e, portanto, numerável.
Como A é numerável existe uma bijecção f : |N1 → A.
Defina-se g : S → |N1 como se segue:
Qualquer que seja a sequência (a1, ..., an) (n≥1) de elementos de A:
g( (a1, ..., an) ) = p1e1 p2e2 ... pnen com e1 = f-1(a1), ...., en = f-1(an)
onde (tal como na demonstração anterior) pi (i≥1) designa o i-ésimo número primo: p1 = 2, p2 = 3, ...
Como qualquer natural positivo é decomponível de forma única num produto de potências de números
primos, e como f é uma bijecção, pode concluir-se que g é injectiva (c.q.d.)
∇
182