Cardinalidade de Conjuntos 2013 2

8/17/2019 Cardinalidade de Conjuntos 2013 2

1/23

Cardinalidade de Conjuntos:Conjuntos fnitos, infnitos,

enumeráveis e não-enumeráveis

Ana Maria Luz F. Amaral

Matemática Discreta 2!".2


2/23

#eor$e Cantor %!&'(-

!)!&*Matemático alemão #eor$e Cantor %!&'(-!)!&* + oinventor da moderna eoria dos Conjuntos e doscamados /meros ransfnitos. Atrav+s do seuoje 0amoso M+todo da Dia$onal 1ode-se

demonstrar um 0ato at+ então im1ensável: uee3istem infnitos maiores do ue outros4

5s conceitos matemáticos inovadores 1ro1ostos 1or Cantor en0rentaram uma resist6ncia si$nifcativa1or 1arte da comunidade matemática da +1oca. 5s

matemáticos modernos, 1or seu lado, aceitam1lenamente o tra7alo desenvolvido 1or Cantor nasua teoria dos conjuntos, reconecendo-a comouma mudan8a de 1aradi$ma da maior im1ort9ncia.

•“Deus criou os números naturais. O resto é obra dos

homens.” Leopold Kronecker (182!18"1#•“ $ teoria dos con%untos de &antor é uma moléstia' uma

doena per)ersa' da *ual al+um dia' os matem,ticos estar-ocurados.” enri /oincaré(180!1"12#•“in+uém nos e3pulsar, do para4so *ue 5eor+ &antor abriu

para n6s” Da)id ilbert (1872!1"#

http://pt.wikipedia.org/wiki/Ficheiro:Georg_Cantor.jpghttp://pt.wikipedia.org/wiki/Ficheiro:Georg_Cantor.jpg


3/23

umário Cardinalidade de Conjuntos: Conjuntos fnitos e infnitos Conjuntos enumeráveis e não-

enumeráveis %;otel de ;il7ert eM+todo da Dia$onal de Cantor*


4/23

Cardinalidade de

Conjuntosceinerman:

< 5 n/mero de elementos em um conjunto A se denota1or =A=. A cardinalidade de A nada mais + do ue o

n/mero de o7jetos no conjunto. Diz-se ue o conjunto + fnito se sua cardinalidade +

um inteiro. >m caso contrário, dizemos ue oconjunto + infnito?

>3em1los:

e A@!,2,"B, =A=@"

0|| =∅


5/23

Conjuntos fnitos e

infnitos. Menezes:Cardinalidade + defnida usando 0un8es 7ijetoras.

A cardinalidade de um conjunto A +:

Finita: se e3iste uma 7ije8ão entre A e o conjunto!,2,",..., nB 1ara al$um n 1ertencente aos aturais: =A=@n.

Enfnita: se e3iste uma 7ije8ão entre A e um su7conjunto1r1rio de A.

ortanto, um conjunto A + um: conjunto fnito %1ossui cardinalidade fnita* se 0or

1ossGvel re1resentá-lo 1or e3tensão Conjunto infnito se 0or 1ossGvel retirar al$uns elementos

de A e, mesmo assim, esta7elecer uma 7ije8ão com A.


6/23

>3: 5 conj. dos aturais +

infnito


7/23

Conjuntos enumeráveis e

não- enumeráveisDefni8ão %. Menezes*: Hm conjunto A + dito: Finitamente contável se 0or fnitoI Infnitamente contável ou enumerável: uando e3iste

uma 7ije8ão entre o conjunto A e um su7conjunto infnito de

E este caso 0 cama-se enumera8ão dos elementos de A.>screvendo-se 0%!*@a!, 0%2*@a2,..., 0%n*@an,... em-se entãoA@a!,a2,...,an,...B

Não contável: caso contrário


8/23

Conjuntos enumeráveis e

não- enumeráveis


9/23

>3em1lo: ;otel de ;il7ertJeremos um vGdeo ue mostra o

$erente do ;otel ;il7ert, ue

1ossui infnitos uartos, tratandoo 1ro7lema de acomodar novoss1edes uando o otel já teminfnitos s1edes. Cada s1edeem um uarto.

57serve ue o $erente 0ala ue ootel está lotado, no sentido deue á infnitos s1edes, masnão no sentido de ue não cai7a

mais s1edes.


10/23

;otel de ;il7ert: vGdeo da>ui1e M" da HECAM

%a1ro3idamente ! min*.


11/23

>3em1lo: ;otel de ;il7ertum 1rimeiro momento um novo s1ede ce$a e $ostaria de se

acomodar no otel. e o otel tivesse a1enas um n/merofnito de uartos, então + claro ue o reuerimento não1oderia ser cum1rido, mas como o otel 1ossui um n/meroinfnito de uartos então se movermos o s1ede do uarto !1ara o uarto 2, o s1ede do uarto 2 1ara o uarto " e assim1or diante, movendo o s1ede do uarto 1ara o uarto K!,1odemos acomodar o novo s1ede no uarto !, ue a$oraestá va$o. or um ar$umento análo$o + 1ossGvel alocar um

n/mero infnito (enumerável) de novos clientes %um ni7uscom infnitos 1assa$eiros*: a1enas mova o s1ede do uarto !1ara o uarto 2, o s1ede do uarto 2 1ara o uarto ', e em$eral do uarto 1ara o uarto 2, assim todos os uartos den/mero Gm1ar estarão livres 1ara os novos s1edes.

http://pt.wikipedia.org/wiki/Finitohttp://pt.wikipedia.org/wiki/Enumer%C3%A1velhttp://pt.wikipedia.org/wiki/Enumer%C3%A1velhttp://pt.wikipedia.org/wiki/Finito


12/23

>ntão, um desafo ainda maior se a1resenta ao $erente do ;otel

;il7ert: acomodar os 1assa$eiros de uma e3cursão com infnitos

ni7us cada um com infnitos 1assa$eiros. 5 $erente resolve este

1ro7lema realocando seus s1edes - desta vez, um s1ede ueesteja no uarto n deverá se mudar 1ara o uarto 2n . 5 $erente dis1e

de infnitas va$as novamente. De1ois, o $erente associa a cada ni7us

um n/mero 1rimo di0erente de dois. >ntão, ele acomoda os

1assa$eiros se$undo a se$uinte re$ra: o 1assa$eiro ue está na

cadeira n do ni7us 1 ocu1ará o uarto de n/mero 1 n

>3em1lo: ;otel de ;il7ert


13/23

>3em1lo: ;otel de ;il7erte ce$asse um $ru1o infnito de s1edes

ao ;otel de ;il7ert, contendo um novo

s1ede 1ara cada numero real, o $erente1oderia os1edá-los

ão, a se$uir veremos o 1or u6

57serve ue em todas as situa8es acima

sem1re conse$uimos enumerar a uantidadede s1edes e os uartos do ;otel, ou seja, +1ossGvel construir uma 7ije8ão entre e auantidade de s1edes e uma 7ije8ão entre

o n/mero de uartos


14/23

Hm conjunto


15/23

M+todo da dia$onal de

CantorOuando se tina conjuntos infnitos enumeráveis de s1edes 1ara se

os1edar no ;otel de ;il7ert, sem1re se conse$uia reor$anizar oss1edes, mas no momento ue voc6 tem uma uantidade infnita não-enumerável %n/meros Neais* sur$e um 1ro7lema, afnal e3istem infnitos


16/23

5s infnitos de Cantor:vGdeo da >ui1e M" da

HECAM %a1ro3idamente!' min*.


17/23

o caso do ;otel de;il7ert...


18/23

o caso do ;otel de;il7ert...


19/23

5 conjunto dos n/meros

Neais + não-enumerávelComo Cantor disse no vGdeo: Dois conjuntos tem amesma cardinalidade se + 1ossGvel construir uma7ije8ão entre eles. %. Menezes cama estesconjuntos de equipotentes 4

eorema: N + não enumerável.

Ed+ia da 1rova: ConstruGmos uma 7ije8ão entre N e@3 1ertencente a NIT3T!B@U,!V. eja 0:→N

Com o ar$umento da dia$onal de Cantor mostramosue U,!V + não enumerável, lo$o se N tem amesma cardinalidade de então N + não

enumerável.■


20/23

>3istem infnitos e não contáveis1ro7lemas 1ara os uais não e3isteualuer al$oritmo ca1az de solucioná-los4


21/23

>3ercGcio: Mostre ue oconjunto dos Erracionais +

não-enumarável


22/23

>3ercGcos >3ercGcios de W.! a W.) do aulo X.

Menezes, Matemática Discreta para

Computação e Inormática, 2a. edi8ão,a$ra Luzzatto Y Enstituto de En0ormáticada HFN#, orto Ale$re, 2Z.

>3ercGcios e8ão ".! do W( ao &' do [.L.

#erstin$, Fundamentos Matemáticos 1araa Ci6ncia da Com1uta8ão. (\ edi8ão, LC>ditora, Nio de [aneiro %2!*.


23/23

Ne0er6ncias aulo X. Menezes, Matemática Discreta para Computação eInormática, 2a. edi8ão, a$ra Luzzatto Y Enstituto de En0ormática daHFN#, orto Ale$re, 2Z. Ca1Gtulo W.

[.L. #erstin$, Fundamentos Matemáticos 1ara a Ci6ncia daCom1uta8ão. (\ edi8ão, LC >ditora, Nio de [aneiro %2!*. . !")-

!'2 >. N. ceinerman, Matemática Discreta, omson, ão aulo, 2Z.

1.( Nenata de Freitas, etrucio Jiana. ;otel de ;il7ert. Dis1onGvel em:

tt1:YYRRR.u].7rY$ru1odelo$icaYotel^il7ert^slides.1d0 ;otel de ;il7ert, vGdeo da >ui1e M" da HECAM %a1ro3idamente

! min*. Dis1onGvel em: tt1:YY_outu.7eY1j5J;z_^DJH %Acesso em!WYWY2!"*

5s infnitos de Cantor, vGdeo da >ui1e M" da HECAM%a1ro3idamente !' min*. Dis1onGvel em:tt1:YYm".ime.unicam1.7rYrecursosY!!2 %Acesso em !WYWY2!"*
http://www.uff.br/grupodelogica/hotel_hilbert_slides.pdfhttp://youtu.be/pjOVHzy_DVUhttp://m3.ime.unicamp.br/recursos/1120http://m3.ime.unicamp.br/recursos/1120http://youtu.be/pjOVHzy_DVUhttp://www.uff.br/grupodelogica/hotel_hilbert_slides.pdf

Documents

Cardinalidade de Conjuntos 2013 2