itc2004cap4 - Conjuntos Enumeráveis e Conjuntos Não Enumeráveis

4 Conjuntos Enumer¶ aveis e Conjuntos N~ ao Enumer ¶ aveis Ad e ¯ n i » c~ ao de Dedekind, de conjunto in¯nito, ¶ e usada ma di scu ss~ ao de p rop ri edades de conjuntos in¯nitos e de conjuntos ¯nitos. ¶ E demonstrado, dentre outras coisas, que conjuntos enume r¶ aveis s~ ao os menores, em tamanho, dent re os conjuntos in¯nitos. Prop riedades e exemplos, de conjuntos enumer¶ aveis e de conjuntos n~ ao enumer¶ a ve is, s~ ao dadas. 4.1 Conjuntos ¯nitos e in¯nitos Na Se» c~ ao 2.1, C a p ¶ ³tulo 1, me ncionamos info rmalmente que um conjunto ¯nito ¶ eu m conjunto que cont ¶ em ap enas uma quant idade ¯nita de elemen tos; emb o ra este concei to p ossa ser tr ansfo rmado em uma de¯ni» c~ ao matem¶ atica mais p recisa , daremos p refer ^ encia au m ad e ¯ n i » c~ ao alternativa (De¯ni» c~ ao 4.1), fo rmulada por Dedekind. F oi enfatizado, na Se» c~ ao 2 .1, do C a p ¶ ³tulo 2, que o conjunto N ,d o s n ¶ umeros naturais, ¶ eu m conjunto in¯nito .S e j a N p = f 2 ; 4 ; 6 ;:: : g oc o n j u n t od et o d o so sn ¶ umeros naturais pa res. Como foi mostrado ao leito r, no Problema 8, Exerc ¶ ³cios 3.6.1, existe uma co rresp ond ^ encia um-a-um entre o conjunto N e seu sub conjunto p r¶ oprio N p . Em outras palavras, Uma pa rte ¶ et ~ ao numerosa quanto o to do. 1 Esta pro priedade estranha (de um conjunto in¯nito) incomo dou muitos matem¶ a- ticos, inclusive Geo rg Canto r . F oi Richard Dedekind (1831{191 6) 2 que tornou esta 1 Uma diferen» ca not¶ avel em rela» c~ ao ao axioma de Euclides: \O todo ¶ e maio r que qualquer de suas pa rtes." (325 a.C.). 2 Richa rd Dedekind, um do s maior es matem¶ aticos, nasceu em 6 de outubro de 183 1, em Brunswick, Alemanha. De in ¶ ³cio, os interesses de Dedekind estavam na F ¶ ³s ic a e n a Qu ¶ ³mica; ele considerav a a Matem¶ atica meramente como uma serva das ci ^ encias. Mas isto n~ ao durou muito; ao s dezessete anos, 77 78 Conjuntos Enumer ¶ aveis e Conj untos N ~ ao E numer ¶ aveis p ropriedade a ca racter ¶ ³st ica de¯nidora de um conjunto in¯nito. A seguinte de¯ni» c~ ao foi dada p or Dedekind e m 1888. De¯ni» c~ ao 4.1 Um conjun to X ¶ e in¯nito quando p ossui um sub conjunto pr¶ oprio Y ,t a l que existe uma co rresp ond^ encia um- a-um entre X e Y . Um conjunto ¶ e ¯nito se n~ ao for in¯nito. Em outras palavras, um conjunto X ¶ e in¯nit o se e somente se exis te uma inje» c~ ao f : X ! X tal que f ( X ) ¶ e um sub conjunto p r¶ oprio de X . Logo, o conjunto N de numeros natur ais ¶ e um conjunto in¯nito. Exemplo 4.1 O conjunto ¿ e os conjuntos unit¶ arios 3 s~ ao ¯nitos. Solu» c~ ao. (a) Como o conjunto vazio n~ ao p ossui nenhu m sub conjunto pr¶ opri o , o conj u n t o vazio ¶ e ¯nito. (b) Seja f a g um conjunto unit¶ ario qualquer. Como o ¶ unico sub conjunto pr ¶ oprio de f a g ¶ e o conjunto vazio, e n~ ao h¶ a nenhuma c orresp ond^ encia biu n ¶ ³vo ca ent re f a g e ¿ , f a g ¶ e necessariamente ¯nito. Te o r e m a 4 . 1 (a) T o do sup erconjunto, de um conjunto in¯nito, ¶ ei n ¯ n i t o . (b) T o do sub conjunto, de um conjunto ¯nito, ¶ e¯ n i t o . Demonst ra» c~ ao. (a) Seja X um c onjunto in¯nito ¶ e e sej a Y um sup erc onjunto de X ,i . e . , X ½ Y . Ent~ ao, p ela De¯ni» c~ ao 4. 1, exi s te um a inje » c~ ao f : X ! X t al que f ( X ) 6 = X . De¯na uma fun» c~ ao g : Y ! Y po r g ( y )= ½ f ( y ) se y 2 X y se y 2 Y ¡ X Deixamos ao leito r veri¯car que a fun» c~ ao g : Y ! Y ¶ e injetora e que g ( Y ) 6 = Y . Segue ent~ ao, p ela De¯ni» c~ ao 4.1, que Y ¶ e in¯nito. (b) Seja Y um conju nto ¯nito e seja X um sub conjunto de Y , i.e., X ½ Y .P a r a demonstrar q ue X ¶ e ¯nito, sup omos o contr¶ ario, que X ¶ e in¯nito. Ent~ ao, por (a), o conjunto Y deve ser in¯nito. I sto ¶ e um a contradi» c~ ao. P ortanto, o conjunto X ¶ e¯ n i t o . ele havia se mudado , da F ¶ ³sica e da Qu ¶ ³mica, par a a Matem¶ atica, cuja l¶ o g i c aa c h a v am a i ss a t i s f a t ¶ oria. A o sd e z e n o v ea n o s ,m a t r i c u l o u - s en aU n i v e r s i d a d ed eG Ä ottingen pa ra estudar Matem ¶ atica, e recebeu seu grau de douto r tr^ es anos de p ois, sob a or ienta» c~ ao de Gauss. Sua contribui» c~ ao fundamental µ aM a t e m ¶ atic a inclui o famoso \co rte de Dedekind", um conceito importante no estudo de n¶ umeros irracionais, que o leito r po der¶ a ter a o portunidade de estuda r em um curso de an¶ alise real. 3 Um co nj un to uni t¶ ario ¶ e um conjunto que consiste de um ¶ unico elemento. Conjuntos Enumer ¶ aveis e Conjuntos N ~ ao Enumer ¶ aveis 79 Te o r e m a 4 . 2 Seja g : X ! Y uma co rresp ond ^ encia um-a-um. Se o conjunto X ¶ e in¯nito, ent~ ao Y ¶ e i n¯nito. Demonst ra» c~ ao. Como X ¶ e in¯nito, p ela De¯ni» c~ ao 4.1, e xis t e um a i n je» c~ ao f : X ! X tal que f ( X ) 6 = X . Como g : X ! Y ¶ e uma corresp ond ^ encia um-a-um, tam b¶ em o ¶ e g ¡ 1 : Y ! X (T eorema 3.14, Cap ¶ ³t ulo 3). T emos ago ra o seguinte diagrama de inje» c~ oes: YY g ¡ 1 ? ? y x ? ? g X ¡ ¡¡ ! f X Con seqÄ ue ntemente, a c omp osi» c~ ao h = g ± f ± g ¡ 1 : Y ! Y de inje» c~ oes ¶ eu m a inje» c~ ao [ Prob lema 7, Exerc ¶ ³cios 3.7.1]. Finalmente, temos h ( Y )=( g ± f ± g ¡ 1 )( Y )=( g ± f )( g ¡ 1 ( Y )) =( g ± f )( X )= g ( f ( X )) e g ( f ( X )) 6 = Y ,p o r q u e f ( X ) 6 = X . Logo, h ( Y ) ¶ e um sub conjunto p r¶ oprio de Y ,ep o r t a n t o Y ¶ e in¯nito. Co rol¶ ario 4.1 Seja g : X ! Y uma c o rresp ond^ encia um-a-um. S e o conjunto X ¶ e ¯nito, ent~ ao Y ¶ e¯ n i t o . Demonst ra» c~ ao. Exerc ¶ ³cio. Te o r e m a 4 . 3 Seja X um conjunto in¯ nito e seja x 0 2 X .E n t ~ ao X ¡f x 0 g ¶ e in¯nito. Demonst ra» c~ ao. Pela De¯ni» c~ a o 4. 1, ex ist e uma inj e» c~ ao f : X ! X tal que f ( X ) Ã X . H¶ a dois casos a se rem considera dos: (1) x 0 2 f ( X ) ,o u( 2 ) x 0 2 X ¡ f ( X ) .E m c a d a caso, devemos construir um a inje» c~ ao gX ¡f x 0 g : ! X ¡f x 0 g ,t a lq u e g ( X ¡f x 0 g ) 6 = X ¡f x 0 g . Caso 1. x 0 2 f ( X ) . Existe um elemento x 1 em X tal que f ( x 1 )= x 0 .U m a f u n » c~ ao g : X ¡f x 0 g! X ¡f x 0 g p o de agora ser de¯nida p o r g ( x )= ½ f ( x ) se x 6 = x 1 x 2 se x = x 1 2 X ¡f x 0 g 80 Conjuntos Enumer ¶ aveis e Conj untos N ~ ao Enum er ¶ aveis em que x 2 ¶ e um elemento do conjunto n~ ao vazio X ¡ f ( X ) , arbitra riamente ¯xado. Segue que gX ¡f x 0 g : ! X ¡f x 0 g ¶ e injetora e que g ( X ¡f x 0 g )= f ( X ¡f x 0 ;x 1 g ) [f x 2 g6 = X ¡f x 0 g .P o r t a n t o , X ¡f x 0 g ¶ e i n¯nito neste caso. Caso 2. x 0 2 X ¡ f ( X ) . De¯na uma fun» c~ ao g : X ¡f x 0 g! X ¡f x 0 g po r g ( x )= f ( x ) pa ra to do x 2 X ¡f x 0 g . Como f : X ! X ¶ e injeto ra, tamb ¶ em o ¶ e g : X ¡f x 0 g! X ¡f x 0 g . Finalmente, g ( X ¡f x 0 g )= f ( X ) ¡f f ( x 0 ) g6 = X ¡f x 0 g P ortanto, em qualquer caso, X ¡f x 0 g ¶ e in¯nito. No que segue, denotaremos por N k , k 2 N , o conjunto de to dos os n¶ ume ros naturais de 1 at ¶ e k ;i s t o ¶ e, N k = f 1 ; 2 ;::: ; k g . Como uma aplica» c~ ao do T eorema 4.3, mostramos no seguinte exemplo que cada N k ¶ e¯ n i t o . Exemplo 4.2 Par a c a d a k 2 N , o conjunto N k ¶ e¯ n i t o . Demonst ra» c~ ao. Demonst ra remos isto p elo p rinc ¶ ³pio de indu» c~ ao matem¶ atica. P elo Exem- plo 4.1, a a¯rma» c~ ao ¶ e verdadeira par a k =1 . Ago ra, sup onha que o conjunto N k ¶ e¯ n i t o pa ra algum n¶ ume ro natural k . C onsidere o conjunto N k +1 = N k [f k +1 g .S e N k +1 for in¯nito, ent~ ao, p elo T eo rema 4.3, N k +1 ¡f k +1 g = N k ser¶ a um conjunto in¯nito, o que contradiz a hip¶ ote se de indu» c~ ao. Logo, se N k ¶ e¯ n i t o ,e n t ~ ao N k +1 ¶ e ¯nito. P ortanto, p elo princ ¶ ³pio de indu» c~ ao matem¶ atica, o conjunto N k ¶ e ¯nito para cada k 2 N . Na verdade, existe uma conex~ ao ¶ ³ntima en tre um c onjunt o ¯nito n~ ao vaz i o e um conjunto N k . Te o r e m a 4 . 4 Um conjunto X ¶ e ¯nito se e soment e se X = ¿ ou X es t¶ a em corres- po n d ^ encia um-a-um com algum N k . Demonst ra» c~ ao. Se X ¶ ev a z i oo ue s t ¶ a em co rresp ond^ encia um-a -um com algum N k , ent~ ao, p e l o Corol¶ ario do T eorema 4.2, e Exemplos 4.1 e 4.2, o conjunto X ¶ e¯ n i t o . Pa ra mostrar a rec ¶ ³proca, mostramos, e quivalentemente, s ua contrapositiva: Se X 6 = ¿ e X n~ ao est¶ ae mc o r r e s p o n d ^ encia um-a-um com nenhum N k ,e n t ~ ao X ¶ e in¯nito. Podemos tomar um elem ento x 1 de X ,et e rn o v a m e n t e X ¡f x 1 g n~ ao vazio ; p ois, caso cont r¶ ario, ter ¶ ³amos X = f x 1 g em co rrespond ^ encia com N 1 , uma contradi» c~ ao com a hip¶ otese sobre X . Continuando desta maneira, s up onhamos que escolhemos elementos x 1 , x 2 , ::: , x k de X .E n t ~ ao X ¡f x 1 ;x 2 ;::: ;x k g ¶ en ~ ao vaz io; caso cont r¶ ario, tere mos X = f x 1 ;x 2 ; ::: ; x k g em corresp ond^ e ncia um-a-um com N k ,u m ac o n t r a d i » c~ ao com nossa hip¶ otese sob re X . Logo, p o demos sempre escolher um elemento x k +1 de X ¡f x 1 ;x 2 ;::: ;x k g . Ent~ ao, por indu» c~ ao matem¶ atica, para to do n¶ umero natural n , existe um subc onjunto Conjuntos Enumer ¶ aveis e Conjuntos N ~ ao Enumer ¶ aveis 81 pr ¶ oprio f x 1 ;x 2 ;::: ;x n g de X . Denotemos o conjunto dos x n 's escolhidos p or Y . 4 Ent~ ao a fun» c~ ao f : Y ! Y ¡f x 1 g , de¯nida p or f ( x k )= x k +1 pa ra to do k 2 N , estab e lece uma co rresp ond ^ encia um-a-um entre Y e seu sub c onj unto pr¶ oprio Y ¡f x 1 g . P o rtant o, p ela De¯ni» c~ ao 4.1, Y ¶ e in¯nit o e p o rtanto, p elo T eo rema 4.1, X ¶ e in¯nito. Menciona remos aqui que o T eorema 4.4 sugere uma de¯ni» c~ ao alternativa de c on- juntos ¯nitos e in¯nitos. Po demos de¯nir um conjunto como sendo ¯nito se e somente se ele ¶ e va zio ou est¶ a em co rresp ond^ encia um-a-um com a lgum N k , e sendo in¯nito se es o m e n t es en ~ ao ¶ e ¯nito. Dest a de¯ni» c~ ao alternativa, nossa De¯ni» c~ ao 4.1 p o de s er demonstrada como um teo rema. Entretanto, isto requeriria mais ou menos o mesmo montante de trabalho requerido p ela nossa presente ab o rdagem. 4.1.1 Ex erc ¶ ³cios 1. Complet e a demonst ra» c~ ao do T eo rema 1. 2. Seja g : X ! Y uma co rresp ond^ encia um-a- um. Demonstre que se X ¶ e ¯nit o, ent~ ao Y ¶ e¯ n i t o . 3. De monstre que os conjuntos Z , Q e R s~ ao in¯nitos. 4. De monstre que se A ¶ e um conjunto in¯nito, ent~ ao A £ A tamb¶ em o ¶ e. 5. Demonstre que se A e B s~ ao conjuntos in¯nitos, ent~ ao A [ B ¶ e um conjunto in¯nito. 6. Demonstre que a reuni~ ao de um n ¶ umero ¯nito de conjuntos ¯nitos ¶ e um c onjunto ¯nito. 7. Sejam A e B dois conjuntos tais que A [ B ¶ e in¯nito. Demonstre que ao menos um dos dois conjuntos A e B ¶ e in¯nit o. 8. Demonstre a seguinte generaliza» c~ ao do T eorema 4.3: Se Y ¶ e um sub co njunto ¯nito de um conjunto in¯nito X ,e n t ~ ao X ¡ Y ¶ e in¯nito. 4.2 Equip ot ^ encia de conjuntos Dois conjuntos ¯nitos X tem o mesmo n¶ umero de elementos se e somente se exist e uma co rresp ond ^ encia um- a-um f : X ! Y . Emb o ra a frase \mesmo n¶ umero de elementos" n~ ao se aplique aqui s e X e Y s~ ao in¯nitos, parece natural p ensa r que dois conjunto in¯ni- tos, que e stejam em c orrespond^ encia um- a- um, t em o mesmo tamanh o. F ormaliza remos esta intui» c~ ao como segue: De¯ni» c~ ao 4.2 Dois conjuntos X e Y dizem- se equip ote ntes , fato den otado p o r X » Y , quando exist e uma co rresp ond^ encia um- a-um f : X ! Y . 4 Aqui os auto res usaram implicitamente o \a xioma da escolha", um axioma importa nte a ser discutido no C ap ¶ ³tulo 6. Uma forma do axioma da esc olha p o de ser enunciada como: \Seja P um conjunto n~ ao vazio, de sub conjuntos n~ ao vazios de um conjunto dado X .E n t ~ ao existe um conjunto R ½ X tal que pa ra to do C 2 P , C \ R ¶ e um conjunto unit¶ ario". Este axioma ser¶ a usado em to das as pa rtes deste livro, sem ser explicitamente mencionado. 82 Conjuntos Enumer ¶ aveis e Conj untos N ~ ao Enum er ¶ aveis Obviamente, to do conjunt o ¶ e equip otente a si mesmo. Como a inversa de uma co rresp ond ^ encia um-a-um ¶ e uma co rrespond ^ encia um-a-um (T eorema 3.14), X » Y s ees o m e n t es e Y » X . Convencionaremos que o s ¶ ³mb olo f : X » Y signi¯ca r¶ a \ f : X ! Y ¶ e uma corresp ond^ enc ia um-a-um e portanto X » Y ". Us and o esta not a» c~ ao conveniente, a primeira metade do Problema 9, Exerc ¶ ³cios 3.7.1 p o de ser re-enunciado como: Se f : X » Y e g : Y » Z ,e n t ~ ao g ± f : X » Z . A cabamos de demonstrar ent~ ao o seguinte teorema. Te o r e m a 4 . 5 Seja I um conjunto de conjuntos e se ja R uma rela» c~ ao em I dada p or: X R Y se e somente se X e Y s~ ao memb ros d e I e X » Y .E n t ~ ao R ¶ e uma rela» c~ ao de equival ^ encia em I . No seguinte exemplo, os s ¶ ³mbolos ]0 ; 1[ e ] ¡ 1 ; 1[ denotam intervalos de n¶ umeros reais. Exemplo 4.3 (a) ]0 ; 1[ » ] ¡ 1 ; 1[ . (b) ] ¡ 1 ; 1[ » R ,e R » ]0 ; 1[ . Solu» c~ ao. (a) A fun» c~ ao f :] 0 ; 1[ ! ] ¡ 1 ; 1[ ,d a d ap o r f ( x )= 2 x ¡ 1 ,¶ e uma corresp on- d^ encia um-a- um. Po rtanto, ]0 ; 1[ » ] ¡ 1 ; 1[ . (b) A fun» c~ ao trigonom ¶ etrica g :] ¡ 1 ; 1[ ! R ,d a d ap o r g ( x )= t g ( ¼x = 2) ,¶ eu m a co rresp ond ^ encia um-a-um ; p o rtanto ] ¡ 1 ; 1[ » R . O leitor deveria veri¯car esta asser» c~ ao esb o» cando um gr¶ a¯co d e g ( x )=t g ( ¼x = 2) . U ma demonstra» c~ ao rigoro sa p o de ser obtida veri¯cando-se as seguintes duas observa» c~ oe s: (1) g :] ¡ 1 ; 1[ ! R ¶ ec o n t ¶ ³nua, e ilimitada, tanto superiormente como inferio rmente. (2) g 0 ( x )=( ¼= 2) sec 2 ( ¼x = 2) > 0 , 8 x , ) g ¶ e estrit amente cr escente . Como a \rela» c~ ao" de equip ot^ enc ia ¶ e transitiva, 5 ]0 ; 1[ » ] ¡ 1 ; 1[ e ] ¡ 1 ; 1[ » R implicam ]0 ; 1[ » R . Te o r e m a 4 . 6 Sejam X , Y , Z e W conjuntos com X \ Z = ¿ = Y \ W ,es e j a m f : X » Y e g : Z » W .E n t ~ ao f [ g :( X [ Z ) » ( Y [ W ) . Demonst ra» c~ ao. Como f : X ! Y e g : Z ! W s~ ao fun» c~ oes com X \ Z = ¿ ,p e l o Te o r e m a 3 . 8 , d o C a p ¶ ³tulo 3, f [ g : X [ Z ! Y [ W ¶ e uma fun» c~ ao. Deixa remos ao leitor a demonstra» c~ ao d e qu e esta ¶ ultima fun» c~ ao ¶ e uma correspond^ enc ia um-a-um. 5 F alando estritamente, \ » "n ~ ao ¶ eu m ar e l a » c~ ao de equival ^ encia, por que seu dom ¶ ³nio n~ ao ¶ eu m conjunto (veja T eorema 2.10 do Cap ¶ ³tulo 2). Mas p o demos cham¶ a-la uma rela» c~ ao se considera rmo-la de¯nida em qualquer conjunto de conjuntos I (T eo rema 4.5). Conjuntos Enumer ¶ aveis e Conjuntos N ~ ao Enumer ¶ aveis 83 Te o r e m a 4 . 7 Sejam X , Y , Z e W conjuntos tais que X » Y e Z » W .E n t ~ ao X £ Z » Y £ W . Demonst ra» c~ ao. Sej am f : X » Y e g : Z » W . De¯namos a fun» c~ ao f £ g : X £ Z ! Y £ W ,p o r ( f £ g )( x; z )=( f ( x ) ;g ( z )) pa ra to do ( x; z ) 2 X £ Z . P edimos ao leitor demonstrar que esta ¶ ultima fun» c~ ao ¶ e uma co rresp ond ^ encia u m-a-um. Examinando os v¶ arios conjuntos ¯nitos N k = f 1 ; 2 ; 3 ;::: ;k g , conforme k cresce, e notando que os conjuntos in¯nitos Z , Q ,e R (veja Problema 3, Exerc ¶ ³cios 4.1.1) s~ ao sup erconjuntos de N , parece que o \meno r" conjunto in¯nito ¶ e o conjunto N de to dos os n¶ umeros naturais, ou qualquer conjunto que seja equip otente a N . Aprenderemos em b reve, na Se» c~ ao 4.4, que nem to dos os conjuntos in¯nitos s~ ao equipo tentes a N . De¯ni» c~ ao 4.3 Um conjunto X ¶ ed i t os e r enumer¶ avel quando X » N . Um conjunto cont¶ avel ¶ e um conjunto ¯nito ou enumer¶ avel . Seja X um conjunto enumer¶ avel. Ent~ ao existe uma c orrespond^ encia biun ¶ ³voca f : X » N .S e d e n o t a m o s f (1) = x 1 ;f (2) = x 2 ;f (3) = x 3 ;::: ;f ( k )= x k ;::: ent~ ao X p o de ser denotado alte rnativamente p o r f x 1 ;x 2 ;x 3 ;::: ;x k ;::: g ; as retic^ encias ( ::: )s ~ ao usadas pa ra indica r que os elementos s~ ao etiquetados em uma o rdem de¯nida, confo rme indicado p e los ¶ ³ndices. Uma e xplica» c~ ao para o termo \con t¶ avel " est¶ aa g o r a em pauta. P a ra um conjunto ¯nito, ¶ et e o r i c a m e n t ep o s s ¶ ³vel contar seus elementos e o termo ¶ e adequado. Muito embora a contagem de fato de to dos os elementos de um conjunto enumer¶ av el X = f x 1 ;x 2 ;x 3 ;::: ; g sej a imp oss ¶ ³vel, o conjunto X est¶ ae m co rresp ond ^ encia biun ¶ ³vo ca com os n¶ ume ros de contagem, os n¶ umeros naturais. Te o r e m a 4 . 8 T o do sub conjunto in¯nito, de um conjunto enumer¶ avel, ¶ e enumer¶ avel. Demonst ra» c~ ao .S e j a Y um sub conjunto in¯nito de um conjunto enumer¶ av el X = f x 1 ; x 2 ;x 3 ;: : : g .S e j a n 1 om e n o r ¶ ³ndice pa ra o qual x n 1 2 Y ,es e j a n 2 om e n o r ¶ ³ndic e pa ra o qual x n 2 2 Y ¡ x n 1 . T endo de¯nido x n k ¡ 1 ,s e j a n k om e n o r ¶ ³ndice tal que x n k 2 Y ¡f x n 1 ;x n 2 ;::: ;x n k ¡ 1 g .U m t a l n k sempre existe pois Y ¶ e in¯nito, o que ga rante que Y ¡f x n 1 ;x n 2 ;::: ;x n k ¡ 1 g6 = ¿ pa ra cada k 2 N . De ste mo do, const ru ¶ ³mos uma correspond^ encia um-a -um f : Y » N , s endo f ( k )= x n k pa ra cada k 2 N .P o r t a n t o , Y¶ e enumer¶ avel. Uma de monstr a» c~ ao mais curta, p o r ¶ em menos intuitiva, do T eorema 4.8, ¶ e indicada no Problema 10 a o ¯nal desta se» c~ ao. O seguinte co r ol¶ ario ¶ eu m ac o n s e q Ä u^ encia ime diata da De¯ni» c~ ao 4.3 e do T eo rema 4.8. 84 Conjuntos Enumer ¶ aveis e Conj untos N ~ ao Enum er ¶ aveis Co rol¶ ario 4.2 T o do sub c onjunto de um conjunto cont¶ avel ¶ ec o n t ¶ avel. Mais exemplos e prop rieda des de conjuntos enumer¶ aveis s~ ao dados na pr¶ oxima se» c~ ao. 4.2.1 Ex erc ¶ ³cios 1. Complet e a demonst ra» c~ ao do T eo rema 6. 2. Complet e a demonst ra» c~ ao do T eo rema 7. 3. De monstre que se X e Y s~ ao dois conjuntos, ent~ ao X £ Y » Y £ X . 4. De monstre que se ( X ¡ Y ) » ( Y ¡ X ) ent ~ ao X » Y . 5. Demonstre a seguinte generaliza» c~ ao do T e o rema 4.6: Seja f X ° j ° 2 ¡ g e f Y ° j ° 2 ¡ g duas fam ¶ ³lias de c onjuntos disjuntos, tal que X ° » Y ° pa ra cad a ° 2 ¡ .E n t ~ ao S ° 2 ¡ X ° » S ° 2 ¡ Y ° . 6. Demonstre que se X ¶ e um conjunto enumer¶ avel e Y ¶ e um sub c onjunto ¯nito de X , ent~ ao X ¡ Y ¶ e enumer¶ avel. [Compa re com o Problema 8 , Exe rc ¶ ³cios 4.1.1.] 7. Demonstre que se X ¶ e um c onjunto enumer¶ avel e Y ¶ e um conj unto ¯nito, ent~ ao X [ Y ¶ ee n u m e r ¶ avel. 8. Dem onstre que o conjunto N p ,d et o d o so sn ¶ umeros naturais pares, e o conjunto N i , de to dos os n¶ umeros naturais ¶ ³mpares, s ~ ao enumer¶ aveis. 9. Seja A um conjunto n~ ao vazio, e seja 2 A o conjunto das fun» c~ oes de A no conjunto f 0 ; 1 g . Demonstr e que } ( A ) » 2 A . 10. Sejam X um conjunto enumer¶ avel e Y um sub conjunto i n¯nito de X .S e j a g : X » N ,es e j a h : Y ! N a fun» c~ ao de¯ nida p or h ( y )= n¶ umero de e lementos em f 1 ; 2 ; 3 ;::: ;g ( y ) g\ g ( Y ) Demonstre que h ¶ e uma co r resp ond^ encia um-a-um e que p o rtanto Y ¶ e enume r¶ avel . 4.3 Exemplos e p rop riedad es de conjuntos enume r¶ a- veis O conjunto N p de to dos os n¶ umeros naturais pares e o conjunto N i de todos os n ¶ umeros naturais ¶ ³mpares s~ ao enumer¶ aveis (Problema 8, Exerc ¶ ³ci o s 4.2. 1 ) . Com o a r eu n i~ ao N p [ N i (= N ) destes dois conjuntos enumer¶ av eis ¶ e e numer¶ avel, o p r¶ oximo t eorema deveria ser previs ¶ ³vel. Te o r e m a 4 . 9 A uni~ ao de dois conjuntos enumer¶ aveis ¶ e e numer¶ avel. Demonst ra» c~ ao .S e j a m A e B dois conjuntos enumer¶ aveis. Mostraremos que A [ B ¶ e enumer¶ a vel nos dois casos seguintes: Conjuntos Enumer ¶ aveis e Conjuntos N ~ ao Enumer ¶ aveis 85 Caso 1. A \ B = ¿ . Como A » N e N » N p ,t e m o s A » N p . De mo do semelhante, temos B » N i . ConseqÄ uente mente, p elo T e o rema 4.6, temos ( A [ B ) » ( N p [ N i )= N , o que demonstra que A [ B ¶ e enumer¶ av el. Caso 2. A \ B 6 = ¿ . Seja C = B ¡ A .E n t ~ ao A [ C = A [ B e A \ C = ¿ ; o conjunto C ½ B ¶ eo u ¯nito ou enumer¶ avel [Co rol¶ ario 4.2 do T eorema 4.8]. Se C ¶ e ¯nito, p elo Problema 7d o sE x e r c ¶ ³cios 4.2.1, A [ C ¶ e enumer¶ avel, e se C ¶ e enumer¶ avel, ent~ ao A [ C ¶ e enumer¶ avel, p elo caso 1 acima. P o rtanto, o conjunto A [ B ¶ e enumer¶ avel. Co rol¶ ario 4.3 Sejam A 1 ;A 2 ;::: ;A n conjuntos enumer ¶ aveis. Ent~ ao S n k =1 A k ¶ ee n u - mer¶ av el. Demonst ra» c~ ao . A demonstra» c~ ao ¶ e deixada ao leito r, como um exerc ¶ ³cio. Pe dimos ao leitor veri¯ca r o pr¶ oximo exemplo. Exemplo 4.4 O conjunto Z de to dos os inteiros ¶ e enumer¶ avel. Te o r e m a 4 . 1 0 O conjunto N £ N ¶ e enumer¶ avel. Demonst ra» c~ ao . Considere a f un» c~ ao f : N £ N ! N dada por f ( j; k )=2 j 3 k pa ra to do ( j; k ) 2 N £ N . Esta fun» c~ ao ¶ e i njeto ra, de mo do que N £ N » f ( N £ N ) ½ N : Como N £ N ¶ e in¯nito, f ( N £ N ) tamb¶ em o ¶ e. P elo T eo rema 4.8 , f ( N £ N ) ¶ e e numer¶ avel ep o r t a n t o N £ N ¶ e enumer¶ avel. Co rol¶ ario 4.4 Par a c a d a k 2 N ,s e j a A k um conjunto enum er¶ avel sat isfazend o A j \ A k = ¿ pa ra todo j 6 = k .E n t ~ ao S k 2 N A k ¶ e e numer¶ avel. 6 Demonst ra» c~ ao .P a r ac a d a k 2 N ,s e j a f k : N ! N £f k g uma fun» c~ ao dada p o r f k ( j )= ( j; k ) para t o do j 2 N . Clara mente, cada f k : N ! N £f k g ¶ e u ma corresp ond ^ encia um-a-um. Ou seja, N » N £f k g . Como A k » N e N » N £f k g pa ra cada k 2 N , temos A k » N £f k g pa ra cada k 2 N . Segue ent~ ao, do Problema 5 dos Exerc ¶ ³cios 4.2.1, que S k 2 N A k » S k 2 N N £f k g . Mas o conjunto S k 2 N N £f k g ¶ e igual ao conjunto enumer¶ avel N £ N .P o r t a n t o , S k 2 N A k ¶ e enumer¶ avel. 6 Este resultado ¶ e verdadeiro sem a hip¶ otese \ A k \ A j = ¿ para to do j 6 = k ." Veja Problema 7. 86 Conjuntos Enumer ¶ aveis e Conj untos N ~ ao Enum er ¶ aveis Exemplo 4.5 O conjunto Q de to dos o s n¶ u meros racionais ¶ e enumer¶ avel. Demonst ra» c~ ao . Re p resen ta remos cada n¶ umero racional de maneira ¶ unica como p=q , sendo p 2 Z , q 2 N eom ¶ aximo divisor comum de p e q ig ual a 1 .S e j a Q + o conjunto de tais elementos com p=q > 0 ,es e j a Q ¡ = f¡ p= q j p=q 2 Q + g .E n t ~ ao Q = Q + [f 0 g[ Q ¡ . ¶ E evidente que Q + » Q ¡ . Po rtanto, pa ra mostrar que Q ¶ e enumer¶ avel, ¶ e s u¯ciente mostrar que Q + ¶ e enumer¶ avel. P ara e ste p rop¶ osito, consideramos a f un» c~ ao f : Q + ! N £ N ,d a d a p o r f ( p=q )=( p; q ) . Como esta fu n» c~ ao ¶ e injetora, temos Q + » f ( Q + ) ½ N £ N . Como Q + , como um su p erconjunto de N ,¶ e in¯nito, f ( Q + ) ¶ e um sub conjunto in¯nito do conjunto enumer¶ avel N £ N .P o r t a n t o , f ( Q + ) ¶ e enumer¶ avel ec o n s e q Ä uentemente Q + ¶ e enumer¶ avel. A demonstra» c~ ao est¶ a agora completa. Op r ¶ oximo teorema indica que os conjunto enumer¶ aveis s~ ao, em um certo sentid o, os meno res em \tamanho" dentre os conjuntos in¯nitos. Te o r e m a 4 . 1 1 T o do conjunto in¯nito cont ¶ em um sub conjunto enumer¶ avel. Demonst ra» c~ ao .S e j a X um conjunto in¯nito qualquer. Ent~ ao X 6 = ¿ , de mo do que p o demos escolher um elemento, digamos x 1 , no conjunto X . A segu ir , seja x 2 um elemento em X ¡f x 1 g . De mo do seme lhant e, escolha um elemento x 3 do conjunto n~ ao vazio X ¡f x 1 ;x 2 g . T endo assim de ¯nido x k ¡ 1 , escolhemos um elemento x k no conjunto X ¡f x 1 ;x 2 ;::: ;x k ¡ 1 g .T a l x k existe para cada k 2 N , p o rque X ¶ e in¯nito, o que ga rante que X ¡f x 1 ;x 2 ;::: ;x k ¡ 1 g6 = ¿ pa r a to d o k 2 N . O conjunto f x k j k 2 N g ¶ e um sub conjunto enumer¶ avel de X , e a demonstra» c~ ao est¶ ac o m p l e t a . 4.3.1 Ex erc ¶ ³cios 1. Demonstre a ass er» c~ ao do Exemplo 4.3: O conjunto Z de to dos os inteiros ¶ ee n u - mer¶ av el. 2. De monstre o Corol ¶ ario 4.3 do T eorema 4.9. 3. De monstre que a uni~ ao de um n¶ ume ro ¯nito de conjuntos cont¶ aveis ¶ ec o n t ¶ av el. 4. Dem onstre que se A e B s~ ao conjuntos enumer¶ a veis, ent~ ao tamb¶ em o ¶ e A £ B .E m pa rticular, Z £ N , Z £ Z ,e Q £ Q s~ ao enume r¶ aveis. 5. Encontre uma fun» c~ ao inj et ora f : Q ! Z £ N ed ^ e uma demonst ra» c~ ao alternativa pa ra o Exemplo 4.5. 6. Demonstre que o conjunto dos c ¶ ³rculos no plano ca rtesiano, tendo raios racionais e c e n t r o se mp o n t o sc o ma m b a sa sc o o r d e n a d a sr a c i o n a i s ,¶ e enumer¶ av el. 7. Demonstre que se pa ra cada k 2 N , B k ¶ e um c onjunto enumer¶ avel, ent~ ao S k 2 N B k ¶ e enumer¶ avel. 4.4 Conjuntos n ~ ao en umer¶ aveis T o dos os conjuntos in¯nitos que vimos at¶ e o momento s~ ao enumer¶ a veis. Isto p o de leva r o leitor a indaga r se to dos os conjuntos in¯nitos s~ ao enumer¶ aveis. ¶ Ec o m u m e n t e

itc2004cap4 - Conjuntos Enumeráveis e Conjuntos Não Enumeráveis

UFPE

Fundamentos de Matemática

Continue navegando

Materiais relacionados

Perguntas relacionadas

Considerando esse contexto, sabemos que existe infinitos números naturais infinitos números reais. Sendo assim, compare a infinidade desses dois co...

1) Quando se estuda a teoria dos conjuntos, além das propriedades particulares existentes para cada um, existem tantas outras definições extremamen...

Em 1925 que Hilbert propôs no congresso internacional da matemática o paradoxo do infinito através do hotel de Hilbert. Durante a história do hotel...

Quando se estuda a teoria dos conjuntos, além das propriedades particulares existentes para cada um, existem tantas outras definições extremamente ...

Outros materiais