Baixe o app para aproveitar ainda mais
Prévia do material em texto
ESPAÇOS MÉTRICOS E ESPAÇOS TOPOLÓGICOS Nuno C. Freire e M. F. Veiga Setembro 2010 ISBN 989-20-2175 i Prefácio A aplicação da Matemática, em que se consideram unicamente conceitos abstractos ao estudo da realidade Física, reflecte como o pensamento humano é moldado à existência material. Em Topologia obtem-se uma Teoria relativa aos conceitos de figura, pela caracterização da forma_ Figuras que podem obter-se uma da outra por uma deformação continuada são chamadas homeomorfas; homeomorfismo é um conceito fundamental em Topologia; e distinguem-se figuras formadas por "um só" ou "vários bocados"_ E de número, pela formulação geral rigorosa do conceito de limite. Assim em particular a Topologia é fundamental em Análise Matemática. Já da Antiguidade se recolhem os Elementos de Euclides, um primeiro exemplo de uma Teoria Axiomática. Esta obtem-se na dedução de propriedades feita a partir de outras e uma propriedade só é aceite como verdadeira_Um Teorema da Teoria_ Se foi demonstrada ou seja, se ficou provado que é consequência lógica de propriedades anteriores. Indispensável é assim a Lógica Matemática; esta assenta na distinção entre os valores lógicos Verdadeiro e Falso, e tem como Princípios fundamentais a não contradição (uma proposição não pode ser simultaneamente Verdadeira e Falsa) e o terceiro excluído (dada uma proposição, esta é Verdadeira ou é Falsa, não podendo dar-se outro caso). E a Teoria de Conjuntos, que dá corpo rigoroso a toda a Matemática, que teve avanços notáveis no séc. XIX. Este livro é inicialmente concebido como um texto para o estudante que lhe dá chão seguro para proseguir em Análise e, de forma geral para todo o Curso. A matéria é exposta na forma de exercícios resolvidos, recolhida de obras consagradas. Sugere-se ao leitor que vá seguindo as resoluções para de seguida, pouco a pouco, procurar por si resolver recorrendo quando necessário a uma solução exposta. Inicia com uma abordagem intuitiva de Teoria de Conjuntos e noções básicas de Lógica Matemática no Cap. I. Aconselha-se a leitura atenta deste Capítulo. Da experiência de um dos Autores, o Aproveitamento é muito melhor quando se começa pelos Espaços Métricos, expostos no Cap. II; assim se facilita o processo de abstracção. Np Cap. III trata-se a Topologia Geral. As matérias são desenvolvidas de modo a que excedem um Curso habitual de Topologia de um Semestre. Nomeadamente o Cap. IV não terá cabimento nesse âmbito. Para o estudo da Topologia incluímos no Cap. III o esboço de uma Axiomática rigorosa de Teoria de Conjuntos, baseada na Axiomática de Bernays-Gödel-von Neumann que é adoptada pelo texto de referência [Dugundji]. Numa primeira abordagem (quiçá inevitavelmente para um primeiro Curso) é suficiente o Cap. I. Motivados pelo interesse no tema, apresentamos desenvolvimentos possivelmente apropriados para pós-graduação. São indicadas referências bibliográficas para o aprofundamento em Topologia, que esperamos possam ser úteis para Colegas interessados. ii ÍNDICE Prefácio ..................................................................................................i I RELAÇÕES, CONJUNTOS E FUNÇÕES .......................................1 I.1 Relações numa variável e conjuntos ...............................................2 I.2 Relações binárias e funções .......................................................... 21 I.3 Axioma de Zermelo e produto cartesiano infinito Operação de Hilbert .......................................................... .............25 I.4 Funções associadas de conjuntos de uma função ........ .......... .... 26 I.5 Relações de equivalência e relações de ordem ............ .............. 29 I.6 O conjunto N. Noções de cardinalidade ......................... .............. 36 I.7 Filtros e ultrafiltros. Redes ..............................................................47 I. 8 Exercícios e complementos ............................................................ 54 Bibliografia do Capítulo I ................................................................ 57 II ESPAÇOS MÉTRICOS ................................................................ 58 II.1 Desigualdades de Cauchy-Schwarz, Hölder e Minkowski .............59 II.2 Distância num conjunto. Espaço métrico. Sucessões convergentes .............................................................. 61 II.3 Vizinhanças de um ponto num espaço métrico ............................. 72 II.4 Métricas equivalentes .....................................................................75 II.5 Topologia de um espaço métrico .................................................. 80 II.6 Topologia de subespaço métrico. Separabilidade ......................... 97 II.7 Condições de cardinalidade em espaços métricos ...................... 103 II.8 Limite de uma função entre espaços métricos num ponto e continuidade ..............................................................................111 II.9 Métricas sobre o produto cartesiano de espaços métricos ......... 126 II.10 Espaços métricos completos. Categoria ................................ ....130 II.11 Separação em espaços métricos ................................................143 II.12 Compacidade em espaços métricos ...........................................144 II.13 Conjuntos conexos em espaços métricos .................................. 154 II. 14 Exercícios e complemantos ................................................ .... 161 Bibliografia do Capítulo II ...................................................... ... 164 iii III ESPAÇOS TOPOLÓGICOS .................................................................165 III.1 Uma axiomática da teoria de conjuntos.. Números ordinais e números cardinais ...................................................166 III.2 Espaço topológico e base de uma topologia .........................................178 III.3 Vizinhanças de um ponto .......................................................................185 III.4 Subespaços topológicos ........................................................................ 188 III.5 Conjuntos fechados. Definição da topologia pelo operador de fecho ....190 III.6 Conjuntos notáveis associados a um conjunto no espaço topológico ...192 III.7 Convergência no espaço topológico .....................................................197 III.8 Limites e continuidade .......................................................................... 201 III.9 Separação ............................................................................................ 210 III.10 Topologia produto e topologia ccociente. Espaços completamente regulares. Obtenção de topologias ...................................................................... 221 III.11 Compacidade .......................................................................................239 III.12 Conjuntos conexos ...............................................................................257 III. 13 Exercícios e complementos .................................................................268 IV METRIZABILIDADE ..............................................................................270 IV.1 Espaços topológicos metrizáveis separáveis .......................................271 IV.2 Teoremas complementares ................................................................. 275 IV.3 Exercícios e complementos ................................................................. 280 Bibliografia dos Capítulos III, IV ........................................................... 283 -1- I RELAÇÕES, CONJUNTOS E FUNÇÕES -2- I.1 RELAÇÕES NUMA VARIÁVEL E CONJUNTOS Uma relação Rx numa variável x ∈ U (x pertence a U) é uma expressão em que figuram palavras da linguagem comum, acrescidas ou não de sinais ou símbolos matemáticos, que se transforma numa afirmação (proposição)para cada valor atribuido à variável x, percorrendo o conjunto U. Neste Cap. I não distinguimos entre os conceitos de colecção ou classe de entes, e o conjunto que constituem; o que é tema de III.1. em que expomos uma teoria axiomática de conjuntos, a que seguimos neste livro. Podem ocorrer numa Teoria matemática, relações numa variável x, que envolvam apenas símbolos matemáticos e a variável x. Sempre que não é claro no contexto, deve indicar-se expressamente o conjunto de valores que se considera para a variável, escrevendo Rx x ∈ U. I.1.1 Exemplos (1) Rx ≡ x é divisível por 3 x ∈ N é uma relação em x, considerada para x variando no conjunto dos números naturais N 1,2, . . .; (2) Rx ≡∣ x ∣ 1 x ∈ R é uma relação na variável x percorrendo o conjunto R dos números reais; (3) Rz ≡∣ z ∣ 1 z ∈ C é uma relação em C, o conjunto dos números complexos; (4) Rp ≡ p ∈ Q p ∈ N0 é uma relação na variável p, onde p varia no conjunto dos inteiros não negativos N0 (Q representa o conjunto dos números racionais). I.1.2 Observações (1) A cada conjunto dado A, podemos associar a relação correspondente x ∈ A, que é uma relação na variável x. No entanto, uma relação numa variável pode não definir nenhum conjunto. Aceitamos os princípios do terceiro excluido e da não contradição (uma proposição é verdadeira ou é falsa, e não pode ser verdadeira e falsa simultaneamente) da Lógica Clássica, e conclui-se facilmente que a relação x ∉ x não define nenhum conjunto: se A é o conjunto dos elementos x tais que x ∉ x, suponhamos A ∈ A; então A ∉ A, de modo que não pode ser A ∈ A, pelo princípio da não contradição. Pelo princípio do terceiro excluído, deve ter-se portanto A ∉ A; mas então A ∈ A, pela definição do conjunto A, o que não pode ser, de novo pelo princípio da não contradição. (2) O aluno já terá distinguido que expressões como "x ∉ x" , "x ∈ x" , serão ”absurdas”. Esta última, por exemplo porque uma vez conceptualizado um conjunto X, há que distinguir o conjunto dos elementos que lhe pertencem, e que são exactamente os objectos que satisfazem a relação x ∈ X. Deste modo deve escrever-se 1 ∈ 0,1,4 no lugar de 1 ∈ 0,1,4, ∈ em vez de ∈ ; em ambos os casos, se X é um conjunto formado por elementos a,b,u, escrevemos X a,b,u por exemplo. (A relação Rx ≡ x ∈ x ∈ N não é ”absurda”, recorde-se, mas uma relação impossível pois não é verificada por nenhum número natural). Questões como estas inserem-se na Teoria da Lógica Matemática aprofundada, e neste curso aceitaremos tacitamente axiomas de regularidade (numa Teoria Matemática, aceitam-se como verdadeiras certas hipóteses sem necessidade de demonstração, que se chamam axiomas), que dão lugar aos conceitos e notações habituais em Teoria dos Conjuntos. -3- I.1.3 Substituições numa relação Se Rx x ∈ U é uma relação em x, e c ∈ U, diz-se que a proposição Rc é obtida por substituição da variável x pela constante c I.1.4 Os valores lógicos V,F Segundo os princípios do terceiro excluido e da não contradição, a cada proposição P corresponde ou o valor lógico V, se a proposição é verdadeira, ou o valor lógico F, se é falsa; e não pode ocorrer um terceiro caso. Para simplificar, escreve-se P V, P F respectivamente no primeiro (segundo) caso. I.1.5 Exercício Em cada um dos exemplos (1),...,(4) anteriores, determine o valor lógico das proposições R4 e R1. (Note que 1,4 pertencem ao conjunto relativo à variável em cada exemplo). Resolução (1) R1 F. R4 F. (2) R1 ≡∣ 1 ∣ 1 V. R4 ≡∣ 4 ∣ 1 4 1 F. (3) R1 ≡∣ 1 ∣ 1 V. R4 ≡∣ 4 ∣ 1 4 1 F. (4) R1 ≡ 1 ∈ Q 1 ∈ Q V. R4 ≡ 4 ∈ Q 2 ∈ Q V. I.1.6 Formação de novas relações e tabelas de verdade Sendo Rx,Sx duas relações numa variável x percorrendo um mesmo conjunto U, então para cada substituição de x por uma constnte c ∈ U a proposição Rc ou Sc pode não significar o mesmo que Rc, nem que Sc. A proposição Rc ou Sc, ou mais geralmente R ou S, em que R,S são quaisquer proposições, designa-se por R ∨ S, neste caso Rc ∨ Sc. Uma vez que podemos considerar a proposição Rc ∨ Sc para cada valor da constante c tomada em U, faz sentido considerar a relação Rx ∨ Sx x ∈ U. Analogamente, dadas Rx,Sx, ambas relações em x ∈ U pode considerar-se a relação Rx e Sx, que se representa por Rx ∧ Sx. E assim como dada uma proposição R podemos considerar a sua negação, que notamos ~R, a negação da relação Rx x ∈ U é a relação ~Rx x ∈ U, sendo ~Rc a negação da proposição Rc, para cada substituição da variável x pela constante c fixada em U. Importante é também saber se uma relação Rx implica uma relação Sx, para a variável x tomando valores em U. Isto é verdade sse (abreviatura de ”se e só se”) para cada substituição da variável x por um elemento c ∈ U, as proposições obtidas Rc, Sc respectivamente verificam Rc Sc isto é, se sempre que se dá Rc V então tem-se Sc V; escreve-se neste caso Rx Sx x ∈ U. Rx,Sx são equivalentes quando Rx Sx e reciprocamente Sx Rx, nota-se então Rx Sx. Frequentemente, interessa ter informação sobre o valor lógico de uma proposição, ou de uma relação numa variável, obtida a partir de outras por utilização dos símbolos lógicos ∨,∧, ~,, não apenas no caso em que a proposição obtida é verdadeira (ou a proposição obtida por substituições numa relação), para estudar um problema; para isso utilizam-se as tabelas de verdade do cálculo proposicional, que indicam a variação dos valores lógicos. -4- I.1.7 Tabelas de verdade da disjunção, conjunção, negação, implicação e equivalência P Q P ∨ Q P ∧ Q ~P P Q P Q V V V V F V V V F V F F F F F V V F V V F F F F F V V V I.1.8 Exemplos (1) Sabendo-se que uma disjunção P ∨ Q V, e que P F, pode inferir-se pela observação da tabela, que Q V; (2) Se soubermos que uma implicação P Q é verdadeira (i.e, P Q V, e portanto se verifica o caso da 1ª linha, ou os casos da 3ª ou 4ª linhas da tabela de verdade), e que o consequente Q da implicação é Q F, podemos concluir que P F pela observação da tabela. I.1.9 Observação As tabelas de verdade aplicam-se também a relações, indicando-se o conjunto em que se considera a variável. Para uma relação Rx x ∈ U, põe-se Rx V x ∈ A se Rc V para cada subtituição da variável por qualquer constante c ∈ A ⊂ U. Por exemplo x2 0 x ∈ R é falsa, e x2 0 x ∈ R\0 é verdadeira. Também x2 1 x 1 x ∈ R é falsa, e x2 1 x 1 x ∈ R0 é verdadeira, onde R0 é o conjunto dos números reais não negativos. Para significar que duas relações Rx,Sx x ∈ U têm o mesmo valor lógico (i.e., para cada substituição da variável por uma constante c, as proposições Rc,Sc têm o mesmo valor lógico, Rc Sc), escreve-se Rx Sx. Por exemplo as relações em x ∈ N, Rx ≡ x é divisível por 4, e Sx ≡ x é divisível por 2 ,verificam Rx ∨ Sx Sx, Rx ∧ Sx Rx. Diz-se que as proposições R,S (respectivamente as relações em x, Rx,Sx) são equivalentes sse R S (respectivamente Rx Sx) I.1.10 Exemplo Dadas quaisquer proposições R,S, as tabelas de verdade de R S e de ~R ∨ S mostram que R S ~R ∨ S: R S ~R R S ~R ∨ S R S ~R ∨ S V V F V V V V F F F F V F V V V V V F F V V V V Uma proposição que assume sempre o valor lógico V diz-se uma tautologia. Assim R S ~R ∨ S é uma tautologia. R ∨ S S ∨ R, R ∧ S S ∧ R são tautologias -5- I.1.11 Exercícios (1) Verifique usando uma tabela de verdade, que ~ ~R R é uma tautologia. (2) Mostre que são tautologias, utilizando tabelas de verdade: (i) R R ∨ S; (ii) R ∧ S R; (iii) R S R S ∧ S R; (iv) R T ∧ S T R ∨ S T; (v) H T ~T ~H; (vi) R S ∧ R T R S ∧ T. (vii) R S ~R ∨ S. (3) Utilizando o exercício anterior, pode concluir quese R,S 0 são relações na variável ∈ R, onde R é o conjunto dos números reais positivos, então as implicações (i) R R ∨ S e (ii) R ∧ S R são verdadeiras? Porquê? (4) Sendo x0 ∈ a,b A ⊂ R, 0, (i) determine o maior subconjunto E de R tal que R ≡ x0 − ,x0 ⊂ A é verdadeira, com x0 ab2 , para todo o ∈ E. (ii) indique um valor de x0 tal que, para qualquer 0, sejam verdadeiras simultãneamente x0 − ,x0 ∩ A ≠ , x0 − ,x0 ∩ Ac ≠ . (Ac R\A é o conjunto complementar de A em R). Resolução (1) R ~R ~ ~R V F V F V F Uma vez que R, ~ ~R assumem sempre o mesmo valor lógico, conclui-se que ~ ~R R é uma tautologia. (2) (i) R S R ∨ S R R ∨ S V V V V V F V V F V V V F F F V (ii) R S R ∧ S R ∧ S R V V V V V F F V F V F V F F F V -6- (iii) R S R S R S S R R S ∧ S R V V V V V V V F F F V F F V F V F F F F V V V V Uma vez que os valores lógicos nas 3ª e última coluna coincidem, conclui-se a tautologia. (iv) R S T R ∨ S R T S T R T ∧ S T R ∨ S T V V V V V V V V V V F V F F F F V F V V V V V V V F F V F V F F F V V V V V V V F V F V V F F F F F V F V V V V F F F F V V V V Uma vez que sempre que o antecedente R T ∧ S T na penúltima coluna é verdadeiro, também o consequente R ∨ S T na última coluna é verdadeiro, concluimos que a implicação R T ∧ S T R ∨ S T é verdadeira. (v) H T ~H ~T H T ~T ~H V V F F V V V F F V F F F V V F F F F F V V V V Uma vez que os valores lógicos de H T, ~T ~H coincidem nas 5ª e 6ª colunas coincidem, conclui-se que H T ~T ~H. (vi) R S T S ∧ T R S R T R S ∧ R T R S ∧ T V V V V V V V V V V F F V F F F V F V F F V F F V F F F V V V V F V V V V V V V F V F F V V V V F F V F V V V V F F F F V V V V Coincidindo os valores lógicos nas duas últimas colunas, conclui-se a equivalência. (vii) R S ~R R S ~R ∨ S R S ~R ∨ S V V F V V V V F F F F V F V V V V V F F V V V V -7- (3) Sim, porque para cada substituição de por uma constante 0, as implicações R0 R0 ∨ S0 e R0 ∧ S0 R0 são verdadeiras ((2),(i),(ii)). (4) (i) O maior valor de para o qual ab2 − , ab2 ⊂ a,b é o maior 0 tal que ab2 − ≥ a ∧ ab2 ≤ b 0 ≤ ab2 − a b−a2 ∧ ≤ b−a2 ; é portanto b−a2 . Conclui-se 0, b−a2 . (ii) x0 a. I.1.12 Cálculo Proposicional e obtenção de conjuntos. Dados conjuntos X,Y definidos respectivamente por relações Rx,Sx, obtêm-se X Y x : Rx ∨ Sx x : x ∈ X ∨ x ∈ Y (”x :” leia-se ”x tal que”), X ∩ Y x : Rx ∧ Sx x : x ∈ X ∧ x ∈ Y e Y\X x : Sx ∧ ~Rx x ∈ Y : x ∉ X, onde x ∉ Y significa ~x ∈ Y. Se se consideram todos os conjuntos, como subconjuntos de um mesmo conjunto universal U, nota-se apenas Xc no lugar de U\X. Mais geralmente, se A1, . . . ,An são conjuntos, a reunião (resp. intersecção) finita dos conjuntos Ak k 1, . . . ,n é o conjunto Ak (resp. Ak) definido por k ∈ Sn k ∈ Sn Ak x : x ∈ A1 ∨. . .∨x ∈ An k ∈ Sn ( Ak x : x ∈ A1 ∧. . .∧x ∈ An) k ∈ Sn Para cada n ∈ N, Sn é a secção de índice n de N, Sn 1, . . . ,n. I.1.13 Observação De I.1.11 (1) concluimos que se A é um subconjunto de um conjunto universo U, tem-se Acc U. I.1.14 Exemplos (1) N0 0,1,2, . . . N 0. (2) Se k ∈ N, representa-se kN0 0,k, 2k, 3k, . . ., e para cada p ∈ N, kN p k p, 2k p, 3k p, . . .. Com k 3, obtem-se 3N0 p N, 3N0 p . p ∈ S3 p ∈ S3 I.1.15 Definição Se X ≠ ,Y ≠ , o par ordenado x,y (x ∈ X,y ∈ Y) pode definir-se como sendo o conjunto x,x,y x,y. Obtem-se então o conjunto produto cartesiano de X por Y, X Y x,y : x ∈ X,y ∈ Y. O produto cartesiano X X representa-se também por X2. De modo análogo, sendo X1, . . . ,Xm conjuntos não vazios, m ∈ N, define-se o produto cartesiano X1 . . .Xm k1m Xk x1, . . . ,xm : xk ∈ Xk,k 1, . . . ,m Nota-se X1 . . .Xm Xm se Xk X k 1, . . . ,m, para cada m ∈ N2, onde N2 2,3, . . .. Exemplos (1) O plano cartesiano real é o produto cartesiano R2. (2) i,−1,−i, 1 ∈ C4, onde C é o plano complexo. -8- I.1.16 Exercícios (1) Mostre que dados conjuntos não vazios A,B,C,D tem-se: (i) A C D A C A D; (ii) A B C A C B C (iii) A C ∩ D A C ∩ A D; (iv) A ∩ B C ∩ D A ∩ C B ∩ D. (2) Mostre que se R,S são proposições, a) verificam-se as leis de De Morgan: ~R ∨ S ~R ∧ ~S e ~R ∧ S ~R ∨ ~S são tautologias. (Utilize uma tabela de verdade grande); b) se P,A,B são proposições, (i) P ∧ A ∧ B P ∧ A ∧ P ∧ B; (ii) P ∧ A ∨ B P ∧ A ∨ P ∧ B; c) verifique também utilizando uma tabela de verdade, que pode trocar-se em b) (i), (ii) ∧ ∨ obtendo outras equivalências. d) Conclua de b) e a) que se P,R,S são proposições, então (i) P ∧ ~R ∨ S P ∧ ~R ∧ P ∧ ~S; (ii) P ∧ ~R ∧ S P ∧ ~R ∨ P ∧ ~S. (3) Determine : (i) 4N0 p (ii) 4N0 p (iii) 2N ∩ 4N. p ∈ S4 p ∈ S4 (4) Determine as intersecções, e interprete graficamente: (i) x,x2 : x ∈ R ∩ x,x4 : x ∈ R0; (ii) x, 2x 1 : x ∈ R ∩ x,x2 : x ∈ R; (iii) x,x3 : x ∈ R ∩ x,x : x ∈ R0; (iv) eit : t ∈ 0,2 ∩ z ∈ C : Rez Imz, onde Rez x, Imz y para z x iy ∈ C. Resolução (1) (i) x,y ∈ A C D x ∈ A ∧ y ∈ C D x ∈ A ∧ y ∈ C ∨ y ∈ D x ∈ A ∧ y ∈ C ∨ x ∈ A ∧ y ∈ D x,y ∈ A C ∨ x,y ∈ A D x,y ∈ A C A D; (ii) x,y ∈ A B C x ∈ A B ∧ y ∈ C x ∈ A ∨ x ∈ B ∧ y ∈ C x ∈ A ∧ y ∈ C ∨ x ∈ B ∧ y ∈ C x,y ∈ A C ∨ x,y ∈ B C x,y ∈ A C B C; (iii) x,y ∈ A C ∩ D x ∈ A ∧ y ∈ C ∧ y ∈ D x ∈ A ∧ y ∈ C ∧ x ∈ A ∧ y ∈ D x,y ∈ A ∩ C A ∩ D; (iv) x,y ∈ A ∩ B C ∩ D x ∈ A ∩ B ∧ y ∈ C ∩ D x ∈ A ∧ x ∈ B ∧ y ∈ C ∧ y ∈ D x ∈ A ∧ y ∈ C ∧ x ∈ B ∧ y ∈ D x,y ∈ A ∩ C B ∩ D. -9- 2 a) R S ~R ~S R ∨ S R ∧ S ~R ∨ S ~R ∧ ~S ~R ∧ S ~R ∨ ~S V V F F V V F F F F V F F V V F F F V V F V V F V F F F V V F F V V F F V V V V Como os valores lógicos das colunas 7ª e 8ª (resp. 9ª e 10ª) coincidem, concluem-se as leis de De Morgan. b) (i) P A B A ∧ B P ∧ A P ∧ B P ∧ A ∧ B P ∧ A ∧ P ∧ B V V V V V V V V V V F F V F F F V F V F F V F F V F F F F F F F F V V V F F F F F V F F F F F F F F V F F F F F F F F F F F F F Coinicidindo as duas últimas colunas, conclui-se a equivalência (ii) P A B A ∨ B P ∧ A ∨ B P ∧ A P ∧ B P ∧ A ∨ P ∧ B V V V V V V V V V V F V V V F V V F V V V F V V V F F F F F F F F V V V F F F F F V F V F F F F F F V F F F F F F F F F F F F F Como a 5ª coluna coincide com a última, conclui-se a equivalência. c) P A B A ∨ B P ∨ A P ∨ B P ∨ A ∨ B P ∨ A ∨ P ∨ B V V V V V V V V V V F V V V V V V F V V V V V V V F F F V V V V F V V V V V V V F V F V V F V V F F V V F V V V F F F F F F F F Uma vez que as duas últimas colunas coincidem, concluimos a equivalência P ∨ A ∨ B P ∨ A ∨ P ∨ B. -10- A equivalência restante é P ∨ A ∧ B P ∨ A ∧ P ∨ B: P A B A ∧ B P ∨ A ∧ B P ∨ A P ∨ B P ∨ A ∧ P ∨ B V V V V V V V V V V F F V V V V V F V F V V V V V F F F V V V V F V V V V V V V F V F F F V F F F F V F F F V F F F F F F F F F Como a 4ª e a última coluna coincidem, conclui-se a equivalência. d) (i) Fazendo A ≡ ~R e B ≡ ~S, concluimos de 1 a) e b) (i) que P ∧ ~R ∨ S P ∧ ~R ∧ ~S P ∧ A ∧ B P ∧ A ∧ P ∧ B P ∧ ~R ∧ P ∧ ~S, desde que provemos que se P1 P2 então P ∧ P1 P ∧ P2. Determinando então as tabelas de verdade: P P1 P2 P ∧ P1 P ∧ P2 V V V V V V V F V F V F V F V V F F F F F V V F F F V F F F F F V F F F F F F F Verifica-se que quando P1, P2 têm o mesmo valor lógico, nas 1ª, 4ª, 5ª e última linhas,também P ∧ P1, P ∧ P2 assumem o mesmo valor lógico. Ou seja: se P1 P2, então também P ∧ P1 P ∧ P2. (ii) Utilizando o resultado provado em (2) b) (i) P1 P2 P ∧ P1 P ∧ P2, (uma vez sabido que uma implicação P Q é verdadeira, podemos utilizar este resultado, e designá-lo escrevendo P Q directamente), obtemos de (1) a), b) (ii): P ∧ ~R ∧ S P ∧ ~R ∨ ~S P ∧ A ∨ B P ∧ A ∨ P ∧ B P ∧ ~R ∨ P ∧ ~S, como queríamos. (3) (i) Para cada p 1,2,3,4, tem-se: 4N0 p é o conjunto dos números naturais, cujo resto da divisão por p 1,2,3 é p, e zero para p 4. Uma vez que cada número natural verifica pelo menos um destes casos, obtem-se (i) 4N0 p N. p ∈ S4 Como nenhum número natural verifica dois destes casos simultãneamente, tem-se também (ii) 4N0 p . p ∈ S4 -11- (iii) Sendo todo o múltiplo de 4 um múltiplo de 2, tem-se 2N ∩ 4N 4N. (4) (i) O par ordenado x,y pertence à intersecção dos dois conjuntos sse a ordenada y é da forma y x2 x4, onde x ∈ R, x 0. A única raiz real positiva de x2 x4 sendo x 1, concluimos que a intersecção é o conjunto 1,1. (ii) Para x ∈ R, tem-se 2x 1 x2 x2 − 2x − 1 0 x 2 22 ; deste modo a intersecção procurada é 2 − 22 , 5 − 2 , 2 22 , 5 2 . (iii) 0,0, 1,1. (iv) eit cos t i sin t verifica cos t sin t 0 ≤ t 2 sse t 4 ∨ t 54 , portanto a intersecção procurada é 22 i 22 ,− 22 − i 22 . I.1.17 Axiomas da selecção e da extensão e inclusão de conjuntos. I.1.18 Axioma da selecção A relação Rx na variável x define um conjunto A se existe um conjunto E tal que Rx x ∈ E. Põe-se então A x : Rx. I.1.19 Inclusão de conjuntos Se X,Y são conjuntos, pomos X ⊂ Y sse a implicação x ∈ X x ∈ Y é verdadeira. Diz-se então que X é um subconjunto de Y. Em particular, tem-se sempre X ⊂ X. I.1.20 Axioma da extensão Sendo Rx, Sx relações numa variável satisfazendo o axioma da selecção, A x : Rx, B x : Sx, tem-se A B sse Rx Sx. I.1.21 Observações (1) Destes dois axiomas, o axioma da extensão parece ”óbvio” mas é aceitando-os em Teoria dos conjuntos, que podemos utilizar os conceitos intuitivos habituais, lidando com conjuntos e relações. Em particular, resulta deste último axioma e da definição de inclusão de conjuntos, que dados conjuntos A,B, tem-se A B A ⊂ B ∧ B ⊂ A. (as tabelas de verdade mostram imediatamente que, dadas proposições P,Q, tem-se P Q P Q ∧ Q P). -12- (2) Notando que o conjunto vazio pode ser definido por qualquer relação impossível, por exemplo x : Sx com Sx ≡ x ≠ x, ou, sendo Rx uma relação num conjunto, x : Rx ∧ ~Rx, ( duas relações impossíveis são equivalentes, pois assumem o valor lógico F para qualquer substituição da variável por uma constante), reconhece-se, pondo, para cada conjunto X, X x : x ∈ X que X \ X . Também X \ x : x ∈ X ∧ ~x ≠ x x : x ∈ X ∧ x x x : x ∈ X X. (3) Uma vez que Rx ∨ Rx Rx, Rx ∧ Rx Rx para qualquer relação Rx, tem-se X X X, X ∩ X X para cada conjunto X. (4) Das equivalências Rx ∨ Sx Sx ∨ Rx, Rx ∧ Sx Sx ∧ Rx (as tabelas de verdade mostram imediatamente que dadas proposições R,S tem-se R ∨ S S ∨ R e R ∧ S S ∧ R, (ver I.1.6), concluimos que X Y x : x ∈ X ∨ x ∈ Y x : x ∈ Y ∨ x ∈ X Y X e X ∩ Y Y ∩ X para quaisquer conjuntos X,Y. (5) Se P Q, então P ∨ Q Q é uma tautologia. Para o verificar, utilizando uma tabela de verdade, basta verificar se, em cada linha tal que P Q V, as colunas de P ∨ Q, Q assumem o mesmo valor lógico; o que é o mesmo que, supondo a hipótese P Q, constatar que P ∨ Q, Q são equivalentes: P Q P Q P ∨ Q V V V V V F F V F V V V F F V F São os casos da 1ª e 3ª,4ª linhas. Podemos concluir que se Rx,Sx são relações na variável x, tais que Rx Sx então Rx ∨ Sx Sx e, pondo para cada conjunto X, X x : x ∈ X, que se X ⊂ Y então X Y x : x ∈ X ∨ x ∈ Y x : x ∈ Y Y. Analogamente, a tabela de verdade mostra que se R S, então R ∧ S R e portanto se X ⊂ Y, tem-se X ∩ Y X. I.1.22 Exemplo Se X,Y são subconjuntos de um mesmo conjunto universal U, tem-se: x ∈ X Yc x ∈ U ∧ ~x ∈ X Y x ∈ U ∧ ~x ∈ X ∨ x ∈ Y x ∈ U ∧ ~x ∈ X ∧ x ∈ U ∧ ~x ∈ Y x ∈ Xc ∧ x ∈ Yc x ∈ Xc ∩ Yc, donde X Yc Xc ∩ Yc. (Utilizando o Ex. 1.1.16 (1) d) (i).). I.1.23 Exercícios (1) Prove que se X,Y ⊂ U então X ∩ Yc Xc Yc. (2) No que segue, supomos todos os conjuntos sendo subconjuntos de um mesmo conjunto U. Prove que: (i) A ⊂ A B e B ⊂ A B; (ii) A ∩ B ⊂ A e A ∩ B ⊂ B; (iii) A ⊂ B Bc ⊂ Ac; (iv) A ⊂ B A ∩ Bc ; -13- (3) Se X é um conjunto, diz-se que A1, . . . ,Ap é uma partição de X sse cada Ai ⊂ X , Ai ∩ Aj sempre que i ≠ j 1 ≤ i, j ≤ p e Ai X. i ∈ Sp Prove que se p é um número natural, então pN0 m : 1 ≤ m ≤ p é uma partição de N. (4) Mostre que para quaisquer conjuntos A,B,C tem-se (i) C \ A B C \ A ∩ C \ B; (ii) C \ A ∩ B C \ A C \ B. (5) Prove que A ⊂ A ′ e B ⊂ B ′ sse A B ⊂ A ′ B ′. Resolução (1) x ∈ X ∩ Yc x ∈ U ∧ ~x ∈ X ∩ Y x ∈ U ∧ ~x ∈ X ∧ x ∈ Y x ∈ U ∧ ~x ∈ X ∨ x ∈ U ∧ ~x ∈ Y x ∈ Xc Yc, o que prova a igualdade. (Utilizámos o anterior Ex. 1.1.16 (1) d) (ii)). (2) (i) Uma vez que a tabela de verdade de mostra que P P ∨ Q (verifique que é uma tautologia), encontra-se: x ∈ A x ∈ A ∨ x ∈ B; isto prova, pela definição de A B, que A ⊂ A B. Uma vez que P ∨ Q Q ∨ P é uma tautologia, obtem-se A B B A, e a inclusão B ⊂ A B conclui-se da demonstração anterior. (ii) Tem-se P ∧ Q P e P ∧ Q Q (verifique estas tautologias; note que o símbolo " " separa proposições formadas por outras utilizando os símbolos "∨" ,"∧" ). Então x ∈ A ∩ B x ∈ A ∧ x ∈ B x ∈ A, donde A ∩ B ⊂ A e analogamente A ∩ B ⊂ B. (iii) Suponhamos A ⊂ B; então x ∈ A x ∈ B, e se x ∉ B (i.e., se x ∈ Bc), não pode portanto ser x ∈ A, donde x ∉ A; assim x ∉ B x ∉ A, i.e. Bc ⊂ Ac. Como ~ ~P P, tem-se Acc A, Bcc B, e da inclusão provada conclui-se Bc ⊂ Ac A ⊂ B, provando a equivalência. (iv) Suponhamos A ⊂ B i.e., x ∈ A x ∈ B. Então se x ∈ A não pode verificar-se x ∉ B; assim nenhum x verifica x ∈ A ∧ x ∈ Bc donde A ∩ Bc . Reciprocamente, se A ∩ Bc , e se x ∈ A, não pode ser x ∈ Bc, x ∉ B; conclui-se que se x ∈ A então x ∈ B, i.e., A ⊂ B. (3) O resto da divisão por p de um número natural n é zero (caso em que n ∈ pN0 p), ou um número m, 1 ≤ m p; desta forma, N pN0 m m ∈ Sp porque pN0 m 1 ≤ m ≤ p é exactamente o conjunto dos números naturais, cujo resto da divisão por p é m. Se 1 ≤ m,m′ ≤ p e m ≠ m′ então pN0 m ∩ pN0 m′ ; assim pN0 m : 1 ≤ m ≤ p é uma partição de N. (4) Notar que substituindo o conjunto universal U, por qualquer conjunto C, nos anteriores Exemplo, e Ex (1), o essencial da demonstração se aplica, (X A e Y B) obtendo-se as igualdades (i), (ii). (Isto mostra que o caso A,B ⊂ U anteriormente considerado, é um caso particular). (5) A B ⊂ A ′ B ′ x,y ∈ A B x,y ∈ A ′ B ′ x ∈ A x ∈ A ′ e y ∈ B y ∈ B ′ sse A ⊂ A ′ e B ⊂ B ′. -14- I.1.24 Exercícios (1) Mostre que se X,Y são conjuntos, (i) X ⊂ X Y; (ii) X ∩ Y ⊂ X. (Sug: I.1.11, (2) (i), (ii). (2) Utilizando o axioma da extensão e a técnica em I.1.20, (2)...(5), prove que: a) (i) X ∩ Y ∩ Z X ∩ Y Z; (ii) X Y Z X Y Z. (Sug: I.15 b), c)); b) (i) X ∩ Y Z X ∩ Y X ∩ Z; (ii) X Y ∩ Z X Y ∩ X Z. (Sug: I.1.15 b), c)). c) (i) A relação "X ⊂ Z e Y ⊂ Z" é equivalente a X Y ⊂ Z. (Sug: I.1.11, (2) ((iv)). (ii) A relação "Z ⊂ X e Z ⊂ Y" é equivalente a Z ⊂ X ∩ Y. (Sug: I.1.11, (2) (vi)). Resolução (1) (i) Uma vez que x ∈ X x ∈ X ∨ x ∈ Y, concluimos X x : x ∈ X ⊂ x : x ∈ X ∨ x∈ Y X Y. (ii) Tendo-se x ∈ X ∧ x ∈ Y x ∈ X conclui-se X ∩ Y x : x ∈ X ∧ x ∈ Y ⊂ x : x ∈ X X. (2) a) (i) X ∩ Y ∩ Z x : x ∈ X ∧ x ∈ Y ∧ x ∈ Z x : x ∈ X ∧ x ∈ Y ∧ x ∈ Z X ∩ Y ∩ Z; (ii) X Y Z x : x ∈ X ∨ X ∈ Y ∨ x ∈ Z x : x ∈ X ∨ x ∈ Y ∨ x ∈ Z X Y Z. b) (i) X ∩ Y Z x : x ∈ X ∧ x ∈ Y ∨ x ∈ Z x : x ∈ X ∧ x ∈ Y ∨ x ∈ X ∧ x ∈ Z x : x ∈ X ∧ x ∈ Y x : x ∈ X ∧ x ∈ Z X ∩ Y X ∩ Z; (ii) X Y ∩ Z x : x ∈ X ∨ x ∈ Y ∧ x ∈ Z x : x ∈ X ∨ x ∈ Y ∧ x ∈ X ∨ x ∈ Z X Y ∩ X Z. c) (i) x ∈ X x ∈ Z ∧ x ∈ Y x ∈ Z x ∈ X ∨ x ∈ Y x ∈ Z, donde se conclui que X ⊂ Z ∧ Y ⊂ Z X Y ⊂ Z; (ii) x ∈ Z x ∈ X ∧ x ∈ Z x ∈ Y x ∈ Z x ∈ X ∧ x ∈ Y e conclui-se Z ⊂ X ∧ Z ⊂ Y Z ⊂ X ∩ Y. -15- I.1.25 Exercícios (1) Prove que para quaisquer conjuntos A,B,C,D se tem: (i) A A \ B A ∩ B e A \ B ∩ A ∩ B ; (ii) A \ B A \ A ∩ B A B \ B; (iii) A ∩ B \ C A ∩ B \ A ∩ C; (iv) A \ B \ C A \ B C; (v) A \ B \ C A \ B A ∩ C; (vi) A \ B ∩ C \ D A ∩ C \ B D. (2) Prove que: a) A \ B A se e só se A ∩ B ; b) A \ B B A B \ B se e só se B . c) A ⊂ B A ∩ B A A B B. (Sug: Verifique, utilizando uma tabela de verdade, que se P,Q são proposições, Q uma tautologia, então P P ∧ Q (faça sempre V na coluna de Q) e portanto, se R é uma relação impossível, P ∧ ~R P; e que se Q é uma relação impossível então P ∨ Q P. Pode utilizar (1) (ii) para (2) a), b). Resoluções (1) (i) Uma vez que dadas proposições P,Q se tem P P ∧ ~Q ∨ Q, conclui-se a propriedade correspondente para relações numa variável, obtendo-se x ∈ A x ∈ A ∧ x ∉ B ∨ x ∈ B x ∈ A ∧ x ∉ B ∨ x ∈ A ∧ x ∈ B, donde se conclui A A \ B A ∩ B pelo princípio de extensão. A relação em x, x ∈ A ∧ x ∉ B ∧ x ∈ A ∧ x ∈ B é equivalente à relação impossível x ∉ B ∧ x ∈ B que define assim o conjunto . Portanto A \ B ∩ A ∩ B , pelo axioma da extensão. (ii) Dadas proposições P,Q tem-se P ∧ ~Q P ∧ P ∧ ~P ∨ P ∧ ~Q P ∧ P ∧ ~P ∨ ~Q P ∧ P ∧ ~P ∨ ~Q P ∧ ~P ∨ ~Q P ∧ ~P ∧ Q donde se conclui A \ B A \ A ∩ B. Também P ∧ ~Q P ∨ Q ∧ ~Q ∧ ~Q P ∨ Q ∧ P ∨ ~Q ∧ ~Q P ∨ Q ∧ P ∨ ~Q ∧ ~Q P ∨ Q ∧ ~Q (esta última equivalência porque os valores lógicos de P ∨ ~Q ∧ ~Q e de ~Q são sempre o mesmo, já que se S R então R ∧ S S, como mostram as 1ª, 3ª e 4ª linhas da tabela de verdade), donde podemos concluir A \ B A B \ B. (iii) x ∈ A ∩ B \ C x ∈ A ∧ x ∈ B ∧ x ∉ C x ∈ A ∧ x ∈ B ∧ x ∉ C x ∈ A ∧ x ∈ B ∧ x ∉ A ∨ x ∉ C x ∈ A ∧ x ∈ B ∧ ~x ∈ A ∨ ~x ∈ C x ∈ A ∧ x ∈ B ∧ ~x ∈ A ∧ x ∈ C x ∈ A ∧ x ∈ B ∧ ~x ∈ A ∩ C x ∈ A ∩ B \ A ∩ C, onde a terceira equivalência se justifica porque se P,Q,R são proposições tais que P Q e Q R, então as proposições P ∧ Q e P ∧ R são equivalentes, como mostra a tabela de verdade nas 1ª, 5ª, 7ª e 8ª linhas (fazer P ≡ x ∈ A ∧ x ∈ B, Q ≡ x ∉ C, R ≡ x ∉ A ∨ x ∉ C): P Q R P Q Q R P ∧ Q P ∧ R V V V V V V V V V F V F V F V F V F V F V V F F F V F F F V V V V F F F V F V F F F F F V V V F F F F F V V F F e assim A ∩ B \ C A ∩ B \ A ∩ C. -16- (iv) x ∈ A \ B \ C x ∈ A ∧ ~x ∈ B ∧ ~x ∈ C x ∈ A ∧ ~x ∈ B ∧ ~x ∈ C x ∈ A ∧ ~x ∈ B ∨ x ∈ C x ∈ A \ B C (v) x ∈ A \ B \ C x ∈ A ∧ ~x ∈ B ∧ ~x ∈ C x ∈ A ∧ ~x ∈ B ∨ x ∈ C x ∈ A ∧ ~x ∈ B ∨ x ∈ A ∧ x ∈ C x ∈ A \ B A ∩ C. (vi) x ∈ A \ B ∩ C \ D x ∈ A ∧ ~x ∈ B ∧ x ∈ C ∧ ~x ∈ D x ∈ A ∧ x ∈ C ∧ ~x ∈ B ∧ ~x ∈ D x ∈ A ∩ C ∧ ~x ∈ B ∨ x ∈ D x ∈ A ∩ C \ B D. (2) a) Por (1), (ii) tem-se A \ B A \ A ∩ B. Logo se A ∩ B , A \ A ∩ B A \ A (se Sx é uma relação impossível, então ~Sx é uma relação sempre verdadeira, e x ∈ A ∧ ~Sx x ∈ A). Portanto se A ∩ B tem-se A \ B A. Reciprocamente, se A ⊂ A \ A ∩ B então tem-se x ∈ A x ∈ A ∧ ~x ∈ A ∩ B V; a tabela de verdade mostra que, dadas proposições P,Q, se Q pode tomar o valor lógico F, então P P ∧ Q não toma sempre o valor lógico V. Portanto tem de se verificar ~c ∈ A ∩ B V para cada substituição de x pela consante c, i.e, c ∈ A ∩ B F e x ∈ A ∩ B deve ser uma relação impossível, i.e., A ∩ B . b) Utilizando (1), (ii) A B \ B A \ B. A igualdade referida é portanto a igualdade de conjuntos A \ B B A \ B, que é verdadeira se B , pois então B x : Sx, onde Sx é uma relação impossível, donde se verifica a equivalência x ∈ A \ B ∨ Sx x ∈ A \ B (se S F então P ∨ S P para qualquer proposição P). Reciprocamente, a inclusão A \ B B ⊂ A \ B só se verifica se B ⊂ A \ B, porque dadas proposições P,Q, P ∨ Q P só assume o valor lógico V quando Q P toma o valor lógico V. Então tem de ser x ∈ B x ∈ A ∧ ~x ∈ B, donde x ∈ B ~x ∈ B, e por isso tem de ser sempre c ∈ B F para cada substituição de x pela constante c, i.e., x ∈ B é impossível e B . c) Dadas proposições P,Q tem-se: P Q P ∧ Q P é uma tautologia, como se verifica pela tabela de verdade; assim A ⊂ B A ∩ B A. Também a proposição P Q P ∨ Q Q é uma tautologia, donde se conclui que A ⊂ B A B B. I.1.26 Quantificação Vimos que dada uma relação numa variável Rx x ∈ E, a substituição de x por uma constante c em E, transforma a relação Rx na proposição Rc. Sendo A ⊂ E, podemos considerar as proposições ”para cada x ∈ A, Rx”, significando que todos os objectos x ∈ A, satisfazem a relação Rx, e ”existe pelo menos um x ∈ A, Rx”, significando que existe pelo menos um objecto x em A que verifica Rx. A proposição ”para cada x ∈ A, Rx”, ou doutro modo, ”para qualquer x ∈ A, Rx”, ou ainda ”para todo o x ∈ A, Rx” escreve-se ∀x ∈ A, Rx, ou também ∀x ∈ A Rx. Convém, para clareza, muitas vezes, colocar Rx entre parêntesis, pondo ∀x ∈ ARx, e pode escrever-se também Rx ∀x ∈ A, utilizando ou não os parêntesis. A proposição ”existe pelo menos um x ∈ A, Rx” escreve-se ∃x ∈ A, Rx, com a mesma ressalva para o uso de parêntesis. As proposições assim obtidas, a partir de uma relação numa variável, dizem-se proposições quantificadas, e ”∀”, ”∃” são respectivamente os quantificadores universal, e existencial. Um outro quantificador, é o que afirma a existência de um único elemento num dado conjunto, verificando a relação. Escreve-se então ∃1 x, Rx se o conjunto em que x varia está subentendido, ou ∃1 x ∈ A, Rx (∃1 x ∈ ARx). -17- I.1.27 Exemplos (1) Dada a relação Rx ≡ x2 2 x ∈ R, podem considerar-se as proposições quantificadas ∀x 0x2 2 F, ∃x ∈ Rx2 2 V; ∀x ∈ −, 2 2 ,x2 2, verdadeira, ∀x ∈ N2x2 2, verdadeira; assim como ∃1x ∈ 1,2x2 2 V, ∃1x ∈ Qx2 2 F. (2) Como vemos no exemplo acima, no primeiro e no terceiro casos, o mesmo quantificador pode formar uma proposição falsa a partir da mesma relação numa variável, quantificando a variável num conjunto, mas verdadeira quantificando noutro conjunto. I.1.28 Exercício Dadas as seguintes relações numa variável, indique quais das proposições quantificadas são verdadeiras ou falsas: (1) Rx ≡ 3 x ∈ Q x ∈ R (i) ∀x, Rx; (ii) ∃x ∈ Z 3 x ∈ Q; (iii) ∀x ∈ −1,0,1 Rx. (2) Rx ≡∣ x ∣ a x a x ∈ R (i) ∀x 0∣ x ∣ a x a (ii) ∃1x, ∣ x ∣ a x a (iii) ∀x, Rx (3) R ≡ 2 0 (i) ∀ 0,12 ; (ii) ∀ ∈ 0,1R; (iii) ∃ ∈ −1,1R. Resolução (1) (i) ∀x ∈ R 3 x ∈ Q F, pois por exemplo 2 ∈ R, 3 2 ∉ Q. (ii) V (considere-se x 8) (iii) V (2) (i) V; (ii) F; (iii) F (3) (i) V; (ii) F; (iii) V I.1.29 Exercício Sendo 0 1 fixo, indique quais das proposições seguintes são verdadeiras, ou falsas: a) ∃ n ∈ N0 1n ; b) ∀ n ∈ N 1n ; c) nn1 ∀n ∈ N. Resolução a) V; b) F; c) F. -18- I.1.30 Observações (1) Quando se consideram proposições compostas por diversas proposições quantificadas, a indicação, que deve constar em cada uma destas proposições quantificadas, da variável que se quantifica e do respectivo conjunto, permite ler a proposição obtida considerando de cada vez em cada uma, os símbolos relativos a variáveis que não as quantificadas em cada proposição, como constantes. Em Análise real, segundo a definição do limite u de uma sucessão un, recorde-se que u limun s e só se é verdadeira a proposição quantificada ∀ 0∃ p ∈ Nn ≥ p ∣ un −u ∣ . (2) Em expressões envolvendo mais que uma proposição quantificada, a ordem pela qual são feitas as quantificações respeitantes é importante. Por exemplo considerando a proposição quantificada acima, a proposição ∃ p ∈ N∀ 0n ≥ p ∣ un − u ∣ significa que un é constante e igual a u a partir de uma ordem p; esta proposição é falsa se considerarmos u ≠ 0, un nun2 , mas lim nun2 u segundo a definição. I.1.31 Exercícios (1) Indique quais das seguintes proposições são verdadeiras ou falsas: (i) ∀ a ∈ 0,1∃ 0Ia, ⊂ 0,1, onde Ia, a − ,a ; (ii) ∀ a ∈ 0,1∃ 0Ia, ⊂ 0,1; (iii) ∃ a ∈ 0,2 ∩ 0,1∀ 0Ia, ⊂ 0,2 ∩ 0,1; (iv) ∃ a ∈ 0,1∀ 0Ia, ⊂ 0,1; (v) ∃ 0∀a ∈ 0,1Ia, ⊂ 0,1; (vi) ∀x ∈ R∀ 0∃ n ∈ N 1n ∣ x ∣ ; (vii) ∀x ∈ R∃ n ∈ N∀ 0 1n ∣ x ∣ ; (viii) ∀ n ∈ N nn1 1 n1n ; (ix) ∀ a ∈ Ra 1n ∀ n ∈ N a ≤ 0; (x) ∀x ∈ N∀ 0∃ y ∈ R∣ x − y ∣ ∀x ∈ N∀ 1∃ b ∈ R 1 ∣ xb ∣ (2) Indique, justificando, quais das seguintes proposições são ou não verdadeiras: a) ∃ a ∈ Z∀ m ∈ Za m 0; b) ∀ m ∈ Z∃ a ∈ Za m 0; c) ∃ ∈ Q∀ q ∈ Qq q q. Resolução (1) (i) F (a 1; (ii) V; (iii) F; (iv) F; (v) F ; (vi) V; (vii) F; (viii) V; (ix) V; (x) V (ambas as proposições são verdadeiras). -19- (2) a) F. (O elemento m que satisfaz a m 0, para cada a ∈ Z considerado, é único, m −a). b) V. c) V ( 1). I.1.32 Propriedade Seja Rx x ∈ X uma relação numa variável. Pelo significado da proposição ∀x,Rx, ”para todo o x, verifica-se Rx”, a sua negação é a proposição ”existe pelo menos um x que não verifica Rx”. Obtem-se assim a propriedade da negação do quantificador universal, ~∀x,Rx ∃x, ~Rx. A negação de ”existe pelo menos um x tal que Rx” é ”para todo o x, ~Rx”, i.e., ~∃x,Rx ∀x, ~Rx. Para a negação de uma implicação ∀x,Px Qx, atendendo a que Px Qx ~Px ∨ Qx, e portanto ~Px Qx ~~Px ∨ Qx ~~Px ∧ ~Qx Px ∧ ~Qx, obtem-se ~∀x,Px Qx ∃x,Px ∧ ~Qx. Analogamente, ~∃x,Px Qx ∀x,Px ∧ ~Qx. I.1.33 Exemplos (1) A negação de ∃x ∈ R,x2 −1 é ∀x ∈ R,x2 ≠ −1. (2) Se xn é uma sucessão real, a ∈ R, a negação de limxn a é ~∀ 0,∃p ∈ N, ∀n ∈ N,n ≥ p ∣ xn − a ∣ , portanto é a proposição ∃ 0,~∃p ∈ N, ∀n ∈ N,n ≥ p ∣ xn − a ∣ ∃ 0,∀p ∈ N,∃n ∈ N,n ≥ p ∧∣ xn − a ∣≥ . I.1.34 Exercícios (1) Negue as proposições quantificadas: (i) ∀m ∈ Z,m2 m; (ii) ∃q ∈ Q,q2 2; (iii) ∀x ∈ R,∀y ∈ R,x2 y2 x y. (2) Explicite em linguagem lógica que a sucessão real un não é um infinitamente grande positivo. (3) Sendo f uma função real da variável real, exprima logicamente que não se verifica limx→0 fx 1. Resoluções (1) (i) ∃m ∈ Z,m2 ≤ m; (ii) ∀q ∈ Q,q2 ≠ 2; (iii) ∃x ∈ R, ∃y ∈ R,x2 y2 ∧ x ≤ y. (2) A negação de ∀ 0,∃p ∈ N ∀n ∈,n ≥ p un 1 é ∃ 0,∀p ∈ N ∃n ∈ N,n ≥ p ∧ un ≤ 1 . (3) Trata-se de negar a proposição ∀ 0,∃ 0 ∀x ∈ R, ∣ x ∣ ∣ fx − 1 ∣ . Obtem-se ∃ 0,∀ 0 ∃x ∈ R,∣ x ∣ ∧∣ fx − 1 ∣≥ . -20- I.1.35 Definição Se C X : ∈ A é uma classe não vazia de conjuntos, indiciada num conjunto de índices A, dizemos que C é uma família de conjuntos. A reunião generalizada (resp. intersecção generalizada) da classe é o conjunto C X : ∈ A x : ∃ ∈ A,x ∈ X (resp.C X : ∈ A x : ∀ ∈ A,x ∈ X). Se todos os conjuntos X são subconjuntos de um mesmo conjunto X, A , põe-seX : ∈ A eX : ∈ A X. I.1.36 Observações (1) Admitimos o Axioma da reuniâo: Para qualquer classe de conjuntos C, existe sempre o conjutoC. (2) Pelas definições tem-seX : ∈ A ⊂ X ⊂ X : ∈ A para cada ∈ A. (2) Se X : ∈ A é tal que cada X verifica A ⊂ X ⊂ B então tem-se A ⊂ X : ∈ A eX : ∈ A ⊂ B I.1.37 Exercício Determine as intersecções e reuniões generalizadas: (i)−n, 1 : n ∈ N (ii)0,1 − 1n : n ∈ N; (iii)−q.q : q ∈ Q (iv)−q,q : q ∈ Q (v)− 1n , 1n : n ∈ N (vi)1 − 1n , 1 1n : n ∈ N. I.1.38 Resolução (i) x ∈ R : ∃n ∈ N,−n x ≤ 1 −, 1; (ii) x ∈ R : ∃n ∈ N, 0 ≤ x ≤ 1 − 1n 0,1; (iii) R; (iv) 0; (v) x ∈ R : ∀n ∈ N,− 1n x 1n 0; 1 − 1n x 1 1n ,∀n ∈ N x 1,1 − 1n , 1 1n : n ∈ N 1. I.1.39 Definição Se X,Y são conjuntos não vazios, diz-se que uma parte não vazia ⊂ X Y do conjunto produto cartesiano X Y, é uma relação de X para Y. Se x,y ∈ , nota-se também xy. Por exemplo, com X N, Y Q, n, 1n : n ∈ N é uma relação de N para Q. Tem-se 11, 2 12 , 23 123 , etc. Se A é um conjunto, representamos PA W : W ⊂ A o conjunto das partes de A. Sendo X ≠ ,Y ≠ , X Y é uma relação de X para Y tal que ∀x ∈ X,∀y ∈ Y,xy; PX PY é uma relação de PX para PY tal que ∀A ⊂ X∀B ⊂ Y, AB. I.1.40 Exercício Indique qual das seguintes afirmações é verdadeira: (i) x,yV sse x,y ∈ V é uma relação de V2 para PV; (ii) x,yV sse x,y ∈ V é uma relação de V V para V. Resolução (i) é verdadeira, pois cada par ordenado x,y ∈ V2 verifica x,yV sse x,y,V é um par ordenado tal que x,y ∈ V, onde V ∈ PV. (ii) é falsa. -21 I.2 RELAÇÕES BINÁRIAS E FUNÇÕES I.2.1 Definição Se X Y ≠ uma relação d e X para Y diz-se uma relação binária em X; assim uma relação binária em X é uma parte não vazia do produto cartesiano X2. Por exemplo x0y sse ∃ m ∈ Ny xm uma relação binária em R tal que 1,1 ∈ 0, 1,2 ∉ 0, 2,4, 2,8, 2,16 ∈ 0. Também a1b sse b 2a é a relação binária em N, 1 1,2, 2,4, 3,6, . . .. I.2.2 Definição (1) Se a relação f de X para Y verifica a propriedade de cada elemento de X estar na relação com exactamente um elemento de Y, i.e., se x,y ∈ f ∧ x,y ′ ∈ f y ′ y, dizemos que f é uma função de X em Y ou uma aplicação de X em Y; nota-se y fx sse x,y ∈ f. Em I.2.1, 0 não é função, 1 é uma função de N em N. O conjunto das funções de X em Y nota-se YX. (2) Se X é um conjunto não vazio, uma sucessão em X é uma função u : N → X, habitualmente designada pondo u un, un : n un. O conjunto das sucessões em X é portanto o conjunto XN. I.2.3 Se f é uma função de X em Y, nota-se f : X → Y, x fx y sempre que x,y ∈ f. Se X é um conjunto, ≠ A ⊂ X, e f ⊂ A Y é uma função, deve notar-se f : A ⊂ X → Y. O conjunto A x ∈ X : ∃ fx x ∈ X : ∃ y, x,y ∈ f é o domínio da função f, e representa-se por dom f. O conjunto y ∈ Y : ∃ x ∈ dom f, x,y ∈ f é chamado o conjunto imagem de f, codomínio ou contradomínio ou conjunto imagem de f, e representa-se por Imf ou fX.. I.2.4. Exemplo Para a função fx 1senx deve pôr-se f : R \ k : k ∈ Z ⊂ R → R. O domínio de 1senx é A R \ k : k ∈ Z e o codomínio é fA R \ −1,1. I.2.5 Definição Se f : X → Y é uma função, ≠ A ⊂ X, então x, fx : x ∈ A é uma função de A em Y, que se chama a função restrição de f a A. A função restrição de f a A representa-se por f ∣ A. -22- I.2.6 Definição A função f : X → Y diz-se injectiva se ∀x,x ′ ∈ Xfx fx ′ x x ′; sendo ≠ A ⊂ X, f é injectiva em A sse a função restrição de f a A é injectiva. Também se diz então que f é uma injecção de A em Y. f diz-se que é sobrejectiva, ou que é uma sobrejecção de X em Y, sse fX Y, i.e., sse todo o elemento de Y é imagem de um elemento de X. Para significar que f é uma função sobrejectiva de X em Y, diz-se também que f é uma função de X sobre Y. Se f : X → Y é injectiva, então fx,x : x ∈ X é uma função de fX em X, chamada a função inversa da função f, e que se represnta por f−1; dizemos então que f admite uma inversa e, se f é injectiva e sobrejectiva dizemos que f é invertível com inversa f−1. A função f−1 inversa de f : X → Y é a função f−1 : Y → X definida por f−1 y,x : fx y,x ∈ X,y ∈ Y fx,x : x ∈ X, f−1y x sse fx y. Se f é injectiva e sobrejectiva, diz-se que f é bijectiva, ou que é uma bijecção. I.2.7 Exemplos (1) Se ≠ A ⊂ X, a aplicação I : A → X, Ix x diz-se a aplicação de inclusão; I é injectiva. A aplicação IA : A → A, IAx x, que se chama a identidade de A, é uma bijecção. (2) Dado um produto cartesiano de conjuntosk1m Xk, cada aplicação prk : k1m Xk → Xk, prkx1, . . . ,xm xk k 1, . . . ,m diz-se a projecção de índice k. prk é sobrejectiva, não é injectiva em geral. I.2.8 Exercício Determine subconjuntos A,B de R \ 0,1 e de Q respectivamente, tais que a função restrição da função f : R \ 0,1 → Q, fx 1Ix2 , onde Ix ”maior inteiro m ≤ x” é a função característica de x, a A, (i) admita uma inversa; (ii) seja invertível de A em B. Resolução (i) A N; (ii) A N, B 1 n2 : n ∈ N. I.2.9 Exercício a) Esboce no plano cartesiano R2 as relações binárias (i) M x,y ∈ R2 : max∣ x ∣,∣ y ∣ ≤ 1; (ii) e x,y ∈ R2 : x2 y2 ≤ 1; (iii) S x,y ∈ R2 :∣ x ∣ ∣ y ∣≤ 1; (iv) M x,y ∈ R2 : max∣ x ∣,∣ y ∣ 1; (v) e x,y ∈ R2 : x2 y2 1; (vi) S x,y ∈ R2 :∣ x ∣ ∣ y ∣ 1. (vii) f x,x2 : x ∈ R. (Sug: para (i), (iv), considere as rectas y x 1). b) Indique, justificando, quais das relações binárias anteriores são, ou não, funções. c) Mostre que M −1,12. -23- Resoluções b) Apenas f em (vii) é uma função, pois em cada uma das outras alíneas, tem-se por exemplo 0,−1, 0,1 ∈ , designando por a respectiva relação binária. c) Tem-se ∣ a ∣≤ 1 a ∈ −1,1 a ∈ R, e assim x,y ∈ M max∣ x ∣,∣ y ∣ ≤ 1 x,y ∈ −1,12. I.2.10 Observação Considerando uma relação numa variável Rx x ∈ A, pode suceder que a cada x ∈ A tal que Rx V corresponda um único elemento bem determinado y. Pode então considerar-se a relação em duas variáveis Rx,y definida por Rx,y V sse y verifica Rx, e não é inteiramente óbvio que exista um conjunto não vazio B tal que Rx,y seja uma relação de A para B; se B existe, então R ⊂ A B, R é uma relação de A para B e é uma função f : A → B. Aceitamos o seguinte axioma, que assegura que existe B. Axioma da substituição Sejam A um conjunto e Rx,y uma relação em duas variáveis. Se para cada x ∈ A, existe um único y que verifica Rx,y, existe uma função f de domínio A tal que y fx é equivalente a x ∈ A ∧ Rx,y. I.2.11 Definição Dadas funções f : X → Y,g : Y → Z, diz-se função composta de g com f, ou composição de g com f, ou ainda função g após f, e representa-se por gof, a função gof : X → Z definida por gofx z sse fx y e gy z, ou seja, gof x, z ∈ X Z : ∃y ∈ Y, x,y ∈ f ∧ y, z ∈ g. Nota-se gofx gfx x ∈ X. Se h : Z → W é outra função, define-se analogamente hogof : X → W que se representa por hogof, hogofx hgfx x ∈ X e o mesmo para a composição de funções em qualquer número finito. I.2.12. Observação Se f : X → Y,g : Imf → Z são funções injectivas, então a função gof : X → Img é bijectiva, e tem-se gof−1 f−1og−1. Com efeito, para cada z ∈ Img, f−1g−1z f−1y x sse gy z, fx y sse gofx z, e dom f−1og−1 dom gof−1. I.2.13 Exemplo Para cada função f : X → Y tem-se foIXx fIXx fx x ∈ X e assim foIX f. Também IYfx fx x ∈ X donde IYof f. I.2.14 Exercícios (1) Prove que: a) Se f : X → Y é bijectiva, então f−1of IX e fof−1 IY. b) Se f : X → Y,g : Y → X são tais que gof IX e fog IY, então existe f−1 g. (2) Se dadas f : X → Y,g : Y → X se verifica gof IX então g é sobrejectiva e f é injectiva. -24- Resoluções (1) a) Para cada x ∈ X é f−1fx x0 se fx0 fx por definição de f−1 e então x0 x ( f é injectiva) e f−1fx x IXx. Coincidindo f−1of com IX em cada ponto x ∈ X, e tendo as duas funções o mesmo domínio, concluimos que f−1of IX. Qualquer que seja y ∈ Y, tem-se fof−1y fx sse f−1y x sse fx y. Assim fof−1y y IYy para cada y ∈ Y, e tendo ambas fof−1, IY domínio Y e coincidindo em cada ponto, conclui-se que fof−1 IY. b) Mostremos que f é injectiva e sobrejectiva. Se fa fb,a,b ∈ X então pela hipótese gfa gofa IX a a e gfb gofb IX b b donde a b e f é injectiva. Para cada y ∈ Y, tem-se também pela hipótese fgy fogy y, donde o elemento x gy ∈ X tem imagem fx y por f e f é sobrejectiva. Tem-se: para cada y ∈ Y, gy x fx fogy IYy y e fx y gy gofx x. Portanto gy x sse fx y, e como domg Y concluimos que g f−1. (2) Para cada x ∈ X, tem-se gfx gofx IXx x; pondo fx y, existe portanto y ∈ Y tal que gy x, o que mostra que g é sobrejectiva. f é ínjectiva, pois para cada a,b ∈ X, fa fb a gfa gfb b. I.2.15 Definição Se u un é uma sucessão em X e : N → N, k k nk é uma função tal que k k ′ nk nk′ (estritamente crescente), diz-se que a sucessão vk obtida pela composição vk uo : N → N é uma subsucessão de un. Designa-se habitualmente vk unk. I.2.16 Exemplos (1) 1/2k − 1 é a subsucessão da sucessão 1/n que corresponde à função estritamente crescente k 2k − 1. (Subsucessão 1/3,1/5,1/7. . . dos termos de ordem ímpar) (2) As sucessões 1/3,1/3,1/5,1/7, . . . e 1/3,1/7,1/5,1/9,1/13,1/11, . . . não são subsucessões de 1/n. I.2.17 Observação Pela definição em I.1.15, se X1, . . . ,Xm m ∈ N são conjuntos não vazios, e representarmos uma função f : Sm 1, . . . ,m → X Xk : k 1, . . . ,m pondo f f1, . . . , fm, entãok1m Xk é o conjunto destas m −sequências, e pode identificar-se com o conjunto das funções f ∈ X1,...,mtais que fk ∈ Xk para cada k 1, . . . ,m ( fk corresponde à coordenada−k da m −sequência). -25- I.3 AXIOMA DE ZERMELO E PRODUTO CARTESIANO INFINITO OPERAÇÃO DE HILBERT I.3.1 Definição Sendo X : ∈ A uma classe não vazia de conjuntos não vazios, o produto cartesiano da classe é, designando X ∈A X, o conjunto das funções f ∈ XA tais que f ∈ X para cada ∈ A. Representamos este conjunto por ∈A X; cada f ∈ pode representar-se por f x, onde x f ∈ A. Se A N, notamos k1 Xk, f xk k 1,2, . . . para cada f ∈ k1 Xk. Os x ∈ A são as coordenadas de x. Para cada ∈ A, a função p : → X, px x que faz corresponder a x a coordenada− de x diz-se a projecção de índice . X é, para cada índice ∈ A, o conjunto das coordenadas−. I.3.2 Observação Se em I.3.1 o conjunto de índices A é uma classe não vazia de conjuntos não vaziosM e, para cada M ∈ M, o conjunto das coordenadas-M éM, então M∈MM é, pela definição, o conjunto das funções x : M →M : M ∈ M tais que xM xM ∈ M para cada conjuntoM ∈ M. Estas funções são chamadas as funções de escolha paraM, e não é inteiramente óbvio que exista, pelo menos uma tal função de escolha. Aceitamos o seguinte axioma da Teoria de Conjuntos, que é equivalente a ser M∈MM ≠ . I.3.3 Axioma da Escolha de Zermelo. Se C é uma classe não vazia constituída por conjuntosnão vazios, existe uma função : C → C : C ∈ C tal que C ∈ C para cada conjunto C ∈ C. A função chama-se o selector de Zermelo; escolhe em cada conjunto C da classe C um elemento C do qual se sabe apenas que C ∈ C. I.3.4 Símbolo de escolha de Hilbert. Dada uma relação numa variável Rx tal que ∃x,Rx é verdadeira, pode fixar-se uma vez por todas um dos objectos que verificam Rx, e se designa por xRx. A operação de Hibert, que consiste em obter xRx para cada relação Rx tal que ∃x,Rx é verdadeira, dá um processo de obter uma constante a partir de uma relação não impossível numa variável. Aceitando-a, como fazemos, fica implícito que aceitamos também o Axioma de Zermelo, como se prova em Lógica Matemática. -26- I.4 FUNÇÕES ASSOCIADAS DE CONJUNTOS DE UMA FUNÇÃO I.4.1 Definição Se f : X → Y é uma função, podemos considerar as funções f : PX → PY, definida por fA fx : x ∈ A A ⊂ X, e f−B x ∈ X : fx ∈ B, f− : PY → PX, associadas a f. f diz-se a função associada de conjuntos directa de f, e a função f− chama-se a função associada de conjuntos inversa de f. Põe-se f , f− . I.4.2 Observação A função associada de conjuntos inversa de f existe sempre, ainda que f não admita uma inversa. Sempre que não haja risco de confusão, representamos fA fA, f f e f−B f−1B, f− f−1. I.4.3 Exemplos (1) A função f : −1,1 ⊂ R → R, fx 11−∣x∣ não é injectiva, é sobrejectiva. Tem-se f0 1; f−1,1,2 12 , 13 ; f 13 , 12 32 , 2. (2) Para a função característica Ix tem-se I−1,1 0,1; IR Z. Esta função I : R → R não é injectiva nem sobrejectiva. (3) Sendo f : Q → R, fs s2 verifica-se fQ ⊂ Q, fZ ⊂ N0. Verifica-se também que fZ \ 0 ⊂ N, f−1,1 0,1. (4) Sendo Xi : i ∈ I uma classe de conjuntos, subconjuntos de um conjunto universo X, Yj : j ∈ J uma classe de subconjuntos de Y, e f : X → Y uma função, tem-se: y ∈ f∩Xi : i ∈ I ∃x ∈ ∩Xi : i ∈ I,y fx ∀i ∈ I∃x ∈ Xiy fx ∀i ∈ Iy ∈ fXi y ∈ ∩fXi : i ∈ I. Portanto f∩Xi : i ∈ I ⊂ ∩fXi : i ∈ I. Notar que a inclusão recíproca não é verdadeira,.i.e. pode suceder ∩ fXi : i ∈ I ⊈ f∩Xi : i ∈ I, como mostra o contra-exemplo f0 0, fx sin 1x x ≠ 0: tem-se f−1,0 ∩ 0,1 0, f−1,0 ∩ f0,1 −1,1. No entanto, para a função associada de conjuntos inversa, tem-se x ∈ f−1∩Yj : j ∈ J ∃y ∈ ∩Yj : j ∈ J, fx y ∃y ∈ Y∀j ∈ Jy ∈ Yj ∧ fx y ∀j ∈ J,x ∈ f−1Yj x ∈ ∩f−1Yj : j ∈ J, e assim f−1∩Yj : j ∈ J ∩f−1Yj : j ∈ J. I.4.4 Exercícios (1) Com f : R → R, fx x4, determine: a) (i) f1; (ii) f−1,1; (iii) f−1,1; (iv) fR; (v) fR \ 0, 12 (vi) f0,. b) (i) f−10; (ii) f−1−1; (iii) f−1Q 2 ; (iv) f−10,; (v) f−11, (vi) f−1−2,. (2) Mostre que nas hipóteses de I.4.3 (4), tem-se: a) fXi : i ∈ I fXi : i ∈ I; b) f−1Yj : j ∈ J f−1Yj : j ∈ J. (3) Mostre que se f : X → Y é uma função, então f é injectiva de e só se ∀A,B ⊂ X, fA ∩ B fA ∩ fB. (4) Prove que se f : X → Y é uma função, A ⊂ B ⊂ X, A ′ ⊂ B ′ ⊂ Y, então tem-se fA ⊂ fB e f−1.A ′ ⊂ f−1B ′. (5) Seja f : X → Y uma função. Mostre que: a) se f é injectiva, a função associada de conjuntos directa de f é injectiva; b) se f é sobrejectiva, então a função associada de conjuntos directa é sobrejectiva. -27- (6) Prove que sendo f : X → Y uma função, A ⊂ X, B ⊂ Y, tem-se: a) A ⊂ f−1fA; b) se f é injectiva, então f−1fA ⊂ A; c) f é injectiva se e só se ∀A ⊂ X, f−1fA A. d) B ⊃ ff−1B e, se f é sobrejectiva, então B ⊂ ff−1B (7) Mostre que se f : X → Y é uma função, A,B ⊂ X, a) fB \ fA ⊂ fB \ A; b) se f é sobrejectiva, então fAc ⊂ fAc; c) se f é injectiva, então fB \ A ⊂ fB \ fA e fAc ⊂ fAc; d) a função f é bijectiva se e só se ∀A ⊂ X, fAc fAc. Resoluções (1) Com f : R → R, fx x4 tem-se: a) (i) f1 f1 1; (ii) f−1,1 fx : x ∈ −1,1 1; (iii) f−1,1 fx : −1 ≤ x ≤ 1 x4 : −1 ≤ x ≤ 1 0,1; (iv) fR x4 : x ∈ R 0,; (v) fR \ 0, 12 x4 : x ≤ 0 ∨ x 12 0,; (vi) f0, x4 : x 0 0,. b) (i) f−10 x ∈ R : x4 0 0; (ii) f−1−1 x ∈ R : x4 −1 ; (iii) f−1Q 2 x ∈ R : x4 ∈ Q ∨ x4 2 x ∈ R : x4 ∈ Q; (iv) f−10, x ∈ R : x4 ≥ 0 R (v) f−11, x ∈ R : x4 1 1,; (vi) f−1−2, x ∈ R : x4 −2 R. (2) a) y ∈ fXi : i ∈ I ∃x ∈ Xi : i ∈ I, fx y ∃i ∈ I, x ∈ Xi, fx y ∃i ∈ I,y ∈ fXi y ∈ fXi : i ∈ I. b) x ∈ f−1Yj : j ∈ J fx ∈ Yj : j ∈ J ∃j ∈ J, fx ∈ Yj x ∈ f−1Yj : j ∈ J. (3) Supondo f injectiva, consideremos y ∈ fA ∩ fB. Pela definição, tem-se então y fa,a ∈ A ∧ y fb,b ∈ B; então fa fb, o que implica a b ∈ A ∩ B e portanto y ∈ fA ∩ B e tem-se assim fA ∩ fB ⊂ fA ∩ B. Como é sempre fA ∩ B ⊂ fA ∩ fB por I.4.3 (4), cocluimos que se f é injectiva então fA ∩ B fA ∩ fB. Reciprocamente, assumindo esta igualdade para todos os A,B ⊂ X temos: para cada a,b ∈ X, se fa fb então fa fa ∩ fb fa ∩ b donde a b e f é injectiva. (4) A ⊂ B ∀x,x ∈ A x ∈ B ∀y,y ∈ fA ∃x ∈ A,y fx ∃x,x ∈ B,y fx ∀y,y ∈ fA y ∈ fB fA ⊂ fB. Também se A ′ ⊂ B ′ então ∀x,x ∈ f−1A ′ fx ∈ A ′ fx ∈ B ′ ∀x,x ∈ f−1A ′ x ∈ f−1B ′ f−1A ′ ⊂ f−1B ′. (5) a) Mostremos que se f é injectiva e fA ⊂ fB então A ⊂ B, donde se conclui o resultado. Supondo que para todo o a ∈ A se verifica fa ∈ fB, i.e., existe b ∈ B tal que fa fb, concluimos a b e assim a ∈ B e portanto A ⊂ B. b) Sendo B ⊂ Y temos: se B , então B f, ∈ PX; se B ≠ , e f é sobrejectiva, então para cada b ∈ B existe pelo menos um a ∈ X tal que fa b,a ∈ f−1b ⊂ f−1B. Portanto o conjunto A b∈B f−1b ⊂ X satisfaz a condição de, para cada b ∈ B, existir pelo menos um a ∈ A com fa b ou seja, B ⊂ fA; como obviamente fA ⊂ B conclui-se fA B e f : PX → PY é sobrejectiva. -28- (6) a) pois x ∈ A fx ∈ fA; b) suponhamos f injectiva; se então x ∈ f−1fA tem-se fx ∈ fA pela definição e, de novo pela definição, fx fa,a ∈ A. Concluimos x a ∈ A e portanto f−1fA ⊂ A. c) Das alíneas a), b) concluimos que se f é injectiva, então para cada A ⊂ X, A f−1fA. Reciprocamente, se esta inclusão é verdadeira, consideremos a,b ∈ X tais que fa fb; então a,b f−1fa,b f−1fa, fb f−1fa a o que implica a b e f é injectiva. d) Pelas definições, y ∈ ff−1B sse y fx para algum x ∈ f−1B i.e., tal que fx ∈ B, o que mostra que então y ∈ B; portanto B ⊃ ff−1B. Supondo que f é sobrejectiva, seja b ∈ B. Existe pelo menos um x ∈ X verificando fx b, o que implica x ∈ f−1b ⊂ f1B (pela (4)), e então b fx ∈ ff−1B o que mostra que B ⊂ ff−1B. (7) a) Seja y ∈ fB \ fA. Então ∃b ∈ B,y fb ∧ ∀a ∈ A,y ≠ fa o que implica ∃b ∈ B \ A,y fb e portanto y ∈ fB \ A e fB \ fA ⊂ fB \ A; b) por a), fAc Y \ fA fX \ fA ⊂ fX \ A fAc; c) y ∈ fB \ A ∃x ∈ B \ A, fx y ∃x ∈ B \ A, fx y ∧ y ∉ fA y ∈ fB \ fA pois sendo f injectiva, y não é imagem de nenhum outro elemento, a não ser x ∈ B; não pode ser y fa,a ∈ A porque isto implicaria a b ∉ A o que é impossível. Concluimos assim a inclusão. Fazendo B X obtemos fAc fX \ A ⊂ fX \ fA ⊂ Y \ fA fAc; d) Pelas alíneas anteriores concluimos que se f é bijectiva então fAc fAc. Reciprocamente, se esta igualdade se verifica, então fX fc fc c Y e f é sobrejectiva. Também f é injectiva, pois se b ≠ a então b ∈ ac e fb ∈ fac fac,o que mostra que fb ≠ fa. I.4.5 Observação Dadas funções f : X → Y,g : Y → Z encontra-se, para C ⊂ Z: gof−1C x ∈ X : gfx ∈ C x ∈ B : fx ∈ g−1C f−1g−1C, em analogia com I.2.12. Se f e g são bijectivas, então I.4.4 (5) e I.2.14 (1) b) mostram que a função associada de conjuntos directa de f (de g) tem por inversa a função associada de conjuntos inversa de f (de g) e para cada C ⊂ Z, gof−1C f−1og−1C. I.4.6 Se f : X → Y é uma função, y ∈ Y, o conjunto f−1y chama-se a fibra de f em y; a fibra de f em y é não vazia se e só se y ∈ Imf, onde Imf é o contradomínio ou conjunto imagem de f. -29- I.5 RELAÇÕES DE EQUIVALÊNCIA E RELAÇÕES DE ORDEM I.5.1 Definição Uma relação binária em X diz-se uma relação de equivalência em X se verifica as propriedades: reflexiva: ∀x ∈ X,xx; simétrica: ∀x,y ∈ X,xy yx; transitiva: ∀x,y, z ∈ X,xy ∧ yz xz. I.5.2 Exemplos (1) Se X é um conjunto não vazio, a relação definida por xy sse "x,y ∈ X e x y" (relação de igualdade em X) é uma relação de equivalência em X. (2) Com ≠ A ⊂ X, a relação definida por xy sse "x ∈ A ∧ y ∈ A" é uma relação de equivalência em A, mas não é uma relação de equivalência em X se A ≠ X. (3) Dada uma função f : X → Y, a relação binária f em X definida por xf y sse "x,y ∈ X e fx fy" é uma relação de equivalência em X, chamada a relação de equivalência associada à função f. I.5.3 Definições Seja uma relação de equivalência em X. Para cada x ∈ X, o conjunto Cx y ∈ X : xy chama-se a classe de equivalência de x. O conjunto das classes de equivalência Cx x ∈ X diz-se o conjunto cociente de X segundo , e representa-se por X / . Assim X / Cx : x ∈ X ⊂ PX. A aplicação : X → X / , : x Cx que faz corresponder a cada x ∈ X a respectiva classe de equivalência chama-se a aplicação canónica de X sobre X / _Esta aplicação é obviamente sobrejectiva_. I.5.4 Exemplo Para a relação de igualdade no conjunto não vazio A, a classe de equivalência de a ∈ A é Ca a, e o conjunto cociente é a : a ∈ A; a aplicação canónica associa a cada elemento, o ”singleton” por ele constituído, a a. I.5.5 Exercício Determine o conjunto cociente e a aplicação canónica, nos exemplos I.5.2 (2), (3). I.5.6 Resolução (2) Com xy sse "x ∈ A ∧ y ∈ A" x,y ∈ A tem-se Cx y ∈ A : x ∈ A ∧ y ∈ A A; assim : A → A / , x Cx A. A aplicação canónica é constante, e A / A. (3) Sendo xf y sse "x,y ∈ X e fx fy" tem-se: Cx f−1fx é a fibra de f em fx. X / f f−1fx : x ∈ X e x f−1fx. -30- I.5.7 Teorema Sejam X um conjunto e uma relação de equivalência em X. Então: (a) Cada elemento x ∈ X pertence à sua classe de equivalência Cx; (b) dois elementos x,y ∈ X são equivalentes para se e só se têm a mesma classe de equivalência, i.e., para cada x,y ∈ X, tem-se xy sse Cx Cy; (c) o conjunto cociente X / é uma partição de X. Dem. (a) É consequência de xx para cada x ∈ X; (b) supondo xy, seja a ∈ Cx; então xa e, como xy, tem-se também yx, pela simetria. Da propriedade transitiva conclui-se ya, donde ay e a ∈ Cy. Isto mostra que Cx ⊂ Cy e portanto Cx Cy. Reciprocamente, se Cx Cy, então pela (a) tem-se x ∈ Cy donde xy pela definição de Cy; (c) Pela alínea (a), tem-se x ∈ Cx,∀x ∈ X. Portanto X x∈X Cx. Para mostrar que X / é uma partição de X, basta provar que se Cx ≠ Cy então Cx ∩ Cy ; efectivamente, se existe a ∈ Cx ∩ Cy concluimos que Cx Cy do modo seguinte: a hipótese a ∈ Cx,a ∈ Cy implica ax e ay. Então pela simetria e transitividade de , tem-se ax e ya donde yx. De (b) concluimos Cx Cy, provando (c). C.Q.D. 1.5.8 Observação Pela propriedade (c) no teorema, duas classes de equivalência ou são disjuntas, ou coincidem. Dada uma relação de equivalência num conjunto X, o conjunto cociente X / dá uma partição do conjunto X. Reciprocamente, cada partição X : ∈ A de um conjunto não vazio X permite definir uma relação binária em X, que é uma relação de equivalência, pondo xy sse "∃ ∈ A,x,y ∈ X" . Esta relação binária é obviamente reflexiva, simétrica e transitiva. A aplicação canónica é x X sse x ∈ X; o conjunto cociente é exactamente a partição X : ∈ A. I.5.9 Exemplo A relação binária em N definida por xy sse "x,y são da mesma paridade" é uma relação de equivalência em N, que pode ser definida pela partição 2N − 1,2N do conjunto dos números naturais, onde 2N 2x : x ∈ N é o conjunto dos números pares e 2N − 1 2x − 1 : x ∈ N é o conjunto dos números ímpares. I.5.10 Exercício Com ≠ A ⊂ X, explicite a relação de equivalência em X cujo cociente X / é a partição A,Ac de X e indique a aplicação canónica. I.5.11 Resolução xy sse "x,y ∈ X e x,y ∈ A ∨ x,y ∈ Ac" x A se x ∈ A,x Ac se x ∉ A. I.5.12 Definição Sejam uma relação de equivalência em X e f : X → Y uma função. Diz-se que f é compatível com se ∀x,y ∈ X,xy fx fy. -31- I.5.13 Exemplo A relação de equivalência f associada à função f : X → Y em I.5.2 Exemplos (3), xf y sse "x,y ∈ X ∧ fx fy" é compatível com f. I.5.14 Teorema Sejam uma relação de equivalência em X e f : X → Y uma função.As seguintes condições são equivalentes: (i) f é compatível com ; (ii) existe uma única aplicação f : X / → Y tal que f fo, onde : X → X / é a aplicação canónica. Dem. (i) (ii) Supondo f compatível com , a função f : X / → Y, fCx fx é bem definida com valores em Y: pois Cx Cy implica xy (Teorema I.5.7) donde fx fy. Tem-se f fo pela definição de f. Além disso f é única, porque se g : X / → Y verifica fx gCx então obviamente gCx fx. (ii) (i) Se existe f nas condições dadas, suponhamos x,y ∈ X e xy; então x Cx Cy y (teorema I.5.7) donde deve ser fx fCx fCy fy. Isto mostra que f é compatível com . C.Q.D. I.5.15 Observação A função f no teorema anterior é injectiva se e só se ∀x,y ∈ X, f Cx fCy Cx Cy sse ∀x,y ∈ X, fx fy Cx Cy sse ∀x,y ∈ X, fx fy xy; uma vez que f é compatível com , i.e., ∀x,y ∈ X,xy fx fy, vemos que f é injectiva se e só se é a relação de equivalência associada a f. I.5.16 Seja f : X → Y uma função, e designe R f a relação de equivalência em X associada à função f. Chama-se aplicação cociente de f por R e nota-se f/R a função f/R : X/R → Y definida por f/R Cx fx x ∈ X. Conclui-se de I.1.15 que f / R é injectiva, e Imff/R Imf. I.5.17 Observação. Segundo I.2.1, uma relação binária no conjunto não vazio X é uma parte não vazia do produto cartesiano X2. é uma relação de equivalência se e só se para cada x ∈ X, x,x ∈ ∧ y,x ∈ sempre que x,y ∈ ∧ x, z ∈ sempre que x,y, y, z ∈ , correspondendo a ser reflexiva, simétrica e transitiva. Facilmente se verifica que se i : i ∈ I é um conjunto não vazio de relações de equivalência em X, então ∩i : i ∈ I é uma relação de equivalência em X. Além disso, se R é uma relação binária em X, existe uma relação de equivalência 0 em X que contém R a saber, 0 X2; existe portanto, e é bem determinada, a relação de equivalência em X que é a intersecção de todas as relações de equivalência em X que contêm R. I.5.18 Definição (1) Se X é um conjunto não vazio e R é uma relação binária em X, diz-se que a intersecção das relação de equivalência em X que contêm R é a relação de equivalência gerada por R. (2) Se ≠ A ⊂ X, a relação de equivalência determinada pelo conjunto A é a relação de equivalência em X gerada pela relação binária xRAy x,y ∈ A,RA A2. Nota-se X/A o conjunto cociente X/RA, X/A é o conjunto cociente de X pelo subconjunto A. -32- I.5.19 Observação Verifica-se facilmente que a relação de equivalência gerada por RA em I.5.19 (2) é A2 x,x : x ∈ X. O conjunto cociente X/A A,x: x ∈ X ”reduz” o conjunto A a um ponto. I.5.20 Definição Uma relação binária ≤ num conjunto E diz-se uma relação de ordem parcial, ou uma ordem parcial em E se verifica as propriedades de: reflexividade: ∀a ∈ E,a ≤ a; anti-simetria: ∀a,b ∈ E,a ≤ b ∧ b ≤ a a b; transitividade: ∀a,b,c ∈ E,a ≤ b ∧ b ≤ c a ≤ c. E,≤ (ou E) diz-se um conjunto parcialmente ordenado. Se também ∀a,b ∈ E, a ≤ b ou b ≤ a diz-se que ≤ é uma ordem total e que E é totalmente ordenado ou uma cadeia. . I.5.21 Exemplos (1) A relação de ordem usual em R, x ≤ y sse y − x ≥ 0, é uma ordem total em R; (2) a relação binária ≤ em N definida por n ≤ m sse "n é um divisor de m" é uma ordem parcial em N. I.5.22 Exercício Prove que a relação de inclusão de conjuntos em PX é uma ordem parcial em PX. I.5.23 Resolução Reflexividade: Uma vez que P P para qualquer proposição P, se A ∈ PX tem-se x ∈ A x ∈ A donde ∀A ∈ PX,A ⊂ A; anti-simetria: para cada A,B ∈ PX, se A ⊂ B e B ⊂ A então x ∈ A x ∈ B e x ∈ B x ∈ B donde x ∈ A x ∈ B e A B; transitividade: quaisquer que sejam A,B,C ∈ PX, se A ⊂ B e B ⊂ C então x ∈ A x ∈ B, x ∈ B x ∈ C e então x ∈ A x ∈ C concluindo-se A ⊂ C. I.5.24 Definições Seja E,≤ um conjunto parcialmente ordenado, e seja ≠ A ⊂ E. a) Um elemento m ∈ E é um minorante de A (respectivamente um majorante de A) se satisfaz ∀a ∈ A,m ≤ a (resp. ∀a ∈ A,a ≤ M); se o conjunto A tem pelo menos um minorante (majorante), A diz-se um conjunto minorado (resp.um conjunto majorado); b) se de entre os minorantes (majorantes) de A, existe um maior minorante i resp. um menor majorante s, então diz-se que i é o ínfimo de A, e nota-se i infA; respectivamente, diz-se que s é o supremo de A, e representa-se s supA; no caso particular infA ∈ A diz-se que infA é o mínimo de A, e nota-se infA minA e, respectivamente, se supA ∈ A diz-se que supA é o máximo de A e designa-se supA maxA. c) diz-se que uma parte não vazia M de E é uma cadeia se ∀x,y ∈ M,x ≤ y ∨ y ≤ x. d) um elemento v ∈ E é minimal (resp. w é um elemento maximal) se ∀a ∈ E,a ≤ v a v (resp. se ∀a ∈ E,w ≤ a a w). -33- I.5.25 Observação Se A é uma parte não vazia no conjunto parcialmente ordenado E,≤, tem-se i infA se e só se (inf 1) ∀a ∈ A, i ≤ a; (inf 2) ∀m ∈ E,m ≤ a ∀a ∈ A m ≤ i. Também s supA sse (sup 1) ∀a ∈ A,a ≤ s; (sup 2) ∀M ∈ E,a ≤ M ∀a ∈ A s ≤ M. No caso particular E,≤ R,≤, (inf 2) e (sup 2) podem tomar a forma (Rinf) ∀ 0,∃a ∈ A,a i ; (Rsup)∀ 0,∃a ∈ A,a s − . I.5.26 Observação Num conjunto parcialmente ordenado, o ínfimo (resp. o supremo) de uma parte não vazia, se existe, é único. I.5.27 Exemplos (1) Em R munido da ordem usual, todo o conjunto não vazio e minorado (resp. majorado) tem ínfimo (resp. supremo). (2) Em PX,⊂ os conjuntos ,X são respectivamente um elemento minimal, e um elemento maximal; além disso, tem-se infX minX e X supX maxX. Se existem pelo menos dois elementos diferentes em X, PX não é uma cadeia. (3) Em PN,⊂, C Sn 1, . . . ,n : n ∈ N é uma cadeia; é um minorante de C, S1 1 minC e sup C N, não existe maxC. I.5.28 Exercícios (1) Mostre que se X ≠ então cada conjunto xc x ∈ X no conjunto parcialmente ordenado PX \ X,⊂ é um conjunto maximal. (2) Considere a relação binária em N2 2,3, . . . definida por nm sse "n,m ∈ N2 e n divide m" . a) Mostre que o conjunto 2N 2k : k ∈ N não tem majorantes; b) determine inf2N; este ínfimo é um mínimo ? c) prove que C 3k : k ∈ N é uma cadeia em N2,. I.5.29 Resoluções (1) Se A ⊂ X, A ≠ X e x ∈ X, a hipótese xc ⊂ A é equivalente a Ac ⊂ x e, como Ac ≠ , tem de ser Ac x i.e., A xc. Portanto xc é um elemento maximal, para cada x ∈ X. (2) a) Para ser 2kM tem de verificar-se também 2k ≤ M "≤" a ordem usual em R, e não existe nenhum número naturalM tal que ∀k ∈ N, 2k ≤ M. Portanto o conjunto 2N não tem nenhum majorante em N2,. b) Para todo o númrero da forma 2k, k ∈ N, 2 divide 2k; e se m ∈ N2 e, para todo o k ∈ N, m2k então m2 fazendo k 1. Portanto 2 inf2N pela definição de ínfimo. É 2 min2N, já que 2 ∈ 2N. c) Para cada 3n, 3m ∈ C, tem-se n ≤ m ou m ≤ n e, no primeiro caso, 3n3m tendo-se 3m3n no segundo caso. Assim C é uma cadeia em N2,. -34- I.5.30 Definição Se E, é um conjunto parcialmente ordenado, ≠ F ⊂ E, a restrição 0 da ordem parcial a F é obviamente uma ordem parcial em F, que se diz a ordem parcial induzida por em F. Habitualmente escreve-se F, para significar o conjunto parcialmente ordenado F,0. I.5.31 Lema de Zorn Se no conjunto parcialmente ordenado M,≤ toda a cadeia não vazia tem pelo menos um majorante, então existe emM pelo menos um elemento maximal. I.5.32 Observação O lema de Zorn é equivalente ao axioma da Escolha de Zermelo I.3.3. I.5.33 Definição Seja X um conjunto não vazio. Se é uma relação binária em X tal que (i) é reflexiva, i.e., ∀x ∈ X,x x; (ii) é transitiva, i.e., ∀x,y, z ∈ X,x y ∧ y z x z; (ii) ∀x,y ∈ X,∃a ∈ X,x a ∧ y a, então o par X, (ou somente X) diz-se um conjunto dirigido. I.5.34 Observação Um conjunto parcialmente ordenado X,≤ diz-se filtrante ou superiormente filtrante se a ordem parcial verifica, além das propriedades de reflexividade, anti-simetria e transitividade (ver I.5.17), a propriedade de, para cada x,y ∈ X, existir pelo menos um elemento a ∈ X tal que x ≤ a e y ≤ a. Assim, um conjunto parcialmente ordenado filtrante é também um conjunto dirigido. Certos autores chamam a uma relação binária num conjunto X verificando as propriedades reflexiva e transitiva, uma quase-ordem. Pode suceder, segundo a definição I.1.28, X, ser um conjunto dirigido e no entanto a relação binária em X não ser uma ordem parcial. Um exemplo importante, de que veremos uma aplicação adiante, é o seguinte: consideremos um conjunto não vazioM, e uma classe de conjuntos F ⊂ PM tal que ∀F ∈ F,F ≠ e se verifique ∀F,F ′ ∈ FF ∩ F ′ ∈ F.. Sendo : F → F : F ∈ F o selector de Zermelo em I.3.3, podemos considerar a relação binária em A F : F ∈ F definida por a a′ sse existem F,F ′ ∈ F tais que a F, a′ F ′ e F ′ ⊂ F. Então A, é um conjunto dirigido, mas em geral, da hipótese a a′ e a′ a não pode concluir-se a a′ e não é uma ordem parcial em A. I.5.35 Observação Se E,≤ é um conjunto parcialmente ordenado, pode existir um subconjunto F não vazio de E tal que não exista minF. Por exemplo, com E Q e ≤ a ordem parcial usual de R induzida sobre Q, não existe min 2 ,2 ∩ Q. O que não que dizer que, para outra ordem parcial sobre Q, não possa suceder que cada subconjunto não vazio tenha um mínimo. Se E,≤ é um conjunto parcialmente ordenado, e existe o mínimo de uma parte A de E, diz-se também que minA é o primeiro elemento de A. -35- I.5.36 Definição Um conjunto parcialmente ordenado E,≤ diz-se um conjunto bem ordenado se toda a parte não vazia de E tem primeiro elemento. Diz-se então também que ≤ é uma boa ordem em E. I.5.37 Observação Todo o conjunto bem ordenado é totalmente ordenado, como se reconhece considerando dois quaisquer elementos e o mínimo do conjunto por eles formado. Uma propriedade dos conjuntos parcialmente ordenados, equivalente ao axioma da Escolha de Zermelo, é que dado qualquer conjunto não vazio E, existe pelo menos uma ordem parcial ≤ em E, para a qual E,≤ é um conjunto bem ordenado. I.5.38 Princípio da boa ordenação Se E é um conjunto não vazio, existe pelo menos uma boa ordem em E. -36- I.6 O CONJUNTO N. NOÇÕES DE CARDINALIDADE. I.6.1 O conjunto N 1,2, . . . dos números naturais pode ser caracterizado pela axiomática de Peano: (I) existe um número natural chamado ”um” e representado por 1; (II) cada número natural a tem um sucessor a′ que é também um número
Compartilhar