Conjuntos, aula 3

Conjuntos, aula 3

Numero de elementos de um conjunto - I MODULO 1 - AULA 4

Numero de elementos de um conjunto - I

O infinito! Nenhuma outra questao tem tocado tao profundamente o espırito humano.

David Hilbert Objetivos

Estudar os problemas que consistem em determinar o numero de elementos de um conjunto. Apresentar o Princıpio da Inclusao-Exclusao, que eu ma formula para o numero de elementos da uniao de dois conjuntos.

An ocao de contagem foi fundamental no desenvolvimento do homem.

E natural ao ser humano a atitude de agrupar objetos, animais, pessoas etc, ec onta-los. Isto e, formar conjuntos e contar seu numero de elementos.

Ar esolucao de muitos problemas consiste na contagem do numero de elementos de um certo conjunto. Por exemplo, contar o numero de solucoes de uma equacao ou de um problema. Em determinados casos, pode ser difıcil ate mesmo dizer se um determinado problema tem alguma solucao.

A frase que inicia nossa aula, do grande matematico David Hilbert, faz uma louvacao ao infinito. Isto numa aula onde nos propomos a encontrar o numero de elementos de um conjunto. Pois bem, realmente, a aula promete.

Antes de mais nada, vamos estabelecer um criterio que determina se um conjunto e finito ou infinito. Faremos isto usando a nocao de bijecao,i sto e, uma funcao f : X −→Y entre dois conjuntos X e Y tal que:

• Se a e b sao elementos de X tais que f(a)= f(b), entao a = b.D ito de outra maneira, se f(a) 6= f(b), entao a 6= b.

• Para todo elemento b ∈ Y , existe algum elemento de a ∈ X tal que f(a)= b.

Ou seja, uma bijecao entre dois conjuntos estabelece uma relacao um a um entre os seus elementos.

DISCRETADISCRETA MATEMTICA Numero de elementos de um conjunto - I

Por exemplo, a funcao f : {1,2,3,4,5,6,}−→ {2,4,6,8,10,12,... },

definida por f(x)= 2x,eu m bijecao entre o conjunto dos numeros naturais e o conjunto dos numeros pares.

Agora podemos dizer que um conjunto X e infinito se existe um subconjunto proprio Y ⊂ X eu ma bijecao f : X −→Y .

O exemplo acima mostra que o conjunto dos numeros naturais e infinito. Assim, quando um conjunto nao e infinito ele e chamado de finito.

Isto parece um pouco estranho, comecar pelo infinito, mais complicado.

Voce deve estar se perguntado: por que simplesmente nao contamos o numero dos elementos? O fato eq ue contar e uma aplicacao da nocao de bijecao. Com a nocao de bijecao podemos comparar conjuntos sem, necessariamente, contar o numero de seus elementos.

Vejaas eguinte historia:

Existia, ha muitos e muitos anos atras, uma tribo bem primitiva que habitava uma terra maravilhosa, onde nao havia terremoto, fazia calor o ano todo, enfim, era um paraıso. Esta tribo tinha uma cultura rica, eram sofisticados em varios setores das atividades humanas, mas nao havia desenvolvido a capacidade de contar. Isto e, seus habitantes nao conheciam, por assim dizer, numeros. No entanto, eles tinham muitas nocoes de Matematica, sendo que o chefe desta tribo era um matematico particularmente sagaz. Foi entao que, jab em proximo das grandes festas anuais da tribo, duas famılias rivais se envolveram em uma disputa. Cada uma delas afirmava ser mais forte do que a outra. O chefe, temendo que a disputa tivesse consequencias mais graves, chamou os representantes das duas famılias e disse que ele colocaria um fim na questao, mas exigia que as famılias aceitassem o seu veredito. Como ambas aceitaram as condicoes do chefe, ele estabeleceu que todos os membros das duas famılias comparecessem ao patio de dancas tribais naquela noite. Entao, a luz das tochas, o chefe tracou um linha que dividia o patio de um extremo ao outro e, na medida que os membros das famılias chegavam, ele os posicionava, dispondo um membro de cada famılia em frente a algum outro, da outra famılia, uma famılia de um lado da linha, a outra famılia do outro lado da linha. Assim, quando todos estiveram presentes, o chefe foi capaz de dizer, sem nenhuma duvida, qual famılia tinha mais membros do que a outra. Usando esta informacao ele deu o seu veredito.

Moral da historia: podemos comparar conjuntos sem, necessariamente, contar seus elementos.

Numero de elementos de um conjunto - I MODULO 1 - AULA 4

mos estabelecendo uma bijecao entre ele e o conjunto {1,2,3,4,,n}, onde

Quando contamos o numero de elementos de um conjunto finito, estan eos eu numero de elementos.

Note que, na pratica, poderemos ter dificuldade em contar o numero de elementos de um conjunto. Por exemplo, hau mn umero finito de estrelas na nosso galaxia, mas nao ha como conta-las.

Numeros transfinitos e a Hipotese do Contınuo.

Hav arios tipos de infinito. Existe mesmo uma aritmetica destes diversos infinitos: sao os numeros transfinitos, desenvolvidos por Cantor.

Os conjuntos dos numeros inteiros e racionais tem a mesma cardinalidade, enquanto que os numeros reais possuem uma cardinalidade maior.

AH ipotese do Contınuo afirma que nao hau m conjunto cuja cardinalidade esteja entre a dos numeros naturais e a dos numeros reais.

Um conjunto que nao e finito e chamado infinito.S ao exemplos de conjuntos infinitos o conjunto dos inteiros positivos, o conjunto dos numeros reais e o conjunto de palavras que podemos formar com nosso alfabeto.

Em alguns casos, nao ef acil descobrir se um certo conjunto e finito ou infinito. Vamos a dois exemplos que dizem respeito aos numeros primos:

— Existem infinitos numeros primos?

Ar esposta es im, e uma prova ja aparece no livro Elementos,d o matematico grego Euclides,h a cerca de 2300 anos.

Voce conhecerae sta demonstracao nesta disciplina. Ela estan a aula 29, no modulo de logica, como um exemplo do metodo da contradicao.

Por outro lado, dois primos sao chamados primos gemeos, se sua diferenca e 2. Por exemplo, 3 e 5, 5 e 7, 1 e 13, 17 e 19, sao primos gemeos.

— Existem infinitos primos gemeos?

Ar esposta e desconhecida, embora os matematicos tentem solucionar este problema hav arios seculos.

Denotaremos por n(A) on umero de elementos de um conjunto finito A. O conjunto vazio nao tem elementos; portanto n(∅)=0 .

Se A e B sao dois conjuntos disjuntos, entao n(A∪B)= n(A)+ n(B), pois se x ∈ A∪B entao x ∈ A ou x ∈ B,m as x nao pode estar em ambos A e B,j aq ue A ∩ B = ∅.

Por exemplo, o numero total de pessoas em uma festa e igual ao numero de homens mais o numero de mulheres, ja que toda pessoa eu mh omem ou uma mulher, mas nao ambos.

A diferenca entre estes dois numeros e6 − 5= 1= n(A ∩ B). Assim, neste exemplo vale que

DISCRETADISCRETA MATEMTICA Numero de elementos de um conjunto - I

De fato, e sempre verdadeiro o seguinte:

princıpio de inclusao-exclusao Se A e B sao dois conjuntos finitos, entao

Para entender, observe o diagrama a seguir, onde vemos que A ∪ B pode ser visto como a uniao de tres conjuntos disjuntos:

x zy AB

Exemplo 26

Uma pesquisa em uma turma de graduacao em Matematica, de 60 alunos, revelou que 40 deles pretendem fazer Licenciatura e 30 deles pretendem fazer Bacharelado.

Supondo que todo aluno da turma queira fazer Bacharelado ou Licenciatura, decida quantos alunos esperam fazer Licenciatura e Bacharelado.

Solucao: Vamos considerar os seguintes conjuntos:

B = {alunos que querem fazer Bacharelado} L = {alunos que querem fazer Licenciatura}

Portanto, 10 alunos nesta turma esperam fazer Bacharelado e Licenciatura. O problema pode ser representado pelo diagrama

Numero de elementos de um conjunto - I MODULO 1 - AULA 4

Uma outra solucao seria usarmos uma variavel. Como nao sabemos quanto e n(B ∩ L), vamos escrever n(B ∩ L)= x. Agora completamos o diagrama.

30-x xBL 40-x

Substituindo o valor obtido de x no diagrama acima, obtemos o numero de elementos de todas as partes de B ∪ L.

Exemplo 27

Uma pesquisa foi realizada com pessoas que leem revistas semanais. Entrevistando 200 pessoas, descobriu-se o seguinte:

85 pessoas compram a revista A, 75 pessoas compram a revista B, 65 pessoas compram a revista C, 30 pessoas compram as revistas A e B, 25 pessoas compram as revistas A e C, 20 pessoas compram as revistas B e C, 10 pessoas compram as tres revistas.

DISCRETADISCRETA MATEMTICA Numero de elementos de um conjunto - I

Com base nestes dados, responda ao seguinte:

a) Quantas pessoas compram pelo menos uma das revistas? b) Quantas pessoas nao compram nenhuma das tres revistas? c) Quantas pessoas compram exatamente uma das revistas? d) Quantas pessoas compram exatamente duas das revistas?

Solucao:

Seja U o conjunto das pessoas que foram entrevistadas. Sejam

B = {x ∈ U | x compra a revista B} C = {x ∈ U | x compra a revista C} O diagrama ao lado representa a situacao.

Comecemos com a regiao que representa o conjunto das pessoas que compram as tres revistas. Este e o conjunto A ∩ B ∩ C e tem 10 elementos.

Em seguida, consideramos as intersecoes de dois conjuntos. Um total de 30 pessoas compra as revistas A e B,i sto e, n(A ∩ B) = 30. Portanto, compram apenas as revistas A e B.

Analogamente, n(A∩C) = 25. Portanto, 25−10 = 15 pessoas compram apenas as revistas A e C.

Por ultimo, n(B ∩ C) = 20. Portanto, 20 − 10 = 10 pessoas compram apenas as revistas B e C.

Com as informacoes obtidas ate agora, temos o diagrama da figura ao lado.

Op roximo passo e determinar o numero de pessoas que compram apenas ar evista A, apenas ar evista B ou apenas ar evista C.

Numero de elementos de um conjunto - I MODULO 1 - AULA 4

Vejamos, n(A) = 85. Subtraindo o numero dos que compram outras revistas, temos:

Portanto, 40 pessoas compram apenas a revista A. Analogamente, n(B) = 75. Logo, pessoas compram apenas a revista B. Finalmente n(C) = 65. Portanto,

Agora podemos acabar de preencher o diagrama e passar a responder as perguntas:

a) Somando o numero de elementos de todas as partes de A ∪ B ∪ C, obtemos

Portanto, 160 pessoas compram pelo menos uma das tres revistas. b) Como n(U) = 200, entao pessoas nao compram nenhuma das tres revistas.

c) Temos que 40 pessoas compram apenas revista A, 35 compram apenas revista B e 30 compram apenas revista C. Portanto,

40+35+30 = 105 pessoas compram apenas uma das revistas.

DISCRETADISCRETA MATEMTICA Numero de elementos de um conjunto - I d) Temos que 20 pessoas compram revistas A e B,m as nao C; 15 pessoas compram revistas A e C,m as nao B; 10 pessoas compram revistas B e C,m as nao A. Portanto,

Em particular, se A e B sao disjuntos,e ntao n(A ∩ B) = 0 e logo,

Portanto, se dois conjuntos sao disjuntos, o numero de elementos de sua uniao eas oma dosn umeros de elementos destes conjuntos. Isto e,

Resumo

Nesta aula iniciamos o estudo de problemas que envolvem a determinacao do numero de elementos de um certo conjunto. Vimos que os conjuntos se dividem em conjuntos finitos,q ue sao os que possuem um certo numero de elementos, e os conjuntos infinitos.

Para oc asod a uniao de dois conjuntos, vimos a formula n(A ∪ B)= n(A)+ n(B) − n(A ∩ B), chamada de “princıpio da inclusao-exclusao”.

Na proxima aula, continuaremos a discussao da questao do numero de elementos da uniao de conjuntos.

Numero de elementos de um conjunto - I MODULO 1 - AULA 4

Exercıcios

DISCRETADISCRETA MATEMTICA Numero de elementos de um conjunto - I

Apendice: As somas infinitas

Aq uestao finito versus infinito e fundamental e estap resente emt oda a

Historia da Matematica. Anaximandro (610-540a.C.), que foi contemporaneo de Tales de Mileto, inaugurou esta polemica posicionando-se a favor do Tales de Mileto foi o primeiro matematico cujo nome ficou registrado na

Historia. Ele previu o eclipse solar que ocorreu sobre a

Grecia e a Mesopotamia no dia 28 de maio de 585a.C.

infinito. Para explicar como o Mundo poderia ser construıdo, ele foi alem das ideias correntes da epoca, de massas elementares, a saber: fogo, ar, terra eagua. Ele concebeu algo ainda mais primitivo, que descreveu com o termo grego apeiron, que pode ser traduzido como ilimitado ou infinito.

Outro debatedor ilustre foi Aristoteles, que era favoravel a um modelo finito do universo. Confrontado com a sequencia 1,2,3,4,5,...,o modelo basico de algo infinito, ele responderia com o argumento de que esta sequencia so existe na mente humana, sendo assim um “infinito virtual”, por assim dizer.

No entanto, o infinito sempre teve muita forca dentro da Matematica.

Foi usando estas ideias de maneira engenhosa que Arquimedes atingiu seus maiores triunfos, calculando areas e volumes de figuras e de solidos nao regulares, tais como areas delimitadas por trechos de parabolas e o volume da intersecao de cilindros de mesmo raio.

Para que o uso pleno destas ideias fosse feito, foi preciso esperar muito tempo, ate que as nocoes de calculo diferencial e integral fossem estabeleci- Voce estudarae sses topicos nas disciplinas de Calculo. das.

E famoso o fascınio que as somas infinitas exerceram sobre os Matematicos desde os tempos mais remotos. Este tipo de problema foi o que atraiu a atencao de Gottfried Wilhelm Leibniz (1646-1716), um dos co-inventores do Calculo, juntamente com Sir Isaac Newton (1642-1727), para a Matematica. Leibniz iniciou sua carreira como diplomata e foi numa de suas missoes em Paris, que conheceu o cientista Christian Huygens, assim como a fina flor da intelectualidade francesa. Huygens desafiou Leibniz a calcular a soma da serie

+

isto e, a soma dos inversos dos numeros triangulares. Leibniz encantou-se

Para saber mais sobre numeros triangulares, veja a

Aula 12 deste modulo de Matematica Discreta.

com estes assuntos e apresentou a solucao a seguir:

Numero de elementos de um conjunto - I MODULO 1 - AULA 4

Usando isto, ele reescreveu a serie original da seguinte maneira:

+=2 
+

Ar esposta2 e correta.

Apesar de engenhosa, uma verdadeira poesia Matematica, a solucao de

Leibniz esta errada. E como acontece, as vezes, na Matematica: chega-se a resposta correta de maneira errada. Na verdade, foi um puro golpe de sorte.

Observe que ele tambem poderia ter feito o seguinte:2 2− 3

E agora, usando a mesma argumentacao, temos

+=2 

DISCRETADISCRETA MATEMTICA Numero de elementos de um conjunto - I

Voce pode explicar isto? Onde estaoe rro?

As identidades algebricas certamente estao corretas. O problema esta no uso de uma propriedade que sabemos ser verdadeira para somas finitas em uma “soma infinita”.

Para fazer estas somas especiais e preciso usar a nocao de convergencia, que voce aprendera na disciplina chamada Analise.

Ar azao pela qual sabemos que a resposta de Leibniz e correta ea seguinte: ep ossıvel calcular a soma de um numero arbitrario de termos da

Em geral, Vocev eraad emonstracao

desta formula na Aula 29 desta disciplina, como um exemplo do metodo de demonstracao chamado inducao finita.

++ 1
++
+converge para 2.

Bom, voce agora ja percebe que a passagem de finito para infinito e delicada. Mas este tipo de coisa e que torna a Matematica tao rica e fascinante e vocet era muito em breve, a oportunidade de lidar com estes conceitos.

Comentários