Lista de Exercícios Resolvidos - Teoria dos Conjuntos e Funções

113 Exercícios 1 Mostre que ϕ A qualquer que seja o conjunto A 2 Prove as seguintes propriedades das operações de união e interseção a A ϕ A b A A A c A B B A d A B C A B C e A B A se e somente se B A f Se A B e X Y então A X B Y g A B C A B A C h A ϕ ϕ i A A A j A B B A k A B C A B C l A B A se e somente se A B m Se A B e X Y então A X B Y n A B C A B A C 3 Dados os conjuntos A e B Seja X um conjunto com as seguintes propriedades A X e B X Se A Y e B Y então X Y Prove que X A B 4 Dados os conjuntos A e B Seja X um conjunto com as seguintes propriedades X A e X B Se Y A e Y B então Y X Prove que X A B 5 Mostre que A C se e somente se A B C A B C 6 Dê um exemplo de conjuntos A B e C tais que A B C A B C 7 Sejam A e B subconjuntos do conjunto fundamental E Mostre que A B A CB 8 Sejam A e B subconjuntos do conjunto fundamental E Prove as seguintes propriedades de complementares a CCA A b A B se e somente se CB CA c A ϕ se e somente se CA E d CA B CA CB e CA B CA CB f A B ϕ se e somente se A CB g A B E se e somente se CA B h A B se e somente se A CB ϕ i Se A B ϕ e A B E então B CA 9 Prove que A B se e somente se A CB CA B ϕ 10 Seja AΔB A B B A Mostre que a AΔB A B A B b Se AΔB AΔC então B C 11 Prove as seguintes afirmações a A B C A C B C b A B C A C B C c A B C A C B C d Se A X e B Y então A B X Y 122 Exercícios 1 Sejam a função f A B e XY A Mostre que a fX Y fX fY b fX Y fX fY c Se X Y então fX fY d fϕ ϕ 2 Sejam a função f A B e XY B Mostre que a f¹X Y f¹X f¹Y b f¹X Y f¹X f¹Y c Se X Y então f¹X f¹Y d f¹ϕ ϕ e f¹CX Cf¹X 3 Sejam A B e i A B tal que ix x para todo x A função conhecida por inclusão Mostre que i é uma função injetiva 4 Dada uma função f A B Mostre que F A A B onde Fx x fx é injetiva 5 Dada a função f A B Prove que a fX fY fX Y quaisquer que sejam XY A b Se f é injetiva então fX fY fX Y quaisquer que sejam XY A 6 Mostre que a função f A B é injetiva se e somente se fA X fA fX 7 Dada a função f A B Prove que a X f¹fX qualquer que seja X A b f é injetiva se e somente se X f¹fX qualquer que seja X A 8 Dada a função f A B Prove que a ff¹Y Y qualquer que seja Y B b f é sobrejetiva se e somente se ff¹Y Y qualquer que seja Y B 9 Sejam π₁ A B A e π₂ A B B tais que π₁ab a e π₂ab b estas funções são conhecidas como projeções Mostre que π₁ e π₂ são uma funções sobrejetivas 10 Mostre que toda função pode ser escrita como a composta de uma função sobrejetiva com uma injetiva 11 Prove que uma função f A B possui uma inversa à esquerda se e somente se é injetiva 12 Prove que uma função f A B possui uma inversa à direita se e somente se é sobrejetiva 13 Prove que uma função f A B possui uma inversa e somente se é bijetiva 134 Exercícios 1 Prove as seguintes propriedades da adição A1 Associatividade m n p m n p para todo m n p N A2 Comutatividade m n n m para todo m n N A3 Lei do Corte m n m p implica que n p 2 Prove as seguintes propriedades da Multiplicação M1 Associatividade m n p m n p para todo m n p N M2 Comutatividade m n n m para todo m n N M3 Lei do Corte m n m p implica que n p M4 Distributividade m n p m n m p para todo m n p N 3 Prove as seguintes propriedades de Ordem O1 Transitividade Se m n e n p então m p O2 Tricotomia Dados m n N só temse apenas três possibilidades ou m n ou m n ou n m O3 Monotonicidade da adição m n implica que m p n p para todo p N O4 Monotonicidade da multiplicação m n implica que m p n p para todo p N 4 Prove que assumindo os axiomas de P1 e P2 verdadeiros o axioma P3 é equivalente ao seguinte axioma Para todo conjunto A N temse que A sA 0 5 Mostre por indução que a 1 2 3 n nn12 b 1 2² 3² n² n2n² 3n 16 c 1 2³ 3³ n³ 1 2 3 n² 6 Dados a b N prove que existe um número natural m tal que m a b 7 Seja a N Se um conjunto X é tal que a X e além disso n X implica que n 1 X então X contem todos os naturais p tal que p a 8 Mostre que a n 2n para todo n 4 b 2n n² para todo n 4 9 Mostre que todo número natural maior ou igual que 2 possui uma decomposição em fatores primos 113 Exercícios 1 Prova Suponha que A Então x tal que x A Absurdo Pois x Portanto A 2 a Se x A então x A Logo A A Por outro lado se x A então x A logo A A Portanto A A b Se x A então x A A Por outro lado se x A A então x A Portanto A A A c x A B x A ou x B x B ou x A x B A Portanto A B B A d x A B C x A B ou x C x A ou x B ou x C x A ou x B ou x C x A B C e Suponha que A B A então se x B logo x A B A Portanto B A Suponha que B A x A B x A ou x B Se x A então A B A Se x B então x A pois B A Logo A B A Por outro lado se x A então x A B Logo A B A Portanto A B A f Suponha que A B e X Y Seja x A X então x A ou x X Se x A então x B logo x B Y Agora se x X então x Y logo x B Y Portanto A X B Y g x A B C x A ou x B C Se x A então x A B e x A C Logo x A B A C Se x B C então x B e x C o que implica x A B e x A C ou seja x A B A C Portanto A B C A B A C Por outro lado x A B A C x A B e x A C x A ou x B C x A B C Logo A B C A B A C Portanto A B C A B A C h Se existe x A então x Absurdo Logo A i x A A x A e x A x A A A A Por outro lado x A x A e x A x A A Portanto A A A j x A B x A e x B x B e x A x B A Portanto A B B A k x A B C x A B e x C x A e x B x C x A x B e x C x A e x B C x A B C l Suponha A B A Como A A B então se x A segue x A B ou seja x B Portanto A B Suponha A B x A B x A B e x B x A Por outro lado x A B x A e x B x A B Portanto A B A m suponha A c B e X c Y x A x x A e x X x B e x Y x B Y Portanto A x c B Y n x A B U C x A e x B U C x A e x B ou x C Se x A e x B então x A B Logo x A B U A C Se x A e x C então x A C Logo x A B U A C Por outro lado x A B U A C x A B ou x A C Se x A B então x A e x B U C Se x A C então x A e x B U C Logo x A B U C Portanto A B U C A B U A C 3 x A U B x A ou x B como A c X B c X x X Logo X c A U B x A U B x Y x Y Contradição Logo x A U B 4 x X x A B pois x A e x B Logo x A B suponho A B X existe x A B tal que x X y A tal que x y y B x X logo que y X contradição pois x X Portanto A B X 5 suponha A C x A B C x A B e x C x A ou x B e x C Se x A e C logo x A B C Se x B então x B C Logo x A B C Por outro lado x A B C x A ou x B C x A ou x B e x C Se x A e x então x C Logo x A B e x C ou seja x A B C Se x B C então x A B C Portanto A B C A B C suponha A B C A B C x A B C x A B e x C Se x A e x C Se x B e x C e x A Logo A C 6 Sejam A 0 2 B 2 4 C 4 6 A U B n C 0 4 n 4 6 4 A U B n C 0 2 U 2 4 n 4 6 0 2 U 4 Logo A U B n C A U B n C 7 Se x A B x A e x B x A e x C B x A n C B Por outro lado x A n C B x A e x C B x A e x B x A B Portanto A B A n C B 8 a x C C A x C A x A Por outro lado x A x C A x C C A Portanto C C A A b suponha A B x C B x B x A B x C A Portanto C B C A suponha CB CA x CB x B x A pois CB CA Logo A B c suponha A Logo não existe x A ou seja x CA como A x Logo CA suponha CA x CA x A A já que CA d x C A U B x A U B x A e x B x CA e x CB x CA CB Por outro lado x CA CB x A e x B x A U B x C A U B e x C A B x A B x A ou x B x CA ou x CB x CA U CB Por outro lado x CA U CB x A ou x B x A B x C A B f suponha A n B x A x B x C B Portanto A C B suponha CA B É claro A n B Por outro lado x A n B x A e x B x CA e x B Mas CA B Logo não existe x A n B Portanto A n B g suponha A B ū x CA x A x A B ū x B Logo CA B suponha CA B x A B é claro x ū Por outro lado x ū x A e Logo x CA então como CA B temos x A B h suponha A B x A n CB x A B e x B A n CB A n CB Não existe x A n CB x A x CB Logo x A e x B Logo A B i x B x A pois A n B x C A x C A B C A Por outro lado x CA x A x Ā A U B x B B CA Portanto B CA 9 suponho A B x A n C B U C A n B x A n C B ou x C A n B x A x B ou x A x B Como A B então A U C B U C A n B x A x C B x B Agora x B x C A x A Portanto A B 10 a Temos que mostrar A B U B A A U B A n B A Δ B x A B U B A x B A ou x A B x A x B ou x B x A x A U B x A n B x A U B A n B Por outro lado x A U B A n B x A U B x A n B x A ou x B x A x B x A x B ou x B x A x A B U B A Portanto A Δ B A B U B A b Temos que mostrar se A B U B A A C U C A então B C Se x B x A logo x A B U B A A C U C A ou seja x C Logo B C Por outro lado x C x A x A C U C A A B U B A logo x B Daí segue B C Portanto B C 11 x A U B x C então x a c onde a A U B Se a A então a c A x C Logo a c A x C U B x C Se a B então a c B x C Logo a c A x C U B x C Por outro lado x A x C U B x C x A x C ou x B x C x A x C x a c x B x C x a c a B x A U B x C b x A B x C x a c com a A B x a c A x C B x C Por outro lado x A x C B x C x a c com a A B x a c A B x C c x A B C x a c com a A a B a c A C B C Por outro lado x A C B C x a c com a A a B x a c A B C d Suponha A X e B Y x A B x a b com a A X e b B Y Logo x a b X Y Portanto A B X Y 122 Exercícios a a fxy então existe b xy tal que fb a Se b x então fb a fx Se b y então fb a fy Logo a fx fy Por outro lado a fx fy a fx ou a fy a fx b x tal que fb a a fy b y tal que fb a a e fx y b a fxy b xy tal que fb a a fx fy Portanto fxy fx fy d É claro f¹ se existe b B tal que fb x e n t ã o x Absurdo Portanto f 2 a a f¹x y b x y tal que fa b a f¹x f¹y d claro f1 como não existe x então f1 3 Suponha que ix iy com x y A Então x y Portanto i é uma função injetiva 5 α f1x f1y α f1x α f1y b x y tal que f1b α α f1x y 6 Segue do item b do exercício 5 Suponha que fa₁ fa₂ com a₁ a₂ A Se a₁ a₂ A X então a₁ a₂ Se a₁ a₂ X fa₁ a₂ Se ou a₁ A X a₂ X a₁ a₂ pois fA X fA fx 7 Temos f¹fx x X fx fx Logo X f¹fx b Suponha que f é injetivo Pelo item a X f¹fx Se x f¹fx então existe a fx tal que fx a Como f é injetiva segue x X Portanto X f¹fx Suponha fx₁ fx₂ logo x₁ x₂ f¹fx X logo x₁ x₂ Portanto f é injetiva 8 a Se y ff¹y então existe x f¹y tal que y fx Como x f¹y temos fx Y Logo y fx Y Dado y fx Y então y Y Portanto ff¹y Y b Pelo item a ff¹y Y Seja y Y Como f é sobrejetiva existe x f¹Y tal que fx y Portanto y fx para algum x f¹Y implicando y ff¹y Portanto ff¹y Y Seja y B Como ff¹y Y existe x tal que fx y pois y Y Logo para y B existe x A tal que fx y Portanto f é sobrejetiva 9 Sejam π₁ A x B A e π₂ A x B B ab a ab b Para qualquer aA podemos escolher arbitrariamente b B assim temos ab A x B logo π₁ab a ou seja para cada a A existe pelo menos um ponto ab A x B tal que π₁ab a Logo π₁ é sobrejetiva Analogamente π₂ é sobrejetiva 10 Seja f A B uma Função queremos mostrar que é possível decompor f em uma Função sobrejetiva g A C e uma Função injetiva h C B tal que f h o g Seja C f₁A f₁a a A Defina g A C que mapeia cada a A para seu respectiva imagem em C ou seja ga f₁a a A Note que g é sobrejetiva pois a imagem de g é igual a imagem de f Agora defina h C B tal que hc f¹ c c C onde f¹ é o inverso de f restrita à C Como f é sobrejetiva f¹ existe c C e h é injetiva pois f é definida como uma Função isto é um elemento de C leva a único elemento de B Vejamos f h o g Para qualquer a A temos h o g a hga hf₁a f¹ f₁a a Portanto f h o g 11 se f é injetiva para todo y f₁A existe um único x A tal que y f₁x seja x gy Defina a Função g f₁A A tal que gf₁x x x A e g B A tal que gy x₀ x₀ A Fix o y B f₁A Temos g B A é tal que g o f idA se existe g B A tal que g o f idA dados x₁ x₂ A temos f₁x₁ f₁x₂ x₁ gf₁x₁ gf₁x₂ x₂ Portanto f é injetiva 12 Seja g B A tal que fog idB então dado y B ponha x gy Então fx fgy x Portanto f é sobrejetiva Seja f A B sobrejetiva Então y B f1y Para cada y B escolha x A tal que fx y e ponha gy x Definimos uma função g B A tal que fgy y Logo g é a inversa à direita de f 13 Se f A B possui inversa então possui inversa à esquerda e à direita Logo por 11 e 12 f é injetiva e sobrejetiva Portanto f é sobrejetiva e injetiva ou seja é bijetiva Se f é bijetiva então por 11 e 12 f possui inversa à esquerda e ó direta Portanto f possui inversa 134 1 a m n δp m δn p δm n p δm n p m n δp Logo m n p m n p b δm n δn m Logo m n n m c n m n n m p n m n n m p n p 2 a m 1 m m n p 1 m n p m n p m n p b m 1 m m n 1 m n m n n m c m n m p m n 1 m p 1 m n m p n p d m n p 1 m n p m n mp np m n mp m np n m p 1 n p 1 Logo m n p m n m p 3 a m n q N tal que n m q n p z N tal que p n z Logo p n z m q z m q z Portanto m p 4 Suponha que vale P3 Suponha por absurdo que exista A A IN tal que A SA então A SA isto é x A existe y A tal que x Sy sabemos que 1 A caso contrario 1 A SA Se n A mostraremos que Sn A Se Sn A teríamos uma contradição com A SA pois teria que existir y A tal que Sy Sn e por injetividade y n contradizendo a hipótese Logo Sn A A pois não contém nenhum número natural mas por hipótese A Absurdo Por P2 temos que 1 é o único elemento de IN SIN por P1 SIN IN Logo IN 1 SIN implicando 1 A n IN Sn A A IN 5 a se n 1 então 1 1 1 1 2 Logo a igualdade vale para n 1 Suponha que para n k vale 1 2 3 k k k 1 2 Então 1 2 3 k k 1 k 1 k 2 2 De fato 1 2 3 k k 1 k k 1 2 k 1 k k 1 2 2 k 1 2 k2 k 2k 1 2 k2 3k 1 2 k 1 k 2 2 b m n q IN tal que n m q Logo n p m q p m p q Portanto m p n p c m n q IN tal que n m q Logo n p m q p m p q p Portanto m p n p Portanto a igualdade vale n ℕ b Se n 1 então 1² 1 1 21² 31 1 6 Logo vale para n 1 Suponha que vale para n k ou seja 1 2² k² k 2k² 3k 1 6 Então também vale para k 1 ou seja 1 2² k² k 1² k 12k 1² 3k 3 1 6 Temos 1 2² k² k 1² k 2k² 3k 1 6 k 1² k 2k² 3k 1 6 k 1² 6 k 2k 1k 1 6 k 1² 6 k 1 k 2k 1 6 k 1 6 k 1 2 k 1² 3k 1 1 6 Portanto vale n ℕ c Se n 1 então 1³ 1 1² Logo vale para n 1 Suponha que para n k temos 1 2³ k³ 1 2 k² Então 1 2³ k³ k 1³ 1 2 k k 1² De fato 1 2³ k³ k 1³ 1 2 k² k 1³ 2 k 1² k 1³ 2 1 k 1² k³ 3k² 3k 1 1 2 k k 1² Portanto n ℕ vale a igualdade