itc2004cap3 - Relações e Funções

3 Rela» c~ oes e F un» c~ oes Oc a p ¶ ³tulo inicia-se com uma discuss~ ao sob re pares o rdenados e o prod uto ca rtesiano de dois conjuntos. O conceito de rela» c~ ao ¶ ee n t ~ ao de¯nido como sendo um conjunto de pa res ordenados. A conex~ ao ¶ ³ntima entre parti» c~ oes e rela» cµ oes de equival ^ e ncia, num conjunto, ¶ e cuidadosamente examinada. Como prepa ra» c~ ao pa ra os leitores que p r etendem seguir estudando mais matem¶ atica mo derna, p rop riedades imp ortantes de fun» c~ oes s~ ao estudadas. Uma grande quantidade de exemplos ¶ ec o n s t r u ¶ ³da. 3.1 Pro duto ca rtesia no de conjuntos Dados dois objetos quaisquer a e b , p o demos fo rmar um novo objeto ( a; b ) , chamado pa r o rdenado a , b . 12 O adjetivo \o rdenado" enfatiza aqui que a o rdem p ela qual os objetos a e b aparecem entre par ^ entese s ¶ e essencial. Note que o pa r ordenado ( a; b ) n~ ao ¶ eo mesmo que o conjunto f a; b g .H ¶ au mm o d os a t i s f a t ¶ orio, embora complicado, de de¯nir o pa r ordenado ( a; b ) como sendo o conjunto ff a g ; f a; b gg , de onde segue a p ropriedade \ ( a; b )=( c; d ) , a = c e b = d " (Veja Problema 11, Exerc ¶ ³cios 1.3.1). Dois pa res ordenado s ( a; b ) e ( c; d ) s~ ao considerados iguais (=) se e so ment e se a = c e b = d . Po r exemplo, ( x; y )=( 7 ; 8) s ees o m e n t es e x =7 e y =8 . Em geom etr ia an al ¶ ³tica, o plano cartesiano po de ser consider ado como o conjunto de to dos os pares o rdenados de n ¶ umeros r eais. Enu nciaremos formalmente este c onceito do seguinte mo do: De¯ni» c~ ao 3.1 Sejam A e B dois conjuntos quaisquer. O conjunto de to dos os pa res o rdenados ( x; y ) ,c o m x 2 A e y 2 B ,¶ e chamado o p ro duto ca rtesi ano de A e B ,e ¶ e 1 Infelizmente, a nota» c~ ao ( a; b ) para um par ordenado ¶ e a mesma par a um intervalo ab erto quando a e b s~ ao n ¶ umeros reais. Entretanto, o leitor atento dever ¶ a ser sempre capaz de fazer a distin» c~ ao a pa rtir do contexto. 2 Desde o Cap ¶ ³tulo 2, j¶ a¯ z e m o sao p » c~ ao p or denota r o intervalo aberto de extremos a e b po r ] a; b [ . (N. do T.) 49 50 Relac » ~ oes e Func » ~ oes denotado p o r A £ B . Simb olicamente, A £ B = f ( x; y ) j x 2 A ^ y 2 B g Pa ra o par ordenado ( a; b ) , a ¶ e chamado a p rimeira co o rdenada e b ¶ ea segunda co o rdenada . Exemplo 3.1 Seja m A = f a; b; c g e B = f 1 ; 2 g . Enc ontre os produtos cartesianos A £ B e B £ A . Solu» c~ ao. P ela De¯ni» c~ ao 3.1 acima, temos A £ B = f ( a; 1) ; ( a; 2) ; ( b; 1) ; ( b; 2) ; ( c; 1) ; ( c; 2) g e B £ A = f (1 ;a ) ; (1 ;b ) ; (1 ;c ) ; (2 ;a ) ; (2 ;b ) ; (2 ;c ) g Notamos que A £ B 6 = B £ A . P o demos representa r geometricamen te o p ro duto ca rtesia no A £ B como o conjunto de p ontos destacados na seguinte ¯gura. Figura 7. Exemplo 3.2 Seja A um conjunto qualquer. Encontre A £ ¿ e ¿ £ A . Solu» c~ ao. Como A £ ¿ ¶ e o conjunto de todos os pa res ordenados ( a; b ) , tais que a 2 A e b 2 ¿ ,ec o m ooc o n j u n t ov a z i o ¿ n~ ao cont ¶ em nenhum elemento, n~ ao h ¶ a nenhum b em ¿ ;p o r t a n t o A £ ¿ = ¿ . Analogamente, ¿ £ A = ¿ . Te o r e m a 3 . 1 Sejam A , B e C tr ^ es conjuntos quaisquer. E nt~ ao (a) A £ ( B \ C )=( A £ B ) \ ( A £ C ) . (b) A £ ( B [ C )= ( A £ B ) [ ( A £ C ) . Relac » ~ oes e Func » ~ oes 51 Demonst ra» c~ ao. (a) ( a; x ) 2 A £ ( B \ C ) , ( a 2 A ) ^ ( x 2 B \ C ) Def. 3.1 , ( a 2 A ) ^ ( x 2 B ^ x 2 C ) Def. de \ , ( a 2 A ) ^ ( a 2 A ) ^ ( x 2 B ) ^ ( x 2 C ) Idemp., As so c. (Cap . 1) , [( a 2 A ) ^ ( x 2 B )] ^ [( a 2 A ) ^ ( x 2 C )] Com. , Assoc. (Cap. 1) , [( a; x ) 2 A £ B ] ^ [( a; x ) 2 A £ C ] Def. 3.1 , ( a; x ) 2 ( A £ B ) \ ( A £ C ) Def. de \ Po rtanto, p ela De¯ni» c~ ao 2.1 , do Ca p ¶ ³tulo 2, acabamos de demonstra r que A £ ( B \ C )=( A £ B ) \ ( A £ C ) Info rmalmente, est a igualdade po de ser enunciada: O p ro duto ca rtesiano distribui sob re a interse» c~ ao. Deixa remos a demonstra» c~ ao da pa rte (b) ao leitor, como exerc ¶ ³cio. Te o r e m a 3 . 2 Sejam A , B e C conjuntos quaisquer. Ent~ ao A £ ( B ¡ C )=( A £ B ) ¡ ( A £ C ) Ou seja, o produto c a rtesi ano distr ibui sobre a complementa» c~ ao. Demonst ra» c~ ao. ( a; x ) 2 A £ ( B ¡ C ) , ( a 2 A ) ^ ( x 2 B ¡ C ) Def. 3.1 , ( a 2 A ) ^ ( x 2 B ^ x 6 2 C ) Def. 2.5 (Cap. 2) , ( a 2 A ) ^ ( a 2 A ) ^ ( x 2 B ) ^ ( x 6 2 C ) Idemp. , Asso c. (Cap . 1) , [( a 2 A ) ^ ( x 2 B )] ^ [( a 2 A ) ^ ( x 6 2 C )] Com., Asso c. (Cap. 1) , [( a; x ) 2 A £ B ] ^ [( a; x ) 6 2 A £ C ] Def. 3.1 , ( a; x ) 2 ( A £ B ) ¡ ( A £ C ) Def. 2.5 (Cap. 2) Assim, acabamos de de monstra r que A £ ( B ¡ C )=( A £ B ) ¡ ( A £ C ) 52 Relac » ~ oes e Func » ~ oes 3.1.1 Ex erc ¶ ³cios 1. Descreva cada um dos seguintes c onjuntos, geometr icamente , esb o» cando um gr¶ a¯co no plano car tesiano. (a) f ( x; y ) 2 R £ R j x = y g (b) f ( x; y ) 2 R £ R j x>y g (b) f ( x; y ) 2 R £ R jj x + y j· 1 g 2. Sob quais condi» c~ oes nos conj untos A e B ser¶ a verdade que A £ B = B £ A ? 3. Demonstre o T eo r ema 3.1(b): A £ ( B [ C )=( A £ B ) [ ( A £ C ) . 4. Demonstre que A £ B = ¿ , A = ¿ _ B = ¿ . 5. Demonstre que , se A , B e C s~ ao conjuntos e A ½ B ,e n t ~ ao A £ C ½ B £ C . 6. Se o c onjunto A tem m e lemen tos e o conjunt o B tem n elementos, quantos eleme ntos (pa res ordenados) tem A £ B ? 7. O p ro d uto cartesiano A £ A tem 9 elementos, dent re os quais s~ ao encontrados ( ¡ 1 ; 0) e (0 ; 1) . Encontre os elementos res tantes e o conjunto A . 8. Demonstre ou refute (dando um contra-exemplo) cada uma das seguintes a¯rma» c~ oes. (a) A £ B ½ C £ D s ees o m e n t es e A ½ C e B ½ D . (b) O conjunto das partes } ( A £ B ) de A £ B ¶ e o produto cartesiano } ( A ) £ } ( B ) dos conjuntos das pa rt es } ( A ) e } ( B ) . (c) ( A £ B ) [ ( C £ D )=( A [ C ) £ ( B [ D ) . 9. Demonstre que , se A , B , C e D s~ ao quatro conjuntos quaisquer, ent~ ao ( A £ C ) \ ( B £ D )=( A \ B ) £ ( C \ D ) : 10. Sejam A 1 ;A 2 ;::: ;A n conjuntos quaisquer. P o de vo c ^ e generali za r a De¯ni» c~ ao 3.1 ao pr o dut o car tesi ano A 1 £ A 2 £ A 3 de tr ^ es conjuntos? P o de v o c^ e generaliza r isto ao p ro duto ca rtesiano A 1 £ A 2 £¢ ¢ ¢£ A n de n conjuntos? 11. De¯na o par o rdenado ( x; y ) como sen do o conjunto ff x g ; f x; y gg . Use esta de¯ni» c~ ao pa ra demonstrar que ( a; b )=( c; d ) se e somen te se a = c e b = d . 3.2 Rela» c~ oes Dados dois conjuntos A e B ,n ~ ao necess a riamente distintos, quando dizemos que um elemento a de A est¶ a relacionado a outro elemen to b de B ,por uma rela» c~ ao R ,e s t a m o s fazendo uma a¯rma» c~ ao sob re o pa r ord enado ( a; b ) no produto cartesiano A £ B .P o r - tanto, uma de¯ni» c~ ao mate m¶ atica de uma rela» c~ ao p o de ser dada preci samente em termos de pa res ordenados no produto c a rtesiano de conjuntos. De¯ni» c~ ao 3.2 Uma rela» c~ ao R de A pa ra B (ou de A em B )¶ e um subconjunto do p ro duto c artesiano A £ B . ¶ E costume denotar ( a; b ) 2 R po r a R b .O s ¶ ³mb olo a R b ¶ e lido \ a est¶ a R -relacionado a b ". Fr e q Ä uentem ente A e B s~ ao um mesmo conjunto, digamos X . Nesse ca so, diremos que R ¶ e uma rela» c~ ao em X em vez de \de X pa ra X ". Po r exemplo, em uma comunidade Relac » ~ oes e Func » ~ oes 53 X , 3 dizer que a (para Alb erto) ¶ e o ma rido de b (para Beatriz), ¶ e considera r Alb ert o e Beatriz como um par (o r denado) ( a; b ) na rela» c~ ao M ( d es e rom a r i d od e :: : ). O s¶ ³mbolo a M b ou ( a; b ) 2 M p o de ser lido \ a ¶ e ma rido de b ". N~ ao ¶ e necess¶ ario colo car Beatriz depois de Alb erto no pa r ordenado ( a; b ) .P o d e m o s dizer que Beatriz ¶ e a esp osa de Alberto, ou que o pa r o rden ado ( b; a ) est¶ an ar e l a » c~ ao E ( d es e rae s p o s ad e ::: ). O s ¶ ³mbolo b E a ou ( b; a ) 2 E p o de ser lido: \ b ¶ eae s p o s ad e a ". Neste exemplo, a rela» c~ ao E ¶ e chamada a rela» c~ ao inversa de M . De¯ni» c~ ao 3.3 Sejam A e B dois conjuntos, n~ ao necessa riamente distint os, e seja R uma rela» c~ ao de A para B .E n t ~ ao a rel a» c~ ao inversa R ¡ 1 da rela» c~ ao R ¶ e a rela» c~ ao de B pa ra A tal que b R ¡ 1 a se e som ente se a R b .O u s e j a , R ¡ 1 = f ( b; a ) j ( a; b ) 2 R g Exemplo 3.3 (a) Sejam A = f a; b g , B = f x; y ; z g ,es e j a R ½ A £ B dada p or R = f ( a; x ) ; ( b; y ) g .E n t ~ ao R ¡ 1 = f ( x; a ) ; ( y; b ) g½ B £ A . (b) Seja R = f ( x; y ) 2 N £ N j x divide y g Ent~ ao R ¡ 1 = f ( y; x ) 2 N £ N j y ¶ em ¶ ultip lo de x g Seja R uma rel a» c~ ao de A pa ra B .O dom ¶ ³nio da rela» c~ ao R ,d e n o t a d o p o r Dom( R ) , ¶ e o conjunto de to dos aqueles a 2 A tais que a R b para algum b 2 B ;ea imagem de R ,d e n o t a d ap o r Im( R ) ,¶ e o conjunto de to dos aqueles b 2 B , tai s que a R b para algum a 2 A . Simb olicamente, Dom( R )= f a 2 A j ( a; b ) 2 R pa ra algum b 2 B g e Im( R )= f b 2 B j ( a; b ) 2 R pa ra algum a 2 A g No exemplo das rela» c~ oes M ( s e rom a r i d od e ::: )e E (ser a e sp osa de ::: ) na comunidade X ,od o m ¶ ³nio de M ¶ e o conjunto de to dos os homens e m X que s~ ao casados, enquanto q ue o dom ¶ ³nio de E ¶ e o conju nto das esposas em X ,eai m a g e md e E ¶ e o conjunto de todos os maridos em X ,I s t o ¶ e, Dom( E )=I m ( M ) e Im( E )=D o m ( M ) Po d e v o c^ e tir a r uma conclus~ ao geral? (V eja Problema 3 ao ¯nal des ta se» c~ ao). 3 Aqui, X ¶ e o conjunto de to dos os memb ros da comunidade. 54 Relac » ~ oes e Func » ~ oes Exemplo 3.4 No Exemplo 3.3(a), Do m( R )= f a; b g e Im( R )= f x; y g .N o E x e m p l o 3.3(b), Dom( R )= N =I m ( R ) . De¯ni» c~ ao 3.4 Seja R uma rela» c~ ao em um c onjunto X .E n t ~ ao dizemos que (a) R ¶ e re°exiva s ees o m e n t es e 8 x 2 X; x R x . (b) R ¶ e sim¶ etrica se e somente se x R y ) y R x . (c) R ¶ e transitiva se e somente se x R y ^ y R z ) x R z . (d) R ¶ eu m a rela» c~ ao de e quival ^ encia se e somente se R ¶ e re°exiva, sim ¶ et rica e transitiva. Ar e l a » c~ ao de igualdade, = , no conjunto R de n¶ umeros re ais ¶ e claramente uma rela» c~ ao de equival ^ encia. Seja X um conjunto de bolas colo ridas e sejam duas bolas a e b relacionad as p o r R se e somente se a e b tem a mesma c or. Ent~ ao a rel a» c~ ao R ¶ eu m a rela» c~ ao de equival^ enci a. Rela» c~ oes de equival ^ encia s~ ao particula rmente imp ortantes na matem¶ atica mo derna. P o r exemplo, grupos quocientes na ¶ algeb ra, espa» cos quocient es na topologia, e sistemas num ¶ ericos mo dula res na teoria dos n¶ umeros, t o dos envolvem certos tip os de rela» c~ oes de equival ^ encia. Dado um conjunto n~ ao vazio X , existem sempre pe lo menos duas rel a» c~ oe s d e equival ^ encia e m X ; uma dest as ¶ ea rela» c~ ao diagonal ¢ X (tam b¶ em chamad a rela» c~ ao identidade ) d e¯ni da po r ¢ X = f ( x; x ) j x 2 X g que relaciona cada elemento com ele mesm o. Geometricamen te, se X ¶ e re p resent ado como um intervalo linear, ent~ ao X £ X ¶ e um quadrado e ¢ X ¶ e a diagonal \principa l" do quadrado. Figura 8. H¶ a, no out ro extremo, s empre outra rela» c~ ao de equival ^ encia R = X £ X em X .A rela» c~ ao ¢ X ¶ e a meno r de to das as rela» c~ o e sd ee q u i v a l ^ encia em X , enquanto que X £ X ¶ eam a i o r . Exemplo 3.5 Seja m um inteiro p ositivo qualquer ¯xado. A rela» c~ ao de congru ^ encia ´ m¶ odulo m , no conjunto Z dos n¶ umeros inteiro ¶ e de¯nida p o r x ´ y (mo d m ) se e somente se x ¡ y = km para algum k 2 Z . A rela» c~ ao de c ongru ^ encia ¶ e uma rela» c~ ao de equival ^ encia em Z . Relac » ~ oes e Func » ~ oes 55 Demonst ra» c~ ao. (a) P ar a cada x em Z , como x ¡ x =0 ¢ m ,t e m o s x ´ x (mo d m ) .P o r t a n t o , a rela» c~ ao ¶ er e ° e x i v a . (b) Se x ´ y (mo d m ) ,e n t ~ ao x ¡ y = km pa ra algum k 2 Z .C o n s e q Ä uent emente, y ¡ x =( ¡ k ) m e ¡ k 2 Z ,o u y ´ x (mo d m ) .P o r t a n t o , a r e l a » c~ ao ¶ e sim ¶ et rica. (c) Se x ´ y (mo d m ) e y ´ z (mo d m ) ,e n t ~ ao x ¡ y = k 1 m e y ¡ z = k 2 m pa ra alguns k 1 e k 2 em Z .P o r t a n t o , x ¡ z =( x ¡ y )+( y ¡ z )=( k 1 + k 2 ) m e k 1 + k 2 2 Z , o que mostra que x ´ z (mo d m ) .P o r t a n t o , a r e l a » c~ ao ¶ e transitiva. Po rtanto, acabamos de demonstrar que a rela» c~ ao de congru ^ encia (m ¶ odulo m )¶ e uma rela» c~ ao de equival^ encia em Z . Como um caso exp ecia l pa ra o Exemplo 3.5, sej a m =2 .E n t ~ ao, x ´ y (mo d 2) se e soment e se x ¡ y ¶ e um intei ro pa r. ConseqÄ uentement e, x ´ y (mo d 2) se e somente se x e y s~ ao amb os pa res ou ambos ¶ ³m pa res. 3.2.1 Ex erc ¶ ³cios 1. Seja R uma rela» c~ ao de A para B . Demonstre que ( R ¡ 1 ) ¡ 1 = R . 2. Seja A = f a; b; c g es e j a R = f ( a; c ) ; ( c; b ) ; ( a; b ) g . Encontre o dom ¶ ³nio de R ea imagem de R . 3. Seja R uma rela» c~ ao de A para B . Demonstre que (a) Dom( R ¡ 1 )= I m ( R ) (b) Im( R ¡ 1 )=D o m ( R ) 4. Seja A = f a; b; c g es e j a R = f ( a; a ) ; ( b; b ) ; ( c; c ) ; ( a; b ) ; ( b; a ) ; ( c; a ) ; ( a; c ) g Demonstre que R ¶ e re°exiva e transitiva, mas n~ ao ¶ e sim¶ etrica. 5. D ^ e um exemplo de uma rela» c~ ao que ¶ e re °exiva e transitiva, mas n~ ao ¶ e sim¶ etrica. 6. D ^ e um exemplo de uma rela» c~ ao que ¶ e sim¶ etrica e transitiva, mas n~ ao ¶ er e ° e x i v a . 7. Seja R uma rela» c~ ao em um conjunto X . D emonstre que (a) R ¶ er e ° e x i v as ees o m e n t es e R ¾ ¢ X ; (b) R ¶ e sim ¶ etrica se e soment e se R = R ¡ 1 ; (c) R ¶ e re °exiva se e soment e se R ¡ 1 ¶ e re°exiva; (d) R ¶ e sim ¶ etriva s e e somente s e R ¡ 1 ¶ e sim ¶ etric a; (e) R ¶ e tr ansitiva se e somente se R ¡ 1 ¶ e transitiva; (f ) R ¶ e uma rela» c~ ao de e quival ^ encia se e so mente s e R ¡ 1 ¶ e uma rela» c~ ao de equival ^ encia. 8. Seja X = Z £ ( Z ¡f 0 g ) . De¯na uma rela» c~ ao » em X declarando que ( a; b ) » ( c; d ) s ees o m e n t es e ad = bc . Demonstre que a rela» c~ ao » ¶ e uma rela» c~ ao de equival^ encia. 56 Relac » ~ oes e Func » ~ oes 3.3 P a rti» c~ oes e rela» c~ oes d e equival ^ encia De¯ni» c~ ao 3.5 Seja X um conjunto n~ ao v azi o. Po r uma pa rti» c~ ao P de X quere mos dizer um conjunto de sub conjuntos n~ ao vazios de X, tal que (a) Se A; B 2 P e A 6 = B ,e n t ~ ao A \ B = ¿ . (b) S C 2 P C = X . Intuitivamente, uma pa rti» c~ ao de X ¶ e uma sub divis~ ao de X em \peda» cos" n ~ ao vazios e mutuamente disjuntos. Exemplo 3.6 Seja m um inteiro p ositivo qualquer. P ara cada intei ro j , 0 · j m , seja Z j = f x 2 Z j x ¡ j = km pa ra algum k 2 Z g .E n t ~ a ooc o n j u n t o f Z 0 ; Z 1 ; Z 2 ;::: ; Z m ¡ 1 g fo rma uma parti» c~ ao de Z . Em pa rticular, seja m =2 .E n t ~ ao o co njunto de conjuntos f Z 0 ; Z 1 g , em que Z 0 = f x 2 Z j x ¶ ep a r g e Z 1 = f x 2 Z j x ¶ e¶ ³mpar g fo rma uma parti» c~ ao d e Z . (Veja tamb ¶ em Problem a 4, Exerc ¶ ³cios 3.3.1.) Existe uma conex~ ao ¶ ³ntima en tre pa rti» c~ oe s de um conjunto n~ ao vazio e rela» c~ oes d e equival ^ encia ness e conjunto. Pa ra compreender essa conex~ ao, p recisa rem os da seg uint e de¯ni» c~ ao. De¯ni» c~ ao 3.6 Seja E uma rela» c~ ao de equival ^ e n c i ae mu mc o n j u n t on ~ ao vazio X .P a r a cada x 2 X , de¯nimos o conjunto x= E = f y 2 Y j y E x g que ¶ e chamado a c lasse de equival^ encia det erminada pelo elemento x . O conjunto de to das e ssas classes de equiva l ^ enc ia em X ¶ ed e n o t a d op o r X= E ;o us e j a , X= E = f x= E j x 2 X g . 4 Os ¶ ³mb olo X= E ¶ e lido \ X m¶ odulo E ", ou simplesmente \ X mo d E ". 5 Te o r e m a 3 . 3 Seja E uma rela» c~ ao de equival^ encia em um conjunto n~ ao vazio X .E n t ~ ao (a) Cada x= E ¶ e um sub conju nto n~ ao vazio de X . (b) x= E \ y= E 6 = ¿ se e somen te se x E y . (c) x E y s ees o m e n t es e x= E = y= E . 4 X= E ¶ ec h a m a d o conjunto quo ciente de X pel a re l a» c~ ao de equival ^ encia E .( N . d o T . ) 5 Analogamente, x= E ¶ e lido \ x m¶ odulo E "( N .d oT . ) Relac » ~ oes e Func » ~ oes 57 Demonst ra» c~ ao. (a) Como E ¶ e re°ex iva, pa ra cada x 2 X ,t e m o s x E x .P e l a D e ¯ n i » c~ ao 3.6, x 2 x= E ep o r t a n t o x= E ¶ e um sub c onjunto n~ ao vazio de X . (b) Como E ¶ e uma rela» c~ ao de equival^ encia e X 6 = ¿ ,t e m o s x= E \ y= E 6 = ¿ , ( 9 z )( z 2 x= E ^ z 2 y= E ) , ( z E x ) ^ ( z E y ) Def. 3.6 , ( x E z ) ^ ( z E y ) E ¶ e sim¶ etric a , x E y E ¶ e transitiva (c) De (a) e (b) acima, segue i mediatamente que x= E = y= E ) x E y . Precisamos ago ra p rovar que x E y ) x= E = y= E . Sup onhamos x E y .E n t ~ ao z 2 x= E ) z E x Def. 3.6 ( z E x ) ^ ( x E y ) ) ( z E y ) E ¶ e transitiva ) z 2 y= E Def. 3.6 Com o z ¶ e qualquer, segue que x= E ½ y= E . Um a rgumento s imila r deduz y= E ½ x= E ;p o r t a n t o x= E = y= E . Te o r e m a 3 . 4 Seja E uma rela» c~ ao de equival^ encia em um conjunto n~ ao vazio X .E n t ~ ao X= E ¶ eu m ap a r t i » c~ ao de X . Demonst ra» c~ ao. Pelo T eorema 3.3(a) e p ela De¯ni» c~ ao 3.6, X= E = f x= E j x 2 X g ¶ e uma fam ¶ ³lia de sub c onjuntos n~ ao vazios de X . Mostraremos ent~ ao que x= E 6 = y= E ) ( x= E ) \ ( y= E )= ¿ mostrando sua contrap ositiva: ( x= E ) \ ( y= E ) 6 = ¿ ) x= E = y= E .A ¶ ultima a¯rma» c~ ao ¶ e uma conseqÄ u^ enci a direta do T eo rema 3.3(b) e (c). Finalmente, temos que mostrar que S x 2 X x= E = X .I s t o t a m b ¶ em ¶ et r i v i a l ,p o i sc a d a x 2 X pe r te n ce a x= E . Isto completa a demonstra» c~ ao do teo rema. Acabamos de ver, no T eo rema 3.4, que uma rela» c~ ao de equival ^ encia no c onjunto n~ ao vazio X d¶ a origem a uma pa rti» c~ ao em X . Mostraremos a seguir que a rec ¶ ³proca do T eo rema 3.4 ¶ e verdadeira; isto ¶ e, c ada parti» c~ ao de X d¶ a origem a uma rela» c~ ao d e equival ^ encia em X . De¯ni» c~ ao 3.7 Seja P uma parti» c~ ao de um conjunto n~ ao vazio X . De¯nimos uma rela» c~ ao X= P em X ,p o r x ( X= P ) y se e somente se existe um conjunto A 2 P tal que x 2 A e y 2 A . 58 Relac » ~ oes e Func » ~ oes Cautel a! O leito r deveria ler e compa rar cuida dosamente as de¯ni» c~ o e s3 . 6e3 . 7 , d em o d o a compreender as delicadas diferen» ca s entre es tas nota» c~ oes simila res: x= E , X= E ,e X= P . Te o r e m a 3 . 5 Seja P uma parti» c~ ao de um conjunto n~ ao vazio X .E n t ~ ao a r e la» c~ ao X= P ¶ e uma rela» c~ ao de eq uival ^ enc ia em X , e a s classe s de equiva l ^ encia de ¯nidas p ela rela » c~ ao de equival ^ encia X= P s~ ao p recisamente os conjuntos em P . Simbolicamente, X= ( X= P )= P . Demonst ra» c~ ao . C o m ot o d oe l e m e n t od e X est¶ a contido em algum A 2 P , x ( X= P ) x ; isto ¶ e, X= P ¶ e re°exiva. A simet ria de X= P ¶ e uma cla ra conseq Ä u^ e ncia da De¯ni» c~ ao 3.7. P a ra mostrar que a rela» c~ ao X= P ¶ e transitiva, sejam x , y ,e z tr ^ es elem entos de X sati sfazendo x ( X= P ) y e y ( X= P ) z Ent~ ao, p ela De¯ni» c~ ao 3.7, existem A e B em P tais que, x; y 2 A e y; z 2 B . Conse- quentemente, y 2 A \ B 6 = ¿ . Segue ent~ ao, p ela de¯ni» c~ ao de parti» c~ ao, que A = B . Por t a n t o , x; z 2 A ea s s i m x ( X= P ) z . Logo, X= P ¶ e uma rela» c~ ao de equival^ encia em X . Pa ra demonstr ar o resto do teorema, se ja x um elemento qualquer de X .E x i s t e um e somente um conjunto A em P tal que x 2 A .( P o r q u ^ e?) Con seqÄ uenteme nte, p ela De¯ni» c~ ao 3.7, t emos x= ( X= P )= A Acabamos de p rova r que cada classe de equival ^ enc ia, m¶ odulo X= P ,¶ e um conjunto da fam ¶ ³lia P . Reciproca mente, seja A um conjunto qualquer na parti» c~ ao P . Como A 6 = ¿ , existe um elemento x em X que p ertence a A . P elo nosso argumento p r¶ evio, x= ( X= P )= A . Isto demo nstra que X= ( X= P )= P . A demonst ra» c~ ao do teo re ma est¶ a completa. To d a r e l a » c~ ao de equival ^ encia E em um conjunto X d¶ ao r i g e mau m ap a r t i » c~ ao X= E (de X ) (T e o rema 3.4); esta parti» c~ ao, p or sua vez, d etermina uma rela» c~ ao de equival^ encia X= ( X= E ) (T eorema 3.5). O fato crucial ¶ e que X= ( X= E )= E ( v e j aP r o b l e m a6 ) . Isto, juntam ente com X= ( X= P )= P , est ab elec e a conex~ ao ¶ ³ntima e ntre rela» c~ oes de equival ^ encia e parti» c~ oes. Ilustremos o T eorema 3.5 por um ex emplo concreto. Sejam Z 0 e Z 1 oc o n j u n t od e inteiros pa res e o conjunto de inteiros ¶ ³mpa res, re sp ectivame nte. Ent~ ao P = f Z 0 ; Z 1 g fo rma uma parti» c~ ao do conjunto Z dos inteiros. Pela de¯ni» c~ ao da rela» c~ ao Z = P ,t e m o s a ( Z = P ) b se e somen te se amb os a; b 2 Z 0 ou a; b 2 Z 1 .I s t o ¶ e, a ( Z = P ) b se e somen te se amb os a e b s~ ao pares ou amb os s~ ao ¶ ³mpa res. ¶ Ef ¶ acil veri¯car que esta rela» c~ ao Z = P ¶ ed e fato uma rel a» c~ ao d e equiv al^ encia. Na verdade , a ( Z = P ) b s ees o m e n t es e a ´ b (mo d 2) . P o rtanto, a rela» c~ ao Z = P ¶ e a r ela» c~ ao familia r ´ (m o d 2) . [V eja Exemplo 3.5.] Reciprocamente, dado o conjunto Z , juntamente com a re la» c~ ao E tal que x E y se es o m e n t es e x ´ y (mod 2) ,t e m o s a= E = f x 2 Z j x ´ a (mo d 2) g = ½ Z 0 se a ¶ ep a r Z 1 se a ¶ e¶ ³mpar

itc2004cap3 - Relações e Funções

UFPE

Fundamentos de Matemática

Continue navegando

Materiais relacionados

Perguntas relacionadas

7. O estudo de funções é fundamental na matemática, pois as funções desempenham um papel crucial em modelar relações entre variáveis em diversos co...

Neste sentido, para Vygostki o desenvolvimento cognitivo do ser humano é: Assinale a alternativa correta. a. Conversão das relações sociais em fu...

PERGUNTA 3 - No tocante às funções administrativas típicas das organizações, é correto afirmar: a. São consideradas funções administrativas: Pla...

Assinale a alternativa que nomeia CORRETAMENTE as formas de raciocínio algébrico a que o enunciado está se referindo. a. Generalização e formaliza...

Outros materiais