Resoluções do Curso de Análise - cap. 2

Prévia do material em texto

Resoluções Curso de Análise Vol. 1 - Cap. 2
Elon Lages Lima
George Euzébio
Dezembro 2020
Capítulo 1
Conjuntos Finitos, Enumeráveis e
Não-Enumeráveis
1. Prove que, na presença dos axiomas P1 e P2, o axioma (A) abaixo é
equivalente a P3. (A) Para todo subconjunto não-vazio A ⊂ N, tem-se
A− s(A) 6= ∅.
Resolução:
Seja X ⊂ N não vazio tal que 1 ∈ X e para todo n ∈ X temos que s(n) ∈ X.
Seja Y = N−X, se X 6= N, pelo axioma (A) existe n ∈ Y − s(Y ). Como
1 ∈ X, então 1 < n e existe m ∈ N tal que s(m) = n ∈ Y e m 6∈ Y , portanto,
m ∈ X, mas pela caracterização de X, m ∈ X =⇒ s(m) ∈ X, o que é um
absurdo, pois X ∩ Y = ∅, portanto, devemos ter Y = ∅.
2. Dados os números naturais a, b, prove que existe um número natural
m tal que m · a > b.
Resolução:
Pelo princípio da tricotomia temos as três possibilidades
a < b ou a = b ou b < a
nos casos em que b ≤ a basta tomarm = 1, se b < a, oum = 2, se a = b. Para
o caso a < b, pelo algoritmo da divisão temos que existem números naturais
q e r tais que b = aq + r, com 0 ≤ r < a. Dessa última desigualdade, se
somarmos aq em ambos os membros, obtemos
aq + r < a+ aq =⇒ b < a(1 + q)
e tomando m = 1+ q, temos então que existe um natural m = 1+ q de modo
que b < a ·m.
2
3
3. Seja a um número natural. Se um conjunto X é tal que a ∈ X e, além
disso, n ∈ X =⇒ n + 1 ∈ X, então X contém todos os números
naturais ≥ a.
Resolução:
Se a = 1, então não há nada a fazer, pois o axioma P3 já garante isso. Do
contrário, se a > 1, então seja Ia−1 = {1, 2, 3, . . . , a − 1}, desse modo se
tomarmos o conjunto Ia−1 ∪X, podemos observar que 1 ∈ Ia−1 ∪X e como
X possui a propriedade de que ∀n ∈ X =⇒ n+1 ∈ X, então Ia−1 ∪X = N
pelo axioma P3. Então, como Ia−1 ∪ X − Ia−1 = X, temos que o conjunto
X contém todos os números naturais ≥ a.
5. Um elemento a ∈ N chama-se antecessor de b ∈ N quando se tem a < b
mas não existe c ∈ N tal que a < c < b. Prove que, exceto 1, todo
número natural possui um antecessor.
Resolução:
Pelo axioma P2, o número 1 não possui antecessor. Desse modo, seja X o
conjunto de todos os naturais tais que não exista k tal que m < k < m+ 1.
Vemos rapidamente que X é não-vazio, uma vez que 2 ∈ X. Supondo que X
contém todos os naturais de 2 a n, para algum n ∈ N. Vamos mostrar que
n+ 1 ∈ X. De fato, se existe c ∈ N tal que n < c < n+ 1, mas isso implica
que n − 1 < c − 1 < n, ou seja, um absurdo contra a hipótese. Logo, pelo
exercício 3, X contém todos os naturais maiores que ou iguais a 2.
6. Use indução para demonstrar os seguintes fatos:
a) 2(1 + 2 + . . .+ n) = n(n+ 1);
b) 1 + 3 + 5 + . . .+ (2n+ 1) = (n+ 1)2;
c) (a− 1)(1 + a+ . . .+ an) = an+1 − 1, seja quais forem a, n ∈ N;
d) n ≥ 4 =⇒ n! > 2n
Resolução:
Afim de economizarmos tempo, todas as expressões acima são facilmente ver-
ificadas quando n = 1, portanto partimeros imediatamente para a implicação
n ∈ X =⇒ n+ 1 ∈ X.
a) Supondo que seja válido 2(1 + 2 + . . .+ n) = n(n+ 1) para algum n ∈ N,
ao somarmos 2n+ 2 a ambos os lados da igualdade obtemos
2(1 + 2 + . . .+ n) + (2n+ 2) = n(n+ 1) + (2n+ 2)
2(1 + 2 + . . .+ n) + 2(n+ 1) = n(n+ 1) + 2(n+ 1)
2[1 + 2 + . . .+ n+ (n+ 1)] = (n+ 1)[(n+ 1) + 1]
4CAPÍTULO 1. CONJUNTOS FINITOS, ENUMERÁVEIS E NÃO-ENUMERÁVEIS
o que nos mostra que se a expressão é válida para algum natural n, então
também será válida para o seu sucessor n+1, o que nos mostra que é válido
para todo natural n.
b) Supondo ser válido 1+3+5+ . . .+(2n+1) = (n+1)2 para algum n ∈ N,
iremos somar 2n+ 3 em ambos os lados da igualdade de modo a obtermos
1 + 3 + 5 + . . .+ (2n+ 1) + (2n+ 3) = (n+ 1)2 + 2n+ 3
1 + 3 + 5 + . . .+ (2n+ 1) + [2(n+ 1) + 1] = n2 + 4n+ 4
1 + 3 + 5 + . . .+ (2n+ 1) + [2(n+ 1) + 1] = (n+ 2)2 = [(n+ 1) + 1]2
ou seja, vemos que a validade da afirmação para algum n natural implica na
sua validade para n+ 1, sendo então válido para todo n natural.
c) Se para algum n ∈ N é válido que (a − 1)(1 + a + . . . + an) = an+1 − 1,
então, ao somarmos an+2 − an+1, teremos
(a− 1)(1 + a+ . . .+ an) + (an+2 − an+1) = an+1 − 1 + (an+2 − an+1)
(a− 1)(1 + a+ . . .+ an) + (a− 1)an+1 = an+2 − 1
(a− 1)(1 + a+ . . .+ an + an+1) = a(n+1)+1 − 1
e a expressão acima nos mostra que também é válido para n+ 1, portanto é
válido para todo n ∈ N.
d) Se é válido n! > 2n para algum n ∈ N, com n ≥ 4, multiplicando a
desigualdade por n+ 1 temos
(n+ 1)n! > (n+ 1)2n
(n+ 1)! > n2n + 2n, comon ≥ 4
(n+ 1)! > 4 · 2n + 2n
> 2n+2 + 2n
> 2n+1
portanto, vemos que também é válido para n + 1, o que implica dizer que é
válido para todo n ∈ N, com n ≥ 4.
7. Use o Segundo Princípio da Indução para demonstrar a unicidade da
decomposição de um número natural em fatores primos.
Resolução:
Seja X = {1, 2, 3, . . . , m} o conjunto de todos os naturais que possuem
única decomposição em fatores primos menores que n. Suponhamos que
n admita uma decomposição do tipo n = p1, com p1 primo, e n = p1 =
q1q2 . . . qs, onde q1 ≤ q2 ≤ . . . ≤ qs são primos. Como q1 divide q1q2 . . . qs,
5
então q1 | p1, que é primo, portanto q1 = p1. Ou seja, temos então que ao
cancelarmos esses fatores obtemos 1 = q2 . . . qs e se s > 1 teríamos que todos
os primos qi, com 2 ≤ i ≤ s, diviriam 1, o que é um absurdo, logo s = 1 e
verificamos o passo de indução. Agora supondo ser válido para todo natural
com uma decomposição de comprimento k, mostraremos ser válido para uma
decomposição de comprimento k + 1. Se n admite decomposições distintas,
temos n = p1p2 . . . pk+1 = q1q2 . . . qs. Como q1 | p1p2 . . . pk+1, q1 | pi, para
algum i, e q1 ≥ p1. Por outro lado, p1 | q1q2 . . . qs, ou seja, p1 | qj, para
algum j, e garantimos que p1 ≥ q1. Dessas duas desigualdades garantimos
que p1 = q1. Agora cancelando esses termos iguais obtemos
p2 . . . pk+1 = q2 . . . qs
ou seja, o membro esquerdo da igualdade é uma decomposição de compri-
mento k, logo, pela hipótese de indução, admite uma única decomposição.
Ou seja, k = s− 1 =⇒ k + 1 = s e pi = qi, com 1 ≤ i ≤ k + 1, portanto as
decomposições são únicas. Assim, pelo segundo princípio de indução, vemos
que X = N.
Para finalizarmos, sendo n = p1p2 . . . pk, ao agruparmos os primos repetidos
obtemos n = pα11 p
α2
2 . . . p
αr
r .
8. Seja X um conjunto com n elementos. Use indução para provar que o
conjunto das bijeções (ou permutações) f : X → X tem n! elementos.
Resolução:
De fato, se n = 1, então há somente uma bijeção. Supondo que X possua n
elementos de modo a ter n! bijeções. Então tomemos o conjunto Y = X∪{a}
que possui n + 1 elementos. Dessa maneira, para formarmos os n + 1 pares
ordenados (y, f(y)) teremos (n + 1 opções para o primeiros, n opções para
o segundo, (n− 1) opções para o terceiro e assim sucessivamente de modo a
termos (n + 1) · n · (n − 1) . . . 1 = (n + 1)! bijeções totais. E pelo princípio
de indução garantimos que se um conjunto X possui n elementos, então
podemos montar n! bijeções f : X → X.
9. Sejam X e Y conjuntos finitos.
a) Prove que card(X ∪ Y ) + card(X ∩ Y ) = card(X) + card(Y )
b) Qual seria a fórmula correspondente para três conjuntos?
c) Generalize.
Resolução:
a) Sendo X = {x1, x2, . . . , xn} e Y = {yn+1, yn+2, . . . , yn+m} conjuntos fini-
tos com card(X) = n e card(Y ) = m. Vamos supor inicialmente que X e
6CAPÍTULO 1. CONJUNTOS FINITOS, ENUMERÁVEIS E NÃO-ENUMERÁVEIS
Y são disjuntos, ou seja, card(X ∩ Y ) = 0. Desse modo, podemos montar a
função injetora f : In+m → X∪Y definida por f(n) =
{
xi, se 1 ≤ i ≤ n
yi, se n+ 1 ≤ i ≤ n+m
.
Dessa maneira, temos que card(X∪Y )+0 = n+m = card(X)+card(Y ) =⇒
card(X ∪ Y ) + card(X ∩ Y ) = card(X) + card(Y ). Supondo agora que
X ∩ Y 6= ∅, temos então que X ∪ Y = (X −X ∩ Y ) ∪ Y . Como X −X ∩ Y
e Y são disjuntos, então card(X ∪ Y ) = card(X − X ∩ Y ) + card(Y ), mas
também temos que card(X−X∩Y ) = card(X)−card(X∩Y ), e desse modo
podemos concluir que card(X ∪Y ) = card(X)+card(Y )−card(X ∩Y ) =⇒
card(X ∪ Y ) + card(X ∩ Y ) = card(X) + card(Y ).
b) card(X1∪X2∪X3)+card(X1∩X2)+card(X1∩X3)+card(X2∩X3) =
card(X1) + card(X2) + card(X3) + card(X1 ∩X2 ∩X3)
c) card(
⋃
Xi) +
∑
i 6=j card(Xi ∩Xj) =
∑n
i=1 card(Xi)+ card(
⋂
Xi).
10. Dado um conjunto finito X, prove que uma função f : X → X é
injetiva se, e somente se, é sobrejetiva (e portanto uma bijeção).
Resolução:
(⇒) Sendo X um conjunto finito com n elementos, se f não é sobrejetora,
deve existir pelo menos um par n, m ∈ X, com n 6= m, de modo que f(n) =
f(m), mas pela injetividade de f , temos que f(n) = f(m) =⇒ n = m, o
que nos leva a um absurdo. Logo concluímos que esse absurdo vem do fato
de f não ser sobrejetora.
(⇐) Se f não é injetora e X possuindo n elementos, então devemos ter
pelo menos um par n, m ∈ X, com n 6= m, onde f(n) = f(m). Como f
é sobrejetora, então existe f−1 : X → X de modo que n = f−1(f(n)) e
m = f−1(f(m)), ou seja, n = f−1(f(n)) = f−1(f(m)) = m, ou seja, temos
que f(n) = f(m) =⇒ n = m, logo f é injetora.
11. Formule matematicamente e demonstre o seguinte fato (conhecido como
o "princípio das gavetas"). Se m < n, então, de qualquer modo como
se guardem n objetos em m gavetas, haverá sempre uma gaveta, pelo
menos, que conterá mais de um objeto.
Resolução:
O princípio das gavetas pode ser formulado como se segue: "Dados n, m ∈ N,
com m < n, então não existe uma bijeção f : Im → In". De fato, como
m < n, então temos que Im ⊂ In e pelo teorema 3 (Seja A ⊂ In. Se existir
uma bijeção f : In → A, então A = In), se existir a bijeção f : Im → In,
então n = m, o que seria um absurdo. Portanto f não é bijetora.
7
12. Seja X um conjunto com n elementos. Determine o número de funções
injetivas f : Ip → X.
Resolução:
Para montarmos um função f injetora definida em Ip, temos que tomar
p elementos dos n elementos de X, logo, dessa maneira, a quantidade de
funções injetoras se dará por An,p = n!(n−p)! .
13. Quantos subconjuntos com p elementos possui um subconjunto X,
sabendo-se que X tem n elementos?
Resolução:
O subconjunto de X deve conter exatamente p elementos escolhidos dentre
os n elementos de X de modo que a ordem de escolha não importa, ou
seja, a permutação de seus elementos não altera o conjunto formado. Desse
modo, a quantidade de subconjuntos com p elementos formados a partir dos
n elementos de X será Cn,p = n!p!(n−p)! .
14. Prove que se A tem n elementos, então P(A) tem 2n elementos.
Resolução:
Para demonstrarmos esse fato usaremos indução sobre o número de elementos
de A. Se n = 1, então A possui dois subconjuntos, o própio A e ∅. Portanto,
card(P(A)) = 21. Agora supondo que se A = {a1, a2, a3, . . . , an}, ou seja,
possui n elementos, então card(P(A)) = 2n, calcularemos a card(P(A ∪
{an+1})). Iremos substituir um elemento de A, digamos a1, por an+1, de modo
a ter um novo conjunto A′ = {a2, a3, . . . , an, an+1}, que também possui n
elementos e card(P(A′)) = 2n. Como A∪{an+1} = A∪A′, então card(P(A∪
{an+1})) = card(P(A))+card(P(A′)) = 2n+2n = 2·2n = 2n+1. O que conclui
nossa prova por indução.
15. Defina uma função sobrejetiva f : N → N tal que para todo n ∈ N, o
conjunto f−1(n) é infinito.
Resolução:
Basta tomar f = g◦h de modo que h : N→ N×N é sobrejetiva e g(m,n) = n.
16. Prove que se X é infinito enumerável, o conjunto das partes finitas de
X também é (infinito) enumerável.
Resolução:
Basta tomar X =
⋃
i∈N
Xi, com Xi ∈ P(X). Assim podemos montar uma
bijeção f : N→ P(X) definida por f(n) = Xn.
8CAPÍTULO 1. CONJUNTOS FINITOS, ENUMERÁVEIS E NÃO-ENUMERÁVEIS
17. Seja f : X → X uma função. Um subconjunto Y ⊂ X chama-se
estável relativamente a f quando f(Y ) ⊂ Y . Prove que um conjunto
X é finito se, e somente se, existe uma função f : X → X que só admite
os subconjuntos estáveis ∅ e X.
Resolução:
(⇒) Sejam X um conjunto finito e f : X → X uma função. Como f(∅) = ∅,
então temos que ∅ ⊂ X e f(∅) ⊂ ∅ garantem que o conjunto ∅ é estável. Seja
então o conjunto não-vazio Y ⊂ X tal que f(Y ) ⊂ Y . Como X é finito, então
Y também o é, ou seja, f(Y ) ⊂ Y =⇒ ∀n ∈ Y, ∃m ∈ Y tal que f(m) = n,
portanto f é sobrejetora e, pelo exercício 10, temos que f é uma bijeção.
Desse modo, podemos tomar f(xi) = xj, com i 6= j, para garantirmos que
os únicos conjuntos estáveis são ∅ e X, uma vez que Id : X → X nos mostra
que todos os subconjuntos de X são estáveis.
(⇐) Se existe f de modo que os únicos conjuntos estáveis sejam ∅ e X, então,
pelo resultado anterior, temos que se X for infinito, então algum elemento
de X não terá imagem por f , logo, X é finito.
18. Seja f : X → X uma função injetiva tal que f(X) 6= X. Tomando
x ∈ X − f(X), prove que os elementos x, f(x), f(f(x)), . . . são dois a
dois distintos.
Resolução:
Sendo x ∈ X − f(X), então para todo y ∈ f(X), x 6= y, dessa maneira
temos que f(x) ∈ f(X), portanto x 6= f(x). Como f é injetiva, temos que
f(x) = f(f(x)) =⇒ x = f(x), o que não é possível pela afirmação anterior,
logo f(x) 6= f(f(x)). Definindo como fn(x) as n aplicações de f no ponto x,
então temos que p/ n = 1, f(x) 6= f(f(x)) equivale a f 1(x) 6= f 2(x). Supondo
que para um dado n, seja válido, fn(x) 6= fn+1(x), se tivermos então que
fn+1(x) = fn+2(x), pela injetividade de f , temos que fn+1(x) = fn+2(x) =⇒
fn(x) = fn+1(x), o que seria um absurdo. Logo, por indução, vemos que
∀n ∈ N, fn(x) 6= fn+1(x). Portanto, os elementos x, f(x), f(f(x)), . . . são
dois a dois distintos.
19. Seja X um conjunto infinito e Y um conjunto finito. Mostre que existe
uma função sobrejetiva f : X → Y e uma função injetiva g : Y → X.
Resolução:
Sendo Y = {y1, y2, y3, . . . , yn} um conjunto finito, podemos tomar um sub-
conjunto X0 = {x1, x2, x3, . . . , xn−1} ⊂ X, de modo a definirmos uma
função f : X → Y definida por f(x) =
{
yi, sex ∈ X0
yn, sex 6∈ X0
, é fácil ver que
f é sobrejetiva, uma vez que Im(f) = Y .
9
Para a função g, basta tomar g : Y → X0 ⊂ X definida por g(yi) = xi, com
1 ≤ i ≤ n.
20. a) Se X é finito e Y é enumerável, então F(X;Y ) é enumerável.
b) Para cada função f : N → N seja Af = {n ∈ N; f(n) 6= 1}.Prove
que o conjunto X das funções f : N → N tais que Af é finito é
um conjunto enumerável.
Resolução:
a) Como X é finito, então existe uma bijeção h : Im → X, logo card(X) = m.
Em outras palavras, todas as funções f são m-uplas ordenadas de elementos
de Y , uma vez que podemos tomar f ◦ h : Im → Y . Portanto, F(X;Y ) =
Y × Y × Y × . . . × Y (m fatores) e F(X;Y ) será o produto cartesiano de
conjuntos enumeráveis, sendo então enumerável.
b) Pela definição do conjunto X, podemos definir uma função g : Af → N
de modo que g associe a cada Af a sua cardinalidade, uma vez que Af é
finito, então a cardinalidade será um número natural. Desse modo, temos
que X = F(Af ;N), onde Af é finito e N é enumerável, logo, pelo item
anterior, temos que X é enumerável.
21. Obtenha uma decomposição N = X1 ∪ X2 ∪ . . . ∪ Xn ∪ . . . tal que os
conjuntos X1, X2, . . . , Xn, . . . são infinitos e dois a dois disjuntos.
Resolução:
Basta tomar Xi = f−1(i), onde f é definida como a função do exercício 15.
22. Defina f : N × N → N, pondo f(1, n) = 2n − 1 e f(m + 1, n) =
2m · (2n− 1). Prove que f é uma bijeção.
Resolução:
Sendo k ∈ N, usando a decomposição em fatores primos, temos que k =
pα11 p
α2
2 p
α3
3 . . . p
αm
m . Como o único primo par é o número 2 e o produto de
números ímpares é um número ímpar, temos que k = 2α1(2l− 1). Se α1 = 0,
então k = 2l − 1, então podemos perceber que todos os naturais podem ser
descritos pela função f , logo f é sobrejetora.
Se f(m,n) = f(p, q), então 2m(2n− 1) = 2p(2q − 1). Se m 6= p, então, pela
decomposição de fatores primos, os números serão diferentes, uma vez que
2n− 1 e 2q − 1 não possuem fatores 2, portanto devemos ter sempre m = p,
o que nos leva a 2n− 1 = 2q − 1 =⇒ n = q, mostrando que f é injetiva.
23. Seja X ⊂ N um subconjunto infinito. Prove que existe uma única
bijeção crescente f : N→ X.
10CAPÍTULO 1. CONJUNTOS FINITOS, ENUMERÁVEIS E NÃO-ENUMERÁVEIS
Resolução:
A existência é dada pelo corolário 2 do teorema 8 (Dado um subconjunto
infinito X ⊂ N, existe uma bijeção crescente f : N→ X). Para a unicidade,
basta usar indução sobre n no processo de construção de Bn do teorema 8.
24. Prove que todo conjunto infinito se decompõe como uma reunião de
uma infinidade enumerávelde conjuntos infinitos, dois a dois disjuntos.
Resolução:
Pelo teorema 7, todo conjunto infinito X, contém um subconjunto infinito
enumerável, desse modo, seja X1 ⊂ X esse conjunto infinito enumerável.
Temos então que X −X1 6= ∅, uma vez que X é infinito, e que X ′ = X −X1
também é infinito. Logo, ainda pelo teorema 7, podemos obter X2 ⊂ X ′
infinito e enumerável. Temos que X1 e X2 são disjuntos pela definição de X2.
Assim, podemos proceder de maneira indutiva repetindo os passos anteriores
de modo a obter X1, X2, . . . , Xn, . . . todos infinitos enumeráveis e disjuntos
dois a dois, onde X =
⋃
i∈N
Xi.
25. Seja A um conjunto. Dadas duas funções f, g : A → N, defina a soma
f + g : A→ N, o produto f · g : A→ N, e dê significado da afirmação
f ≤ g. Indicando com ξX a função caracterísitca de um subconjunto
X ⊂ A, prove:
a) ξX∩Y = ξX · ξY ;
b) ξX∪Y = ξX + ξY − ξX∩Y . Em particular,
ξX∪Y = ξX + ξY ⇐⇒ X ∩ Y = ∅;
c) X ⊂ Y ⇐⇒ ξX ≤ ξY ;
d) ξA−X = 1− ξX .
Resolução:
Definindo f+g, f ·g : A→ N temos que dado n ∈ A, [f+g](n) = f(n)+g(n)
e [f · g](n) = f(n) · g(n), de modo geral, a soma e o produto de funções dar-
se-á somente se x ∈ D(f) ∩ D(g). Dizemos que f ≤ g quando para todo
n ∈ A tivermos f(n) ≤ g(n). Temos também que ξX : A→ {0, 1} é definida
por ξX(x) =
{
1, sex ∈ A
0, sex 6∈ A
a) Temos que x ∈ X ∩ Y ⇐⇒ x ∈ X e x ∈ Y , logo, x 6∈ X ∩ Y ⇐⇒ x 6∈
X ou x 6∈ Y , em outras palavras, temos que ξX∩Y (x) =
{
1, sex ∈ X ∩ Y
0, sex 6∈ X ∩ Y
ou seja, se x ∈ X ∩ Y , então ξX = 1 e ξY = 1 =⇒ ξX∩Y = 1 = 1 · 1 =
ξX · ξY . Por outro lado, se x 6∈ ξX∩Y , então ξX = 0 ou ξY = 0 =⇒
11
ξX∩Y = 0 = 0 · 1 = 1 · 0 = 0 · 0 = ξX · ξY , portanto, ξX∩Y = ξX · ξY .
b) Se x ∈ X ∪ Y , então x ∈ X − Y ou x ∈ Y − X ou x ∈ X ∩ Y . As-
sim, se ξX∪Y (x) = 1 e x ∈ X ∩ Y , então ξX = 1, ξY = 1 e ξX∩Y = 1 =⇒
ξX∪Y (x) = 1 + 1 − 1, por outro lado, se ξX∪Y (x) = 1 e x 6∈ X ∩ Y , en-
tão ξX = 1, ξY = 0 e ξX∩Y = 0 ou ξX = 0, ξY = 1 e ξX∩Y = 0 =⇒
ξX∪Y (x) = 1+0−0 = 0+1−0. Por último, ξX∪Y (x) = 0 =⇒ ξX = ξY = 0,
logo, temos que ξX∪Y = ξX + ξY − ξX∩Y .
c) Sendo X ⊂ Y , podemos escrever Y = (Y −X)∪X, onde (Y −X)∩X = ∅.
Pelo item anterior, temos que ξY = ξ(Y−X) + ξX =⇒ ξY ≥ ξX .
d) Temos que ∀X ⊂ A, A = (A−X)∪X, com (A−X)∪X = ∅. Novamente
pelo item b, temos que ξA = ξA−X + ξX =⇒ ξA−X = ξA − ξX = 1− ξX .
26. Prove que o conjunto das sequências crescentes (n1 < n2 < n3 < . . .)
de números naturais não é enumerável.
Resolução:
Procederemos do seguinte modo, tomemos inicialmente n1 ∈ N = Xn1 . Para
n2, seja o conjunto Xn2 = {x ∈ N;n1 < x}, então n2 ∈ Xn2 . E procederemos
de modo semelhante para os demais ni ∈ Xni , onde Xni = {x ∈ N;ni−1 <
x}. Dessa maneira, garantimos que todos os Xni são infinitos enumeráveis.
Como o conjunto X das sequências crescentes de números naturais é formado
por elementos da forma (n1, n2, n3, . . . , ni, . . .) de modo que ni ∈ Xni , então
podemos tomar X =
∞∏
i=1
Xni . Logo X é não enumerável.
27. Sejam (N, s) e (N′, s′) dois pares formados, cada um, por um conjunto e
uma função. Suponhamos que ambos cumpram os axiomas de Peano.
Prove que existe uma única bijeção f : N → N′ tal que f(1) = 1′,
f(s(n)) = s′(f(n)). Conclua que:
a) m < n⇐⇒ f(m) < f(n);
b) f(m+ n) = f(m) + f(n) e
c) f(m · n) = f(m) · f(n).
Resolução:
f é crescente, uma vez que dadosm, n ∈ N, então s(m) < s(n), o que nos leva
a m′ < n′. É fácil observamos esse fato por indução. Temos que f(1) = 1′
e sendo f(n) = n′, a definição de f garante que f(s(n)) = s′(f(n)) = s′(n′).
Pelo exercício 23, f é única.
a) Pelo que vimos anteriormente, a função f é crescente, logo m < n ⇐⇒
f(m) < f(n).
b) Novamente procederemos por indução, uma vez que s(m) = m + 1 e
12CAPÍTULO 1. CONJUNTOS FINITOS, ENUMERÁVEIS E NÃO-ENUMERÁVEIS
n+ s(m) = s(n+m). Sendo f(1) = 1′, temos que, por definição, f(n+1) =
f(s(n)) = s′(f(n)) = s′(n′) = n′+1′ = f(n)+ f(1). Supondo ser válido para
algum m ∈ A que f(n+m) = f(n) + f(m), temos então que f(n+ s(m)) =
f(s(m+n)) = s′(f(n+m)) = s′(f(n)+ f(m)) = f(n)+ s′(f(m)). Portanto,
concluímos por indução que f(m+ n) = f(m) + f(n).
c) Por indução temos que m · 1 = m e n · s(m) = n + n · m. Temos que
f(n · 1) = f(n) = f(n) · 1′ = f(n) · f(1) e que se para um dado m ∈ A
tivermos f(n ·m) = f(n) · f(m), então f(n · s(m)) = f(n+ n ·m) = f(n) +
f(n ·m) = f(n) + f(n) · f(m) = f(n) · f(s(m)). Portanto, concluímos que
f(n ·m) = f(n) · f(m).
28. Dada uma sequência de conjuntosA1, A2 , . . . , An, . . ., considere os con-
juntos lim supAn =
∞⋂
n=1
(
∞⋃
n=1
Ai
)
e lim infAn =
∞⋃
n=1
(
∞⋂
n=1
Ai
)
.
a) Prove que lim supAn é o conjunto dos elementos que pertencem
a An para uma infinidade de valores de n e que lim infAn é o
conjunto dos elementos que pertencem a todo An salvo para um
número finito de valores de n.
b) Conclua que lim infAn ⊂ lim supAn.
c) Mostre que seAn ⊂ An+1 para todo n então lim infAn = lim supAn =
∞⋃
n=1
An.
d) Por outro lado, se An ⊃ An+1 para todo n então lim infAn =
lim supAn =
∞⋂
n=1
An.
29. Dados os conjuntos A e B, suponha que existam funções injetivas f :
A → B e g : B → A. Prove que existe uma bijeção h : A → B.
(Teorema de Cantor-Bernstein-Schröder).
Resolução:
Se existe uma aplicação injetiva f : A → B então card A ≤ card B. Por
outro lado, se existe uma aplicação injetiva g : B → A então card B ≤
card A, portanto, card A = card B. Mas card A = card B implica na ex-
istência de uma bijeção entre os conjuntos A e B.