Teoria de conjuntos/ funções

Prévia do material em texto

Tópicos de conjuntos e funções - lista 1
Prof. Ivaldo Nunes
Exerćıcio 1. Sejam P1, P2, Q1, Q2 propriedades referentes a elementos de um conjunto-
universo U . Suponha que P1 e P2 esgotam todos os casos posśıveis (ou seja, um elemento
qualquer de U ou tem a propriedade P1 ou tem P2). Suponha ainda que Q1 e Q2 são
incompat́ıveis (isto é, excluem-se mutuamente). Suponha, finalmente, que P1 ⇒ Q1 e
P2 ⇒ Q2. Prove que valem as rećıprocas: Q1 ⇒ P1 e Q2 ⇒ P2.
Exerćıcio 2. Expressões tais como “para todo” e “qualquer que seja” são chamadas de
quantificadores e aparecem em sentenças dos tipos:
(1) “Para todo x, é satisfeita a condição P (x)”
(2) “Existe algum x que satisfaz P (x)”, onde P (x) é uma condição envolvendo a
variável x.
(a) Sendo A o conjunto de todos os objetos x (de um certo conjunto universo U)
que satisfazem a condição P (x), escreva as sentenças (1) e (2) acima, usando a
linguagem de conjuntos.
(b) Quais são as negações de (1) e (2)? Escreva cada uma destas negações usando
conjuntos e compare com as sentenças obtidas em (a).
(c) Para cada sentença abaixo, diga se ela é verdadeira ou falsa e forme a sua negação:
– Existe um número real x tal que x2 = −1.
– Para todo inteiro n, vale n2 > n.
– Para todo número real x, tem-se x > 1 ou x2 < 1.
– Para todo número real x existe um número real n tal que n > x.
– Existe um número real n tal que, para todo x, tem-se n > x.
Exerćıcio 3. Considere os conjuntos abaixo:
F = conjunto de todos os filósofos
M = conjunto de todos os matemáticos
C = conjunto de todos os cientistas
P = conjunto de todos os professores
(a) Exprima cada uma das afirmações abaixo usando a linguagem de conjuntos:
1) Todos os matemáticos são cientistas.
2) Alguns matemáticos são professores.
3) Alguns cientistas são filósofos.
4) Todos os filósofos são cientistas ou professores.
5) Nem todo professor é cientista.
(b) Faça o mesmo com as afirmativas abaixo:
6) Alguns matemáticos são filósofos.
7) Nem todo filósofo é cientista.
8) Alguns filósofos são professores.
9) Se um filósofo não é matemático, ele é professor.
10) Alguns filósofos são matemáticos.
(c) Tomando as cinco primeiras afirmativas como hipóteses, verifique quais das afir-
mativas do segundo grupo são necessariamente verdadeiras.
Exerćıcio 4. O diagrama de Venn para os conjuntos X, Y, Z decompõe o plano em oito
regiões. Numere as regiões e exprima cada uma dos conjuntos abaixo como reunião de
algumas dessas regiões. (Por exemplo: X ∩ Y = 1 ∪ 2.)
(a) (Xc ∪ Y )c
1
(b) (Xc ∪ Y ) ∪ Zc
(c) (Xc ∩ Y ) ∪ (X ∩ Zc)
(d) (X ∪ Y )c ∩ Z
Exerćıcio 5. Exprimindo cada uma membro como reunião de regiões numeradas, prove
as igualdades:
(a) (X ∪ Y ) ∩ Z = (X ∩ Z) ∪ (Y ∩ Z)
(b) X ∪ (Y ∩ Z)c = X ∪ Y c ∪ Zc
Exerćıcio 6. Dados os conjuntos A e B, seja X um conjunto com as seguintes proprie-
dades:
(1) A ⊂ X e B ⊂ X,
(2) Se A ⊂ Y e B ⊂ Y então X ⊂ Y .
Prove que X = A ∪B.
Exerćıcio 7. Enuncie e demonstre um resultado análogo ao anterior, caracterizando
A ∩B.
Exerćıcio 8. Sejam X, Y ⊂ U . Prove que:
(a) A ∩B = ∅ se, e somente se, A ⊂ Bc
(b) A ∪B = U se, e somente se, Ac ⊂ B.
Exerćıcio 9. Dê exemplo de conjuntos A,B,C tais que (A ∪B) ∩ C 6= A ∪ (B ∩ C).
Exerćıcio 10. Dado um número natural a, seja Y ⊂ N um conjunto com as seguintes
propriedades:
(1) a ∈ Y ;
(2) n ∈ Y ⇒ n + 1 ∈ Y .
Prove que Y contém todos os números naturais maiores do que ou igual a
Exerćıcio 11. Use o exerćıcio anterior para provar que 2n + 1 ≤ 2n para todo n ≥ 2 e,
em seguida, que n2 < 2n para todo n ≥ 5.
Exerćıcio 12. Prove, por indução, que(
n + 1
n
)n
≤ n
para todo n ≥ 3 e conclua dáı que a sequência
1,
√
2,
3
√
3,
4
√
4, . . .
é decrescente a partir do terceiro termo.
Exerćıcio 13. Prove, por indução, que
1 + 22 + 32 + · · ·+ n2 = n(n + 1)(2n + 1)
6
.
Exerćıcio 14. Seja X ⊂ N um conjunto não-vazio, com a seguinte propriedade: para
qualquer n ∈ N, se todos os números naturais menores do que n pertencem a X então
n ∈ X. Prove que X = N.
Sugestão: use o prinćıpio da boa ordenação.
Exerćıcio 15. Seja P (n) uma propriedade relativa ao número natural n. Suponha que
P (1) e P (2) são verdadeiras e que, para qualquer n ∈ N, a verdade de P (n) e P (n + 1)
implica a verdade de P (n + 2). Prove que P (n) é verdadeira para todo n ∈ N.
2
Exerćıcio 16. Use indução para provar que
13 + 23 + +33 + · · ·+ n3 = n
2(n + 1)2
4
.
Exerćıcio 17. Prove que:
(a) A ∪B = B se, e somente se, A ⊂ B.
(b) A ∩B = B se, e somente se, B ⊂ A.
Exerćıcio 18. A diferença entre conjuntos é definida por A \ B = {x ∈ A : x /∈ B}.
Prove que (A \B) ∪ (B \ A) = (A ∪B) \ (A ∩B).
Exerćıcio 19. A diferença simétrica entre conjuntos é definida por A∆B = (A \ B) ∪
(B \ A). Prove que A∆B = A∆C implica B = C.
Exerćıcio 20. Seja f : X → Y uma função. A imagem inversa por f de um conjunto
B ⊂ Y é o conjunto f−1(B) = {x ∈ X : f(x) ∈ B}. Prove que:
(a) A ⊂ f−1(f(A)) para todo A ⊂ X.
(b) f(f−1)(B) ⊂ B para todo B.
(c) f é injetiva se, e somente se, A = f−1(f(A)) para todo A ⊂ X.
(d) f é sobrejetiva se, e somente se, f(f−1)(B) = B para todo B ⊂ Y .
Exerćıcio 21. Prove que a função f : X → Y é injetiva se, e somente se, existe uma
função g : Y → X tal que g(f(x)) = x para todo x ∈ X.
Exerćıcio 22. Prove que a função f : X → Y é sobrejetiva se, e somente se, existe uma
função h : Y → X tal que f(h(y)) = y para todo y ∈ Y .
Exerćıcio 23. Dada a função f : X → Y , suponha que g, h : Y → X são funções tais
que g(f(x)) = x para todo x ∈ X e f(h(y)) = y para todo y ∈ Y . Prove que g = h.
Exerćıcio 24. Defina uma função sobrejetiva f : N → N tal que, para todo n ∈ N, a
equação f(x) = n possui uma infinidade de soluções x ∈ N.
Sugestão: use que todo número natural se escreve, de modo único sob a forma 2ab, onde
a, b ∈ N e b é ı́mpar.
Exerćıcio 25. Prove, por indução, que um conjunto com n elementos possui 2n subcon-
juntos.
Exerćıcio 26. Dados n (n ≥ 2) objetos de pesos distintos, prove que é possśıvel deter-
minar qual o mais leve e qual o mais pesado fazendo 2n− 3 pesagens em uma balança de
pratos. É esse o número mı́nimo que permitem determinar o mais leve e o mais pesado?
Exerćıcio 27. Prove que, dado um conjunto com n elementos, é posśıvel fazer uma fila
com seus subconjuntos de tal modo que cada subconjunto da fila pode ser obtido a partir
do anterior pelo acréscimo ou pela supressão de um único elemento.
3