resolucao_exercicios_unidade_1

Prévia do material em texto

RESOLUÇÃO DOS EXERCÍCIOS 
UNIDADE 1 
 
TÓPICO 1 
1. Demonstre através do método de indução que, para qualquer número natural 
n, 
a)  
2
1nn
n...321


 
RESOLUÇÃO 
Vamos mostrar que  
2
1nn
n...321


 qualquer que seja n um número 
natural 
Primeiro passo: mostrar que vale para n =1. 
 
2
111
2
21
1:)1(P




 
Suponhamos agora que a afirmação vale para n = k 
 
2
1kk
k...321:)k(P


 
Vamos agora mostrar P(k+1): 
 
 
  
  
2
2k1k
2
1k2k
2
)1k(21kk
)1k(
2
1kk
)1k(k...321








   
 
Como k foi suposto qualquer número natural, segue que a propriedade vale para 
qualquer número natural n, CQD. 
b) 
n2n  
Vamos mostrar que 
n2n 
 qualquer que seja n um número natural 
Primeiro passo: mostrar que vale para n =1. 
122:)1(P 1 
 
Suponhamos agora que a afirmação vale para n = k 
k2:)k(P k 
 
Vamos agora mostrar P(k+1): 
 1kkk2k222
k1k 
 
Como k foi suposto qualquer número natural, segue que a propriedade vale para 
qualquer número natural n, CQD. 
 
2. Demonstre os resultados a seguir através da demonstração direta que, dados 
a e b dois números reais quaisquer, 
 
a) 
baba 
. 
Sejam a e b dois números reais quaisquer. Sabemos que o módulo de um número real 
é sempre positivo. Assim, não importa se a – b> 0 ou se a – b < 0, 
  0baba 22 
. Por outro lado, se a e b forem números positivos ou ambos 
negativos, 
baba 
, e caso a seja positivo e b negativo, 
baba 
. De posse 
destes comentários, 
 
 2
22
22
22
ba
ba2ba
ab2ba
baba




 
Extraindo a raiz quadrada de ambos os lados da equação, temos que 
baba 
, 
CQD. 
 
 
b) 
baba  
 
 
2
2
22
222
ba
ba
ba2ba
ba2baba




 
 
c) 
baba 
 
 
 
2
2
22
222
ba
ba
ba2ba
ba2baba
baba





 
3. Demonstre os resultados a seguir utilizando a técnica de demonstração por 
absurdo. 
a) Se um número real x for tal que x + x = x, então x obrigatoriamente é igual a 0. 
Suponhamos por absurdo que exista um número real x diferente de zero para o qual x 
+ x = x. 
Então 2.x = x 
Como x é diferente de zero, podemos dividir ambos os lados da igualdade por x: 
x
x
x
x2





, ou seja, 2 = 1: absurdo‼ 
Portanto, se um número real for tal que x + x = x, necessariamente x = 0, CQD. 
 
b) Se dois números a e b são números pares, então o número a + b também é um 
número par. 
Sejam a e b dois números pares. Então existem números inteiros p e q para os quais a 
= 2p e b = 2q. 
Suponhamos por absurdo que a +b seja um número impar. Então existe um número 
inteiro k tal que (a+b) = 2k + 1. 
Por outro lado, a+b = 2p + 2q = 2(p + q). 
Pelas duas igualdades, 2k + 1 = 2(p + q) 
2( p + q – k) = 1 
p + q – k = ½ : contradição, pois a adição de números inteiros só pode resultar em um 
número inteiro e ½ é racional! 
Portanto, se a e b são números pares, necessariamente a + b é um número par. 
 
TÓPICO 2 
 
1. Demonstre utilizando o Princípio da Indução as seguintes propriedades da 
adição de números naturais: 
a) Dados dois números naturais m e n, segue que m + n = n + m (comutatividade) 
Vamos dividir esta demonstração em duas partes, ambas demonstradas pelo princípio 
de indução: 
1ª parte: Vamos mostrar que 1 + n = n + 1, para todo natural n. 
2ª parte: vamos mostrar que m + n = n + m, quaisquer que sejam m e n 
naturais. 
1ª PARTE: 
Seja X o conjunto de todos os números naturais n tais que 1 + n = n + 1. 
Note que 1 pertence a X pois, 1+1 = 1 + 1. 
Suponhamos agora que um dado k pertença a X, ou seja, que 1 + k = k + 1 para 
algum k, e vamos mostrar que 
)k(
 pertence a X. 
 
 
 
1)k(
11k
1k1
1k1)k(1






 
Segue que 
)k(
 pertence a X e, portanto, pelo Princípio da Indução, 1 + n = n + 1, 
qualquer que seja n natural. 
2ª PARTE: 
Seja Y o conjunto de todos os números naturais m tais que m + n = n + m, qualquer 
que seja n natural. 
Note que 1 pertence a Y pois, 1 + n = n + 1. 
Suponhamos agora que um dado k pertença a Y, ou seja, que k + n = n + k para 
algum k, e vamos mostrar que 
)k(
 pertence a Y. 
 
 
 
 
 
 
)k(n
1kn
1kn
1nk
1nk
n1k
n1kn)k(









 
Segue que 
)k(
 pertence a Y e, portanto, pelo Princípio da Indução, m + n = n + m, 
quaisquer que sejam m, n números naturais. 
Propriedade associativa 
k pertence a X e, portanto, 1 + k = k + 1 
Propriedade associativa 
1 pertence a Y e, portanto, 1 + n = n + 1 
Propriedade associativa 
Propriedade associativa 
k pertence a Y e, portanto, k + n = n + k 
b) Sejam m, n e p três números naturais quaisquer, se m + n = m + p, então n = p 
(lei do corte). 
Seja X o conjunto formado por todos os números naturais m para os quais vale 
a seguinte propriedade: se m + n = m + p, então n = p. 
Note que 1 pertence a X pois, 
pn
)p()n(
1p1n
p1n1





 
Suponhamos agora que um dado k pertença a X, ou seja, que valha a propriedade: 
Se k + n = k + p, então n = p, e vamos mostrar que 
)k(
 pertence a X. 
 
pn
pknk
kpkn
)kp(kn
)k(p)k(n
p)k(n)k(









 
Segue que 
)k(
 pertence a X e, portanto, pelo Princípio da Indução, se m + n = m + p, 
então n = p, quaisquer que sejam m, n e p números naturais. 
 
2. Demonstre a propriedade de tricotomia para a relação de ordem: 
Dados dois números naturais m e n, uma e apenas uma das afirmações a seguir 
ocorre: ou m = n; ou m < n; ou m > n. 
Sejam m e n dois números naturais. De acordo com a Proposição 1.2.6 (Tricotomia), 
exatamente uma das três situações deve ocorrer: 
( i ) m = n 
(ii) existe um número natural p tal que m = n + p. 
Mas pela Definição 1.2.2, isso significa que n < m. 
(iii) existe um número natural q tal que n = m + q 
Propriedade comutativa 
Axioma 1 
Propriedade associativa 
Definição da soma de números naturais 
k pertence a X 
Axioma 1 
Propriedade comutativa 
Mas pela Definição 1.2.2, isso significa que m < n. 
Portanto, dados dois números naturais m e n, ou m = n, ou n < m, ou ainda m < n, 
CQD. 
 
3. Demonstre a propriedade comutativa da multiplicação de números naturais. 
Vamos mostrar que 
mnnm 
, quaisquer que sejam m e n números naturais através 
do principio de indução. Do mesmo jeito que fizemos no caso da adição de números 
naturais, dividiremos esta demonstração em duas partes: 
1ª parte: Vamos mostrar que 1.n = n.1, para todo natural n. 
2ª parte: vamos mostrar que m.n = n.m, quaisquer que sejam m e n naturais. 
1ª PARTE: 
Seja X o conjunto de todos os números naturais n para os quais 1.n = n.1 
Claramente, o número 1 pertence a X, pois 1.1 = 1.1. 
Suponhamos então que um dado número natural k pertença a X, isto é, que 1.k = k.1 e 
vamos mostrar que 
)k(
 pertence a X. 
1)k(
)k(
1k
11k
1k1)k(1








 
Logo 
)k(
 pertence a X. Como k foi pego como sendo qualquer número natural, 
segue que a propriedade vale para qualquer n. 
2ª PARTE: 
Seja Y o conjunto de todos os números naturais m para os quais m.n = n.m, qualquer 
que seja n natural. 
Na primeira parte, mostramos que1 pertence a Y. 
Seja k um número natural pertencente a Y, isto é, para o qual valha k.n = n.k e vamos 
mostrar que esta propriedade também é válida para 
)k(
. Para isso, utilizaremos a 
propriedade distributiva da multiplicação. 
)k(n
nkn
1nkn
n1nk
n)1k(n)k(







 
Segue que 
)k(
 pertence a Y. Como k foi considerado um número natural qualquer, 
segue que a propriedade é válida para qualquer m, CQD. 
4. Demonstre a monotonicidade para a multiplicação de números naturais. 
Sejam m e n dois números naturais tais que m < n. vamos mostrar que, então 
pnpm 
 para todo número natural p. 
Se p = 1, não há o que mostrar: m < n realmente implica em m.1 < n.1. 
Suponhamos agora que a propriedade seja válida para p = k e vamos provar que ela 
também é válida para 
).k(
 
)k(nnknmkm)k(m
knkm
nm
mkm)k(m











 
Portanto a propriedade é válida para todo natural p, CQD. 
5. Seja X um subconjunto de N que possui elemento máximo. Mostre que este 
elemento máximo é único (unicidade do máximo de X). 
Seja X um subconjunto de N que possui elemento máximo, isto é, existe um número 
natural m pertencente a X tal que 
nm
 qualquer que seja n elemento de X. Vamos 
provar que este elemento é único através da demonstração por absurdo. 
Suponhamos então que este elemento não seja único. Então existe p diferente de m 
pertencente a X tal que 
np 
 qualquer que seja n elemento de X. Como m pertence a 
X, 
mp 
. Por outro lado, m é o elemento máximo de X, ou seja, 
pm 
. Pelas duas 
desigualdades, p = m: contradição, pois p foi suposto diferente de m. Segue que o 
elemento máximo de X é único, CQD. 
TÓPICO 3 
 
1. Mostre que o conjunto 






 i,
2
1
,2,A 
 é um conjunto finito via definição. 
Dizemos que um conjunto A é finito se A for um conjunto vazio ou se existe uma 
função bijetora 
AI: n 
 para algum n pertencente a N. Assim, se A for um conjunto 
vazio, diremos que A tem zero elementos; se A for um conjunto não vazio finito, 
diremos que A tem n elementos. 
Consideremos n = 4 e definamos a função 
AI: 4 
 da seguinte forma: 
 )1(
; 
2)2( 
, 
2
1
)3( 
, 
i)4( 
. 
Note que esta função é sobrejetora, pois todos os elementos do conjunto A estão 
associados a alguém do conjunto 
4I
; além disso, esta associação é única, 
caracterizando a injetividade da função. Portanto, a função é bijetora, implicando em A 
ser finito.. 
 2. Prove que, dados dois números naturais m e n, se existir uma bijeção 
nm II: 
, segue que 
nm II 
 e, portanto m = n. (Dica: suponha que m seja 
menor do que n e recaia no Teorema 1.3.1) 
Dados dois números naturais m e n, suponhamos que existe uma bijeção 
nm II: 
. 
Como a função é uma bijeção, podemos supor que 
nm
, sem perda de 
generalidade. 
Então 
nm II 
, por definição, isto é 
mI
 é um subconjunto de 
nI
 e 
nm II: 
é uma 
bijeção. Logo, pelo Teorema 1.3.1: 
nm II 
., isto é, m = n. 
3. Mostre que se X e Y forem dois conjuntos tais que exista uma função injetora 
YX:f 
e se Y for um conjunto finito, então X também será finito e o número de 
elementos de X não excede o número de elementos de Y. (Dica: Utilize o fato de f 
ser um bijeção entre X e f(X) e o Teorema 1.3.2). 
Sejam X e Y dois conjuntos, sendo Y um conjunto finito, tais que exista uma função 
injetora 
YX:f 
. Consideremos então o conjunto imagem de f em Y, f(Y). 
Claramente f(Y) é um subconjunto de Y e, visto que Y é finito, pelo Teorema 1.3.2, f(Y) 
também é finito, sendo que o número de elementos de f(Y) não excede o número de 
elementos de Y. Por outro lado, a função f será uma função bijetora de X em f(Y), 
implicando em X e f(Y) terem o mesmo número de elementos. Portanto X é um 
conjunto finito e seu número de elementos não excede o número de elementos de Y, 
como queríamos demonstrar.. 
4. Mostre que se X e Y forem dois conjuntos tais que exista uma função 
sobrejetora 
YX:f 
e se X for um conjunto finito, então Y também será finito e 
o número de elementos de Y não excede o número de elementos de X. (Dica: 
Como f é sobrejetora, podemos considerar a função inversa a f - por que? – e 
recaia no exercício anterior). 
Sejam X e Y dois conjuntos, sendo X finito, tais que existe uma função sobrejetora 
YX:f 
. Então o conjunto imagem de f é Y – f(Y) = Y. Consideremos então a 
função 
XY:g 
 definida da seguinte forma: 
Seja y em Y. Como f era sobrejetora, existe x em X tal que f(x) = y. Definamos então 
g(y) = g(f(x)) = x. 
Claramente g é uma função injetora. 
De fato, se 
)z(g)y(g 
 para y, z elementos quaisquer de Y, pela definição de g, 
existem x, w em X tais que f(x) = y e f(w) = z. Agora 
wx))w(f(g))x(f(g)z(g)y(g 
 
Assim, temos uma função g injetora entre dois conjuntos Y e X tais que X é finito. Pelo 
exercício anterior, segue que Y é finito e tem, no máximo, o mesmo número de 
elementos de X, como queríamos demonstrar. 
5. Mostre que N é um conjunto infinito construindo uma bijeção entre N e o 
conjunto dos números pares. 
Seja X o conjunto formado por todos os números pares, isto é, 
 Nn:n2X 
. 
Claramente, X é um subconjunto próprio de N, pois N contém também os números 
ímpares. 
Consideremos agora a função 
XN:f 
 tal que f(n) = 2n, para todo n em N. 
Claramente a função está bem definida, pois cada elemento de N é mandado em um, 
e apenas um, elemento de X. Como N é um conjunto infinito, basta-nos mostrar que f 
é uma função injetora. Sejam n, m elementos de N tais que f(n) = f(m). Então, pela 
definição de f, 2n = 2m. Agora, pela lei do corte da multiplicação, temos que n=m; ou 
seja, f é injetora. Portanto, o conjunto dos números pares X é infinito, CQD. 
OBS: Utilizamos uma das propriedades de conjuntos infinitos, mas poderíamos ter 
utilizado outra. Isto é, esta solução não é única. 
6. Mostre que os conjuntos dos números inteiros Z e dos números racionais Q 
também são conjuntos infinitos. 
Claramente, o conjunto formado pelos números naturais, N, é um subconjunto próprio 
de Z e também de Q. Então existem funções injetoras 
ZN:f 
 e 
QN:g 
. Como N 
é infinito, segue que tanto Z como Q são infinitos. 
7. Mostre que a função 

 definida no Teorema 1.3.4 é, de fato, uma bijeção. 
Sejam X e Y dois subconjuntos finitos de N disjuntos com m e n elementos 
respectivamente e 
XI: m 
 e 
YI: n 
 duas bijeções. Consideremos então a 
função 
YXI: nm 
 definida da seguinte forma: 





n.mx1m se ),x()x(
,mx1 se ),x()x(

 
A função está bem definida, por X e Y são disjuntos. Vamos mostrar que 

 é uma 
bijeção. 
(i) A função é injetora. 
Sejam x, y elementos distintos de 
nmI 
 tais que x < y (se y < x, a ideia é a mesma). 
Então temos três possibilidades para analisar: 
1) x, y são tais que 
myx1 
. Neste caso, pela definição da função, 
)y()x()y()y()x()x(
injetora portanto, e, bijeção é 
yx
)y()y(
)x()x(




















 
2) x, y são tais que 
nmyx1m 
. Neste caso, pela definição da função, 
)y()x()y()y()x()x(
injetora portanto, e, bijeção é 
yx
)y()y(
)x()x(




















 
3) x e y são tais que 
mx1 
 e 
nmy1m 
. 
Neste caso, pela definição da função, 
)y()x()y()y()x()x(
disjuntos são Y e X
Y)y()y(
X)x()x(












 
Mostramos que a função é injetora. Vamos agora mostrar que é sobrejetora. 
Seja y um elemento de 
YX
. Como X e Y são disjuntos, ou y pertence a X ou y 
pertence a Y. Se y pertence a X, existe 
mx1 
 tal que 
)x()x(y  
. No caso 
de y pertencer a Y, existe 
nmx1m 
 tal que 
)x()x(y  
. De qualquer 
forma, existe um elemento x tal que 
nmx1 
 tal que 
)x(y 
, como queríamos 
demonstrar. 
 
TÓPICO 4 
1. Dados os conjuntos dos números naturais N e 
 Nn|n2X 
, mostre que a 
função 
XN:f 
 tal que 
n2)n(f 
 é uma bijeção. 
No exercício 5 do tópico anterior mostramos que f era injetora. Falta-nos mostrar que é 
sobrejetora. 
Para isso, consideremos m um elemento de X. então existe n em N tal que m = 2n. Ou 
seja, encontramos n em N tal que f(n) = 2n = m. Portanto f é sobrejetora, implicando 
em f ser bijetora, como queríamos demonstrar. 
2. Mostre que o conjunto dos números ímpares é um conjunto enumerável. 
Seja X o conjunto formado pelos números ímpares, isto é,
 Nn:1n2X 
. 
(Observe que o número 1 não está sendo contemplado em X, uma vez que 0 não é 
um número natural. Por outro lado, se mostrarmos que X é enumerável, como a união 
finita de enumeráveis é enumerável, teremos mostrado que o conjunto formado por 
TODOS os números ímpares X

{1} é enumerável). 
Claramente, X é um subconjunto próprio de N, pois N contém também os números 
pares. 
Consideremos agora a função 
XN:f 
 tal que f(n) = 2n+1, para todo n em N. 
Claramente a função está bem definida, pois cada elemento de N é mandado em um, 
e apenas um, elemento de X. 
Vamos mostrar que f é uma função injetora. Sejam n, m elementos de N tais que f(n) = 
f(m). Então, pela definição de f, 2n +1 = 2m +1. Agora, pelas leis do corte da adição e 
da multiplicação, temos que 2n = 2m e, portanto, n = m; ou seja, f é injetora. 
Mostraremos agora que f é sobrejetora. Para isso, consideremos m um elemento de X. 
então existe n em N tal que m = 2n +1. Ou seja, encontramos n em N tal que f(n) = 
2n+1 = m. Portanto f é sobrejetora, implicando em f ser bijetora. Segue da definição de 
enumerabilidade que o conjunto formado pelos números ímpares é enumerável, como 
queríamos demonstrar. 
 
3. Seja Y um conjunto enumerável e 
YX:f 
uma função injetora. Prove que X 
também será um conjunto enumerável. (Dica: lembre-se que a imagem de uma 
função é subconjunto do contra-domínio). 
Seja Y um conjunto enumerável e 
YX:f 
uma função injetora. 
Consideremos o conjunto imagem de f, f(X). Claramente, este conjunto é um 
subconjunto de Y e, portanto, enumerável. 
Então existe uma bijeção g entre N e f(Y). 
Por outro lado, se considerarmos a restrição de f em sua imagem, f(Y), teremos uma 
função bijetora 
)Y(fX:f 
 de X em um conjunto enumerável. 
Então podemos considerar o seguinte diagrama: 
 
  g(n)f g(n) n
X)Y(fN
1
fg 1




 
Como g é uma função bijetora, assim como a inversa de f restrita à sua imagem, 
segue que a função composta 
XN:h 
 definida por 
 )n(gf)n(h 1
, para todo n em 
N é uma função bijetora de N em X. Segue que X é enumerável. 
4. Seja X um conjunto enumerável e 
YX:f 
uma função sobrejetora. Prove 
que Y também será um conjunto enumerável. 
Se f é sobrejetora, existe um subconjunto X’ de X tal que f restrita a este conjunto, é 
injetora e sobrejetora. Como X’ é um subconjunto de X, X’ também é enumerável. 
Assim, temos uma função bijetora entre dois conjuntos enumeráveis. Segue pelo 
exercício anterior que Y também é enumerável. 
 
5. Mostre que o conjunto de todos os números primos é enumerável. 
Sabemos que, a menos do número 2, os outros números primos são todos impares. 
Logo o conjunto dos números primos é um subconjunto do conjunto 
}Nn:1n2{}2{X 
. 
Como o conjunto dos números primos é enumerável, X também é enumerável, pois é 
a união enumerável de enumeráveis. Assim, o conjunto dos números primos é um 
subconjunto de um conjunto enumerável, Segue que ele próprio é enumerável, como 
queríamos demonstrar.