106
Introdução à Teoria dos Conjuntos JOAO CARLOS VIEIRA SAMPAIO Departamento de Matemática. UFSCar. SP

JOAO CARLOS VIEIRA SAMPAIO - ee.ufpe.br · Nesta se»c~ao discutiremos os conectivos » e ^, adiando os demais conectivos, _, ... Cada uma destas quatro possibilidades ¶e coberta

  • Upload
    vokien

  • View
    212

  • Download
    0

Embed Size (px)

Citation preview

Introdução à Teoria dos Conjuntos

JOAO CARLOS VIEIRA SAMPAIO

Departamento de Matemática. UFSCar.

SP

1

L¶ogica Elementar

Neste cap¶³tulo, apresentamos uma introdu»c~ao µa l¶ogica, que nos ser¶a su¯ciente comoferramenta de trabalho nos cap¶³tulos posteriores.

1.1 Proposi»c~oes e seus conectivos

O estudo da l¶ogica ¶e o estudo dos princ¶³pios e m¶etodos usados para distinguir argumentosv¶alidos dos n~ao v¶alidos. O prop¶osito deste cap¶³tulo preliminar em l¶ogica ¶e ajudar o leitora entender os princ¶³pios e m¶etodos usados em cada passo de uma demonstra»c~ao.

O ponto de partida em l¶ogica ¶e o termo \proposi»c~ao", que ¶e usado num sentidot¶ecnico. Por uma proposi»c~ao queremos dizer uma declara»c~ao que ¶e verdadeira ou falsa,mas n~ao ambos. N~ao ¶e necess¶ario que saibamos se a proposi»c~ao ¶e verdadeira ou falsa;a ¶unica quali¯ca»c~ao exigida ¶e que ela deve ser de¯nitivamente uma coisa ou outra.Habitualmente, podemos determinar imediatamente se uma proposi»c~ao ¶e verdadeira oufalsa, mas em alguns casos um pouco de esfor»co ¶e preciso, e em outros casos podeser imposs¶³vel chegar a uma conclus~ao. Os seguintes exemplos dever~ao ilustrar o quequeremos dizer.

Exemplo 1.1 Cada uma das seguintes frases ¶e uma proposi»c~ao.

(a) Londrina ¶e uma cidade no estado do Paran¶a.(b) 2 + 1 ¶e 5.(c) O d¶³gito na 105a casa decimal, na expans~ao decimal de

p3, ¶e 7.

(d) A lua ¶e feita de queijo mineiro.(e) N~ao h¶a vida inteligente em Marte.(f) Est¶a chovendo.

Claramente, (a) ¶e verdadeira, enquanto (b) e (d) s~ao falsas. Podemos ter d¶uvidasquanto ao status (verdadeiro ou falso) de (c) e (e). A veracidade ou falsidade da senten»ca(f) depende das condi»c~oes meteorol¶ogicas no instante em que essa declara»c~ao ¶e feita.

1

2 L¶ogica Elementar

Exemplo 1.2 Nenhuma das frases seguintes ¶e uma proposi»c~ao, porque n~ao faz sentidoquestionar se alguma delas ¶e verdadeira ou falsa.

(a) Venha µa nossa festa!(b) Tudo bem com voce?(c) Tiau, benzinho.

As proposi»c~oes do Exemplo 1.1 s~ao todas proposi»c~oes simples. Uma combina»c~aode duas ou mais proposi»c~oes ¶e uma proposi»c~ao composta. Por exemplo, \2 + 1 ¶e 5e o d¶³gito na 105a casa decimal na expans~ao decimal de

p3 ¶e 7" ¶e uma proposi»c~ao

composta.

Estamos familiarizados com o uso de letras para representar n¶umeros na ¶algebra.No estudo da l¶ogica usamos letras, tais como p, q, r, : : : para representar proposi»c~oes.Uma letra, tal como p, pode representar uma proposi»c~ao simples ou composta. A menosque digamos em contr¶ario, usaremos letras mai¶usculas P , Q, R, : : : para representarproposi»c~oes compostas. Existem muitos modos de se ligar proposi»c~oes tais como p,q, r, : : : para formar proposi»c~oes compostas, mas apenas cinco modos s~ao usadosfreqÄuentemente. Estes cinco conectivos comuns s~ao (a) \n~ao", simbolizado por »;(b) \e", simbolizado por ^; (c) \ou", simbolizado por _; (d) \se : : : ent~ao : : : ",simbolizado por !; e (e) \ : : : se e somente se : : : ", simbolizado por $.

Nesta se»c~ao discutiremos os conectivos » e ^, adiando os demais conectivos, _,!, e $, at¶e a pr¶oxima se»c~ao.

Seja p uma proposi»c~ao. A proposi»c~ao » p, lida \n~ao p" ou \a nega»c~ao de p", ¶everdadeira quando a proposi»c~ao p ¶e falsa, e ¶e falsa quando p ¶e verdadeira. Por exemplo,seja p a proposi»c~ao \Este ¶e um curso f¶acil". Ent~ao sua nega»c~ao » p representa \Esten~ao ¶e um curso f¶acil".

A verdade de » p depende da verdade de p. ¶E conveniente anotar essa dependenciaem uma tabela verdade:

Tabela 1.1:

p » pV F

F V

na qual as letras V e F signi¯cam \verdadeiro" e \falso", respectivamente. Na primeiracoluna da tabela 1.1, listamos os dois poss¶³veis valores l¶ogicos da proposi»c~ao p, sendo elesV e F . Cada linha em uma tabela verdade representa um caso que deve ser considerado,e claramente, nesta situa»c~ao bastante simples, h¶a apenas dois casos. Usando as linhasda Tabela 1.1 vemos que se p ¶e verdadeira ent~ao » p ¶e falsa, e se p ¶e falsa, ent~ao » p ¶everdadeira. ConseqÄuentemente, a Tabela 1.1 nos diz o valor verdade1 de » p em cadacaso.

1ou valor l¶ogico (N. do T.)

L¶ogica Elementar 3

De¯ni»c~ao 1.1 O conectivo ^ pode ser colocado entre duas proposi»c~oes p e q paraformar uma proposi»c~ao composta p ^ q cujos valores verdade s~ao dados na seguintetabela verdade.

Tabela 1.2:

p q p ^ qV V V

V F F

F V F

F F F

O s¶³mbolo p ^ q ¶e lido \p e q" ou \conjun»c~ao de p e q". Por exemplo, seja pa proposi»c~ao \O c¶eu ¶e azul" e seja q a proposi»c~ao \As rosas s~ao vermelhas". Ent~ao aconjun»c~ao p ^ q representa \O c¶eu ¶e azul e as rosas s~ao vermelhas". Numa proposi»c~aocomposta, tal como p ^ q, as proposi»c~oes individuais p e q s~ao chamadas componentes.Uma componente pode ser uma proposi»c~ao simples ou uma proposi»c~ao composta. Numaproposi»c~ao composta com duas componentes, tal como p ^ q, existem no m¶aximo 4 (=2£ 2) possibilidades, chamadas possibilidades l¶ogicas, a serem consideradas; sendo elas:(1) p ¶e verdadeira e q ¶e verdadeira;(2) p ¶e verdadeira e q ¶e falsa;(3) p ¶e falsa e q ¶e verdadeira;(4) p ¶e falsa e q ¶e falsa.

Cada uma destas quatro possibilidades ¶e coberta nas quatro linhas da Tabela 1.2.A ¶ultima coluna d¶a os valores verdade de p ^ q. Uma inspe»c~ao mostra que p ^ q ¶everdadeira em apenas um caso. Isto ¶e, p^ q ¶e verdadeira quando ambas as componentess~ao verdadeiras, e nos outros tres casos p ^ q ¶e falsa. O leitor sensato perceber¶a que aTabela 1.2 re°ete o modo pelo qual a conjun»c~ao \e" ¶e usada no portugues cotidiano.

Usando as Tabelas 1.1 e 1.2, podemos encontrar valores verdade de proposi»c~oescomplicadas envolvendo os conectivos » e ^.

Exemplo 1.3 Construa a tabela verdade para a proposi»c~ao composta

» [(» p) ^ (» q)]

Solu»c~ao.

Se o m¶etodo usado na constru»c~ao da Tabela 1.3 n~ao ¶e ¶obvio, uma palavra deexplica»c~ao pode ajudar. Os cabe»calhos s~ao selecionados de modo que a proposi»c~aocomposta (¶ultima coluna) ¶e gradualmente constru¶³da a partir de suas v¶arias componentes.

4 L¶ogica Elementar

Tabela 1.3:

p q » p » q (» p) ^ (» q) » [(» p) ^ (» q)V V F F F V

V F F V F V

F V V F F V

F F V V V F

Passo 1 1 2 3

As duas primeiras colunas simplesmente registram todos os casos para os valoresverdade de p e q. Usamos ent~ao a Tabela 1.1 para obter as entradas nas terceira e quartacolunas, os valores verdade correspondentes para » p e » q. No pr¶oximo passo usamosas entradas das terceira e quarta colunas e a Tabela 1.2 para obter as entradas na quintacoluna. Finalmente, as entradas da quinta coluna e a Tabela 1.1 d~ao as entradas na sextacoluna|os valores verdade de » [(» p) ^ (» q)]. O estudante aplicado deveria agoracopiar esta ¶ultima proposi»c~ao composta, fechar o livro, e tentar reproduzir a Tabela 1.3.

A proposi»c~ao no exemplo acima, » [(» p) ^ (» q)], usa parenteses e colchetespara indicar a ordem segundo a qual os conectivos se aplicam. FreqÄuentemente, umaexpress~ao pode ser simpli¯cada se pudermos eliminar alguns dos parenteses ou colchetes.A conven»c~ao habitual ¶e concordar que » tem prioridade sobre ^, isto ¶e, o conectivo »deve ser aplicado primeiro. Assim, por exemplo, a express~ao (» p)^ (» q) ¶e simpli¯cadana forma » p ^ » q.

1.1.1 Exerc¶³cios

Nos problemas de 1 a 10, uma senten»ca em portugues ¶e dada. Determine se a senten»ca¶e uma proposi»c~ao (S) ou n~ao (N).

1. Em 7 de junho de 1442 nevou em algum lugar no Rio Grande do Sul.2. Arist¶oteles tinha p¶es chatos.3. O socialismo est¶a errado.4. O homem mais rico do mundo ¶e o Sr. Malagutti, de S~ao Carlos.5. Joana e Pedro s~ao pessoas boas.6. Quanto vale este carro?7. Saia da grama.8. Use sempre cinto de seguran»ca.9. O n¶umero 2987654321 + 37 ¶e primo.10. Beethoven escreveu algumas das m¶usicas de Chopin.11. Dentre as proposi»c~oes dadas nos problemas de 1 a 10, indique aquelas que voceacha que devem ser verdadeiras (V) ou falsas (F), e aquelas cujo status pode ser dif¶³cildeterminar.

L¶ogica Elementar 5

Nos problemas 12 a 19 encontre as tabelas verdade das proposi»c~oes dadas. Use oformato da Tabela 1.1 ou da Tabela 1.2 para os dois ou quatro casos respectivamente.

12. » (» p) 13. » [» (» p)]14. p ^ p 15. » (p^ » p)16. p^ » q 17. » p ^ q18. (p ^ p)^ » p 19. » (p ^ q)

20. Numa proposi»c~ao composta, envolvendo tres componentes distintas p, q e r, quantoscasos s~ao necess¶arios para cobrir todas as possibilidades l¶ogicas? Quantos casos s~aonecess¶arios se houver quatro componentes distintas? Quantos casos s~ao necess¶arios sehouver n componentes distintas?21. O seguinte ¶e uma tentativa de arranjar todos os casos em uma tabela verdade, parauma proposi»c~ao envolvendo tres componentes p, q, e r. Complete o trabalho inacabado.

p q r ¢V V

V V F

V V

V F

V V

V F

F F

F F

Nos problemas 22 a 25, encontre as tabelas verdade para as proposi»c~oes dadas.Use o padr~ao desenvolvido no problema 21 para os v¶arios casos.

22. (p ^ q) ^ r 23. p ^ (q ^ r)24. (p^ » q) ^ r 25. » q ^ (r ^ p)

1.2 Tres conectivos mais

Na l¶³ngua portuguesa h¶a uma ambigÄuidade envolvida no uso do \ou". A proposi»c~ao\Obterei grau de mestre ou grau de doutor" indica que quem o a¯rma pode obterambos, o grau de mestre e o de doutor. Mas em outra proposi»c~ao, \Me casarei comL¶³via ou L¶ucia", a palavra \ou" signi¯ca que apenas uma das duas mo»cas ser¶a escolhida.Na matem¶atica e na l¶ogica, n~ao podemos permitir ambigÄuidades. Portanto, devemosnos decidir sobre o signi¯cado da palavra \ou".

6 L¶ogica Elementar

De¯ni»c~ao 1.2 O conectivo _ pode ser colocado entre duas proposi»c~oes quaisquer p eq para formar a proposi»c~ao composta p _ q. Os valores verdade de p _ q s~ao de¯nidosna Tabela 1.4. Portanto _ ¶e de¯nido como sendo o \ou" inclusivo, tal como usado naprimeira proposi»c~ao acima.

Tabela 1.4:

p q p _ qV V V

V F V

F V V

F F F

O s¶³mbolo p_q ¶e lido \p ou q" ou a \disjun»c~ao de p e q". Repare que a conjun»c~aode p e q ¶e verdadeira apenas quando as duas componentes s~ao ambas verdadeiras (Tabela1.2), enquanto que a disjun»c~ao ¶e falsa quando e apenas quando as duas componentess~ao falsas (Tabela 1.4).

Comparemos as tabelas verdade de p _ q e » (» p^ » q), nas Tabelas 1.3 e1.4. Notamos que em cada caso a ¶ultima coluna ¶e V V V F , de modo que estas duasproposi»c~oes tem os mesmos valores verdade em cada uma das quatro possibilidadesl¶ogicas. Mostrar que certas proposi»c~oes tem os mesmos valores verdade em cada caso ¶euma parte importante da l¶ogica. Na verdade, a l¶ogica trata duas tais proposi»c~oes comosendo uma s¶o.

De¯ni»c~ao 1.3 Quando duas proposi»c~oes P e Q, simples ou compostas, tem os mes-mos valores verdade em cada uma de todas as possibilidades l¶ogicas, dizemos que P ¶elogicamente equivalente ou simplesmente equivalente a Q, e escrevemos P ´ Q.

Resumidamente, duas proposi»c~oes s~ao logicamente equivalentes desde que tenhama mesma tabela verdade. Portanto, temos

p _ q ´» (» p^ » q)Embora duas proposi»c~oes equivalentes sejam consideradas como a mesma, do ponto devista da l¶ogica, preferimos a proposi»c~ao mais simples \p ou q" em vez da proposi»c~aoequivalente mais complicada \N~ao ¶e verdade que nem p e nem q".

De¯ni»c~ao 1.4 O conectivo ! ¶e chamado condicional e pode ser colocado entre duasproposi»c~oes p e q para formar a proposi»c~ao composta p ! q (lida: \se p ent~ao q").Por de¯ni»c~ao, a proposi»c~ao p! q ¶e equivalente µa proposi»c~ao » (p^ » q), e os valoresverdade de p! q s~ao dados na Tabela 1.5.

L¶ogica Elementar 7

Tabela 1.5:

Caso p q » q p^ » q p! q [´» (p^ » q)]1 V V F F V

2 V F V V F

3 F V F F V

4 F F V F V

A motiva»c~ao da De¯ni»c~ao 1.4 ¶e a seguinte. Sejam p a proposi»c~ao \O sol est¶abrilhando" e q a proposi»c~ao \Eu estou jogando tenis". Ent~ao a proposi»c~ao compostap ! q ¶e \Se o sol est¶a brilhando ent~ao eu estou jogando tenis". Agora, quando ¶e queuma tal proposi»c~ao 'considerada falsa? Claramente p! q ¶e falsa se o sol est¶a brilhandomas eu n~ao estou jogando tenis, e apenas neste caso. Em outras palavras p! q ¶e falsase p^ » q ¶e verdadeira, a apenas neste caso. Mas isto ¶e precisamente a De¯ni»c~ao 1.4.Estudaremos agora a tabela verdade de p! q, isto ¶e, de » (p^ » q).

Conforme a De¯ni»c~ao 1.4, o signi¯cado da proposi»c~ao condicional p! q afasta-seradicalmente do nosso uso ordin¶ario de \Se p ent~ao q". Na nossa linguagem ordin¶aria,2

uma senten»c~ao da forma \Se p ent~ao q" ¶e considerada como querendo dizer que q ¶everdadeira sempre que p ¶e verdadeira. Portanto os casos em que p ¶e falsa n~ao precisamser considerados.

Por exemplo, a proposi»c~ao \Se Collor atirou em Figueiredo, ent~ao Itamar foi oprimeiro presidente" ¶e considerada sem sentido, pois ambas as componentes s~ao falsas.ConseqÄuentemente, no uso ordin¶ario n~ao se questiona se uma proposi»c~ao componente ¶everdadeira. Ao criar a linguagem formal, o l¶ogico deseja designar um valor verdade ap ! q para cada uma das quatro possibilidades l¶ogicas, muito embora dois dos casospare»cam ser sem sentido em nossa linguagem ordin¶aria. Por v¶arias raz~oes, que aparecer~aono tempo devido, os l¶ogicos decidiram-se pela de¯ni»c~ao adotada aqui. Portanto, em nossalinguagem formal, p! q ¶e verdadeira em todos os casos exceto no caso 2 (veja Tabela1.5). Como conseqÄuencia desse acerto, seremos capazes de demonstrar alguns teoremas¶uteis bastante simples, cujas demonstra»c~oes, sem tal acerto, seriam desajeitadas ou muitodif¶³ceis.

Introduzimos agora o ¶ultimo dos cinco conectivos mais comuns, um que aparecefreqÄuentemente nos enunciados (proposi»c~oes) de teoremas matem¶aticos.

De¯ni»c~ao 1.5 O conectivo $ ¶e chamado o bicondicional e pode ser colocado entreduas proposi»c~oes p e q para formar a proposi»c~ao composta p$ q (lida: \p se e somentese q"). A proposi»c~ao p$ q ¶e equivalente µa proposi»c~ao (p! q) ^ (q ! p), e os valoresverdade de p$ q s~ao dados na Tabela 1.6.

2Em oposi»c~ao µa \linguagem ordin¶aria", l¶ogica ¶e chamada uma linguagem formal.

8 L¶ogica Elementar

Exemplo 1.4 Encontre a tabela verdade para p$ q.

Solu»c~ao. Seguindo o m¶etodo descrito anteriormente, obtemos a Tabela 1.6.

Tabela 1.6:

Caso p q p! q q ! p p$ q [´ (p! q) ^ (q ! p)]

1 V V V V V

2 V F F V F

3 F V V F F

4 F F V V V

Passo 1 1 2

Da tabela verdade acima, observamos que p $ q ¶e verdadeira se ambas as com-ponentes s~ao verdadeiras ou ambas as componentes s~ao falsas. Em qualquer outro caso(casos 2 e 3) a proposi»c~ao p$ q ¶e falsa.

1.2.1 Exerc¶³cios

Nos problemas de 1 a 12, construa as tabelas verdade para as proposi»c~oes dadas.

1. p_ » p 2. » (p_ » p)3. » (» p_ » q) 4. » p _ q5. (» q)! (» p) 6. q $ p7. p ^ (q _ r) 8. (p ^ q) _ (p ^ r)9. p _ (q ^ r) 10. (p _ q) ^ (p _ r)11.(p _ q) _ r 12. p _ (q _ r)

13. ¶E a proposi»c~ao (» q)! (» p) (Problema 5) logicamente equivalente µa proposi»c~aop! q?14. ¶E a proposi»c~ao » p _ q (Problema 4) logicamente equivalente µa proposi»c~ao p! q?15. Dentre as proposi»c~oes nos Problemas 1 a 12, encontre os pares de proposi»c~oeslogicamente equivalentes.16. Em cada um dos seguintes itens, traduza a proposi»c~ao composta dada em umaforma simb¶olica usando os s¶³mbolos sugeridos.(a) N~ao ocorre que eu seja amig¶avel a voce. (A)(b) Se ela ¶e uma gata, ent~ao ela tem quatro pernas. (G;P )(c) O pre»co do arroz aumenta se e somente se o suprimento de arroz n~ao atende µademanda. (P; S)(d) Ou os grandes laborat¶orios reduzem os pre»cos ou o governo intervir¶a. (L;G)(e) Se a exporta»c~ao de carne aumentar ou se a produ»c~ao pecu¶aria decair, ent~ao o custode vida subir¶a. (E;P;C)

L¶ogica Elementar 9

1.3 Tautologia, implica»c~ao e equivalencia

Examinemos a tabela verdade para a proposi»c~ao p_ » p:

Tabela 1.7:

p » p p_ » pV F V

F V V

Reparemos que a proposi»c~ao p_ » p ¶e verdadeira em todos os casos, isto ¶e, emtodas as possibilidades l¶ogicas. Tal tipo importante de proposi»c~ao merece um nomeespecial.

De¯ni»c~ao 1.6 Uma proposi»c~ao ¶e dita ser uma tautologia quando ¶e verdadeira em cadauma de todas as possibilidades l¶ogicas.

Sejam P e Q duas proposi»c~oes, compostas ou simples. Se a proposi»c~ao condicionalP ! Q ¶e uma tautologia, a proposi»c~ao ¶e chamada uma implica»c~ao e ¶e denotada por P )Q (le-se: P implica Q). Assim as seguintes proposi»c~oes condicionais s~ao tautologias:

(1) p! p.(2) p ^ q ! q ^ p.(3) p! p ^ p.(4) p ^ q ! q.3

Na l¶ogica ou na matem¶atica, \teoremas" signi¯cam proposi»c~oes verdadeiras, e uma\demonstra»c~ao" (de um teorema) ¶e uma justi¯ca»c~ao do teorema.

Teorema 1.1 Sejam p e q duas proposi»c~oes quaisquer. Ent~ao

(a) Lei da Adi»c~ao (Ad.): p) p _ q.(b) Leis de Simpli¯ca»c~ao (Simp.): p ^ q ) p, p ^ q ) q.

(c) Silogismo Disjuntivo (S.D.): (p _ q)^ » p) q.

Demonstra»c~ao. Deixamos as demonstra»c~oes de (a) e (b) ao leitor, como exerc¶³cios. Aseguinte ¶e uma tabela verdade simpli¯cada para (p _ q)^ » p! q:

Tomemos um instante para explicar a constru»c~ao da tabela verdade simpli¯cada:Os valores verdade na Tabela 1.8 s~ao atribu¶³dos, coluna por coluna, na ordem indicada

3Consideraremos _ e ^ como conectivos priorit¶arios em rela»c~ao a ! e $, e escreveremos p! p_ qem lugar de p! (p _ q), etc. Veja tamb¶em o ¶ultimo par¶agrafo da se»c~ao 1.1

10 L¶ogica Elementar

Tabela 1.8:

(p _ q) ^ » p ! q

V V V F F V V

V V F F F V F

F V V V V V V

F F F F V V F

Passo 1 2 1 3 2 4 1

pelos n¶umeros que aparecem na ¶ultima linha da tabela. Em uma tabela verdade sim-pli¯cada, escrevemos os valores verdade diretamente, primeiro sob cada componente eent~ao sob os conectivos. Isto poupa espa»co e tempo.

Agora, retornando µa demonstra»c~ao do teorema, como o passo ¯nal (passo 4) naTabela 1.8 consiste s¶o de V 's, a proposi»c~ao condicional (p _ q)^ » p ! q ¶e de fatouma implica»c~ao.

Se a proposi»c~ao bicondicional P $ Q for uma tautologia, ela ¶e chamada umaequivalencia e ¶e denotada por P , Q (leia-se: P ¶e equivalente a Q).

Da de¯ni»c~ao 1.5 e da Tabela 1.6, P , Q se P e Q tem os mesmos valores verdadeem cada uma de todas as possibilidades l¶ogicas, e reciprocamente, P e Q tem os mesmosvalores verdade em cada uma de todas as possibilidades l¶ogicas se P , Q. Portanto,pela de¯ni»c~ao 1.3, P , Q e P ´ Q tem o mesmo signi¯cado, e portanto podemostrocar , por ´ e vice-versa.

Teorema 1.2 Sejam p e q duas proposi»c~oes quaisquer. Ent~ao

(a) Lei da Dupla Nega»c~ao (D.N.): » (» p) ´ p.(b) Leis Comutativas (Com.): p ^ q ´ q ^ p, p _ q ´ q _ p,(c) Leis de Idempotencia (Idemp.): p ^ p ´ p, p _ p ´ p,(d) Lei Contrapositiva (Contrap.): (p! q) ´ (» q !» p).

Demonstra»c~ao. Deixaremos as demonstra»c~oes das partes (a), (b) e (c) para o leitor,como exerc¶³cios, e delinearemos a demonstra»c~ao de (d).

Temos a seguinte tabela verdade simpli¯cada para a proposi»c~ao bicondicional(p! q)$ (» q !» p):

L¶ogica Elementar 11

Tabela 1.9:

(p ! q) $ (» q ! » p)V V V V F V V

V F F V V F F

F V V V F V V

F V F V V V V

Passo 1 2 1 4 2 3 2

Logo, a Tabela 1.9 mostra que p$ q ¶e equivalente a » q !» p.

O seguinte teorema, creditado a Augustus De Morgan (1806{1871), ¶e uma dasferramentas mais convenientes da l¶ogica.

Teorema 1.3 (Leis de De Morgan (De M.)) Sejam p e q duas proposi»c~oes quais-quer. Ent~ao

» (p ^ q) ´ » p_ » q; e» (p _ q) ´ » p^ » q:

Demonstra»c~ao. Demonstraremos a primeira parte deste teorema e deixaremos a outraparte ao leitor, como exerc¶³cio. Constru¶³mos uma tabela verdade simpli¯cada para abicondicional » (p ^ q)$ (» p_ » q):

Tabela 1.10:

» (p ^ q) $ (» p _ » q)F V V V V F F F

V V F F V F V V

V F F V V V V F

V F F F V V V V

Passo 3 1 2 1 4 2 3 2

A tabela verdade acima mostra que » (p ^ q) ¶e equivalente a » p_ » q.

Teorema 1.4 Sejam p, q e r proposi»c~oes quaisquer. Ent~ao

(a) Leis Associativas (Assoc.): (p ^ q) ^ r ´ p ^ (q ^ r)(p _ q) _ r ´ p _ (q _ r)

(b) Leis Distributivas (Dist.): p ^ (q _ r) ´ (p ^ q) _ (p ^ r)p _ (q ^ r) ´ (p _ q) ^ (p _ r)

(c) Lei Transitiva (Trans.): (p! q) ^ (q ! r)) (p! r).

12 L¶ogica Elementar

Demonstra»c~ao. Deixaremos as demonstra»c~oes das Leis Associativas e da segunda LeiDistributiva para o leitor, como exerc¶³cios.

Demonstremos que p ^ (q _ r) ´ (p ^ q) _ (p ^ r). Como isto envolve trescomponentes, existem 23 = 8 possibilidades l¶ogicas a considerar. A seguinte tabelaverdade mostra que p ^ (q _ r) e (p ^ q) _ (p ^ r) tem os mesmos valores verdade emcada uma das oito possibilidades l¶ogicas. Portanto, p ^ (q _ r) e (p ^ q) _ (p ^ r) s~aoequivalentes.

Tabela 1.11:

p q r q _ r p ^ q p ^ r p ^ (q _ r) (p ^ q) _ (p ^ r)V V V V V V V V

V V F V V F V V

V F V V F V 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 V F F F F

F F F F F F F F

Por simplicidade e por economia de espa»co, constru¶³mos uma tabela verdade sim-pli¯cada, como apresentado na Tabela 1.8, para (p! q) ^ (p! r)! (p! r).

Tabela 1.12:

(p ! q) ^ (q ! r) ! (p ! r)

V V V V V V V V V V V

V V V F V F F V V F F

V F F F F V V V V V V

V F F F F V F V V F F

F V V V V V V V F V V

F V V F V F F V F V F

F V F V F V V V F V V

F V F V F V F V F V F

Passo 1 2 1 3 1 2 1 4 1 2 1

Como o ¶ultimo passo (passo 4) consiste inteiramente de valores V , a Lei Transitivaest¶a demonstrada.

Por causa das Leis Associativas, os parenteses em (p ^ q) ^ r ´ p ^ (q ^ r) e

L¶ogica Elementar 13

(p_ q)_ r ´ p _ (q _ r) tornam-se desnecess¶arios, e as express~oes p^ q ^ r e p _ q _ rtem agora signi¯cados de¯nidos, bem como p1 ^ p2 ^ ¢ ¢ ¢ ^ pn e p1 _ p2 _ ¢ ¢ ¢ _ pn.

Teorema 1.5 Sejam p, q, r e s proposi»c~oes quaisquer. Ent~ao

(a) Dilemas Construtivos (D.C.):

(p! q) ^ (r ! s) ) (p _ r! q _ s);(p! q) ^ (r ! s) ) (p ^ r! q ^ s):

(b) Dilemas Destrutivos (D.D.):

(p! q) ^ (r! s) ) (» q_ » s!» p_ » r);(p! q) ^ (r! s) ) (» q^ » s!» p^ » r):

Demonstra»c~ao. A demonstra»c~ao do Teorema 1.5 ¶e deixada ao leitor como exerc¶³cio.

Teorema 1.6 Sejam p e q duas proposi»c~oes. Ent~ao

(a) Modus Ponens (M.P.): (p! q) ^ p) q.(b) Modus Tolens (M.T.): (p! q)^ » q )» p.(c) Reductio ad Absurdum (R.A.): (p! q), (p^ » q ! q ^ » q).

Demonstra»c~ao. Exerc¶³cio.

1.3.1 Exerc¶³cios

1. Demonstre as partes (a) e (b) do Teorema 1.1.2. Demonstre as partes (a), (b) e (c) do Teorema 1.2.3. Demonstre que » (p _ q) ´» p^ » q.4. Demonstre a parte (a) do Teorema 1.4.5. Demonstre que p _ (q ^ r) ´ (p _ q) ^ (p _ r).6. Demonstre que (p! q)) (p ^ r ! q ^ r).7. Demonstre que (p$ q) ´ (p ^ q) _ (» p^ » q).8. Usando as Leis de De Morgan, escreva em linguagem ordin¶aria a nega»c~ao daproposi»c~ao \Esta fun»c~ao tem uma derivada ou eu sou burro."9. Demonstre as seguintes Leis de De Morgan para tres componentes.(a) » (p ^ q ^ r) ´» p_ » q_ » r(b) » (p _ q _ r) ´» p^ » q^ » r.10. Pode voce generalizar, sem demonstra»c~ao, as Leis de De Morgan para n compo-nentes? Veja o Problema 9 para n = 3.11. Demonstre as seguintes Leis de Absor»c~ao.(a) p ^ (p _ r) ´ p(b) p _ (p ^ q) ´ p12. Demonstre o Teorema 1.5.13. Demonstre o Teorema 1.6.

14 L¶ogica Elementar

1.4 Contradi»c~ao

Em contraste com as tautologias, h¶a proposi»c~oes cujos valores verdade s~ao todos F ,para cada uma das possibilidades l¶ogicas. Tais proposi»c~oes s~ao chamadas contradi»c~oes.Por exemplo, p^ » p ¶e uma contradi»c~ao.

¶E obvio que se t ¶e uma tautologia, ent~ao » t ¶e uma contradi»c~ao; reciprocamente,se c ¶e uma contradi»c~ao, ent~ao » c ¶e uma tautologia.

Teorema 1.7 Sejam t, c e p, uma tautologia, uma contradi»c~ao e uma proposi»c~ao arbi-tr¶aria, respectivamente. Ent~ao

(a) p ^ t , p,p _ t , t.

(b) p _ c , p,p ^ c , c.

(c) c) p, e p) t.

Demonstra»c~ao.

(a) A seguinte tabela verdade para p ^ t$ p mostra que p ^ t ¶e equivalente a p.

Tabela 1.13:

p ^ t $ p

V V V V V

F F V V F

Passo 1 2 1 3 1

A outra equivalencia, p _ t, t, pode ser demonstrada analogamente.

(b) Da seguinte tabela verdade, conclu¶³mos que a proposi»c~ao condicional p_c$ p¶e uma tautologia, e portanto p _ c, p.

Tabela 1.14:

p _ c $ p

V V F V V

F F F V F

Passo 1 2 1 3 1

A demonstra»c~ao de p ^ c, p ¶e similar.

L¶ogica Elementar 15

(c) As tabelas verdade de c ! p e p ! t mostram que as duas proposi»c~oes s~aotautologias, logo c) p e p) t.

Tabela 1.15:

c ! p

F V V

F V F

p ! t

V V V

F V V

No restante deste livro, o s¶³mbolo c, com ou sem¶³ndice, denotar¶a uma contradi»c~ao;e o s¶³mbolo t, com ou sem ¶³ndice, denotar¶a uma tautologia.

1.4.1 Exerc¶³cios

1. Demonstre que p _ t, t e p ^ c, c.2. Demonstre que » t, c e » c, t.3. Demonstre a seguinte Reductio ad Absurdum.

(p^ » q ! c), (p! q)

4. Demonstre que p ^ (p! q) ^ (p!» q), c.5. Demonstre que (p! q)) (p _ r ! q _ r), para qualquer proposi»c~ao r.

1.5 Racioc¶³nio dedutivo

As 17 leis sumarizadas nos Teoremas de 1.1 a 1.6 s~ao ferramentas muito ¶uteis parajusti¯car equivalencias l¶ogicas e implica»c~oes, como ilustrado nos Exemplos de 1.5 a 1.7.Chamaremos estas 17 leis de regras de inferencia. Chamamos a aten»c~ao para o fatode que estas regras foram selecionadas como referencias convenientes e n~ao precisamser independentes entre si. Por exemplo, a Lei Contrapositiva pode ser estabelecida\dedutivamente" pelo uso de outras leis e de de¯ni»c~oes relevantes, como mostra opr¶oximo exemplo.

Exemplo 1.5 Demonstre a Lei Contrapositiva, (p ! q) ´ (» q !» p), usandode¯ni»c~oes relevantes e outras regras de inferencia.

Solu»c~ao.

(p! q) ´ » (p^ » q) Def. 1.4´ » (» q ^ p) Com.´ » [» q^ » (» p)] D.N.´ (» q !» p) Def. 1.4

16 L¶ogica Elementar

Portanto, (p! q) ´ (» q !» p), pela Lei Transitiva.

O m¶etodo de demonstra»c~ao usado no Exemplo 1.5 ¶e chamado racioc¶³nio dedutivo4

ou m¶etodo dedutivo, e difere do m¶etodo de demonstra»c~ao por tabelas verdade.

Em geral, no racioc¶³nio dedutivo, quaisquer axiomas, de¯ni»c~oes, teoremas e regrasde inferencia, previamente enunciados, podem ser usados.

Exemplo 1.6 Prove o Silogismo Disjuntivo por racioc¶³nio dedutivo.

Solu»c~ao.

(p _ q)^ » p ´ » p ^ (p _ q) Com.´ (» p ^ p) _ (» p ^ q) Dist.´ c _ (» p ^ q) » p ^ p ´ c´ (» p ^ q) _ c Com.´ » p ^ q Teorema 1.7(b))q Simp.

Finalmente, pela Lei Transitiva, (p _ q)^ » p) q.

Exemplo 1.7 Demonstre a seguinte Lei de Exporta»c~ao:

(p ^ q ! r) ´ [p! (q ! r)]

por racioc¶³nio dedutivo.

Solu»c~ao.

p! (q ! r) ´ [p!» (q^ » r) De¯ni»c~ao 1.4´ » [p ^ (q^ » r)] Def. 1.4, D.N.´ » [(p ^ q)^ » r] Assoc.´ (p ^ q ! r) De¯ni»c~ao 1.4

Portanto, (p ^ q)! r ´ [p! (q ! r)].

Exemplo 1.8 Demonstre que (p ! r) _ (q ! s) ´ (p ^ q ! r _ s) por racioc¶³ciodedutivo.

Solu»c~ao.

(p! r) _ (q ! s) ´ » (p^ » r)_ » (q^ » s) De¯ni»c~ao 1.4´ (» p _ r) _ (» q _ s) De M., D.N.´ (» p_ » q) _ (r _ s) Com., Assoc.´ » [(p ^ q)^ » (r _ s)] De M., D.N.´ (p ^ q ! r _ s) De¯ni»c~ao 1.4

4ou argumenta»c~ao dedutiva (N. do T.)

L¶ogica Elementar 17

O porque de querermos usar racioc¶³cio dedutivo, em oposi»c~ao a tabelas verdade,pode ser visto da seguinte compara»c~ao: Para veri¯car a equivalencia no Exemplo 1.8,pelo m¶etodo das tabelas verdade, ter¶³amos que construir uma grande tabela verdade com16 (= 24) casos (veja Problema 20 dos Exerc¶³cios 1.1.1 ou Problema 12 dos Exerc¶³cios1.3.1); por outro lado, na solu»c~ao do Exemplo 1.8, acima, estabelecemos tal equivalenciaem apenas cinco passos.

1.5.1 Exerc¶³cios

Demonstre as seguintes tautologias pelo m¶etodo dedutivo.

1. Modus Ponens: p ^ (p! q)) q2. Modus Tollens: » q ^ (p! q))» p3. Reductio ad Absurdum: (p! q), (p^ » q ! c)4. Silogismo Disjuntivo: (p _ q)^ » p) q5. Teorema 1.7(c): c) p6. (p! q), (p! p ^ q)7. (p! q), (p _ q ! q)8. (p! q),» p _ q9. (p! r) ^ (q ! r), (p _ q ! r)10. (p! q) ^ (p! r), (p! q ^ r)11. (p! q) ^ (p!» q),» p12. (p! q) _ (p! r), (p! q _ r)13. (p! r) _ (q ! r), (p ^ q ! r)

1.6 Regras de quanti¯ca»c~ao

Em qualquer discuss~ao geral, temos em mente um universo particular ou dom¶³nio dodiscurso, isto ¶e, uma cole»c~ao de objetos cujas propriedades est~ao sob considera»c~ao. Porexemplo, na a¯rma»c~ao \Todos os humanos s~ao mortais", o universo ¶e a cole»c~ao de todosos humanos. Com este entendimento do universo, a a¯rma»c~ao \Todos os humanos s~aomortais" poder ser expressada alternativamente como:

Para todo x no universo, x ¶e mortal.

A frase \Para todo x no universo" ¶e chamada um quanti¯cador universal, e ¶e simbolizadapor (8x). A senten»ca \x ¶e mortal" diz algo sobre x; simbolizaremos isto por p(x). Usandoestes novos s¶³mbolos, podemos agora escrever a a¯rma»c~ao geral \Todos os homens s~aomortais" como

(8x)(p(x))

Agora considere a a¯rma»c~ao \Alguns homens s~ao mortais". Aqui o universo (oudom¶³nio de discurso) ¶e ainda o mesmo da a¯rma»c~ao pr¶evia. Com este universo em mente,podemos refazer a a¯rma»c~ao \Alguns homens s~ao mortais" sucessivamente como:

18 L¶ogica Elementar

Existe pelo menos um indiv¶³duo que ¶e mortal.Existe pelo menos um x tal que x ¶e mortal.

e como

Existe pelo menos um x tal que p(x).

A frase \Existe ao menos um x tal que" ¶e chamada um quanti¯cador existencial e ¶esimbolizada por (9x). Usando este novo s¶³mbolo podemos agora reescrever a a¯rma»c~ao\Alguns homens s~ao mortais" como

(9x)(p(x))

De um modo geral, suponhamos que temos um dom¶³nio de discurso U e umaa¯rma»c~ao geral, p(x), chamada um predicado proposicional, cuja \vari¶avel" x varia emU . Ent~ao (8x)(p(x)) a¯rma que para todo x, em U , a proposi»c~ao p(x), a respeito dex, ¶e verdadeira, e (9x)(p(x)) signi¯ca que existe pelo menos um x, em U , tal que p(x)¶e verdadeira.

Em matem¶atica elementar, quanti¯cadores s~ao freqÄuentemente suprimidos pelobem da simplicidade. Por exemplo, \(x+1)(x¡1) = x2¡1", em livros do ensino b¶asico,deve ser entendido como dizendo \para todo n¶umero real x, (x+ 1)(x¡ 1) = x2 ¡ 1".Na matem¶atica, \qualquer que seja" e \para todo" signi¯cam a mesma coisa e s~aoambos simbolizados por 8; e \para algum" signi¯ca o mesmo que \existe" e ¶e simboliza-do por 9. Em express~oes menos formais, freqÄuentemente colocamos o quanti¯cadorap¶os a a¯rma»c~ao. Por exemplo, a a¯rma»c~ao \f(x) = 0 para todo x" ¶e a mesma que\(8x)(f(x) = 0)".

Na l¶ogica e na matem¶atica, a nega»c~ao da proposi»c~ao \p(x) ¶e verdadeira para todox (em U)", » [(8x)(p(x))], ¶e considerada o mesmo que a asser»c~ao \existe pelo menosum x (em U) para o qual p(x) ¶e falsa", (9x)(» p(x)). Analogamente, » [(9x)(p(x))]¶e considerada o mesmo que \n~ao h¶a nenhum5 x (em U) tal que p(x) ¶e verdadeira"; ou,em outras palavras, \p(x) ¶e falsa para todo x (em U)", ou (8x)(» p(x)). Sumarizamostudo isto no seguinte axioma:

Axioma 1.1 (Regra da Nega»c~ao do Quanti¯cador (N.Q.)) Seja p(x) um predica-do proposicional, isto ¶e, uma proposi»c~ao sobre um objeto n~ao especi¯cado de um dadouniverso. Ent~ao

» [(8x)(p(x))] ´ (9x)(» p(x))e

» [(9x)(p(x))] ´ (8x)(» p(x))

5Na l¶³ngua portuguesa, \n~ao h¶a nenhum" tem o signi¯cado de \existe nenhum" (N. do T.).

L¶ogica Elementar 19

Estamos usando \´" para denotar que as duas proposi»c~oes quanti¯cadas, nos doislados de ´, s~ao consideradas a mesma em l¶ogica; este uso ¶e consistente com o uso de´ para equivalencias l¶ogicas, como ser¶a visto no pr¶oximo par¶agrafo.

Para entender melhor as proposi»c~oes quanti¯cadas (8x)(p(x)) e (9x)(p(x)), in-specionemos o caso em que o universo de discurso consiste de um n¶umero ¯nito deindiv¶³duos denotados por a1; a2; a3; : : : ; an. Ent~ao, como (8x)(p(x)) a¯rma que p(x)¶e verdadeira para todos, a1; a2; a3; : : : ; an, a proposi»c~ao (8x)(p(x)) ¶e verdadeira se esomente se a conjun»c~ao de

p(a1); p(a2); p(a3); : : : ; p(an)

¶e verdadeira. ConseqÄuentemente,

(8x)(p(x)) corresponde a p(a1) ^ p(a2) ^ ¢ ¢ ¢ ^ p(an)

Analogamente,

(9x)(p(x)) signi¯ca p(a1) _ p(a2) _ ¢ ¢ ¢ _ p(an)

Portanto, a Regra da Nega»c~ao do Quanti¯cador pode ser vista com uma generaliza»c~aodas Leis de De Morgan (Teorema 1.3).

Exemplo 1.9 Quais das seguintes proposi»c~oes ¶e equivalente µa nega»c~ao da proposi»c~ao\Todas as cobras s~ao venenosas"?

(a) Todas as cobras s~ao n~ao venenosas.(b) Algumas cobras s~ao venenosas.(c) Algumas cobras n~ao s~ao venenosas.

Solu»c~ao. O dom¶³nio de discurso U ¶e a cole»c~ao de todas as cobras. Seja p(x) o predicadoproposicional que a¯rma que x ¶e venenosa (onde a vari¶avel x varia sobre U). A a¯rma»c~ao\Todas as cobras s~ao venenosas" ¶e ent~ao traduzida em (8x)(p(x)). Conforme a regrade nega»c~ao do quanti¯cador, Axioma 1.1, » [(8x)(p(x))] ¶e equivalente a (9x)(» p(x)),que representa \Algumas cobras n~ao s~ao venenosas".

1.6.1 Exerc¶³cios

1. Traduza a proposi»c~ao da ¶algebra elementar \A equa»c~ao x2¡3x+2 = 0 tem solu»c~oes"em linguagem l¶ogica, usando um quanti¯cador. Qual ¶e o dom¶³nio de discurso aqui?2. Encontre a proposi»c~ao equivalente µa nega»c~ao de cada uma das seguintes proposi»c~oes,usando N.Q.(a) Todas as cobras s~ao r¶epteis.(b) Alguns cavalos s~ao mansos.(c) Alguns matem¶aticos n~ao s~ao soci¶aveis.(d) Todas as estudantes s~ao ou inteligentes ou atraentes.(e) N~ao h¶a bebe que n~ao seja fofo.

20 L¶ogica Elementar

3. Encontre o dom¶³nio de discurso de cada uma das proposi»c~oes do Problema 2.4. Deduza

» [(9x)(p(x))] ´ (8x)(» p(x))a partir de

» [(8x)(q(x))] ´ (9x)(» q(x)):5. Deduza

» [(8x)(p(x))] ´ (9x)(» p(x))a partir de

» [(9x)(q(x))] ´ (8x)(» q(x)):6. Demonstre que » [(8x)(» q(x))] ´ (9x)(q(x)) e » [(9x)(» q(x))] ´ (8x)(q(x)):[Sugest~ao: Use N.Q.]

1.7 Demonstra»c~ao de validade

Uma das mais importantes tarefas de um l¶ogico est¶a em testar argumentos. Um ar-gumento ¶e a asser»c~ao de que uma proposi»c~ao, chamada a conclus~ao, ¶e conseqÄuenciade outras proposi»c~oes, chamadas hip¶oteses ou premissas. Um argumento ¶e consideradov¶alido se a conjun»c~ao das hip¶oteses implica a conclus~ao. Como exemplo, o seguinte ¶e umargumento no qual as primeiras quatro proposi»c~oes s~ao hip¶oteses, e a ¶ultima proposi»c~ao¶e a conclus~ao.

Se ele estuda medicina, ent~ao prepara-se para ganhar uma boa renda.Se ele estuda artes, ent~ao prepara-se para viver bem.Se ele prepara-se para ganhar uma boa renda ou para viver bem, ent~ao suas des-

pesas de estudos n~ao s~ao desperdi»cadas.Suas despesas de estudos s~ao desperdi»cadas.Portanto, ele n~ao estuda nem medicina e nem artes.

Este argumento pode ser simbolizado como:

H1. M ! R

H2. A! B

H3. (R _B)!» DH4. D

C. :.: »M ^ » A

Para estabelecer a validade deste argumento por meio de uma tabela verdade,precisar¶³amos de uma tabela com 32 (= 25) linhas. Mas podemos demonstrar que esteargumento ¶e v¶alido deduzindo a conclus~ao a partir das hip¶oteses em poucos passosusando as regras de inferencia.

Das hip¶oteses H3 e H4, (R _ B) !» D e D, inferimos » (R _ B), ou equiva-lentemente, » R^ » B, por Modus Tollens e Lei de De Morgan. De » R^ » B,inferimos, de maneira v¶alida, » R (e tamb¶em » B), pelas Leis de Simpli¯ca»c~ao. DeH1, M ! R; com » R inferimos »M .

L¶ogica Elementar 21

Analogamente, A ! B (de H2), e » B, nos faz inferir » A. Finalmente aconjun»c~ao de » M e » A nos d¶a a conclus~ao » M ^ » A. Nesta demonstra»c~ao,as regras de inferencia Modus Tollens (M.T.), Leis de De Morgan (D.M.), e Leis deSimpli¯ca»c~ao (Simp.) s~ao usadas.

Um modo mais formal e conciso de expressar esta demonstra»c~ao de validade, ¶elistar as hip¶oteses e as proposi»c~oes deduzidas a partir delas em uma coluna, com ajusti¯ca»c~ao de cada passo numa coluna ao lado. Em cada passo, a \justi¯ca»c~ao" indicaas a¯rma»c~oes precedentes das quais, e as regras de inferencia pelas quais, a a¯rma»c~aodada naquele passo foi obtida. Para f¶acil inferencia, ¶e conveniente enumerar as hip¶otesese as a¯rma»c~oes deduzidas a partir delas e colocar a conclus~ao µa direita da ¶ultima premissa,separada desta por uma barra = que indica que todas as proposi»c~oes acima s~ao hip¶oteses.A demonstra»c~ao de validade formal para o argumento acima pode ent~ao ser escrita como

1. M ! R (Hip.)

2. A! B (Hip.)

3. (R _B)!» D (Hip.)

4. D=:.: »M ^ » A (Hip./ Concl.)

5. » (R _B) 3, 4, M.T.

6. » R^ » B 5, De M.

7. » R 6, Simp.

8. » B 6, Simp.

9. »M 1, 7, M.T.

10. » A 2, 8, M.T.

11. »M ^ » A 9, 10, Conj.

Uma demonstra»c~ao formal de validade para um dado argumento ¶e uma seqÄuenciade proposi»c~oes, cada uma das quais ¶e ou uma premissa do argumento ou segue deproposi»c~oes precedentes por um argumento v¶alido conhecido, terminando com a con-clus~ao do argumento.

Exemplo 1.10 Construir uma demonstra»c~ao formal de validade para o seguinte argu-mento, usando os s¶³mbolos sugeridos:

Wilson ser¶a eleito presidente do Centro Academico ou ambos, H¶elio e L¶ucio ser~aoeleitos vice-presidentes do Centro Academico. Se Wilson for eleito presidente ou H¶eliofor eleito vice, ent~ao David encaminhar¶a um protesto. Portanto, ou Wilson ser¶a eleitopresidente do Centro Academico ou David encaminhar¶a um protesto. (W;H;L;D).

Demonstra»c~ao.

1. W _ (H ^ L)2. W _H ! D=:

.: W _D

3. (W _H) ^ (W _ L) 1, Dist.

4. W _H (Hip./ Concl.)

5. D 2, 4, M.P.

6. D _W 5, Ad.

7. W _D 6, Com.

22 L¶ogica Elementar

Existe um outro m¶etodo de demonstra»c~ao chamado demonstra»c~ao indireta, oum¶etodo de demonstra»c~ao por redu»c~ao ao absurdo. Uma demonstra»c~ao indireta de vali-dade, para um dado argumento, ¶e feita incluindo-se, como premissa adicional, a nega»c~aode sua conclus~ao, e ent~ao derivando uma contradi»c~ao; assim que uma contradi»c~ao ¶eobtida, a demonstra»c~ao est¶a completa.

Exemplo 1.11 De uma demonstra»c~ao indireta de validade para o seguinte argumento:

p _ q ! rs! p ^ uq _ s =:.: r

Demonstra»c~ao.

1. p _ q ! r

2. s! p ^ u3. q _ s =:.: r4. » r P.I. (Demonstra»c~ao Indireta)

5. » (p _ q) 1, 4, M.T.

6. » p^ » q 5, De M.

7. » p 6, Simp.

8. » q 6, Simp.

9. s 3, 8, S.D.

10. p ^ u 2, 9, M.P.

11. p 10, Simp.

12. p^ » p 7, 11, Conj.

A proposi»c~ao p^ » p, no passo 12, ¶e uma contradi»c~ao; portanto a demonstra»c~aoindireta de validade est¶a completa.

Em contraste a uma \demonstra»c~ao indireta", a demonstra»c~ao formal de validadeintroduzida anteriormente pode ser chamada \demonstra»c~ao direta". Numa demons-tra»c~ao matem¶atica, pode ser usada uma demonstra»c~ao direta ou uma demonstra»c~aoindireta. A escolha do m¶etodo de demonstra»c~ao, para um argumento matem¶atico dado,depende da preferencia e da conveniencia.

1.7.1 Exerc¶³cios

Para cada um dos seguintes argumentos, de uma demonstra»c~ao direta e uma demons-tra»c~ao indireta de validade, e compare seus tamanhos.

L¶ogica Elementar 23

1. A _ (B ^ C) 4. A _BB ! D » B _ C = :.: A _ CC ! ED ^ E ! A _ C» A= :.: C

2. B _ (C ! E) 5. B _ C ! B ^ AB ! D » B = :.: » C» D! (E ! A)» D= :.: C ! A

3. (A _B)! (A! D ^ E) 6. A ^B ! CA ^D = :.: E _ F (A! C)! D

» B _E = :.: B ! D ^E

Nas demonstra»c~oes dos seguintes argumentos, use os s¶³mbolos sugeridos.

7. Se a popula»c~ao cresce rapidamente e a produ»c~ao permanece constante, ent~ao ospre»cos sobem. Se os pre»cos sobem, ent~ao o governo controla os pre»cos. Se sou rico,ent~ao n~ao me preocupo com o aumento dos pre»cos. N~ao ¶e verdade que n~ao sou rico. Ogoverno n~ao controla os pre»cos ou preocupo-me com o aumento dos pre»cos. Portanto,n~ao ¶e verdade que a popula»c~ao cresce rapidamente e a produ»c~ao permanece constante(P : A popula»c~ao cresce rapidamente. C: A produ»c~ao permanece constante. S: Ospre»cos sobem. G: O governo controla os pre»cos. R: Eu sou rico. A: Eu me preocupocom o aumento dos pre»cos.)8. Se Wilson ou Alberto ganham ent~ao L¶ucio e Susana choram. Susana n~ao est¶achorando. Portanto, Alberto n~ao ganhou. (W : Wilson ganha. A: Alberto ganha. L:L¶ucio chora. S: Susana chora.)9. Se eu me inscrevo neste curso e estudo bastante ent~ao tiro boas notas. Se tiro boasnotas, ¯co feliz. N~ao estou feliz. Portanto, n~ao me inscrevi neste curso ou n~ao estudeibastante. (I: Me inscrevo neste curso. E: Estudo bastante. B: Tiro boas notas. F :Estou feliz.)

1.8 Indu»c~ao Matem¶atica

Um outro m¶etodo de demonstra»c~ao, muito ¶util para demonstrar a validade de umaproposi»c~ao P (n), envolvendo o n¶umero natural n, ¶e o seguinte princ¶³pio de indu»c~aomatem¶atica.

Indu»c~ao Matem¶atica. Se P (n) ¶e uma proposi»c~ao envolvendo o n¶umero natural n,tal que(1) P (1) ¶e verdadeira, e(2) P (k)) P (k + 1) para qualquer n¶umero natural arbitr¶ario k,ent~ao P (n) ¶e verdadeira para todo n¶umero natural n.

24 L¶ogica Elementar

O princ¶³pio acima ¶e uma conseqÄuencia de um dos Axiomas de Peano para osn¶umeros naturais.

De modo a aplicarmos o princ¶³pio de indu»c~ao matem¶atica para demonstrarmosum teorema, o teorema tem que ser subdividido em casos, uma caso para cada n¶umeronatural. Assim, devemos veri¯car ambas as condi»c~oes (1) e (2). A veri¯ca»c~ao de (1),habitualmente f¶acil, nos garante que o teorema ¶e verdadeiro pelo menos no caso n =1. Para veri¯car a condi»c~ao (2), devemos provar um teorema auxiliar cuja premissa(hip¶otese) ¶e \P (k) ¶e verdadeira", e cuja conclus~ao (tese) ¶e \P (k + 1) ¶e verdadeira". Apremissa \P (k) ¶e verdadeira" ¶e chamada a hip¶otese de indu»c~ao.

Exemplo 1.12 Demonstre, por indu»c~ao matem¶atica, que

1 + 2 + 3 + ¢ ¢ ¢+ n = n(n+ 1)

2

Demonstra»c~ao. Aqui P (n) representa a proposi»c~ao

\1 + 2 + 3 + ¢ ¢ ¢+ n = n(n+ 1)

2"

Em particular, P (1) representa \1 = (1 ¢ 2)=2", que obviamente ¶e uma a¯rma»c~aoverdadeira. Portanto, a condi»c~ao (1) para a indu»c~ao matem¶atica est¶a satisfeita.

Para demonstrar que a condi»c~ao (2) ¶e satisfeita, assumimos que \P (k)", que ¶e\1 + 2 + 3 + ¢ ¢ ¢ + k = k(k + 1)=2", seja verdadeira. Ent~ao, somamos k + 1 a ambosos membros da igualdade. Temos portanto

1 + 2 + 3 + ¢ ¢ ¢+ k + (k + 1) =k(k + 1)

2+ (k + 1)

=k(k + 1)

2+2(k + 1)

2

=(k + 2)(k + 1)

2

=(k + 1)(k + 2)

2

o que mostra que P (k + 1) ¶e verdadeira. Mostramos assim que as condi»c~oes (1) e (2)da indu»c~ao matem¶atica s~ao satisfeitas. Portanto, pelo princ¶³pio de indu»c~ao matem¶atica,1 + 2 + 3 + ¢ ¢ ¢+ n = n(n+ 1)=2 ¶e verdadeira para cada n¶umero natural n.

A id¶eia de indu»c~ao matem¶atica pode ser usada para fazer de¯ni»c~oes matem¶aticasenvolvendo n¶umeros naturais. Por exemplo, a de¯ni»c~ao de potencias de um n¶umero realqualquer x podem ser de¯nidas por:

x1 = x

xn+1 = xn ¢ x; para cada n¶umero natural n

L¶ogica Elementar 25

As duas equa»c~oes acima indicam que x1 = x, x2 = x ¢ x, x3 = x2 ¢ x, : : : e assimpor diante. Como outra aplica»c~ao, daremos a seguinte de¯ni»c~ao indutiva do s¶³mboloC(n; r).

De¯ni»c~ao 1.7 Sejam n um n¶umero natural e r um inteiro. O s¶³mbolo C(n; r) ¶e de¯nidopor

C(0; 0) = 1, C(0; r) = 0 para cada r6= 0, e

C(n+ 1; r) = C(n; r) + C(n; r ¡ 1)

Teorema 1.8 Se n e r s~ao inteiros, tais que 0 6 r 6 n, ent~ao

C(n; r) =n!

r!(n¡ r)!sendo n! o produto n ¢ (n¡1) ¢ ¢ ¢ 3 ¢2 ¢1, dos primeiros n n¶umeros naturais consecutivos,se n > 0 e 0! = 1 por conven»c~ao.

Demonstra»c~ao. Exerc¶³cio.

Teorema 1.9 (O Teorema Binomial) Se x e y s~ao dois n¶umeros reais e n ¶e umn¶umero natural, ent~ao

(x+ y)n = C(n; 0)xn + C(n; 1)xn¡1y + ¢ ¢ ¢+ C(n; r)xn¡ryr + ¢ ¢ ¢+ C(n; n)yn

Demonstra»c~ao. Demonstraremos a validade deste teorema por indu»c~ao matem¶atica.Primeiramente, o teorema ¶e claramente verdadeiro para n = 1. Para completar ademonstra»c~ao, assumiremos a validade do teorema para n = k; isto ¶e, assumiremosque

(x+ y)k = C(k; 0)xk + C(k; 1)xk¡1y + ¢ ¢ ¢+ C(k; r)xk¡ryr + ¢ ¢ ¢+ C(k; k)yk

Ent~ao, multiplicando ambos os membros da igualdade acima por (x+ y), temos

(x+ y)k+1 = (x+ y)[xk + C(k; 1)xk¡1y + ¢ ¢ ¢+ C(k; r)xk¡ryr + ¢ ¢ ¢+ yk]= xk+1 + [C(k; 0) + C(k; 1)]xky + ¢ ¢ ¢

+ [C(k; r ¡ 1) + C(k; r)]x(k+1)¡ryr + ¢ ¢ ¢+ yk+1= C(k + 1; 0)xk+1 + C(k + 1; 1)xky + ¢ ¢ ¢

+ C(k + 1; r)xk+1¡ryr + ¢ ¢ ¢+ C(k + 1; k + 1)yk+1

que mostra que o teorema ¶e v¶alido para n = k + 1 se for v¶alido para n = k.

Assim, por indu»c~ao matem¶atica, o teorema binomial ¶e verdadeiro para todos osn¶umeros naturais n.

26 L¶ogica Elementar

1.8.1 Exerc¶³cios

1. Demonstre o teorema 1.8 por indu»c~ao matem¶atica.2. Mostre que C(n; 0) = 1 = C(n; n) para todo n¶umero natural n.3. Demonstre por indu»c~ao matem¶atica que, para todo n¶umero natural n,

1 ¢ 2 + 2 ¢ 3 + ¢ ¢ ¢+ r ¢ (r + 1) + ¢ ¢ ¢+ n ¢ (n+ 1) = 13n(n+ 1)(n+ 2):

4. Demonstre por indu»c~ao matem¶atica que, para todo n¶umero natural n,

12 + 22 + 32 + ¢ ¢ ¢+ n2 = 16n(n+ 1)(2n+ 1):

5. Demonstre que para todo n¶umero natural n,

13 + 23 + 33 + ¢ ¢ ¢+ n3 = 14n2(n+ 1)2:

6. Demonstre que para todo n¶umero natural n, 1 + 3 + 5 + ¢ ¢ ¢+ (2n¡ 1) = n2.7. Demonstre que para todo n¶umero natural n,

1

1 ¢ 2 +1

2 ¢ 3 +1

3 ¢ 4 + ¢ ¢ ¢+1

n ¢ (n+ 1) =n

n+ 1:

8. Demonstre as seguintes Leis de De Morgan Generalizadas,(a) » (p1 ^ p2 ^ ¢ ¢ ¢ ^ pn),» p1 _ » p2 _ ¢ ¢ ¢ _ » pn(b) » (p1 _ p2 _ ¢ ¢ ¢ _ pn),» p1 ^ » p2 ^ ¢ ¢ ¢ ^ » pn

9. Demonstre as seguintes Leis Distributivas Generalizadas.(a) p ^ (q1 _ q2 _ ¢ ¢ ¢ _ qn), (p ^ q1) _ (p ^ q2) _ ¢ ¢ ¢ _ (p ^ qn)(b) p _ (q1 ^ q2 ^ ¢ ¢ ¢ ^ qn), (p _ q1) ^ (p _ q2) ^ ¢ ¢ ¢ ^ (p _ qn)

2

O Conceito de Conjunto

Neste cap¶³tulo, apresentamos os conceitos de conjuntos, subconjuntos, e opera»c~oes entreconjuntos (uni~ao, interse»c~ao, e complementa»c~ao), juntamente com as regras fundamen-tais dessas opera»c~oes. Estas s~ao desenvolvidas em paralelo com o Cap¶³tulo 1 sobre l¶ogica.Fam¶³lias indexadas de conjuntos s~ao discutidas. O Cap¶³tulo termina com o Paradoxo deRussel e uma nota hist¶orica.

2.1 Conjuntos e subconjuntos

\O que ¶e um conjunto" ¶e uma quest~ao muito dif¶³cil de se responder.1 Neste tratadoelementar, n~ao entraremos em nenhuma abordagem axiom¶atica complicada da Teoria dosConjuntos, e conter-nos-emos em aceitar o seguinte: um conjunto ¶e qualquer cole»c~ao,dentro de um todo de objetos de¯nidos e distingÄu¶³veis, chamados elementos, de nossaintui»c~ao ou pensamento. Esta de¯ni»c~ao intuitiva de um conjunto foi dada primeiramentepor Georg Cantor (1845{1918), que criou a teoria dos conjuntos em 1895. Exemplos:

(a) O conjunto de todas as cadeiras na sala de aula de Teoria dos Conjuntos.(b) O conjunto de todos os estudantes desta universidade.(c) O conjunto das letras a, b, c e d.(d) O conjunto das regras de uso do laborat¶orio de inform¶atica.(e) O conjunto de todos os n¶umeros racionais cujo quadrado ¶e 2.(f) O conjunto de todos os n¶umeros naturais.(g) O conjunto de todos os n¶umeros reais entre 0 e 1.

Um conjunto que cont¶em apenas um n¶umero ¯nito de elementos ¶e chamado umconjunto ¯nito; um conjunto in¯nito ¶e um conjunto que n~ao ¶e ¯nito. Exemplos de (a) a(e) acima s~ao todos de conjuntos ¯nitos, e Exemplos (f) e (g) s~ao de conjuntos in¯nitos.

Conjuntos s~ao freqÄuentemente designados fechando-se entre chaves os s¶³mbolosque representam seus elementos, quando for poss¶³vel faze-lo. Assim, o conjunto no Ex-emplo (c) ¶e fa; b; c; dg e o conjunto no Exemplo (f) pode ser denotado por f1; 2; 3; : : : g.

1O estudante tomar¶a ciencia da di¯culdade quando chegarmos µas se»c~oes 2.7 e 2.8.

27

28 O Conceito de Conjunto

O conjunto do Exemplo (e) n~ao tem elementos; um tal conjunto ¶e chamado o conjuntovazio, sendo denotado pelo s¶³mbolo ¿.

Usaremos letras mai¶usculas para denotar conjuntos, e letras min¶usculas para de-notar elementos. Se a ¶e um elemento de um conjunto A, escrevemos a 2 A (leia-se: \a¶e um elemento de A" ou \a pertence a A"), enquanto que a62 A signi¯ca que a n~ao ¶eelemento de A.

De¯ni»c~ao 2.1 Dois conjuntos A e B s~ao iguais ou identicos quando cont¶em os mesmoselementos. Isto ¶e, A = B signi¯ca (8x)[(x 2 A)$ (x 2 B)].

A ordem em que aparecem os elementos num conjunto n~ao tem importancia. As-sim, o conjunto fa; b; cg ¶e o mesmo que fb; c; ag, etc. Al¶em disso, como os elementos deum conjuntos s~ao distintos, fa; a; bg, por exemplo, n~ao ¶e uma nota»c~ao apropriada de umconjunto, e deveria ser substitu¶³da por fa; bg. Se a ¶e um elemento de um conjunto, a efag s~ao considerados diferentes, isto ¶e, a6= fag. Pois fag denota o conjunto consistindodo elemento a somente, enquanto que a ¶e apenas o elemento do conjunto fag.

De¯ni»c~ao 2.2 Sejam A e B conjuntos. Se todo elemento de A ¶e elemento de B,ent~ao A ¶e chamado um subconjunto de B, em s¶³mbolos: A ½ B ou B ¾ A. Se A ¶esubconjunto de B, ent~ao B ¶e chamado um superconjunto de A.

Assim, escrevendo logicamente,

A ½ B ´ (8x)[(x 2 A)! (x 2 B)]

Obviamente, todo conjunto ¶e um subconjunto (e um superconjunto) de si mesmo.Quando A ½ B e A 6= B, escrevemos A Ã B, ou B ! A, e dizemos que A ¶e umsubconjunto pr¶oprio de B, ou que B ¶e um superconjunto pr¶oprio de A. Em outraspalavras, A ¶e um subconjunto pr¶oprio de B quando todo elemento de A ¶e um elementode B, mas existe um elemento de B que n~ao ¶e elemento de A. Se A n~ao ¶e subconjuntode B, escrevemos A6½ B.

Teorema 2.1 O conjunto ¿ ¶e um subconjunto de qualquer conjunto.

Demonstra»c~ao. Seja A um conjunto qualquer. Provaremos que a proposi»c~ao condicional

(x 2 ¿)! (x 2 A)¶e verdadeira para todo x. Como o conjunto ¿ n~ao tem nenhum elemento, a a¯rma»c~ao\x 2 ¿" ¶e falsa, enquanto que \x 2 A" pode ser verdadeira ou falsa. Em qualquer doscasos, a a¯rma»c~ao condicional \(x 2 ¿) ! (x 2 A)" ¶e verdadeira, conforme a tabelaverdade para a condicional (casos 3 e 4 da Tabela 1.5, Cap¶³tulo 1).

Assim, ¿ ½ A, para qualquer conjunto A.

O Conceito de Conjunto 29

Teorema 2.2 Se A ½ B e B ½ C ent~ao A ½ C.

Demonstra»c~ao. Demonstraremos que (x 2 A)) (x 2 C):

(x 2 A) ) (x 2 B); porque A ½ B) (x 2 C); porque B ½ C

Portanto, pela Lei Transitiva (Teorema 1.4(c) do Cap¶³tulo 1), temos

(x 2 A)) (x 2 C)

ConseqÄuentemente, demonstramos que A ½ C.

2.1.1 Exerc¶³cios

1. Demonstre que o conjunto de letras da palavra \catarata" e o conjunto de letras dapalavra \catraca" s~ao iguais.2. Decida, dentre os seguintes conjuntos, quais s~ao subconjuntos de quais:(a) A = ftodos os n¶umeros reais satisfazendo x2 ¡ 8x+ 12 = 0g(b) B = f2; 4; 6g(c) C = f2; 4; 6; 8; : : : g(d) D = f6g

3. Liste todos os subconjuntos do conjunto f¡1; 0; 1g.4. Demonstre que [(A ½ B) ^ (B ½ A)] , (A = B) [Nota: FreqÄuentemente, emmatem¶atica, o melhor meio de demonstrar que A = B ¶e mostrar que A ½ B e B ½ A.]5. Demonstre que (A ½ ¿)) (A = ¿).6. Demonstre que(a) [(A Ã B) ^ (B ½ C)]) (A Ã C)(b) [(A ½ B) ^ (B Ã C)]) (A Ã C)

7. De um exemplo de um conjunto cujos elementos s~ao tamb¶em conjuntos.8. Em cada um dos seguintes itens, determine se a a¯rma»c~ao ¶e verdadeira ou falsa.Se for verdadeira, demonstre-a. Se for falsa, mostre-o atrav¶es de um exemplo (um talexemplo, mostrando que uma proposi»c~ao ¶e falsa, ¶e chamado um contra-exemplo).(a) Se x 2 A e A 2 B ent~ao x 2 B.(b) Se A ½ B e B 2 C ent~ao A 2 C.(c) Se A6½ B e B ½ C ent~ao A6½ C.(d) Se A6½ B e B6½ C ent~ao A6½ C.(e) Se x 2 A e A6½ B ent~ao x62 B.(f) Se A ½ B e x62 B ent~ao x62 A.

9. Dado um conjunto com n elementos, demonstre que existem exatemente C(n; r)subconjuntos com r elementos.

30 O Conceito de Conjunto

2.2 Especi¯ca»c~ao de conjuntos

Um modo de construir um novo conjunto, a partir de um conjunto dado, ¶e especi¯caraqueles elementos, do conjunto dado, que satisfazem uma propriedade particular. Porexemplo, seja A o conjunto de todos os estudantes desta universidade. A proposi»c~ao \x¶e paulista" ¶e verdadeira para alguns elementos x de A e falsa para outros. Empregaremosa nota»c~ao

fx 2 A jx ¶e paulistagpara especi¯car o conjunto de todas os estudantes paulistas desta universidade. Similar-mente,

fx 2 A jx n~ao ¶e paulistagespeci¯ca o conjunto de estudantes n~ao paulistas desta universidade.

Como regra, a todo conjunto A e a toda proposi»c~ao p(x) sobre x 2 A, existe umconjunto fx 2 A j p(x)g, cujos elementos s~ao precisamente aqueles elementos x 2 Apara os quais a a¯rma»c~ao p(x) ¶e verdadeira. Numa abordagem axiom¶atica da teoria dosconjuntos, esta regra ¶e habitualmente postulada como um axioma, chamado o Axiomada Especi¯ca»c~ao. O s¶³mbolo fx 2 A j p(x)g ¶e lido: o conjunto de todos os x em A taisque p(x) ¶e verdadeira. A nota»c~ao da forma fx 2 A j p(x)g, que descreve um conjunto ¶echamada a nota»c~ao de constru»c~ao do conjunto.

Exemplo 2.1 Seja R o conjunto dos n¶umeros reais. Ent~ao

(a) fx 2 R jx = x+ 1g ¶e o conjunto vazio.(b) fx 2 R j 2x2 ¡ 5x¡ 3 = 0g ¶e o conjunto f¡1=2; 3g.(c) fx 2 R j x2 + 1 = 0g ¶e o conjunto vazio.

Por causa de freqÄuente aparecimento, atrav¶es do restante deste e dos demaiscap¶³tulos, e em outros t¶opicos de matem¶atica, os seguintes s¶³mbolos especiais ser~aoreservados para os conjuntos descritos:

R = fx jx ¶e um n¶umero realgQ = fx jx ¶e um n¶umero racionalgZ = fx jx ¶e um n¶umero inteirogN = fx jx ¶e um n¶umero naturalgI = fx 2 R j 0 · x · 1gR+= fx 2 R j x > 0g

Note que N ½ Z ½ Q ½ R e N ½ R+ ½ R.¶E bem poss¶³vel que elementos de um conjunto possam ser tamb¶em conjuntos. Por

exemplo, o conjunto de todos os subconjuntos de um conjunto dado A tem conjuntoscomo seus elementos. Este conjunto ¶e chamado conjunto das partes2 de A, e ¶e denotado

2Na teoria dos conjuntos, a existencia do conjunto das partes n~ao ¶e tida como ¶obvia. Como aexistencia de um conjunto das partes n~ao ¶e conseqÄuencia do axioma da especi¯ca»c~ao, um novo axioma¶e necess¶ario; este axioma ¶e habitualmente chamado o Axioma do Conjunto das Partes e pode ser assimenunciado: Para cada conjunto, existe um conjunto de conjuntos que consiste de todos os subconjuntosdo conjunto dado.

O Conceito de Conjunto 31

por }(A).

Exemplo 2.2 }(fag) = f¿; fagg, }(¿) = f¿g, e }(fa; bg) =f¿; fag; fbg; fa; bgg.

Teorema 2.3 Se A consiste de n elementos, ent~ao seu conjunto das partes }(A) cont¶emexatamente 2n elementos.

Demonstra»c~ao. O teorema ¶e claramente verdadeiro para A = ¿. Para um conjunto n~aovazio A, seja A = fa1; a2; a3; : : : ; ang. Dado um elemento ak de A, para cada subcon-junto de A temos duas possibilidades: ou ele cont¶em ak ou n~ao o cont¶em. Portanto,o problema de encontrar o n¶umero de subconjuntos de A pode ser considerado como oproblema de preencher uma lista de n espa»cos em branco 2 2 2 ¢ ¢ ¢2, aleatoriamente,com os n¶umeros 0 e 1, um n¶umero em cada espa»co. Cada preenchimento dos n espa»cosdetermina um subconjunto X de A da seguinte maneira: ak 2 X se e somente se 1aparece no k-¶esimo espa»co (para cada k 2 f1; 2; : : : ; ng). Como existem exatamente2n preenchimentos distintos, existem 2n subconjuntos de A.

¶E tamb¶em interessante a seguinte demonstra»c~ao alternativa do Teorema 2.3:

Demonstra»c~ao alternativa. Primeiramente, o conjunto vazio ¿ pertence a }(A). Emseguida, cada elemento x 2 A forma um subconjunto fxg pertencente a }(A). Observeque o n¶umero desse conjuntos unit¶arios ¶e C(n; 1). Continuando, existem exatamenteC(n; 2) subconjuntos de A contendo exatemente 2 elementos de A.3 Finalmente, existeexatamente C(n; n) = 1 subconjunto de A contendo n elementos de A, que ¶e o pr¶oprioA. Contando o conjunto vazio, o n¶umero total de subconjuntos de A ¶e igual a C(n; 0)+C(n; 1) + ¢ ¢ ¢+ C(n; n). Ent~ao, usando a expans~ao binomial para (1 + 1)n, temos

(1 + 1)n = C(n; 0) + C(n; 1) + ¢ ¢ ¢+ C(n; n)

Assim, o n¶umero de elementos de }(A) ¶e (1 + 1)n = 2n.

2.2.1 Exerc¶³cios

1. Exiba entre chaves os elementos de cada um dos seguintes conjuntos.A = fx 2 N jx < 5gB = fx 2 Z j x2 · 25gC = fx 2 Q j 10x2 + 3x¡ 1 = 0gD = fx 2 R jx3 + 1 = 0gE = fx 2 R+ j 4x2 ¡ 4x¡ 1 = 0g

2. Denote cada um dos seguintes conjuntos pela nota»c~ao de constru»c~ao do conjunto.A = f1; 2; 3gB = f¡1;¡2

3;¡1

3; 0g

3Veja problema 9, Exerc¶³cios 2.1.1

32 O Conceito de Conjunto

C = f1; 3; 5; 7; 9; : : : gD = f1¡p3; 1 +p3g

3. Quais s~ao os elementos do conjunto das partes do conjunto fx; fy; zgg? Quantoselementos tem esse conjunto das partes?4. Seja B um subconjunto de A, e seja }(A : B) = fX 2 }(A) jX ¾ Bg.(a) Seja B = fa; bg e A = fa; b; c; d; eg. Liste os membros do conjunto }(A : B);

quantos s~ao eles?(b) Demonstre que }(A : ¿) = }(A).

5. Sejam A um conjunto com n elementos e B um subconjunto com m elementos,n ¸ m.(a) Encontre o n¶umero de elementos do conjunto }(A : B).(b) Deduza o Teorema 2.3 a partir de (a), fazendo B = ¿.

2.3 Uni~oes e interse»c~oes

Na aritm¶etica, podemos somar, multiplicar, ou subtrair dois n¶umeros quaisquer. Na teoriados conjuntos, h¶a tres opera»c~oes|uni~ao, interse»c~ao, e complementa»c~ao| respectiva-mente an¶alogas µas opera»c~oes adi»c~ao, multiplica»c~ao, e subtra»c~ao de n¶umeros.

De¯ni»c~ao 2.3 A uni~ao de dois conjuntos quaisquer A e B, denotada por A [ B, ¶e oconjunto dos elementos x tais que x pertence a pelo menos um dos dois conjuntos A eB. Ou seja, x 2 A [B se e somente se x 2 A _ x 2 B.

De¯ni»c~ao 2.4 A interse»c~ao de dois conjuntos quaisquer A e B, denotada por A \ B,¶e o conjunto dos elementos x tais que x pertence a ambos os conjuntos A e B. Ems¶³mbolos, A \ B = fx j (x 2 A) ^ (x 2 B)g, ou fx 2 A jx 2 Bg. Se A \ B = ¿,dizemos que A e B s~ao conjuntos disjuntos.

Por exemplo, se A = f1; 2; 3; 4g e B = f3; 4; 5g, ent~ao A [ B = f1; 2; 3; 4; 5g eA \ B = f3; 4g; se Im denota o conjunto de n¶umeros imagin¶arios, ent~ao os conjuntosIm e R s~ao disjuntos.

Exemplo 2.3 No que segue, os conjuntos I;N;Z; : : : s~ao de¯nidos como na ¶ultimase»c~ao.

(a) I \ Z = f0; 1g e N \ I = f1g.(b) Z [Q = Q e Z \Q = Z.(c) I [ I = I e I \ I = I.

O Conceito de Conjunto 33

Teorema 2.4 Sejam X um conjunto e A, B e C subconjuntos de X. Ent~ao temos:

(a) Os elementos neutros:

A [ ¿ = AA \X = A

(b) As leis de idempotencia:

A [ A = AA \ A = A

(c) As leis comutativas:

A [B = B [ AA \B = B \ A

(d) As leis associativas:

A [ (B [ C) = (A [B) [ CA \ (B \ C) = (A \B) \ C

(e) As leis distributivas:

A \ (B [ C) = (A \B) [ (A \ C)A [ (B \ C) = (A [B) \ (A [ C)

Demonstra»c~ao. Deixaremos as demonstra»c~oes das partes (a), (b) e (c) para o leitor,como exerc¶³cios.

(d) De acordo com a De¯ni»c~ao 2.3,

x 2 A [ (B [ C), x 2 A _ (x 2 B [ C)e

x 2 B [ C , x 2 B _ x 2 CAssim,

x 2 A [ (B [ C), x 2 A _ (x 2 B _ x 2 C)Pela Lei Associativa (para a disjun»c~ao), (x 2 A) _ (x 2 B _ x 2 C) ¶e equivalente a(x 2 A _ x 2 B) _ (x 2 C). A ¶ultima a¯rma»c~ao, pela De¯ni»c~ao 2.3, ¶e equivalente a(x 2 A [B) _ (x 2 C), e portanto x 2 (A [B) [ C.

Assim, temosx 2 A [ (B [ C), x 2 (A [B) [ C

Pela de¯ni»c~ao 2.1, A [ (B [ C) = (A [B) [ C.A demonstra»c~ao acima pode ser condensada em uma exposi»c~ao limpa de passos

l¶ogicos essenciais, com a justi¯cativa de cada passo escrita µa direita para f¶acil referencia:

34 O Conceito de Conjunto

x 2 A [ (B [ C) , (x 2 A) _ (x 2 B [ C) Def. de [, (x 2 A) _ [(x 2 B) _ (x 2 C)] Def. de [, [(x 2 A) _ (x 2 B)] _ (x 2 C) Assoc. para _, (x 2 A [B) _ (x 2 C) Def. de [, x 2 (A [B) [ C Def. de [

Portanto, pela De¯ni»c~ao 2.1, acabamos de provar que A[ (B[C) = (A[B)[C.O estudante deveria tentar apreciar este tipo de demonstra»c~ao, ordenada precisa-

mente pela l¶ogica.

Deixaremos a demonstra»c~ao de A \ (B \ C) = (A \ B) \ C ao leitor, comoexerc¶³cio.

(e) Novamente, apenas a primeira parte do item (e) ser¶a demonstrada, sendo a segundaparte deixada como exerc¶³cio.

x 2 A \ (B [ C) , (x 2 A) ^ (x 2 B [ C) Def. de \, (x 2 A) ^ [(x 2 B) _ (x 2 C)] Def. de [, [(x 2 A) ^ (x 2 B)] _ [(x 2 A) ^ (x 2 C)]

Lei Dist. da l¶ogica (Cap. 1), (x 2 A \B) _ (x 2 A \ C) Def. de \, x 2 (A \B) [ (A \ C) Def. de [

Portanto, pela De¯ni»c~ao 2.1, A \ (B [ C) = (A \B) [ (A \ C).

2.3.1 Exerc¶³cios

1. Demonstre que A ½ B , A [B = B.2. Demonstre que A ½ B , A \B = A.3. Demonstre as partes (a), (b), e (c) do Teorema 2.4.4. Demonstre a segunda metade do Teorema 2.4(d).5. Demonstre a segunda metade do Teorema 2.4(e).6. Demonstre que(a) A ½ C e B ½ C implica A [B ½ C.(b) A ½ B e A ½ C implica A ½ B \ C.[Sugest~ao: Use o Teorema 1.5, do Cap¶³tulo 1, se desejar.]

7. Demonstre que (A \B) [ C = A \ (B [ C), C ½ A.8. Demonstre que se A ½ B ent~ao }(A) ½ }(B).9. Demonstre que A [B = A \B , A = B.10. Demonstre que se A ½ B, ent~ao A [ C ½ B [ C e A \C ½ B \C, para qualquerconjunto C.11. Demonstre que se A ½ C e B ½ D ent~ao A [B ½ C [D.

O Conceito de Conjunto 35

2.4 Complementos

Existe, na teoria dos conjuntos, uma opera»c~ao conhecida como complementa»c~ao, que ¶esimilar µa opera»c~ao de subtra»c~ao na aritm¶etica.

De¯ni»c~ao 2.5 Se A e B s~ao conjuntos, o complemento relativo de B em A ¶e o conjuntoA¡B, de¯nido por

A¡B = fx 2 A j x62 BgNesta de¯ni»c~ao, n~ao ¶e assumido que B ½ A.

Exemplo 2.4 Sejam

A = fa; b; c; dg e B = fc; d; e; fgEncontre A¡B e A¡ (A \B).Solu»c~ao.

A¡B = fa; b; c; dg ¡ fc; d; e; fg = fa; bge

A¡ (A \B) = fa; b; c; dg ¡ fc; dg = fa; bg

Embora o conjunto universal no sentido absoluto, o conjunto de todos os conjuntos,n~ao exista (veja o Paradoxo de Russel na se»c~ao 2.7), n~ao h¶a problema em assumirmostemporariamente que todos os conjuntos mencionados, no restante deste e dos demaiscap¶³tulos, s~ao subconjuntos de um conjunto ¯xado U , que pode ser considerado (tem-porariamente) como um conjunto universal no sentido restrito. De modo a enunciar asregras b¶asicas a respeito de complementa»c~oes, do modo mais simples poss¶³vel, assumire-mos, a menos que seja dito em contr¶ario, que todos os complementos s~ao formadosrelativamente a este conjunto U . Escreveremos ent~ao A0 como sendo U ¡A.

Exemplo 2.5 Demonstre que A¡B = A \B0.Solu»c~ao.

x 2 A \B0 ´ (x 2 A) ^ (x 2 U ¡B) Def. de \, Def. de 0´ (x 2 A) ^ [(x 2 U) ^ (x62 B)] Def. 2.5´ (x 2 A \ U) ^ (x62 B)] Assoc. de ^, Def. de \´ (x 2 A) ^ (x62 B) A \ U = A, x 2 (A¡B) Def. 2.5

Portanto, pela De¯ni»c~ao 2.1, A \B0 = A¡B.

36 O Conceito de Conjunto

Teorema 2.5 Sejam A e B conjuntos. Ent~ao

(a) (A0)0 = A.(b) ¿0 = U e U 0 = ¿.(c) A \ A0 = ¿ e A [A0 = U .(d) A ½ B se e somente se B0 ½ A0

Demonstra»c~ao. As demonstra»c~oes das partes (a), (b), e (c) usam apenas de¯ni»c~oes es~ao deixadas ao leitor, como exerc¶³cio. Daremos uma demonstra»c~ao da parte (d):

A ½ B ´ [(x 2 A)! (x 2 B)] Def. de ½´ [(x62 B)! (x62 A)] 4 Contrap.´ [(x 2 B0)! (x 2 A0)] Def. de 0

´ B0 ½ A0 Def. de ½

Portanto, acabamos de demonstrar que (A ½ B) ´ (B0 ½ A0).

Na demonstra»c~ao acima, novamente s¶³mbolos e leis da l¶ogica (do Cap¶³tulo 1) s~aousados, o que nos permite exibir cada passo da demonstra»c~ao de maneira simples eelegante, com justi¯cativas ao lado direito. O leitor ¶e encorajado a fazer uso total doCap¶³tulo 1, nas demonstra»c~oes, sempre que poss¶³vel.

A propriedade mais ¶util de complementos ¶e o seguinte Teorema de De Morgan.Compare-o com as Leis de De Morgan no Cap¶³tulo 1.

Teorema 2.6 (Teorema de De Morgan) Para quaisquer dois conjuntos A e B,

(a) (A [B)0 = A0 \B0(b) (A \B)0 = A0 [B0.

Demonstra»c~a de (a):

x 2 (A [B)0 ´» [x 2 A [B] Def. de 0

´» [(x 2 A) _ (x 2 B)] Def. de [´» (x 2 A)^ » (x 2 B) De M. da l¶ogica´ (x 2 A0) ^ (x 2 B0) Def. de 0

´ x 2 (A0 \B0) Def. de \

Portanto, pela De¯ni»c~ao 2.1, (A [B)0 = A0 \B0.A demonstra»c~ao de (b) ¶e deixada ao leitor.

4Lembremo-nos que a nega»c~ao de x 2 B, » (x 2 B), ¶e denotada por x62 B.

O Conceito de Conjunto 37

Exemplo 2.6 Sejam A, B, e C tres conjuntos quaisquer. Decida se o conjuntoA \ (B ¡ C) ¶e o mesmo que (A \B)¡ (A \ C).Solu»c~ao.

(A \B)¡ (A \ C) = (A \B) \ (A \ C)0 Exemplo 2.5= (A \B) \ (A0 [ C 0) Teor. de De M. (Teor. 2.6)= (A \B \ A0) [ (A \B \ C 0) Dist.= (A \A0 \B) [ (A \B \ C 0) Com.= ¿ [ [A \ (B \ C 0)] Teor. 2.5(c): A \ A0 = ¿= A \ (B ¡ C) Teor. 2.4(a), Exemplo 2.5

Portanto, demonstramos que A \ (B ¡ C) = (A \B)¡ (A \ C).

2.4.1 Exerc¶³cios

1. Sejam A e B conjuntos. Demonstre que A¡B = A¡ (A \B).2. Demonstre as partes (a), (b), e (c) do Teorema 2.5.3. Sejam A e B conjuntos. Demonstre que B ½ A0 se e somente se A \B = ¿.4. Sejam A e B conjuntos. Demonstre que (A¡B) [B = A se e somente se B ½ A.5. Demonstre o Teorema 2.6(b).6. Sejam A, B, e C tres conjuntos quaisquer. Demonstre que(a) (A¡ C) [ (B ¡ C) = (A [B)¡ C,(b) (A¡ C) \ (B ¡ C) = (A \B)¡ C.

7. Sejam A e B dois conjuntos quaisquer. Demonstre que A e B ¡ A s~ao disjuntos, eque A [ B = A [ (B ¡ A). (Isto mostra como representar a uni~ao A [ B como umauni~ao disjunta.)8. Sejam A, B, e C tres conjuntos quaisquer. Demonstre que(a) (A \B \ C)0 = A0 [B0 [ C 0(b) (A [B [ C)0 = A0 \B0 \ C 0.

Generalize estes resultados a proposi»c~oes envolvendo n conjuntos

A1; A2; A3; : : : ; An:

9. Para conjuntos quaisquer A e B demonstre ou refute que(a) }(A) \ }(B) = }(A \B)(b) }(A) [ }(B) = }(A [B).

10. Demonstre que se A ½ C, B ½ C, A [B = C, e A \B = ¿, ent~ao A = C ¡B.11. Sejam A e B dois conjuntos quaisquer. Demonstre que

(A¡B) [ (B ¡ A) = (A [B)¡ (A \B):

38 O Conceito de Conjunto

2.5 Diagramas de Venn

Como aux¶³lio na vizualiza»c~ao de opera»c~oes de conjuntos, introduziremos diagramas,chamados diagramas de Venn, que representam conjuntos geometricamente. Repre-sentaremos o conjunto universal relativo U por um retangulo, e os subconjuntos de Upor c¶³rculos desenhados dentro do retangulo. Por exemplo, na Figura 1, representamosdois conjuntos A e B como dois c¶³rculos sombreados; a parte duplamente hachurada ¶ea interse»c~ao A \B, e a ¶area sombreada total ¶e a uni~ao A [B.

Figura 1.

A Figura 2 mostra dois conjuntos A e B que s~ao disjuntos. A ¶area sombreada naFigura 3 representa o complemento A0 do conjunto A. O conjunto A¡B, o complementorelativo de B em A, ¶e representado pela parte sombreada na Figura 4.

Figura 2.

Figura 3.

O Conceito de Conjunto 39

Figura 4.

Figura 5.

Figura 6.

Um diagrama de Venn t¶³pico de tres conjuntos A, B, e C pode ser desenhadocomo na Figura 5. Esses tres conjuntos dividem o conjunto universal U em 8 partes, talcomo indicado na ¯gura 6.

Usando os diagramas acima, podemos dar argumentos heur¶³sticos simples paraa validade de, por exemplo, a lei distributiva A \ (B [ C) = (A \ B) [ (A \ C),como segue: Da Figura 6, A \ (B [ C) consiste das ¶areas 2, 3 e 7. Por outro lado,(A\B)[ (A\C) ¶e representada pela uni~ao das ¶areas 2 e 7, e ¶areas 3 e 7. Portanto, aigualdade A\(B[C) = (A\B)[(A\C) parece plaus¶³vel. Entretanto, em matem¶atica,um argumento heur¶³stico n~ao pode ser aceito como uma demonstra»c~ao.

40 O Conceito de Conjunto

2.5.1 Exerc¶³cios

1. Desenhe um diagrama de Venn para A ½ B.2. Desenhe diagramas de Venn para A \B0, A0 \B e A0 \B0.3. Desenhe diagramas de Venn para A [B0, A0 [B e A0 [B0.

Nos problemas de 4 a 10, desenhe diagramas de Venn e de argumentos heur¶³sticosde que cada uma das a¯rma»c~oes ¶e plaus¶³vel.

4. A \ (B \ C) = (A \B) \ C.5. A [ (B [ C) = (A [B) [ C.6. A [ (B \ C) = (A [B) \ (A [ C).7. (A [B)0 = A0 \B0.8. (A \B)0 = A0 [B0.9. A \ (B ¡ A) = ¿ e A [ (B ¡ A) = A [B.10. (A [B)¡ (A \B) = (A¡B) [ (B ¡ A).

2.6 Fam¶³lias indexadas de conjuntos

Recordemos que um conjunto ¶e uma cole»c~ao de elementos que s~ao todos distintos.Grosseiramente falando, uma fam¶³lia ¶e uma cole»c~ao de objetos, n~ao necessariamentedistintos, chamados membros. Por exemplo, fa; a; ag ¶e uma fam¶³lia com tres membros,a, a e a. Mas a mesma fam¶³lia fa; a; ag, considerada como um conjunto ¶e apenas oconjunto unit¶ario fag com um ¶unico elemento, a.

Seja ¡ um conjunto e suponhamos que para cada elemento ° de ¡, existe umconjunto associado A°. A fam¶³lia de todos esses conjuntos A° ¶e chamada uma fam¶³liaindexada de conjuntos, indexada pelo conjunto ¡, e ¶e denotada por

fA° j ° 2 ¡g

Por exemplo, a fam¶³lia de conjuntos, f1; 2g; f2; 4g; f3; 6g; : : : ; fn; 2ng; : : : , podeser considerada como uma fam¶³lia indexada de conjuntos, indexada pelo conjunto N dosn¶umeros naturais, sendo An = fn; 2ng para cada n 2 N. Esta fam¶³lia de conjuntos podeser denotada por ffn; 2ng jn 2 Ng.

Uma fam¶³lia arbitr¶aria de conjuntos pode parecer n~ao ser indexada, mas na maioriados casos podemos facilmente encontrar um conjunto ¡ que pode ser usado para indexara fam¶³lia de conjuntos dada.

Exemplo 2.7 Indexe a fam¶³lia F de conjuntos ¿;N;Z;Q;R;R.

Solu»c~ao. Como esta fam¶³lia cont¶em exatamente seis membros (embora dois deles sejamo mesmo), escolhemos ¡ = f1; 2; 3; 4; 5; 6g e fazemos A1 = ¿, A2 = N, A3 = Z,A4 = Q, A5 = R e A6 = R. A fam¶³lia de conjuntos est¶a ent~ao indexada.

Virtualmente todos os s¶³mbolos e nota»c~oes usados para conjuntos aplicam-se afam¶³lias tamb¶em. Por exemplo, ¿ 2 F e R+ 62 F indicam, respectivamente, que ¿

O Conceito de Conjunto 41

¶e um membro da fam¶³lia F e R+ n~ao ¶e membro de F. Podemos tamb¶em escreverF = f¿;N;Z;Q;R;Rg.

Estendamos agora os conceitos de uni~ao [ e interse»c~ao \, das De¯ni»c~oes 1.3 e1.4, a uma fam¶³lia arbitr¶aria de conjuntos.

De¯ni»c~ao 2.6 Seja F uma fam¶³lia arbitr¶aria de conjuntos. A uni~ao dos conjuntos emF, denotada por

S

A2F A ouS

F, ¶e o conjunto de todos os elementos que est~ao em Apara algum A 2 F. Ou seja,

[

A2F

A = fx 2 U jx 2 A para algum A 2 Fg

Se a fam¶³lia F ¶e indexada pelo conjunto ¡, a seguinte nota»c~ao alternativa pode ser usada:[

°2¡

A° = fx 2 U jx 2 A° para algum ° 2 ¡g

Se o conjunto ¡ de¶³ndices ¶e ¯nito, ¡ = f1; 2; 3; : : : ; ng para algum n¶umero naturaln, nota»c~oes mais intuitivas, tais como

n[

i=1

Ai ou A1 [ A2 [ ¢ ¢ ¢ [ An

s~ao usadas freqÄuentemente paraS

°2¡A°.

Exemplo 2.8 Encontre a uni~ao da fam¶³lia de conjuntos

f1g; f2; 3g; f3; 4; 5g; : : : ; fn; n+ 1; : : : ; 2n¡ 1g:

Solu»c~ao. Esta fam¶³lia de conjuntos pode ser considerada como indexada por ¡ =f1; 2; 3; : : : ; ng, sendo Ai = fi; i + 1; : : : ; 2i ¡ 1g, para cada i 2 ¡. O problemase reduz a encontrar

Sn

i=1fi; i + 1; : : : ; 2i ¡ 1g. Observe que cada inteiro entre 1 e2n ¡ 1 pertence a algum Ai na fam¶³lia, e nenhum outro elemento pertence a qualquerdesses Ai. Portanto,

n[

i=1

fi; i+ 1; : : : ; 2i¡ 1g = f1; 2; 3; : : : ; 2n¡ 1g

De¯ni»c~ao 2.7 Seja F uma fam¶³lia arbitr¶aria de conjuntos. A interse»c~ao de conjuntosem F, denotada por

T

A2F ouT

F, ¶e o conjunto de todos os elementos que est~ao em Apara todo A 2 F. Ou seja,

\

A2F

= fx 2 U jx 2 A para todo A 2 Fg

42 O Conceito de Conjunto

Aqui, a a¯rma»c~ao \x 2 A para todo A 2 F" pode ser expressada alternativamentecomo \A 2 F ! x 2 A. Esta ¶ultima express~ao ¶e melhor na demonstra»c~ao de teoremas,como veremos no Teorema 2.7 adiante.

Se a fam¶³lia F ¶e indexada pelo conjunto ¡, a seguinte nota»c~ao alternativa pode serusada:

\

°2¡

A° = fx 2 U jx 2 A° para todo ° 2 ¡g

Se o conjunto de ¶³ndices ¡ for ¯nito, ¡ = f1; 2; : : : ; ng para algum inteiro positivon, ent~ao como no caso da uni~ao, escrevemos habitualmente

n\

i=1

Ai ou A1 \ A2 \ ¢ ¢ ¢An

em vez deT

°2¡A°.

Sejam a e b dois n¶umeros reais quaisquer. Por intervalo aberto ]a; b[ entendemoso subconjunto fx 2 R j a < x < bg de R. Segue que se a ¸ b ent~ao ]a; b[ = ¿.

Exemplo 2.9 Encontre a interse»c~ao da fam¶³lia de intervalos abertos

]0; 1[ ; ]0; 12[ ; ]0; 1

3[ ; : : :

Solu»c~ao. Devemos encontrar o conjuntoT

n2N ]0;1

n[. Falando intuitivamente, a fam¶³lia

dada ¶e uma seqÄuencia de intervalos \decrescentes" ]0; 1=n[ , em que o intervalo ]0; 1=n[se \aproxima" do conjunto vazio ¿ quando n torna-se grande. Portanto, podemosconjeturar que a interse»c~ao

T

n2N ]0; 1=n[ deve ser o conjunto vazio. Demonstraremosque nossa conjetura ¶e verdadeira. Suponha em contr¶ario, que existe algum n¶umero reala 2 Tn2N ]0; 1=n[. Ent~ao ter¶³amos 0 < a < 1=n para todo n 2 N. Isto contradiz o fatode que para um n¶umero real ¯xado a > 0, sempre existe um n 2 N, su¯cientementegrande, tal que 1=n < a. A contradi»c~ao mostra que

T

n2N ]0; 1=n[ = ¿.

Teorema 2.7 Seja fA° j ° 2 ¡g uma fam¶³lia vazia de conjuntos; isto ¶e, ¡ = ¿. Ent~ao(a)

S

°2¿A° = ¿.

(b)T

°2¿A° = U .

Demonstra»c~ao. (a) Para mostrarS

°2¿A° = ¿, mostramos equivalentemente que x62S

°2¿A° para todo x (em U):

x62 S

°2¿A° ´»

0

@x 2 S

°2¿A°

1

A Nota»c~ao

´» (x 2 A° para algum ° 2 ¿) Def. 2.6´ (x62 A° para todo ° 2 ¿) N.Q. (Cap. 1)´ (° 2 ¿! x62 A°)

O Conceito de Conjunto 43

A ¶ultima a¯rma»c~ao ¶e, pelo Teorema 1.7 do Cap¶³tulo 1, verdadeira para todo x 2 U ,pois ° 2 ¿ ¶e uma contradi»c~ao. Isto completa a demonstra»c~ao da parte (a).

(b) Demonstraremos que x 2 T°2¿A° , para todo x em U . Observe que

x 2 T

°2¿A° ´ (x 2 A° ; 8° 2 ¿) Def. 2.7

´ (° 2 ¿! x 2 A°)

A ¶ultima asser»c~ao ¶e, como explicamos na demonstra»c~ao da parte (a), uma a¯r-ma»c~ao verdadeira para todo x 2 U . A demonstra»c~ao est¶a terminada.

Muitos teoremas, a respeito de opera»c~oes de um n¶umero ¯nito de conjuntos, podemser generalizados a teoremas a respeito de opera»c~oes de uma fam¶³lia arbitr¶aria de con-juntos. Por exemplo, o seguinte teorema generaliza o Teorema de De Morgan. Compareeste teorema com o Teorema 2.6.

Teorema 2.8 (Teorema de De Morgan Generalizado) Seja fA° j ° 2 ¡g umafam¶³lia arbitr¶aria de conjuntos. Ent~ao

(a)³

S

°2¡A°

´0

=T

°2¡A0

°.

(b)³

T

°2¡A°

´

0

=S

°2¡A0

° .

Demonstra»c~ao. Demonstraremos apenas a parte (a), e deixaremos a parte (b) ao estu-dante.

x 2Ã

S

°2¡

!

0

´»Ã

x 2 S

°2¡

!

Def. de 0

´» (9° 2 ¡)(x 2 A°) Def. 2.6´ (8° 2 ¡)(x62 A°) N.Q. (Cap. 1)´ (8° 2 ¡)(x 2 A0°) Def. de 0

´ x 2 T°2¡A0

° Def. 2.7

Portanto, pela De¯ni»c~ao 2.1,³

S

°2¡A°

´0

=T

°2¡A0

° .

O seguinte teorema ¶e uma generaliza»c~ao do Teorema 2.4(e).

Teorema 2.9 (Leis Distributivas Generalizadas) Seja A um conjunto e seja F =fB° j ° 2 ¡g uma fam¶³lia arbitr¶aria de conjuntos. Ent~ao

(a) A \³

S

°2¡B°

´

=S

°2¡(A \B°):(b) A [

³

T

°2¡B°

´

=T

°2¡(A [B°):

44 O Conceito de Conjunto

Demonstra»c~ao. Um elemento x est¶a no conjunto A\³

S

°2¡B°

´

se e somente se x 2 Ae x 2 S°2¡B° , o que, de acordo com a De¯ni»c~ao 2.6, ¶e equivalente a

x 2 A e x 2 B° para algum ° 2 ¡

Esta ¶ultima asser»c~ao pode ser expressa, pela De¯ni»c~ao 2.4, como

x 2 A \B° para algum ° 2 ¡

o que, pela De¯ni»c~ao 2.6, ¶e precisamente x 2 S°2¡(A\B°). Assim, pela De¯ni»c~ao 2.1,A \

³

S

°2¡B°

´

=S

°2¡(A \B°).A demonstra»c~ao da parte (b) ¶e um exerc¶³cio.

2.6.1 Exerc¶³cios

1. Sejam ¡ = f1; 2; 3; 4g, e A1 = fa; b; c; dg, A2 = fb; c; dg, A3 = fa; b; cg, A4 =fa; bg. Encontre o seguinte.(a)

S4

i=1Ai.(b)

T4

i=1Ai.2. Para dois n¶umeros reais quaisquer a e b, por intervalo fechado [a; b] entendemos oconjunto fx 2 R j a · x · bg. Se a > b, [a; b] = ¿. Encontre os seguintes conjuntos.(a)

T

n2N[0; 1=n](b)

S

n2N[0; 1=n]

(c)T99

n=1[0; 1=n]

3. Demonstre o Teorema 2.8(b):³

T

°2¡A°

´

0

=S

°2¡A0

°.

4. Demonstre o Teorema 2.9(b): A [³

T

°2¡B°

´

=T

°2¡(A [B°).5. Expanda(a) (A1 [A2) \ (B1 [B2 [B3) em uma uni~ao de interse»c~oes, e(b) (A1 \ A2) [ (B1 \ B2 \ B3) em uma interse»c~ao de uni~oes. [Sugest~ao: Use o

Teorema 2.9 v¶arias vezes.]6. Expanda(a) (

Sm

i=1Ai) \ (Sn

j=1Bj) em uma uni~ao de interse»c~oes, e(b) (

Tmi=1Ai) [ (

Tnj=1Bj) em uma interse»c~ao de uni~oes. [Veja Problema 5.]

7. Sejam fA° j ° 2 ¡g e fB± j ± 2 ¢g duas fam¶³lias de conjuntos. Expanda(a) (

S

°2¡A°) \ (S

±2¢B±) em uma uni~ao de interse»c~oes, e(b) (

T

°2¡A°) [ (T

±2¢B±) em uma interse»c~ao de uni~oes. [Veja Problemas 5 e 6.]

2.7 O paradoxo de Russel

Neste momento muitos de n¶os achamos que entendemos o signi¯cado de conjunto|pelomenos intuitivamente. A maioria de n¶os, fazendo um curso de teoria dos conjuntos pela

O Conceito de Conjunto 45

primeira vez, n~ao perceberia o que h¶a de errado em considerar \o conjunto de todos osconjuntos" ou o assim chamado \conjunto universal" no sentido absoluto. Na verdade,por um per¶³odo de tempo (pelo menos de 1895, quando Georg Cantor pioneiramentecriou uma teoria dos conjuntos, at¶e 1902, quando o Paradoxo de Russel apareceu),a existencia de um tal conjunto universal era considerada como certa. Foi o famoso¯l¶osofo ingles Bertrand Russel (1872{1970)5 que chocou a comunidade matem¶atica em1902, declarando que a admiss~ao de um conjunto de todos os conjuntos levaria a umacontradi»c~ao. Este ¶e o famoso Paradoxo de Russel. Apresentaremos este paradoxo naforma de dois lemas aparentemente contradit¶orios, dos quais um teorema ¶e conseqÄuencia.

Lema 2.1 Suponhamos que existe um conjunto U de todos os conjuntos. Seja R =fS 2 U jS62 Sg.6 Ent~ao R62 R.

Demonstra»c~ao. Suponhamos, ao contr¶ario, que R 2 R. Ent~ao, pela especi¯ca»c~aodo conjunto R, devemos ter R 62 R, o que contradiz a hip¶otese de que R 2 R. Acontradi»c~ao prova que R62 R.

Lema 2.2 Suponhamos que existe um conjunto U de todos os conjuntos. Seja R oconjunto fS 2 U jS62 Sg. Ent~ao R 2 R.

Demonstra»c~ao. Suponha o contr¶ario, que R62 R. Ent~ao, como R 2 U , temos R 2 Rpela de¯ni»c~ao de R. Isto ¶e uma contradi»c~ao. Assim, R 2 R.

Teorema 2.10 N~ao existe um conjunto de todos os conjuntos.

Demonstra»c~ao. Em vista dos Lemas 2.1 e 2.2, o conjunto de todos os conjuntos n~aopode existir. Pois, se existisse, levaria µa contradi»c~ao \R62 R e R 2 R".

Paul R. Halmos coloca-o do seguinte modo: \Nada cont¶em tudo."7

5Bertrand Russel nasceu em 18 de maio de 1872, em Trelleck, Wales, Inglaterra. Antes que comple-tasse quatro anos, seus pais faleceram. Foi sempre um garoto quieto e t¶³mido, at¶e ingressar no TrinityCollege, na Universidade de Cambridge, em 1890. Ap¶os tres anos de Matem¶atica, concluiu que o quelhe estava sendo ensinado estava cheio de erros. Vendeu seus livros de matem¶atica e mudou-se paraa ¯loso¯a. No seu Principia Mathematica (1910{1913), um trabalho monumental em tres volumes,em co-autoria com Alfred North Whitehead (1861{1947), tentou remodelar a teoria dos conjuntos, demodo a evitar paradoxos. Em 1918 escreveu \Quero posicionar-me µa borda do mundo e perscrutar aescurid~ao al¶em, e ver um pouco mais do que outros viram. : : : Quero trazer de volta ao mundo doshomens um pouquinho de sabedoria". Ele seguramente o fez, mais do que \um pouquinho". No mesmoano, foi preso por um coment¶ario desfavor¶avel sobre o ex¶ercito americano. Em 1950 recebeu a Ordemdo M¶erito do rei da Inglaterra e o Premio Nobel de Literatura. Em seus ¶ultimos anos, liderou v¶ariasmanifesta»c~oes contra os armamentos nucleares.

6Conforme a regra da especi¯ca»c~ao, R ¶e um conjunto freqÄuentemente chamado \o conjunto deRussel".

7Paul R. Halmos, Naive Set Theory (Teoria Ingenua dos Conjuntos), D. Van Nostrand Company,Inc., New York, 1960, p.6.

46 O Conceito de Conjunto

2.8 Um coment¶ario hist¶orico

A teoria moderna dos conjuntos ¶e geralmente considerada ter sido criada em 1859 pelomatem¶atico famoso Georg Cantor8 (1845{1918), que notou a necessidade de uma talteoria quando estudava s¶eries trigonom¶etricas. Cantor escreveu: \Por um `conjunto'entenderemos qualquer cole»c~ao dentro de um todo de objetos distintos de¯nidos, denossa intui»c~ao ou pensamento". Esta de¯ni»c~ao n~ao proibe ningu¶em de considerar o\conjunto" de todos os conjuntos, como o fez Bertrand Russel. A di¯culdade real nade¯ni»c~ao de Cantor de um conjunto ¶e a palavra \cole»c~ao". O que ¶e uma cole»c~ao? ¶Eclaro que podemos procur¶a-la em um dicion¶ario e encontrar algo como estas de¯ni»c~oes:

\cole»c~ao: um grupo de objetos coletados."

\grupo: um agregado ou cole»c~ao."

\agregado: uma cole»c~ao."

Estas di¯cilmente nos ajudar~ao. Quando um matem¶atico d¶a uma de¯ni»c~ao, n~ao¶e para que seja um mero sinonimo, tal como o s~ao \cole»c~ao" e \conjunto", ou umade¯ni»c~ao circular como encontrar¶³amos em um dicion¶ario. Aparentemente, Cantor n~aoestava consciente de que o termo \conjunto" era realmente inde¯n¶³vel.

Para evitar qualquer di¯culdade, tal como o Paradoxo de Russel na teoria dosconjuntos, devemos aceitar os termos \conjunto" e \elemento" como termos inde¯nidos,ou primitivos, e guiar estes conceitos primitivos por um n¶umero de axiomas, incluindo oAxioma da Especi¯ca»c~ao e o Axioma do Conjunto das Partes, que foram apresentadosna se»c~ao 2.2. Outros axiomas, tais como \A = B" se e somente se A e B cont¶em osmesmos elementos" (Axioma da Extens~ao), \¿ ¶e um conjunto" (Axioma do ConjuntoVazio), \Se A e B s~ao conjuntos, ent~ao tamb¶em o ¶e fA;Bg" (Axioma do Emparelha-mento), e \Se F ¶e um conjunto de conjuntos ent~ao F ¶e um conjunto" (Axioma dasUni~oes) s~ao freqÄuentemente dados em tratamentos axiom¶aticos da teoria dos conjuntos.

O Paradoxo de Russel n~ao foi o ¶unico a aparecer na teoria dos conjuntos. Logodepois do seu aparecimento, muitos paradoxos foram constru¶³dos por v¶arios matem¶aticose l¶ogicos. Como uma conseqÄuencia de todos esses paradoxos, muitos matem¶aticos el¶ogicos contribu¶³ram a v¶arias formula»c~oes da \teoria axiom¶atica dos conjuntos", cadauma projetada de modo a evitar esses paradoxos e, ao mesmo tempo, a preservar ocorpo principal da teoria dos conjuntos de Cantor. Entretanto, at¶e o momento da escritadestas notas9, ningu¶em apareceu com um sistema axiom¶atico completamente satisfat¶oriopara a teoria dos conjuntos.

Apesar das di¯culdades supracitadas, a teoria dos conjuntos de Cantor j¶a penetrouem todos os ramos da matem¶atica moderna, e provou ser de importancia particularnos fundamentos da an¶alise moderna e da topologia. Na verdade, mesmo os mais

8Georg Cantor nasceu em S~ao Petersburgo, R¶ussia, em 1845, mudou-se para a Alemanha em 1856,estudou matem¶atica na Universidade de Berlim (1863{1869), e ensinou na Universidade de Halle (1969{1905). Um dos interesses de Cantor eram as s¶eries trigonom¶etricas, que o levaram a investigar osfundamentos da an¶alise. Como resultado, ele criou o trabalho revolucion¶ario sobre a teoria dos conjuntose uma aritm¶etica dos n¶umeros trans¯nitos.

91974

O Conceito de Conjunto 47

simples e bem constru¶³dos sistemas axiom¶aticos da teoria dos conjuntos s~ao inteiramenteadequados para a constru»c~ao de virtualmente toda a matem¶atica cl¶assica (e.g., a teoriados n¶umeros reais e complexos, ¶algebra, topologia, etc.).

48 Relac»~oes e Func»~oes

3

Rela»c~oes e Fun»c~oes

O cap¶³tulo inicia-se com uma discuss~ao sobre pares ordenados e o produto cartesianode dois conjuntos. O conceito de rela»c~ao ¶e ent~ao de¯nido como sendo um conjuntode pares ordenados. A conex~ao ¶³ntima entre parti»c~oes e rela»cµoes de equivalencia, numconjunto, ¶e cuidadosamente examinada. Como prepara»c~ao para os leitores que pretendemseguir estudando mais matem¶atica moderna, propriedades importantes de fun»c~oes s~aoestudadas. Uma grande quantidade de exemplos ¶e constru¶³da.

3.1 Produto cartesiano de conjuntos

Dados dois objetos quaisquer a e b, podemos formar um novo objeto (a; b), chamado parordenado a,b.1 2 O adjetivo \ordenado" enfatiza aqui que a ordem pela qual os objetosa e b aparecem entre parenteses ¶e essencial. Note que o par ordenado (a; b) n~ao ¶e omesmo que o conjunto fa; bg. H¶a um modo satisfat¶orio, embora complicado, de de¯niro par ordenado (a; b) como sendo o conjunto ffag; fa; bgg, de onde segue a propriedade\(a; b) = (c; d), a = c e b = d" (Veja Problema 11, Exerc¶³cios 1.3.1).

Dois pares ordenados (a; b) e (c; d) s~ao considerados iguais (=) se e somente sea = c e b = d. Por exemplo, (x; y) = (7; 8) se e somente se x = 7 e y = 8.

Em geometria anal¶³tica, o plano cartesiano pode ser considerado como o conjuntode todos os pares ordenados de n¶umeros reais. Enunciaremos formalmente este conceitodo seguinte modo:

De¯ni»c~ao 3.1 Sejam A e B dois conjuntos quaisquer. O conjunto de todos os paresordenados (x; y), com x 2 A e y 2 B, ¶e chamado o produto cartesiano de A e B, e ¶e

1Infelizmente, a nota»c~ao (a; b) para um par ordenado ¶e a mesma para um intervalo aberto quando ae b s~ao n¶umeros reais. Entretanto, o leitor atento dever¶a ser sempre capaz de fazer a distin»c~ao a partirdo contexto.

2Desde o Cap¶³tulo 2, j¶a ¯zemos a op»c~ao por denotar o intervalo aberto de extremos a e b por ]a; b[.(N. do T.)

49

50 Relac»~oes e Func»~oes

denotado por A£B. Simbolicamente,

A£B = f(x; y) j x 2 A ^ y 2 Bg

Para o par ordenado (a; b), a ¶e chamado a primeira coordenada e b ¶e a segundacoordenada.

Exemplo 3.1 Sejam A = fa; b; cg e B = f1; 2g. Encontre os produtos cartesianosA£B e B £A.Solu»c~ao. Pela De¯ni»c~ao 3.1 acima, temos

A£B = f(a; 1); (a; 2); (b; 1); (b; 2); (c; 1); (c; 2)g

eB £ A = f(1; a); (1; b); (1; c); (2; a); (2; b); (2; c)g

Notamos que A£B6= B £A. Podemos representar geometricamente o produtocartesiano A£B como o conjunto de pontos 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 pares ordenados (a; b), tais que a 2 Ae b 2 ¿, e como o conjunto vazio ¿ n~ao cont¶em nenhum elemento, n~ao h¶a nenhum bem ¿; portanto A£ ¿ = ¿. Analogamente, ¿£ A = ¿.

Teorema 3.1 Sejam A, B e C tres conjuntos quaisquer. Ent~ao

(a) A£ (B \ C) = (A£B) \ (A£ C).(b) A£ (B [ C) = (A£B) [ (A£ C).

Relac»~oes e Func»~oes 51

Demonstra»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., Assoc. (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 \

Portanto, pela De¯ni»c~ao 2.1, do Cap¶³tulo 2, acabamos de demonstrar que

A£ (B \ C) = (A£B) \ (A£ C)

Informalmente, esta igualdade pode ser enunciada: O produto cartesiano distribuisobre a interse»c~ao.

Deixaremos a demonstra»c~ao da parte (b) ao leitor, como exerc¶³cio.

Teorema 3.2 Sejam A, B e C conjuntos quaisquer. Ent~ao

A£ (B ¡ C) = (A£B)¡ (A£ C)

Ou seja, o produto cartesiano distribui sobre a complementa»c~ao.

Demonstra»c~ao.

(a; x)2 A£ (B ¡ C), (a 2 A) ^ (x 2 B ¡ C) Def. 3.1, (a 2 A) ^ (x 2 B ^ x62 C) Def. 2.5 (Cap. 2), (a 2 A) ^ (a 2 A) ^ (x 2 B) ^ (x62 C)

Idemp., Assoc. (Cap. 1), [(a 2 A) ^ (x 2 B)] ^ [(a 2 A) ^ (x62 C)]

Com., Assoc. (Cap. 1), [(a; x) 2 A£B] ^ [(a; x)62 A£ C] Def. 3.1, (a; x) 2 (A£B)¡ (A£ C) Def. 2.5 (Cap. 2)

Assim, acabamos de demonstrar que

A£ (B ¡ C) = (A£B)¡ (A£ C)

52 Relac»~oes e Func»~oes

3.1.1 Exerc¶³cios

1. Descreva cada um dos seguintes conjuntos, geometricamente, esbo»cando um gr¶a¯cono plano cartesiano.(a) f(x; y) 2 R£ R jx = yg(b) f(x; y) 2 R£ R j x > yg(b) f(x; y) 2 R£ R j jx+ yj · 1g

2. Sob quais condi»c~oes nos conjuntos A e B ser¶a verdade que A£B = B £ A?3. Demonstre o Teorema 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, ent~ao A£ C ½ B £ C.6. Se o conjunto A temm elementos e o conjuntoB tem n elementos, quantos elementos(pares ordenados) tem A£B?7. O produto cartesiano A£A tem 9 elementos, dentre os quais s~ao encontrados (¡1; 0)e (0; 1). Encontre os elementos restantes 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 se e somente se A ½ C e B ½ D.(b) O conjunto das partes }(A£B) de A£B ¶e o produto cartesiano }(A)£ }(B)

dos conjuntos das partes }(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 A1; A2; : : : ; An conjuntos quaisquer. Pode voce generalizar a De¯ni»c~ao 3.1ao produto cartesiano A1 £ A2 £ A3 de tres conjuntos? Pode voce generalizar isto aoproduto cartesiano A1 £A2 £ ¢ ¢ ¢ £ An de n conjuntos?11. De¯na o par ordenado (x; y) como sendo o conjunto ffxg; fx; ygg. Use estade¯ni»c~ao para demonstrar que (a; b) = (c; d) se e somente se a = c e b = d.

3.2 Rela»c~oes

Dados dois conjuntos A e B, n~ao necessariamente distintos, quando dizemos que umelemento a de A est¶a relacionado a outro elemento b de B,por uma rela»c~ao R, estamosfazendo uma a¯rma»c~ao sobre o par ordenado (a; b) no produto cartesiano A£B. Por-tanto, uma de¯ni»c~ao matem¶atica de uma rela»c~ao pode ser dada precisamente em termosde pares ordenados no produto cartesiano de conjuntos.

De¯ni»c~ao 3.2 Uma rela»c~ao R de A para B (ou de A em B) ¶e um subconjunto doproduto cartesiano A £ B. ¶E costume denotar (a; b) 2 R por aR b. O s¶³mbolo aR b ¶elido \a est¶a R-relacionado a b".

FreqÄuentemente A e B s~ao um mesmo conjunto, digamos X. Nesse caso, diremosque R ¶e uma rela»c~ao em X em vez de \deX paraX". Por exemplo, em uma comunidade

Relac»~oes e Func»~oes 53

X,3 dizer que a (para Alberto) ¶e o marido de b (para Beatriz), ¶e considerar Alberto eBeatriz como um par (ordenado) (a; b) na rela»c~ao M (de ser o marido de : : : ). Os¶³mbolo aM b ou (a; b) 2 M pode ser lido \a ¶e marido de b".

N~ao ¶e necess¶ario colocar Beatriz depois de Alberto no par ordenado (a; b). Podemosdizer que Beatriz ¶e a esposa de Alberto, ou que o par ordenado (b; a) est¶a na rela»c~ao E(de ser a esposa de : : : ). O s¶³mbolo bEa ou (b; a) 2 Epode ser lido: \b ¶e a esposa dea". 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 necessariamente distintos, e seja Ruma rela»c~ao de A para B. Ent~ao a rela»c~ao inversa R¡1 da rela»c~ao R ¶e a rela»c~ao de Bpara A tal que bR¡1 a se e somente se aR b. Ou seja,

R¡1 = f(b; a) j (a; b) 2 Rg

Exemplo 3.3 (a) Sejam A = fa; bg, B = fx; y; zg, e seja R ½ A £ B dada porR = f(a; x); (b; y)g. Ent~ao R¡1 = f(x; a); (y; b)g ½ B £ A.

(b) SejaR = f(x; y) 2 N£ N j x divide yg

Ent~aoR¡1 = f(y; x) 2 N£ N j y ¶e m¶ultiplo de xg

Seja R uma rela»c~ao de A para B. O dom¶³nio da rela»c~ao R, denotado por Dom(R),¶e o conjunto de todos aqueles a 2 A tais que aR b para algum b 2 B; e a imagem deR, denotada por Im(R), ¶e o conjunto de todos aqueles b 2 B, tais que aR b para alguma 2 A. Simbolicamente,

Dom(R) = fa 2 A j (a; b) 2 R para algum b 2 Bg

eIm(R) = fb 2 B j (a; b) 2 R para algum a 2 Ag

No exemplo das rela»c~oes M (ser o marido de : : : ) e E (ser a esposa de : : : )na comunidade X, o dom¶³nio de M ¶e o conjunto de todos os homens em X que s~aocasados, enquanto que o dom¶³nio de E¶e o conjunto das esposas em X, e a imagem deE¶e o conjunto de todos os maridos em X, Isto ¶e,

Dom(E) = Im(M )

eIm(E) = Dom(M )

Pode voce tirar uma conclus~ao geral? (Veja Problema 3 ao ¯nal desta se»c~ao).

3Aqui, X ¶e o conjunto de todos os membros da comunidade.

54 Relac»~oes e Func»~oes

Exemplo 3.4 No Exemplo 3.3(a), Dom(R) = fa; bg e Im(R) = fx; yg. No Exemplo3.3(b), Dom(R) = N = Im(R).

De¯ni»c~ao 3.4 Seja R uma rela»c~ao em um conjunto X. Ent~ao dizemos que(a) R ¶e re°exiva se e somente se 8x 2 X; xR x.(b) R ¶e sim¶etrica se e somente se xR y ) yR x.(c) R ¶e transitiva se e somente se xR y ^ y R z ) xR z.(d) R ¶e uma rela»c~ao de equivalencia se e somente se R ¶e re°exiva, sim¶etrica e

transitiva.

A rela»c~ao de igualdade, =, no conjunto R de n¶umeros reais ¶e claramente umarela»c~ao de equivalencia. Seja X um conjunto de bolas coloridas e sejam duas bolas a eb relacionadas por R se e somente se a e b tem a mesma cor. Ent~ao a rela»c~ao R ¶e umarela»c~ao de equivalencia.

Rela»c~oes de equivalencia s~ao particularmente importantes na matem¶atica moderna.Por exemplo, grupos quocientes na ¶algebra, espa»cos quocientes na topologia, e sistemasnum¶ericos modulares na teoria dos n¶umeros, todos envolvem certos tipos de rela»c~oes deequivalencia.

Dado um conjunto n~ao vazio X, existem sempre pelo menos duas rela»c~oes deequivalencia em X; uma destas ¶e a rela»c~ao diagonal ¢X (tamb¶em chamada rela»c~aoidentidade) de¯nida por

¢X = f(x; x) jx 2 Xgque relaciona cada elemento com ele mesmo. Geometricamente, se X ¶e representadocomo um intervalo linear, ent~ao X £X ¶e um quadrado e ¢X ¶e a diagonal \principal"do quadrado.

Figura 8.

H¶a, no outro extremo, sempre outra rela»c~ao de equivalencia R = X£X em X. Arela»c~ao ¢X ¶e a menor de todas as rela»c~oes de equivalencia em X, enquanto que X £X¶e a maior.

Exemplo 3.5 Seja m um inteiro positivo qualquer ¯xado. A rela»c~ao de congruencia´ m¶odulo m, no conjunto Z dos n¶umeros inteiro ¶e de¯nida por x ´ y (mod m) se esomente se x¡ y = km para algum k 2 Z. A rela»c~ao de congruencia ¶e uma rela»c~ao deequivalencia em Z.

Relac»~oes e Func»~oes 55

Demonstra»c~ao.

(a) Para cada x em Z, como x¡ x = 0 ¢m, temos x ´ x (mod m). Portanto, arela»c~ao ¶e re°exiva.

(b) Se x ´ y (mod m), ent~ao x¡y = km para algum k 2 Z. ConseqÄuentemente,y ¡ x = (¡k)m e ¡k 2 Z, ou y ´ x (mod m). Portanto, a rela»c~ao ¶e sim¶etrica.

(c) Se x ´ y (mod m) e y ´ z (mod m), ent~ao x¡y = k1m e y¡z = k2m paraalguns k1 e k2 em Z. Portanto, x¡ z = (x¡ y) + (y¡ z) = (k1+ k2)m e k1+ k2 2 Z,o que mostra que x ´ z (mod m). Portanto, a rela»c~ao ¶e transitiva.

Portanto, acabamos de demonstrar que a rela»c~ao de congruencia (m¶odulo m) ¶euma rela»c~ao de equivalencia em Z.

Como um caso expecial para o Exemplo 3.5, seja m = 2. Ent~ao, x ´ y (mod 2)se e somente se x¡y ¶e um inteiro par. ConseqÄuentemente, x ´ y (mod 2) se e somentese x e y s~ao ambos pares ou ambos ¶³mpares.

3.2.1 Exerc¶³cios

1. Seja R uma rela»c~ao de A para B. Demonstre que (R¡1)¡1 = R.2. Seja A = fa; b; cg e seja R = f(a; c); (c; b); (a; b)g. Encontre o dom¶³nio de R e aimagem de R.3. Seja R uma rela»c~ao de A para B. Demonstre que(a) Dom(R¡1) = Im(R)(b) Im(R¡1) = Dom(R)

4. Seja A = fa; b; cg e seja

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. De um exemplo de uma rela»c~ao que ¶e re°exiva e transitiva, mas n~ao ¶e sim¶etrica.6. De um exemplo de uma rela»c~ao que ¶e sim¶etrica e transitiva, mas n~ao ¶e re°exiva.7. Seja R uma rela»c~ao em um conjunto X. Demonstre que(a) R ¶e re°exiva se e somente se R ¾ ¢X ;(b) R ¶e sim¶etrica se e somente se R = R¡1;(c) R ¶e re°exiva se e somente se R¡1 ¶e re°exiva;(d) R ¶e sim¶etriva se e somente se R¡1 ¶e sim¶etrica;(e) R ¶e transitiva se e somente se R¡1 ¶e transitiva;(f) R ¶e uma rela»c~ao de equivalencia se e somente se R¡1 ¶e uma rela»c~ao de equivalencia.

8. Seja X = Z£ (Z¡f0g). De¯na uma rela»c~ao » em X declarando que (a; b) » (c; d)se e somente se ad = bc. Demonstre que a rela»c~ao » ¶e uma rela»c~ao de equivalencia.

56 Relac»~oes e Func»~oes

3.3 Parti»c~oes e rela»c~oes de equivalencia

De¯ni»c~ao 3.5 Seja X um conjunto n~ao vazio. Por uma parti»c~ao P de X queremosdizer um conjunto de subconjuntos n~ao vazios de X, tal que

(a) Se A;B 2 P e A6= B, ent~ao A \B = ¿.(b)

S

C2PC = X.

Intuitivamente, uma parti»c~ao de X ¶e uma subdivis~ao de X em \peda»cos" n~aovazios e mutuamente disjuntos.

Exemplo 3.6 Seja m um inteiro positivo qualquer. Para cada inteiro j, 0 · j < m,seja Zj = fx 2 Z jx¡ j = km para algum k 2 Zg. Ent~ao o conjunto

fZ0;Z1;Z2; : : : ;Zm¡1g

forma uma parti»c~ao de Z. Em particular, seja m = 2. Ent~ao o conjunto de conjuntosfZ0;Z1g, em que

Z0 = fx 2 Z j x ¶e parge

Z1 = fx 2 Z j x ¶e ¶³mpargforma uma parti»c~ao de Z. (Veja tamb¶em Problema 4, Exerc¶³cios 3.3.1.)

Existe uma conex~ao ¶³ntima entre parti»c~oes de um conjunto n~ao vazio e rela»c~oes deequivalencia nesse conjunto. Para compreender essa conex~ao, precisaremos da seguintede¯ni»c~ao.

De¯ni»c~ao 3.6 Seja Euma rela»c~ao de equivalencia em um conjunto n~ao vazio X. Paracada x 2 X, de¯nimos o conjunto

x=E= fy 2 Y j yExg

que ¶e chamado a classe de equivalencia determinada pelo elemento x. O conjunto detodas essas classes de equivalencia em X ¶e denotado por X=E; ou seja, X=E= fx=Ejx 2 Xg.4 O s¶³mbolo X=E¶e lido \X m¶odulo E", ou simplesmente \X mod E".5

Teorema 3.3 Seja Euma rela»c~ao de equivalencia em um conjunto n~ao vazio X. Ent~ao

(a) Cada x=E¶e um subconjunto n~ao vazio de X.(b) x=E\ y=E6= ¿ se e somente se xEy.(c) xEy se e somente se x=E= y=E.

4X=E¶e chamado conjunto quociente de X pela rela»c~ao de equivalencia E. (N. do T.)5Analogamente, x=E¶e lido \x m¶odulo E" (N. do T.)

Relac»~oes e Func»~oes 57

Demonstra»c~ao.

(a) Como E¶e re°exiva, para cada x 2 X, temos xEx. Pela De¯ni»c~ao 3.6, x 2 x=Ee portanto x=E¶e um subconjunto n~ao vazio de X.

(b) Como E¶e uma rela»c~ao de equivalencia e X6= ¿, temos

x=E\ y=E6= ¿ , (9z)(z 2 x=E^ z 2 y=E), (zEx) ^ (zEy) Def. 3.6, (xEz) ^ (zEy) E¶e sim¶etrica, xEy E¶e transitiva

(c) De (a) e (b) acima, segue imediatamente que x=E= y=E) xEy. Precisamosagora provar que xEy ) x=E= y=E. Suponhamos xEy. Ent~ao

z 2 x=E) zEx Def. 3.6(zEx) ^ (xEy)) (zEy) E¶e transitiva

) z 2 y=E Def. 3.6

Como z ¶e qualquer, segue que x=E½ y=E. Um argumento similar deduz y=E½x=E; portanto x=E= y=E.

Teorema 3.4 Seja Euma rela»c~ao de equivalencia em um conjunto n~ao vazio X. Ent~aoX=E¶e uma parti»c~ao de X.

Demonstra»c~ao. Pelo Teorema 3.3(a) e pela De¯ni»c~ao 3.6, X=E= fx=E j x 2 Xg ¶euma fam¶³lia de subconjuntos n~ao vazios de X. Mostraremos ent~ao que

x=E6= y=E) (x=E) \ (y=E) = ¿mostrando sua contrapositiva: (x=E)\ (y=E)6= ¿) x=E= y=E. A ¶ultima a¯rma»c~ao ¶euma conseqÄuencia direta do Teorema 3.3(b) e (c). Finalmente, temos que mostrar queS

x2X x=E= X. Isto tamb¶em ¶e trivial, pois cada x 2 X pertence a x=E. Isto completaa demonstra»c~ao do teorema.

Acabamos de ver, no Teorema 3.4, que uma rela»c~ao de equivalencia no conjunton~ao vazio X d¶a origem a uma parti»c~ao em X. Mostraremos a seguir que a rec¶³procado Teorema 3.4 ¶e verdadeira; isto ¶e, cada parti»c~ao de X d¶a origem a uma rela»c~ao deequivalencia em X.

De¯ni»c~ao 3.7 Seja P uma parti»c~ao de um conjunto n~ao vazio X. De¯nimos umarela»c~ao X=P em X, por x(X=P)y se e somente se existe um conjunto A 2 P tal quex 2 A e y 2 A.

58 Relac»~oes e Func»~oes

Cautela! O leitor deveria ler e comparar cuidadosamente as de¯ni»c~oes 3.6 e 3.7, de modoa compreender as delicadas diferen»cas entre estas nota»c~oes similares: x=E, X=E, e X=P.

Teorema 3.5 Seja P uma parti»c~ao de um conjunto n~ao vazioX. Ent~ao a rela»c~aoX=P ¶euma rela»c~ao de equivalencia em X, e as classes de equivalencia de¯nidas pela rela»c~ao deequivalenciaX=P s~ao precisamente os conjuntos em P. Simbolicamente, X=(X=P) = P.

Demonstra»c~ao. Como todo elemento de X est¶a contido em algum A 2 P, x(X=P)x;isto ¶e, X=P ¶e re°exiva. A simetria de X=P ¶e uma clara conseqÄuencia da De¯ni»c~ao3.7. Para mostrar que a rela»c~ao X=P ¶e transitiva, sejam x, y, e z tres elementos de Xsatisfazendo

x(X=P)y e y(X=P)z

Ent~ao, pela 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, pela de¯ni»c~ao de parti»c~ao, que A = B.Portanto, x; z 2 A e assim x(X=P)z. Logo, X=P ¶e uma rela»c~ao de equivalencia em X.

Para demonstrar o resto do teorema, seja x um elemento qualquer de X. Existeum e somente um conjunto A em P tal que x 2 A. (Porque?)

ConseqÄuentemente, pela De¯ni»c~ao 3.7, temos

x=(X=P) = A

Acabamos de provar que cada classe de equivalencia, m¶odulo X=P, ¶e um conjuntoda fam¶³lia P. Reciprocamente, seja A um conjunto qualquer na parti»c~ao P. ComoA6= ¿, existe um elemento x em X que pertence a A. Pelo nosso argumento pr¶evio,x=(X=P) = A. Isto demonstra que X=(X=P) = P. A demonstra»c~ao do teorema est¶acompleta.

Toda rela»c~ao de equivalencia Eem um conjunto X d¶a origem a uma parti»c~ao X=E(de X) (Teorema 3.4); esta parti»c~ao, por sua vez, determina uma rela»c~ao de equivalenciaX=(X=E) (Teorema 3.5). O fato crucial ¶e que X=(X=E) = E (veja Problema 6).Isto, juntamente com X=(X=P) = P, estabelece a conex~ao ¶³ntima entre rela»c~oes deequivalencia e parti»c~oes.

Ilustremos o Teorema 3.5 por um exemplo concreto. Sejam Z0 e Z1 o conjunto deinteiros pares e o conjunto de inteiros ¶³mpares, respectivamente. Ent~ao P = fZ0;Z1gforma uma parti»c~ao do conjunto Z dos inteiros. Pela de¯ni»c~ao da rela»c~ao Z=P, temosa(Z=P)b se e somente se ambos a; b 2 Z0 ou a; b 2 Z1. Isto ¶e, a(Z=P)b se e somente seambos a e b s~ao pares ou ambos s~ao ¶³mpares. ¶E f¶acil veri¯car que esta rela»c~ao Z=P ¶e defato uma rela»c~ao de equivalencia. Na verdade, a(Z=P)b se e somente se a ´ b (mod 2).Portanto, a rela»c~ao Z=P ¶e a rela»c~ao familiar ´ (mod 2). [Veja Exemplo 3.5.]

Reciprocamente, dado o conjunto Z, juntamente com a rela»c~ao Etal que xEy see somente se x ´ y (mod 2), temos

a=E= fx 2 Z j x ´ a (mod 2)g =½

Z0 se a ¶e par

Z1 se a ¶e ¶³mpar

Relac»~oes e Func»~oes 59

Portanto, Z=E= fZ0;Z1g, que ¶e claramente uma parti»c~ao de Z.

3.3.1 Exerc¶³cios

1. Seja P uma parti»c~ao do conjunto n~ao vazio X. Demonstre que a rela»c~ao de equiva-lencia X=P, como conjunto de pares ordenados, ¶e igual a

S

A2PA£ A.2. No problema 1, seja X um conjunto ¯nito e seja

P = fA1; A2; : : : ; Akg

com o conjunto Aj contendo nj elementos, para j = 1; 2; : : : ; k. Demonstre que on¶umero de pares ordenados da rela»c~ao de equivalencia X=P ¶e exatamente n21 + n

22 +

¢ ¢ ¢+ n2k.3. Seja X = fa; b; c; d; eg e seja P= ffa; bg; fcg; fd; egg.(a) Mostre que P ¶e uma parti»c~ao de X.(b) Encontre a rela»c~ao de equivalencia X=P em X, explicitamente como um conjunto

de pares ordenados.(c) Denote E= X=P e encontre a=E, b=E, c=E, d=Ee e=Eexplicitamente.

4. Veri¯que o Exemplo 3.6 para m = 3.5. Seja X o conjunto Z dos inteiros e seja Euma rela»c~ao em X de¯nida por xEy se esemente se x¡ y = 5k para algum inteiro k.(a) Demonstre que a rela»c~ao E¶e uma rela»c~ao de equivalencia em X.(b) Encontre a parti»c~ao X=Ede X.(c) Veri¯que que a rela»c~ao de equivalencia X=(X=E) ¶e de fato a rela»c~ao de equiva-

lencia E.6. Seja E uma rela»c~ao de equivalencia no conjunto n~ao vazio X. Demonstre queX=(X=E) = E.

3.4 Fun»c~oes

Inquestionavelmente, o conceito de fun»c~ao ¶e uma das id¶eias mais b¶asicas em todos osramos da Matem¶atica. O leitor pode ter j¶a aprendido a seguinte de¯ni»c~ao: uma fun»c~ao¶e uma regra de correspondencia que associa a cada elemento x de um certo conjunto(chamado o dom¶³nio da fun»c~ao) um e apenas um elemento y de um outro conjunto(chamado o contra-dom¶³nio da fun»c~ao). Esta de¯ni»c~ao ¶e nebulosa. O que se quer dizerprecisamente por uma \regra"? De modo a evitar ambigÄuidades, matem¶aticos criaramuma de¯ni»c~ao precisa de fun»c~ao, usando a linguagem de conjuntos.

60 Relac»~oes e Func»~oes

De¯ni»c~ao 3.8 Sejam X e Y conjuntos. Uma fun»c~ao de X em Y ¶e um terno (f;X; Y ),sendo f uma rela»c~ao de X para Y satisfazendo(a) Dom(f) = X.(b) Se (x; y) 2 f e (x; z) 2 f ent~ao y = z.

Seja (f;X; Y ) uma fun»c~ao de X em Y . No que segue, adotaremos o costume deescrever f : X ! Y em lugar de (f;X; Y ), e y = f(x) em vez de (x; y) 2 f . A raz~aopela qual \y = f(x)" ¶e um substituto intelig¶³vel para (x; y) 2 f ¶e queTodo elemento x 2 X tem um elemento y 2 Y , determinado de forma ¶unica, tal que(x; y) 2 f .

Para ver que esta asser»c~ao ¶e verdadeira, seja x 2 X. Ent~ao, pela condi»c~ao (a)da De¯ni»c~ao 3.8, existe um elemento y 2 Y tal que (x; y) 2 f ; se exister um outroelemento z 2 Y com (x; z) 2 f , ent~ao de acordo com a condi»c~ao (b), z = y. Istomostra que y ¶e determinado de forma ¶unica por x.

Seja f : X ! Y uma fun»c~ao. Se y = f(x), dizemos que y ¶e a imagem de x sobf e que x ¶e pr¶e-imagem (ou imagem inversa) de y sob f . O leitor pode interpretar istogeometricamente, conforme ilustrado nas Figuras 9 e 10.

Figura 9.

Figura 10.

Chamaremos o conjunto Y , em f : X ! Y , de contra-dom¶³nio da fun»c~ao. Noteo leitor que o contra-dom¶³nio de uma fun»c~ao n~ao precisa coincidir com a imagem dafun»c~ao6 (veja Exemplo 3.7, abaixo). Chamamos a aten»c~ao do leitor para o fato de quealguns autores usam o termo \contra-dom¶³nio" como sinonimo de \imagem", mas poruma raz~ao t¶ecnica, que ser¶a aparente na Se»c~ao 3.6, faremos distin»c~ao entre \imagem"e \contra-dom¶³nio" de uma fun»c~ao. De um modo geral, a imagem de uma fun»c~ao ¶e umsubconjunto do contra-dom¶³nio dessa fun»c~ao.

6A imagem da fun»c~ao f : X ! Y ¶e a imagem Im(f), da rela»c~ao f . ConseqÄuentemente, Im(f) =ff(x) j x 2 Xg.

Relac»~oes e Func»~oes 61

Exemplo 3.7 Seja f : R ! R de¯nida por f(x) = [x] para todo x 2 R, em que [x]denota o maior inteiro · x, e.g., [p2 ] = 1, [¡1

2] = ¡1.7 Aqui, o contra-dom¶³nio de f

¶e R, enquanto que a imagem de f ¶e Z, um subconjunto pr¶oprio de R.

¶E poss¶³vel alterar o contra-dom¶³nio de uma fun»c~ao sem alterar outros aspectos dafun»c~ao. Por exemplo, para a mesma rela»c~ao f do Exemplo 3.7 acima, f : R ! Q ef : R ! Z s~ao fun»c~oes, porque a De¯ni»c~ao 3.8 ¶e satisfeita. De um modo geral, temoso seguinte teorema.

Teorema 3.6 Seja f : X ! Y uma fun»c~ao e seja W um conjunto contendo a imagemde f . Ent~ao f : X !W ¶e uma fun»c~ao.

Demonstra»c~ao. Demonstraremos primeiramente que f ¶e uma rela»c~ao de X para W :

(x; y) 2 f) x 2 X ^ y 2 Im(f) Def. de Im) x 2 X ^ y 2W Im(f) ½W) (x; y) 2 X £W Def. 3.1

Isto demonstra que f ½ X £W ; em outras palavras, f ¶e uma rela»c~ao de X emW . Como f : X ! Y ¶e uma fun»c~ao, Dom(f) = X e a condi»c~ao (b) da De¯ni»c~ao 3.8est¶a satisfeita. Portanto, f : X !W ¶e uma fun»c~ao.

Teorema 3.7 Sejam f : X ! Y e g : X ! Y fun»c~oes. Ent~ao f = g se e somente sef(x) = g(x); 8x 2 X.

Demonstra»c~ao.

(1) Suponha que f = g e que x ¶e um elemento qualquer de X. Ent~ao,

y = f(x), (x; y) 2 f Nota»c~ao, (x; y) 2 g f = g, g(x) = y Nota»c~ao

Portanto, f(x) = g(x).

(2) Suponha que f(x) = g(x); 8x 2 X. Ent~ao

(x; y) 2 f, y = f(x) Nota»c~ao, y = g(x) f(x) = g(x), (x; y) 2 g Nota»c~ao

7Para cada x 2 R, de¯ne-se [x] = n quando x = n+ ®, com n 2 Z e ® 2 R, com 0 · ® < 1. (N.do T.)

62 Relac»~oes e Func»~oes

Isto demonstra que f = g.

Se o dom¶³nio e o contra-dom¶³nio de uma fun»c~ao s~ao subconjuntos do conjuntodos n¶umeros reais, ent~ao, como na geometria anal¶³tica, o gr¶a¯co da fun»c~ao pode seresbo»cado no plano cartesiano.8 Por exemplo, a fun»c~ao do Exemplo 3.7 tem o seguintegr¶a¯co.

Figura 10.

Exemplo 3.8 Seja A um subconjunto de um conjunto n~ao vazio X. Ent~ao a rela»c~ao

f(x; y) 2 X £ f0; 1g j y = 1 se x 2 A; e y = 0 se x62 Ag

d¶a origem a uma fun»c~ao de X em f0; 1g, conhecidada como fun»c~ao caracter¶³stica de Aem X. Esta fun»c~ao ¶e habitualmente denotada pela letra grega qui, com um ¶³ndice A,ÂA. Ou seja,

ÂA : X ! f0; 1g¶e de¯nida por

ÂA(x) =

½

1 se x 2 A0 se x 2 X ¡A

Embora a fun»c~ao seja, por de¯ni»c~ao, escrita (f;X; Y ) ou f : X ! Y , ¶e freqÄuen-temente um incomodo ter que escrever explicitamente o dom¶³nio e o contra-dom¶³nio deuma fun»c~ao, quando eles s~ao implicitamente claros a partir do contexto. Portanto, deno-taremos uma fun»c~ao por f quando o dom¶³nio e o contra-dom¶³nio de f forem claramentecompreendidos, sem dar explicitamente o dom¶³nio e o contra-dom¶³nio de f .

8Pressupondo-se que a fun»c~ao seja \bem comportada".

Relac»~oes e Func»~oes 63

Exemplo 3.9 Seja X um conjunto. A rela»c~ao diagonal ¢X em X, de¯nida na p¶agina54, ¶e uma fun»c~ao de X em X. Quando queremos enfatizar que a rela»c~ao ¢X ¶e umafun»c~ao, usamos a nota»c~ao alternativa 1X : X ! X, em que 1X(x) = x para todo x emX. A fun»c~ao 1X ¶e chamada fun»c~ao identidade em X.

Exemplo 3.10 Sejam X e Y dois conjuntos n~ao vazios e seja b um elemento ¯xado deY . A rela»c~ao

Cb = f(x; b) j x 2 Xgd¶a origem a uma fun»c~ao Cb : X ! Y , dada por Cb(x) = b para todo x em X. A fun»c~aoCb ¶e chamada fun»c~ao constante.

No c¶alculo, vemos freqÄuentemente uma fun»c~ao de¯nida por duas (ou mais) regrasde correspondencia: por exemplo, h : R! R, de¯nida por

h(x) =

½

1¡ 2x; se x · 0x2 + 1; se x ¸ 0

Esta fun»c~ao pode ser considerada como a uni~ao das seguintes duas fun»c~oes:

(1) f : ]¡1; 0]! R, de¯nida por f(x) = 1¡ 2x, 8x 2 ]¡1; 0](2) g : [0;1[! R, de¯nida por g(x) = x2 + 1, 8x 2 [0;1[

O leitor dever¶a notar que aqui Dom(f) \Dom(g) = f0g e que f(0) = g(0).Os ¶ultimos exemplos motivam o seguinte teorema geral.

Teorema 3.8 Sejam f : A! C e g : B ! D duas fun»c~oes tais que f(x) = g(x);8x 2A \B. Ent~ao a uni~ao de f e g de¯ne uma fun»c~ao

h = f [ g : A [B ! C [Dem que

h(x) =

½

f(x); se x 2 Ag(x); se x 2 B

Demonstra»c~ao.

Como f e g s~ao rela»c~oes, f ½ A£ C e g ½ B £D, e temosh = f [ g ½ (A£ C) [ (B £D)

½ (A [B)£ (C [D)porque ambos A £ C e B £ D s~ao subconjuntos de (A [ B) £ (C [ D). Assim, h ¶euma rela»c~ao de A [B para C [D. Deixaremos ao leitor veri¯car que

Dom(h) = Dom(f) [Dom(g)= A [B

64 Relac»~oes e Func»~oes

Isto mostra que a rela»c~ao h satisfaz a De¯ni»c~ao 3.8(a).

Para cada elemento x 2 A [B, podemos considerar os seguintes tres casos:(1) x 2 A ¡ B, (2) x 2 B ¡ A, e (3) x 2 A \ B. Como f : A ! C e g : B ! Dsatisfazem a De¯ni»c~ao 3.8(b), e f(x) = g(x), 8x 2 A \ B, temos que h(x) ¶e de¯nidode modo ¶unico em cada um dos tres casos. Logo, a rela»c~ao h satisfaz a De¯ni»c~ao 3.8(b)tamb¶em. Portanto, h : A [B ! C [D ¶e de fato uma fun»c~ao.

3.4.1 Exerc¶³cios

1. Teste se cada um dos seguintes diagramas de¯ne ou n~ao uma fun»c~ao de X = fx; y; zgem Y = fu; v; wg.

(a)

(b)

(c)

2. Seja f : R! R a fun»c~ao dada por

f(x) =

½

5 se x ¶e racional

¡3 se x ¶e irracional

Encontre f(1=3), f(7), e f(1; 323232 : : : ).3. Seja a fun»c~ao f : R! R dada por

f(x) =

8

<

:

4x+ 3 se x > 5

x2 ¡ 2 se ¡ 6 · x · 54¡ 5x se x < ¡6

Encontre f(¡7), f(3) e f(6).4. Seja f : X ! Y a fun»c~ao de¯nida pelo diagrama

Relac»~oes e Func»~oes 65

Qual ¶e a imagem desta fun»c~ao?5. Seja a fun»c~ao f : X ! R de¯nida por X = f¡2;¡1; 0; 1; 2g e f(x) = x2 ¡ 3 paratodo x 2 X. Encontre a imagem da fun»c~ao f .6. Cada uma das seguintes express~oes de¯ne uma fun»c~ao de R em R. Encontre aimagem de cada fun»c~ao.(a) f(x) = 2x2 + 5(b) g(x) = cos x(c) h(x) = x3 ¡ 1

7. Seja X ½ Y e f = f(x; x) j x 2 Xg. Demonstre que f : X ! Y ¶e uma fun»c~ao.[Nota. Esta fun»c~ao ¶e chamada uma fun»c~ao inclus~ao, e pode ser denotada por f : X ½ Y .]8. Sejam X = fx; y; zg e Y = f1; 2; 3g. Quais das seguintes ¶e uma fun»c~ao de X emY ? Justi¯que.(a) f = f(x; 1); (y; 2); (z; 3)g(b) g = f(x; 2); (y; 3); (z; 2)g(c) h = f(x; 2); (y; 1)g(d) i = f(x; 1); (x; 2); (y; 1); (z; 3)g

9. Se X = fx; y; zg e Y = f1; 2g, quantas fun»c~oes de X em Y existem? De modogeral, se o conjunto X tem m elementos e se Y tem n elementos, quantas fun»c~oes deX e Y existem?10. Quantas fun»c~oes do problema 9 s~ao constantes?11. Seja f : X ! Y uma fun»c~ao. Demonstre que todo subconjunto g de f d¶a origem auma fun»c~ao.12. Seja f : X ! X uma fun»c~ao de X em X, que tamb¶em ¶e uma rela»c~ao re°exiva emX. Demonstre que f tem que ser a fun»c~ao identidade 1X : X ! X.13. Seja X o intervalo unit¶ario [0; 1]. Encontre uma fun»c~ao f : X ! X que ¶e umarela»c~ao sim¶etrica em X.14. Sejam f : X ! Y e g : X ! Y duas fun»c~oes com o mesmo dom¶³nio e o mesmocontra-dom¶³nio. Demonstre que se f ½ g ent~ao f = g.

3.5 Imagens e imagens inversas de conjuntos

Recordemos que se f : X ! Y ¶e uma fun»c~ao e se x e y s~ao elementos de X e Y ,respectivamente, tais que y = f(x), ent~ao y ¶e a imagem de x, e x ¶e uma pr¶e-imagem ou

66 Relac»~oes e Func»~oes

uma imagem inversa de y. Este conceito pode ser estendido naturalmente de elementosa subconjuntos, como segue:

De¯ni»c~ao 3.9 Seja f : X ! Y uma fun»c~ao, e sejam A e B subconjuntos de X e Y ,respectivamente.(a) A imagem de A sob f , que denotamos por f(A), ¶e o conjunto de todas as imagensf(x) tais que x 2 A.(b) A imagem inversa de B sob f , que denotamos por f¡1(B), ¶e o conjunto de todasas pr¶e-imagens dos elementos y 2 B.

Sob a nota»c~ao de constru»c~ao de um conjunto, temos as seguintes express~oes:

f(A) = ff(x) j x 2 Agf¡1(B) = fx j f(x) 2 Bg

Teorema 3.9 Seja f : X ! Y uma fun»c~ao. Ent~ao(a) f(¿) = ¿.(b) f(fxg) = ff(x)g.(c) Se A ½ B ½ X, ent~ao f(A) ½ f(B).(d) Se C ½ D ½ Y , ent~ao f¡1(C) ½ f¡1(D).

O Teorema 3.9 segue facilmente da De¯ni»c~ao 3.9; portanto, a demonstra»c~ao ¶edeixada para o leitor.

Teorema 3.10 Seja f : X ! Y uma fun»c~ao e seja fA° j ° 2 ¡g uma fam¶³lia desubconjuntos de X. Ent~ao(a) f(

S

°2¡A°) =S

°2¡ f(A°).(b) f(

T

°2¡A°) ½T

°2¡ f(A°).

Demontra»c~ao.

(a) Por uso repetido da De¯ni»c~ao 3.9 e da De¯ni»c~ao 2.6 do Cap¶³tulo 2, temos

y 2 fÃ

[

°2¡

!

, y = f(x) para algum x 2[

°2¡

, y = f(x) para algum x 2 A°; para algum ° 2 ¡, y 2 f(A°) para algum ° 2 ¡, y 2

[

°2¡

f(A°)

Relac»~oes e Func»~oes 67

Portanto, f(S

°2¡A°) =S

°2¡ f(A°).

(b) ComoT

°2¡ ½ A° , para todo ° 2 ¡, pelo Teorema 3.9(c), temos f(T

°2¡A°)½ f(A°), para todo ° 2 ¡. Segue ent~ao, da De¯ni»c~ao 2.7, do Cap¶³tulo 2, quef(T

°2¡A°) ½T

°2¡ f(A°).

Pode n~ao ser poss¶³vel trocar o s¶³mbolo de inclus~ao ½, no Teorema 3.10(b), por umsinal de igualdade, como mostra o pr¶oximo exemplo.

Exemplo 3.11 Sejam X = fa; bg, Y = fcg, ¡ = f1; 2g, A1 = fag, A2 = fbg, e sejaf : X ! Y a fun»c~ao constante f(a) = f(b) = c. Ent~ao f(A1 \ A2) = f(¿) = ¿,enquanto que f(A1) \ f(A2) = fcg. Isto mostre que nem sempre f(

T

°2¡A°) =T

°2¡ f(A°).

Teorema 3.11 Seja f : X ! Y uma fun»c~ao e seja fB° j ° 2 ¡g uma fam¶³lia desubconjuntos de Y . Ent~ao(a) f¡1(

S

°2¡B°) =S

°2¡ f¡1(B°)

(b) f¡1(T

°2¡B°) =T

°2¡ f¡1(B°)

Demonstra»c~ao.

(a) Aplicando-se repetidamente a De¯ni»c~ao 3.9 e a De¯ni»c~ao 2.6 do Cap¶³tulo 2,temos

x 2 f¡1Ã

[

°2¡

!

, f(x) 2[

°2¡

, f(x) 2 B°; para algum ° 2 ¡, x 2 f¡1(B°); para algum ° 2 ¡, x 2

[

°2¡

f¡1(B°)

Assim, acabamos de demonstrar que f¡1(S

°2¡B°) =S

°2¡ f¡1(B°).

(b) Trocando-seS

porT

e a frase \para algum" por \para todo", na demonstra»c~aoda parte (a), temos uma demonstra»c~ao da parte (b). O estudante dever¶a realizar asmudan»cas sugeridas, passo a passo, at¶e estar claramente convencido.

Teorema 3.12 Seja f : X ! Y uma fun»c~ao e sejam B e C subconjuntos quaisquer deY . Ent~ao

f¡1(B ¡ C) = f¡1(B)¡ f¡1(C)

68 Relac»~oes e Func»~oes

Demonstra»c~ao.

Examinemos as seguintes equivalencias:

x 2 f¡1(B ¡ C), f(x) 2 B ¡ C Def. 3.9

, f(x) 2 B ^ f(x)62 C Def. 2.5 (Cap. 2)

, x 2 f¡1(B) ^ x62 f¡1(C) Def. 3.9

, x 2 [f¡1(B)¡ f¡1(C)] Def. 2.5 (Cap. 2)

Isto demonstra que f¡1(B ¡ C) = f¡1(B)¡ f¡1(C).

3.5.1 Exerc¶³cios

1. No Problema 2, Exerc¶³cios 3.4.1, encontre(a) f(f¡1; 0; 1g), f(fp2; ¼g), e f(f2; log 2g)(b) f¡1(f0; 1g), f¡1(f¡3; 3g), f¡1(f4; 5g), e f¡1(f¡3; 4; 5g).

2. No Problema 3, Exerc¶³cios 3.4.1, encontre(a) f(f¡7; 3; 6g), f(f¡8; 2; 7g), e f(f¡9; 1; 8g)(b) f¡1(f0; 1g), f¡1(f¡3; 3g), e f¡1(f1; 2; 3g).

3. No Problema 4, Exerc¶³cios 3.4.1, encontre f(fv;wg), f¡1(fcg), e f¡1(fa; bg).4. Seja f : X ! Y uma fun»c~ao e sejam A ½ X, B ½ Y . Demonstre que(a) A ½ f¡1(f(A))(b) f(f¡1(B)) ½ B.

5. Seja f : X ! Y uma fun»c~ao e sejam A ½ X, B ½ Y . Encontre exemplos quemostrem que as seguintes a¯rma»c~oes s~ao falsas.(a) Se B6= ¿, ent~ao f(B)6= ¿(b) f¡1(f(A)) = A(c) f(f¡1(B)) = B(d) f(X) = Y

6. Mostre que a a¯rma»c~ao do Problema 5(c) ¶e verdadeira quando f(X) = Y .7. Seja f : X ! Y uma fun»c~ao tal que f(X) = Y , e sejam B e C subconjuntos deY . Demonstre que B = C se f¡1(B) = f¡1(C). De um exemplo mostrando que estaa¯rma»c~ao ¶e falsa se f(X)6= Y .8. Sejam X e Y dois conjuntos, e sejam pX : X £ Y ! X e pY : X £ Y ! Y duasfun»c~oes, dadas respectivamente por pX(x; y) = x e pY (x; y) = y, para todo (x; y) 2X £ Y (pX e pY s~ao chamadas proje»c~ao em X e proje»c~ao em Y , respectivamente).Demonstre que se R ¶e uma rela»c~ao de X para Y , isto ¶e, se R ½ X £ Y , ent~aopX(R) = Dom(R) e pY (R) = Im(R).9. Seja f : X ! Y uma fun»c~ao, e sejam A ½ X, B ½ Y . Demonstre que(a) f(A \ f¡1(B)) = f(A) \B(b) f(f¡1(B)) = f(X) \B.

10. Seja f : X ! Y uma fun»c~ao, e seja B ½ Y . Demonstre quef¡1(Y ¡B) = X ¡ f¡1(B)

Relac»~oes e Func»~oes 69

11. Seja f : X ! Y uma fun»c~ao, e sejam A e B subconjuntos de X. De um exemploque mostra que, em geral, n~ao ¶e verdadeiro a¯rmar que

f(A¡B) = f(A)¡ f(B)12. Demonstre o Teorema 3.9.

3.6 Fun»c~oes injetoras, sobrejetoras e bijetoras

No estudo das fun»c~oes, ¶e conveniente dar nomes a tres tipos importantes de fun»c~oes.

De¯ni»c~ao 3.10 Uma fun»c~ao f : X ! Y ¶e injetora ou um-a-um9 quando satisfaz: sex1; x2 2 X e f(x1) = f(x2) ent~ao x1 = x2. Uma fun»c~ao injetora ¶e tamb¶em chamadauma inje»c~ao.

Pela Lei Contrapositiva da l¶ogica, podemos dizer equivalentemente que a fun»c~aof : X ! Y ¶e uma inje»c~ao se e somente se: x1; x2 2 X, com x1 6= x2, implica f(x1)6=f(x2). Por exemplo, a fun»c~ao inclus~ao do Problema 7, Exerc¶³cios 3.4.1, ¶e uma inje»c~ao.

De¯ni»c~ao 3.11 Uma fun»c~ao f : X ! Y ¶e dita ser sobrejetora se satisfaz: se y 2 Y ,ent~ao existe ao menos um x 2 X tal que f(x) = y. Uma fun»c~ao sobrejetora ¶e chamadauma sobreje»c~ao. Em outras palavras, f : X ! Y ¶e uma sobreje»c~ao se e somente sef(X) = Y .

A fun»c~ao do Exemplo 3.7, Se»c~ao 3.4, por exemplo, n~ao ¶e sobrejetora.

Exemplo 3.12 A fun»c~ao seno f : R! [¡1; 1], dada por f(x) = senx ¶e uma sobreje»c~ao;mas se o contra-dom¶³nio [¡1; 1] for trocado por R, ent~ao f : R! R n~ao ¶e sobrejetora.

De¯ni»c~ao 3.12 Uma fun»c~ao f : X ! Y ¶e chamada uma bije»c~ao ou ¶e dita ser bi-jetora se ¶e simultaneamente injetora e sobrejetora. Uma bije»c~ao ¶e tamb¶em chamadacorrespondencia um-a-um.10

Por exemplo, a fun»c~ao identidade no Exemplo 3.9, Se»c~ao 3.4, ¶e uma bije»c~ao. Asde¯ni»c~oes 10, 11, e 12 s~ao ilustradas nos tres diagramas abaixo (Figuras 12, 13 e 14).Os conjuntos X e Y s~ao representados como conjuntos de pontos dentro de c¶³rculos.Em cada ilustra»c~ao, cada ponto em X ¶e emparelhado com algum ponto em Y , poruma °echa desenhada entre ambos. O conjunto de pares assim obtido d¶a origem a umafun»c~ao f : X ! Y .

Para fun»c~oes injetoras, o resultado do Teorema 3.10(b) pode ser melhorado.

9Isto ¶e denotado por f ¶e 1{1. (N. do T.)10Ou correspondencia biun¶³voca (N. do T.)

70 Relac»~oes e Func»~oes

Teorema 3.13 Seja f : X ! Y uma inje»c~ao e seja fA° j ° 2 ¡g uma fam¶³lia desubconjuntos de X. Ent~ao

f

Ã

\

°2¡

!

=\

°2¡

f(A°)

Demonstra»c~ao. Pela De¯ni»c~ao 3.9, e pela De¯ni»c~ao 2.7 do Cap¶³tulo 2, temos

y 2\

°2¡

f(A°), y 2 f(A°); 8° 2 ¡

, (9x° 2 A° tal que y = f(x°)) 8° 2 ¡

Como f : X ! Y ¶e injetora, todos esses x°'s s~ao o mesmo; denotaremos esteelemento por x0. Ent~ao temos

y 2\

°2¡

f(A°), 9x0 2 A° tal que y = f(x0);8° 2 ¡

, 9x0 2\

°2¡

A° tal que y = f(x0)

, y 2 fÃ

\

°2¡

!

Portanto, f(T

°2¡A°) =T

°2¡ f(A°).

Figura 12. f : X ! Y ¶e injetora.

Relac»~oes e Func»~oes 71

Figura 13. f : X ! Y ¶e sobrejetora.

Figura 14. f : X ! Y ¶e bijetora.

Recordemos que se R ¶e uma rela»c~ao de X para Y , ent~ao a inversa

R¡1 = f(y; x) j (x; y) 2 Rg

¶e uma rela»c~ao de Y para X. Como uma fun»c~ao f : X ! Y ¶e um tipo particular derela»c~ao de X para Y , f¡1 ¶e ao menos uma rela»c~ao de Y para X. ¶E natural querer saberquando f¡1 torna-se uma fun»c~ao. Esta quest~ao ¶e considerada no seguinte teorema.

Teorema 3.14 Seja f : X ! Y uma bije»c~ao. Ent~ao f¡1 : Y ! X ¶e uma bije»c~ao.

Demonstra»c~ao. Demonstraremos primeiramente que a rela»c~ao f¡1, de Y para X, formauma fun»c~ao. Como f : X ! Y ¶e sobrejetora, pelo Problema 3(a), Exerc¶³cios 3.2.1,temos Dom(f¡1) = Im(f) = Y . Assim, a condi»c~ao (a) da De¯ni»c~ao 3.8 est¶a satisfeita.Para mostrar que f¡1 satisfaz a outra condi»c~ao, sejam (y; x1) 2 f¡1 e (y; x2) 2 f¡1.Ent~ao temos (x1; y) 2 f e (x2; y) 2 f . ConseqÄuentemente, f(x1) = y = f(x2). Agora,como f : X ! Y ¶e injetora, a ¶ultima igualdade implica x1 = x2. Portanto, acabamosde estabelecer que f¡1 : Y ! X ¶e uma fun»c~ao.

Para mostrar que a fun»c~ao f¡1 : Y ! X ¶e injetora, sejam y1; y2 2 Y , comf¡1(y1) = f¡1(y2) = x (digamos). Ent~ao temos f(x) = y1 e f(x) = y2, e portantoy1 = y2. Isto mostra que f

¡1 ¶e injetora.

Finalmente, resta ser mostrado que f¡1 : Y ! X ¶e sobrejetora. Pelo Problema3(b) dos Exerc¶³cios 3.2.1, temos Im(f¡1) = Dom(f) = X, o que demonstra que f¡1 ¶esobrejetora. Assim, a demonstra»c~ao est¶a completa.

Se f : X ! Y ¶e uma bije»c~ao, a fun»c~ao f¡1 : Y ! X ¶e chamada a fun»c~ao inversade f (veja tamb¶em Problema 14, Exerc¶³cios 3.6.1).

Em virtude do Teorema 3.14, se f : X ! Y ¶e uma bije»c~ao (= correspondenciaum-a-um), diremos que f ¶e uma correspondencia um-a-um entre os conjuntos X e Y .

72 Relac»~oes e Func»~oes

3.6.1 Exerc¶³cios

1. Quais das fun»c~oes nos Problemas 2, 3 e 4, dos Exerc¶³cios 3.4.1 s~ao injetoras? Sobre-jetoras?2. Quais das fun»c~oes nos Problemas 5 e 6, dos Exerc¶³cios 3.4.1 s~ao injetoras? Bijetoras?3. Seja f : R! R a fun»c~ao de¯nida por f(x) = 3x¡ 2, para todo x 2 R.(a) Demonstre que a fun»c~ao f ¶e uma bije»c~ao.(b) Encontre a inversa f¡1 de f .

4. Seja g : ] ¡ ¼=2; ¼=2[! R a fun»c~ao dada por g(x) = tg x, para todo x tal que¡¼=2 < x < ¼=2. Esta fun»c~ao ¶e bijetora? Em caso a¯rmativo, descreva sua fun»c~aoinversa.5. Demonstre que a fun»c~ao caracter¶³stica ÂA : X ! f0; 1g, do Exemplo 3.8, Se»c~ao 3.4,¶e sobrejetora se e somente se ¿ 6= A à X. Quando ¶e que ÂA : X ! f0; 1g torna-seuma inje»c~ao?6. Demonstre que a fun»c~ao constante Cb : X ! Y ¶e sobrejetora se e somente seY = fbg. Quando ¶e que Cb : X ! Y torna-se uma inje»c~ao?7. Demonstre que a proje»c~ao em X, pX : X £ Y ! X, e a proje»c~ao em Y ,pY : X £ Y ! Y , do Problema 8, Exerc¶³cios 3.5.1, s~ao sobrejetoras. Quando ¶e quea proje»c~ao em X ¶e uma inje»c~ao?8. Demonstre que existe uma correspondencia um-a-um entre o conjunto N dos n¶umerosnaturais e o conjunto de todos os n¶umeros naturais pares.9. Demonstre que existe uma correspondencia um-a-um entre o conjunto Z dos n¶umerosinteiros e o conjuntos de todos os inteiros ¶³mpares.10. Sejam X uma conjunto ¯nito com m elementos e Y um conjunto ¯nito com nelementos. Demonstre que(a) Se m > n, ent~ao n~ao pode haver nenhuma inje»c~ao f : X ! Y .(b) Se m · n, ent~ao existem exatamente n!=(n¡m)! inje»c~oes de X em Y .

[Veja tamb¶em o Problema 9, Exerc¶³cios 3.5.1.]11. SejaX um conjunto ¯nito comm elementos. Quantas bije»c~oes de X em X existem?[Nota: Uma bije»c~ao de um conjunto ¯nito em si mesmo ¶e chamada uma permuta»c~ao.]12. Seja f : X ! Y uma fun»c~ao, e sejam A ½ X, B ½ Y . Demonstre que(a) Se f ¶e injetora, ent~ao f¡1(f(A)) = A.(b) Se f ¶e sobrejetora, ent~ao f(f¡1(B)) = B.

13. Seja f : X ! Y uma inje»c~ao, e sejam A e B subconjuntos de X. Demonstre quef(A¡B) = f(A)¡ f(B). [Compare isto com o Problema 11, Exerc¶³cios 3.5.1.]14. Demonstre a seguinte rec¶³proca do Teorema 3.14: Seja f : X ! Y uma fun»c~ao talque f¡1 ¶e uma fun»c~ao de Y para X. Ent~ao f : X ! Y ¶e bijetora.

3.7 Composi»c~ao de fun»c~oes

A um leitor atento, uma fun»c~ao f : X ! Y pode ser considerada como uma m¶aquinaque toma um objeto arbitr¶ario x do conjunto X, opera sobre ele de um certo modo, etransforma-o em um novo objeto f(x), um produto da m¶aquina. Esta id¶eia ¶e ilustradana Figura 15.

Relac»~oes e Func»~oes 73

Figura 15.

Sejam f : X ! Y e g : Y ! Z duas fun»c~oes, sendo o dom¶³nio da segunda igualao contra-dom¶³nio da primeira. Imagine estas duas fun»c~oes como duas m¶aquinas, taisquais uma lavadora e uma secadora. N~ao temos que ser inventores para imaginar apossibilidade de combinar estas duas m¶aquinas em uma nova m¶aquina; o resultado seriauma combina»c~ao lavadora-secadora, que pega uma uma roupa suja x, lava-a de modo atorn¶a-la uma roupa limpa por¶em ¶umida f(x), e ent~ao seca-a. O resultado ¶e uma roupalimpa e seca g(f(x)). A id¶eia ¶e ilustrada na Figura 16.

Figura 16.

A \combina»c~ao" das m¶aquinas f : X ! Y e g : Y ! Z resulta em uma novam¶aquina, denotada por h : X ! Z, que toma um objeto arbitr¶ario x emX, e transforma-o no objeto h(x) = g(f(x)) em Z. A nota»c~ao tradicional para h ¶e g ± f , e (g ± f)(x) =g(f(x)); o nome tradicional para o termo \combina»c~ao" ¶e \composi»c~ao".

Estamos agora prontos para a seguinte de¯ni»c~ao.

De¯ni»c~ao 3.13 Sejam f : X ! Y e g : Y ! Z duas fun»c~oes. A composi»c~ao11 destasduas fun»c~oes ¶e a fun»c~ao g ± f : X ! Z, sendo (g ± f)(x) = g(f(x)), para todo x emX. Em outra nota»c~ao

g ± f = f(x; z) 2 X £ Z j 9y 2 Y tal que (x; y) 2 f ^ (y; z) 2 gg

Exemplo 3.13 Sejam f : R! R e g : R! R duas fun»c~oes, dadas respectivamente porf(x) = x + 1, e g(x) = x2, para todo x em R. Encontre as composi»c~oes (g ± f)(x) e(f ± g)(x).11ou fun»c~ao composta de g e f . (N. do T.)

74 Relac»~oes e Func»~oes

Solu»c~ao. Usando a De¯ni»c~ao 3.13, temos

(g ± f)(x) = g(f(x))= g(x+ 1)

= (x+ 1)2

= x2 + 2x+ 1

(f ± g)(x) = f(g(x))= f(x2)

= x2 + 1

O resultado do Exemplo 3.13 nos mostra que, em geral, g ± f 6= f ± g;12 portanto,a composi»c~ao funcional n~ao ¶e comutativa.

Teorema 3.15 A composi»c~ao funcional ¶e associativa. Ou seja, tendo-se f : X ! Y , eg : Y ! Z, e h : Z ! W , ent~ao

(h ± g) ± f = h ± (g ± f)

Demonstra»c~ao. Notemos primeiramente que ambas, h ± (g ± f) e (h± g)± f , s~ao fun»c~oesde X em W . Portanto, para mostrar que h ± (g ± f) = (h ± g) ± f , pelo Teorema 3.7 daSe»c~ao 3.4, precisamos apenas mostrar que [h ± (g ± f)](x) = [(h ± g) ± f ](x), para todox em X. Usamos a De¯ni»c~ao 3.13 para obter o seguinte:

[h ± (g ± f)](x) = h((g ± f)(x)) = h(g(f(x)))e

[(h ± g) ± f ](x) = (h ± g)(f(x)) = h(g(f(x)))para todo x em X. Isto mostra que [h ± (g ± f)](x) = [(h ± g) ± f ](x), para todo x emX. A demonstra»c~ao est¶a agora completa.

Teorema 3.16 Seja f : X ! Y uma fun»c~ao. Ent~ao

(a) Se existe uma fun»c~ao g : Y ! X tal que g ± f = 1X (sendo 1X : X ! X afun»c~ao identidade, de¯nida no Exemplo 3.9, Se»c~ao 3.4), ent~ao f : X ! Y ¶e injetora.

(b) Se existe uma fun»c~ao h : X ! Y tal que f ± h = 1Y , ent~ao f : X ! Y ¶esobrejetora.

Demonstra»c~ao.

(a) Suponha que existe uma fun»c~ao g : Y ! X tal que g ± f = 1X . Ent~ao paraquaisquer x1 e x2 em X, com f(x1) = f(x2), temos

x1 = (g ± f)(x1) = g(f(x1)) = g(f(x2)) = (g ± f)(x2) = x212Muitas vezes, de¯ne-se f ± g mas n~ao se de¯ne g ± f (N. do T.)

Relac»~oes e Func»~oes 75

Isto demonstra que f : X ! Y ¶e injetora.

(b) Suponha que existe uma fun»c~ao h : Y ! X tal que f ± h = 1Y . Ent~ao, paracada y 2 Y , existe um elemento

x = h(y) 2 X

tal quef(x) = f(h(y)) = (f ± h)(y) = 1Y (y) = y

Pela De¯ni»c~ao 3.11, f : X ! Y ¶e sobrejetora.

3.7.1 Exerc¶³cios

1. Sejam f : R ! R e g : R ! R duas fun»c~oes de¯nidas por f(x) = 2x3 + 1 eg(x) = cosx, respectivamente, para todo x 2 R.(a) Encontre a composi»c~ao g ± f .(b) Encontre a composi»c~ao f ± g.

2. Sejam f : R+ ! R e g : R ! R+ duas fun»c~oes de¯nidas por f(x) = log10 x, paratodo x 2 R+, e g(x) = 10x para todo x 2 R.(a) Encontre a composi»c~ao g ± f : R+ ! R+(b) Encontre a composi»c~ao f ± g : R! R.

3. Sejam f , g e h as fun»c~oes dadas no Problema 6, Exerc¶³cios 3.4.1.(a) Encontre a composi»c~ao g ± f .(b) Encontre a composi»c~ao h ± g.(c) Encontre a composi»c~ao h ± (g ± f).(d) Encontre a composi»c~ao (h ± g) ± f .(e) Compare suas respostas para h ± (g ± f) e (h ± g) ± f ; s~ao a mesma?

4. Seja f : X ! Y uma fun»c~ao. Demonstre que f ± 1X = f = 1Y ± f .5. Seja f : X ! Y uma bije»c~ao e seja f¡1 : Y ! X a fun»c~ao inversa de f . Demonstreque f¡1 ± f = 1X e que f ± f¡1 = 1Y .6. Seja f : X ! Y uma fun»c~ao. Se existem fun»c~oes g : Y ! X e h : Y ! X, tais queg ± f = 1X e f ± h = 1Y , demonstre que f : X ! Y ¶e bijetora e que g = h = f¡1.7. Sejam f : X ! Y e g : Y ! Z fun»c~oes. Demonstre que(a) Se f : X ! Y e g : Y ! Z s~ao injetoras, ent~ao tamb¶em o ¶e g ± f : X ! Z.(b) Se f : X ! Y e g : Y ! Z s~ao sobrejetoras, ent~ao tamb¶em o ¶e g ± f : X ! Z.

8. Seja R uma rela»c~ao de X para Y e seja Suma rela»c~ao de Y para Z. Podemos, comona composi»c~ao de fun»c~oes, de¯nir a composi»c~ao destas rela»c~oes por

S± R = f(x; z) 2 X £ Z j (9y 2 Y )[(x; y) 2 R ^ (y; z) 2 S]g

que ¶e uma rela»c~ao de X para Z. Demonstre que(a) (S± R)¡1 = R¡1 ± S¡1.(b) Se T ¶e uma rela»c~ao de Z para W , ent~ao T ± (S± R) = (T ± S) ± R.

9. Sejam f : X ! Y e g : Y ! Z duas bije»c~oes. Demonstre que g ± f : X ! Z ¶euma bije»c~ao, e que a fun»c~ao inversa (g ± f)¡1 : Z ! X, ¶e o mesmo que a composi»c~ao

76 Relac»~oes e Func»~oes

f¡1 ± g¡1 : Z ! X das fun»c~oes inversas g1¡ : Z ! Y e f¡1 : Y ! X. Ou seja,(g ± f)¡1 = f¡1 ± g¡1.

4

Conjuntos Enumer¶aveis e Conjuntos

N~ao Enumer¶aveis

A de¯ni»c~ao de Dedekind, de conjunto in¯nito, ¶e usada ma discuss~ao de propriedadesde conjuntos in¯nitos e de conjuntos ¯nitos. ¶E demonstrado, dentre outras coisas,que conjuntos enumer¶aveis s~ao os menores, em tamanho, dentre os conjuntos in¯nitos.Propriedades e exemplos, de conjuntos enumer¶aveis e de conjuntos n~ao enumer¶aveis, s~aodadas.

4.1 Conjuntos ¯nitos e in¯nitos

Na Se»c~ao 2.1, Cap¶³tulo 1, mencionamos informalmente que um conjunto ¯nito ¶e umconjunto que cont¶em apenas uma quantidade ¯nita de elementos; embora este conceitopossa ser transformado em uma de¯ni»c~ao matem¶atica mais precisa, daremos preferenciaa uma de¯ni»c~ao alternativa (De¯ni»c~ao 4.1), formulada por Dedekind.

Foi enfatizado, na Se»c~ao 2.1, do Cap¶³tulo 2, que o conjunto N, dos n¶umerosnaturais, ¶e um conjunto in¯nito. Seja Np = f2; 4; 6; : : : g o conjunto de todos os n¶umerosnaturais pares. Como foi mostrado ao leitor, no Problema 8, Exerc¶³cios 3.6.1, existe umacorrespondencia um-a-um entre o conjunto N e seu subconjunto pr¶oprio Np.

Em outras palavras,

Uma parte ¶e t~ao numerosa quanto o todo.1

Esta propriedade estranha (de um conjunto in¯nito) incomodou muitos matem¶a-ticos, inclusive Georg Cantor. Foi Richard Dedekind (1831{1916)2 que tornou esta

1Uma diferen»ca not¶avel em rela»c~ao ao axioma de Euclides: \O todo ¶e maior que qualquer de suaspartes." (325 a.C.).

2Richard Dedekind, um dos maiores matem¶aticos, nasceu em 6 de outubro de 1831, em Brunswick,Alemanha. De in¶³cio, os interesses de Dedekind estavam na F¶³sica e na Qu¶³mica; ele considerava aMatem¶atica meramente como uma serva das ciencias. Mas isto n~ao durou muito; aos dezessete anos,

77

78 Conjuntos Enumer¶aveis e Conjuntos N~ao Enumer¶aveis

propriedade a caracter¶³stica de¯nidora de um conjunto in¯nito. A seguinte de¯ni»c~ao foidada por Dedekind em 1888.

De¯ni»c~ao 4.1 Um conjunto X ¶e in¯nito quando possui um subconjunto pr¶oprio Y , talque existe uma correspondencia um-a-um entre X e Y . Um conjunto ¶e ¯nito se n~ao forin¯nito.

Em outras palavras, um conjunto X ¶e in¯nito se e somente se existe uma inje»c~aof : X ! X tal que f(X) ¶e um subconjunto pr¶oprio de X. Logo, o conjunto N denumeros naturais ¶e um conjunto in¯nito.

Exemplo 4.1 O conjunto ¿ e os conjuntos unit¶arios3 s~ao ¯nitos.

Solu»c~ao. (a) Como o conjunto vazio n~ao possui nenhum subconjunto pr¶oprio, o conjuntovazio ¶e ¯nito. (b) Seja fag um conjunto unit¶ario qualquer. Como o ¶unico subconjuntopr¶oprio de fag ¶e o conjunto vazio, e n~ao h¶a nenhuma correspondencia biun¶³voca entrefag e ¿, fag ¶e necessariamente ¯nito.

Teorema 4.1

(a) Todo superconjunto, de um conjunto in¯nito, ¶e in¯nito.(b) Todo subconjunto, de um conjunto ¯nito, ¶e ¯nito.

Demonstra»c~ao.

(a) Seja X um conjunto in¯nito ¶e e seja Y um superconjunto de X, i.e., X ½ Y .Ent~ao, pela De¯ni»c~ao 4.1, existe uma inje»c~ao f : X ! X tal que f(X)6= X.

De¯na uma fun»c~ao g : Y ! Y por

g(y) =

½

f(y) se y 2 Xy se y 2 Y ¡X

Deixamos ao leitor veri¯car que a fun»c~ao g : Y ! Y ¶e injetora e que g(Y )6= Y .Segue ent~ao, pela De¯ni»c~ao 4.1, que Y ¶e in¯nito.

(b) Seja Y um conjunto ¯nito e seja X um subconjunto de Y , i.e., X ½ Y . Parademonstrar que X ¶e ¯nito, supomos o contr¶ario, que X ¶e in¯nito. Ent~ao, por (a), oconjunto Y deve ser in¯nito. Isto ¶e uma contradi»c~ao. Portanto, o conjunto X ¶e ¯nito.

ele havia se mudado, da F¶³sica e da Qu¶³mica, para a Matem¶atica, cuja l¶ogica achava mais satisfat¶oria.Aos dezenove anos, matriculou-se na Universidade de GÄottingen para estudar Matem¶atica, e recebeu seugrau de doutor tres anos depois, sob a orienta»c~ao de Gauss. Sua contribui»c~ao fundamental µa Matem¶aticainclui o famoso \corte de Dedekind", um conceito importante no estudo de n¶umeros irracionais, que oleitor poder¶a ter a oportunidade de estudar em um curso de an¶alise real.

3Um conjunto unit¶ario ¶e um conjunto que consiste de um ¶unico elemento.

Conjuntos Enumer¶aveis e Conjuntos N~ao Enumer¶aveis 79

Teorema 4.2 Seja g : X ! Y uma correspondencia um-a-um. Se o conjunto X ¶ein¯nito, ent~ao Y ¶e in¯nito.

Demonstra»c~ao. Como X ¶e in¯nito, pela De¯ni»c~ao 4.1, existe uma inje»c~ao f : X ! Xtal que f(X)6= X. Como g : X ! Y ¶e uma correspondencia um-a-um, tamb¶em o ¶eg¡1 : Y ! X (Teorema 3.14, Cap¶³tulo 3). Temos agora o seguinte diagrama de inje»c~oes:

Y Y

g¡1

?

?

y

x

?

?

g

X ¡¡¡!f

X

ConseqÄuentemente, a composi»c~ao h = g ± f ± g¡1 : Y ! Y de inje»c~oes ¶e umainje»c~ao [Problema 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 , porque f(X)6= X.Logo, h(Y ) ¶e um subconjunto pr¶oprio de Y , e portanto Y ¶e in¯nito.

Corol¶ario 4.1 Seja g : X ! Y uma correspondencia um-a-um. Se o conjunto X ¶e¯nito, ent~ao Y ¶e ¯nito.

Demonstra»c~ao. Exerc¶³cio.

Teorema 4.3 Seja X um conjunto in¯nito e seja x0 2 X. Ent~ao X ¡ fx0g ¶e in¯nito.

Demonstra»c~ao. Pela De¯ni»c~ao 4.1, existe uma inje»c~ao f : X ! X tal que f(X) Ã X.H¶a dois casos a serem considerados: (1) x0 2 f(X), ou (2) x0 2 X ¡ f(X). Em cadacaso, devemos construir uma inje»c~ao gX ¡fx0g : ! X ¡fx0g, tal que g(X ¡fx0g)6=X ¡ fx0g.Caso 1. x0 2 f(X).

Existe um elemento x1 em X tal que f(x1) = x0. Uma fun»c~ao

g : X ¡ fx0g ! X ¡ fx0g

pode agora ser de¯nida por

g(x) =

½

f(x) se x6= x1x2 se x = x1 2 X ¡ fx0g

80 Conjuntos Enumer¶aveis e Conjuntos N~ao Enumer¶aveis

em que x2 ¶e um elemento do conjunto n~ao vazioX¡f(X), arbitrariamente ¯xado. Segueque gX¡fx0g : ! X¡fx0g ¶e injetora e que g(X¡fx0g) = f(X¡fx0; x1g)[fx2g 6=X ¡ fx0g. Portanto, X ¡ fx0g ¶e in¯nito neste caso.Caso 2. x0 2 X ¡ f(X).

De¯na uma fun»c~ao g : X ¡ fx0g ! X ¡ fx0g por g(x) = f(x) para todo x 2X ¡ fx0g. Como f : X ! X ¶e injetora, tamb¶em o ¶e g : X ¡ fx0g ! X ¡ fx0g.Finalmente,

g(X ¡ fx0g) = f(X)¡ ff(x0)g 6= X ¡ fx0g

Portanto, em qualquer caso, X ¡ fx0g ¶e in¯nito.

No que segue, denotaremos por Nk, k 2 N, o conjunto de todos os n¶umerosnaturais de 1 at¶e k; isto ¶e, Nk = f1; 2; : : : ; kg. Como uma aplica»c~ao do Teorema 4.3,mostramos no seguinte exemplo que cada Nk ¶e ¯nito.

Exemplo 4.2 Para cada k 2 N, o conjunto Nk ¶e ¯nito.Demonstra»c~ao. Demonstraremos isto pelo princ¶³pio de indu»c~ao matem¶atica. Pelo Exem-plo 4.1, a a¯rma»c~ao ¶e verdadeira para k = 1. Agora, suponha que o conjunto Nk ¶e ¯nitopara algum n¶umero natural k. Considere o conjunto Nk+1 = Nk [ fk+1g. Se Nk+1 forin¯nito, ent~ao, pelo Teorema 4.3, Nk+1¡fk+1g = Nk ser¶a um conjunto in¯nito, o quecontradiz a hip¶otese de indu»c~ao. Logo, se Nk ¶e ¯nito, ent~ao Nk+1 ¶e ¯nito. Portanto,pelo princ¶³pio de indu»c~ao matem¶atica, o conjunto Nk ¶e ¯nito para cada k 2 N.

Na verdade, existe uma conex~ao ¶³ntima entre um conjunto ¯nito n~ao vazio e umconjunto Nk.

Teorema 4.4 Um conjunto X ¶e ¯nito se e somente se X = ¿ ou X est¶a em corres-pondencia um-a-um com algum Nk.

Demonstra»c~ao. Se X ¶e vazio ou est¶a em correspondencia um-a-um com algum Nk,ent~ao, pelo Corol¶ario do Teorema 4.2, e Exemplos 4.1 e 4.2, o conjunto X ¶e ¯nito.

Para mostrar a rec¶³proca, mostramos, equivalentemente, sua contrapositiva: SeX6= ¿ e X n~ao est¶a em correspondencia um-a-um com nenhum Nk, ent~ao X ¶e in¯nito.

Podemos tomar um elemento x1 de X, e ter novamente X¡fx1g n~ao vazio; pois,caso contr¶ario, ter¶³amos X = fx1g em correspondencia com N1, uma contradi»c~ao coma hip¶otese sobre X.

Continuando desta maneira, suponhamos que escolhemos elementos x1, x2, : : : ,xk de X. Ent~ao X¡fx1; x2; : : : ; xkg ¶e n~ao vazio; caso contr¶ario, teremos X = fx1; x2;: : : ; xkg em correspondencia um-a-um com Nk, uma contradi»c~ao com nossa hip¶otesesobre X. Logo, podemos sempre escolher um elemento xk+1 de X ¡ fx1; x2; : : : ; xkg.Ent~ao, por indu»c~ao matem¶atica, para todo n¶umero natural n, existe um subconjunto

Conjuntos Enumer¶aveis e Conjuntos N~ao Enumer¶aveis 81

pr¶oprio fx1; x2; : : : ; xng de X. Denotemos o conjunto dos xn's escolhidos por Y .4

Ent~ao a fun»c~ao f : Y ! Y ¡ fx1g, de¯nida por f(xk) = xk+1 para todo k 2 N,estabelece uma correspondencia um-a-um entre Y e seu subconjunto pr¶oprio Y ¡ fx1g.Portanto, pela De¯ni»c~ao 4.1, Y ¶e in¯nito e portanto, pelo Teorema 4.1, X ¶e in¯nito.

Mencionaremos aqui que o Teorema 4.4 sugere uma de¯ni»c~ao alternativa de con-juntos ¯nitos e in¯nitos. Podemos de¯nir um conjunto como sendo ¯nito se e somentese ele ¶e vazio ou est¶a em correspondencia um-a-um com algum Nk, e sendo in¯nito see somente se n~ao ¶e ¯nito. Desta de¯ni»c~ao alternativa, nossa De¯ni»c~ao 4.1 pode serdemonstrada como um teorema. Entretanto, isto requeriria mais ou menos o mesmomontante de trabalho requerido pela nossa presente abordagem.

4.1.1 Exerc¶³cios

1. Complete a demonstra»c~ao do Teorema 1.2. Seja g : X ! Y uma correspondencia um-a-um. Demonstre que se X ¶e ¯nito, ent~aoY ¶e ¯nito.3. Demonstre que os conjuntos Z, Q e R s~ao in¯nitos.4. Demonstre 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 conjunto¯nito.7. Sejam A e B dois conjuntos tais que A[B ¶e in¯nito. Demonstre que ao menos umdos dois conjuntos A e B ¶e in¯nito.8. Demonstre a seguinte generaliza»c~ao do Teorema 4.3: Se Y ¶e um subconjunto ¯nitode um conjunto in¯nito X, ent~ao X ¡ Y ¶e in¯nito.

4.2 Equipotencia de conjuntos

Dois conjuntos ¯nitos X tem o mesmo n¶umero de elementos se e somente se existe umacorrespondencia um-a-um f : X ! Y . Embora a frase \mesmo n¶umero de elementos"n~ao se aplique aqui se X e Y s~ao in¯nitos, parece natural pensar que dois conjunto in¯ni-tos, que estejam em correspondencia um-a-um, tem o mesmo tamanho. Formalizaremosesta intui»c~ao como segue:

De¯ni»c~ao 4.2 Dois conjuntosX e Y dizem-se equipotentes, fato denotado porX » Y ,quando existe uma correspondencia um-a-um f : X ! Y .

4Aqui os autores usaram implicitamente o \axioma da escolha", um axioma importante a ser discutidono Cap¶³tulo 6. Uma forma do axioma da escolha pode ser enunciada como: \Seja P um conjunto n~aovazio, de subconjuntos n~ao vazios de um conjunto dado X . Ent~ao existe um conjunto R ½ X tal quepara todo C 2 P, C \ R ¶e um conjunto unit¶ario". Este axioma ser¶a usado em todas as partes destelivro, sem ser explicitamente mencionado.

82 Conjuntos Enumer¶aveis e Conjuntos N~ao Enumer¶aveis

Obviamente, todo conjunto ¶e equipotente a si mesmo. Como a inversa de umacorrespondencia um-a-um ¶e uma correspondencia um-a-um (Teorema 3.14), X » Yse e somente se Y » X. Convencionaremos que o s¶³mbolo f : X » Y signi¯car¶a\f : X ! Y ¶e uma correspondencia um-a-um e portanto X » Y ". Usando esta nota»c~aoconveniente, a primeira metade do Problema 9, Exerc¶³cios 3.7.1 pode ser re-enunciadocomo: Se f : X » Y e g : Y » Z, ent~ao g ±f : X » Z. Acabamos de demonstrar ent~aoo seguinte teorema.

Teorema 4.5 Seja Ium conjunto de conjuntos e seja R uma rela»c~ao em Idada por:X R Y se e somente se X e Y s~ao membros de Ie X » Y . Ent~ao R ¶e uma rela»c~ao deequivalencia em I.

No seguinte exemplo, os s¶³mbolos ]0; 1[ e ]¡ 1; 1[ denotam intervalos de n¶umerosreais.

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[, dada por f(x) = 2x¡ 1, ¶e uma correspon-dencia um-a-um. Portanto, ]0; 1[» ]¡ 1; 1[.

(b) A fun»c~ao trigonom¶etrica g : ]¡ 1; 1[! R, dada por g(x) = tg(¼x=2), ¶e umacorrespondencia um-a-um; portanto ]¡ 1; 1[» R. O leitor deveria veri¯car esta asser»c~aoesbo»cando um gr¶a¯co de g(x) = tg(¼x=2). Uma demonstra»c~ao rigorosa pode ser obtidaveri¯cando-se as seguintes duas observa»c~oes:(1) g : ]¡ 1; 1[! R ¶e cont¶³nua, e ilimitada, tanto superiormente como inferiormente.(2) g0(x) = (¼=2) sec2(¼x=2) > 0, 8x, ) g ¶e estritamente crescente.

Como a \rela»c~ao" de equipotencia ¶e transitiva,5 ]0; 1[» ]¡ 1; 1[ e ]¡ 1; 1[» R

implicam ]0; 1[» R.

Teorema 4.6 Sejam X, Y , Z e W conjuntos com X \ Z = ¿ = Y \W , e sejamf : X » Y e g : Z »W . Ent~ao f [ g : (X [ Z) » (Y [W ).

Demonstra»c~ao. Como f : X ! Y e g : Z ! W s~ao fun»c~oes com X \ Z = ¿, peloTeorema 3.8, do Cap¶³tulo 3, f [ g : X [ Z ! Y [W ¶e uma fun»c~ao. Deixaremos aoleitor a demonstra»c~ao de que esta ¶ultima fun»c~ao ¶e uma correspondencia um-a-um.

5Falando estritamente, \»" n~ao ¶e uma rela»c~ao de equivalencia, porque seu dom¶³nio n~ao ¶e umconjunto (veja Teorema 2.10 do Cap¶³tulo 2). Mas podemos cham¶a-la uma rela»c~ao se considerarmo-lade¯nida em qualquer conjunto de conjuntos I(Teorema 4.5).

Conjuntos Enumer¶aveis e Conjuntos N~ao Enumer¶aveis 83

Teorema 4.7 Sejam X, Y , Z e W conjuntos tais que X » Y e Z » W . Ent~aoX £ Z » Y £W .

Demonstra»c~ao. Sejam f : X » Y e g : Z » W . De¯namos a fun»c~ao f £ g : X £ Z !Y £W , por (f £ g)(x; z) = (f(x); g(z)) para todo (x; z) 2 X £ Z. Pedimos ao leitordemonstrar que esta ¶ultima fun»c~ao ¶e uma correspondencia um-a-um.

Examinando os v¶arios conjuntos ¯nitos Nk = f1; 2; 3; : : : ; kg, conforme k cresce,e notando que os conjuntos in¯nitos Z, Q, e R (veja Problema 3, Exerc¶³cios 4.1.1) s~aosuperconjuntos de N, parece que o \menor" conjunto in¯nito ¶e o conjunto N de todosos n¶umeros naturais, ou qualquer conjunto que seja equipotente a N. Aprenderemos embreve, na Se»c~ao 4.4, que nem todos os conjuntos in¯nitos s~ao equipotentes a N.

De¯ni»c~ao 4.3 Um conjunto X ¶e dito ser enumer¶avel quando X » N. Um conjuntocont¶avel ¶e um conjunto ¯nito ou enumer¶avel.

Seja X um conjunto enumer¶avel. Ent~ao existe uma correspondencia biun¶³vocaf : X » N. Se denotamos

f(1) = x1; f(2) = x2; f(3) = x3; : : : ; f(k) = xk; : : :

ent~ao X pode ser denotado alternativamente por fx1; x2; x3; : : : ; xk; : : : g; as reticencias( : : : ) s~ao usadas para indicar que os elementos s~ao etiquetados em uma ordem de¯nida,conforme indicado pelos ¶³ndices. Uma explica»c~ao para o termo \cont¶avel" est¶a agoraem pauta. Para um conjunto ¯nito, ¶e teoricamente poss¶³vel contar seus elementos e otermo ¶e adequado. Muito embora a contagem de fato de todos os elementos de umconjunto enumer¶avel X = fx1; x2; x3; : : : ; g seja imposs¶³vel, o conjunto X est¶a emcorrespondencia biun¶³voca com os n¶umeros de contagem, os n¶umeros naturais.

Teorema 4.8 Todo subconjunto in¯nito, de um conjunto enumer¶avel, ¶e enumer¶avel.

Demonstra»c~ao. Seja Y um subconjunto in¯nito de um conjunto enumer¶avel X = fx1;x2; x3; : : : g. Seja n1 o menor ¶³ndice para o qual xn1 2 Y , e seja n2 o menor ¶³ndicepara o qual xn2 2 Y ¡ xn1 . Tendo de¯nido xnk¡1 , seja nk o menor ¶³ndice tal quexnk 2 Y ¡ fxn1 ; xn2 ; : : : ; xnk¡1g. Um tal nk sempre existe pois Y ¶e in¯nito, o quegarante que Y ¡fxn1 ; xn2; : : : ; xnk¡1g 6= ¿ para cada k 2 N. Deste modo, constru¶³mosuma correspondencia um-a-um f : Y » N, sendo f(k) = xnk para cada k 2 N. Portanto,Y ¶e enumer¶avel.

Uma demonstra»c~ao mais curta, por¶em menos intuitiva, do Teorema 4.8, ¶e indicadano Problema 10 ao ¯nal desta se»c~ao. O seguinte corol¶ario ¶e uma conseqÄuencia imediatada De¯ni»c~ao 4.3 e do Teorema 4.8.

84 Conjuntos Enumer¶aveis e Conjuntos N~ao Enumer¶aveis

Corol¶ario 4.2 Todo subconjunto de um conjunto cont¶avel ¶e cont¶avel.

Mais exemplos e propriedades de conjuntos enumer¶aveis s~ao dados na pr¶oximase»c~ao.

4.2.1 Exerc¶³cios

1. Complete a demonstra»c~ao do Teorema 6.2. Complete a demonstra»c~ao do Teorema 7.3. Demonstre que se X e Y s~ao dois conjuntos, ent~ao X £ Y » Y £X.4. Demonstre que se (X ¡ Y ) » (Y ¡X) ent~ao X » Y .5. Demonstre a seguinte generaliza»c~ao do Teorema 4.6: Seja fX° j ° 2 ¡g e fY° j° 2 ¡g duas fam¶³lias de conjuntos disjuntos, tal que X° » Y° para cada ° 2 ¡. Ent~aoS

°2¡X° »S

°2¡ Y° .6. Demonstre que se X ¶e um conjunto enumer¶avel e Y ¶e um subconjunto ¯nito de X,ent~ao X ¡ Y ¶e enumer¶avel. [Compare com o Problema 8, Exerc¶³cios 4.1.1.]7. Demonstre que se X ¶e um conjunto enumer¶avel e Y ¶e um conjunto ¯nito, ent~aoX [ Y ¶e enumer¶avel.8. Demonstre que o conjunto Np, de todos os n¶umeros naturais pares, e o conjunto Ni,de todos os n¶umeros naturais ¶³mpares, s~ao enumer¶aveis.9. Seja A um conjunto n~ao vazio, e seja 2A o conjunto das fun»c~oes de A no conjuntof0; 1g. Demonstre que }(A) » 2A.10. Sejam X um conjunto enumer¶avel e Y um subconjunto in¯nito de X. Seja g : X »N, e seja h : Y ! N a fun»c~ao de¯nida por

h(y) = n¶umero de elementos em f1; 2; 3; : : : ; g(y)g \ g(Y )

Demonstre que h ¶e uma correspondencia um-a-um e que portanto Y ¶e enumer¶avel.

4.3 Exemplos e propriedades de conjuntos enumer¶a-

veis

O conjunto Np de todos os n¶umeros naturais pares e o conjunto Ni de todos os n¶umerosnaturais ¶³mpares s~ao enumer¶aveis (Problema 8, Exerc¶³cios 4.2.1). Como a reuni~ao Np [Ni(= N) destes dois conjuntos enumer¶aveis ¶e enumer¶avel, o pr¶oximo teorema deveriaser previs¶³vel.

Teorema 4.9 A uni~ao de dois conjuntos enumer¶aveis ¶e enumer¶avel.

Demonstra»c~ao. Sejam A e B dois conjuntos enumer¶aveis. Mostraremos que A [ B ¶eenumer¶avel nos dois casos seguintes:

Conjuntos Enumer¶aveis e Conjuntos N~ao Enumer¶aveis 85

Caso 1. A \B = ¿.Como A » N e N » Np, temos A » Np. De modo semelhante, temos B » Ni.ConseqÄuentemente, pelo Teorema 4.6, temos (A [ B) » (Np [ Ni) = N, o quedemonstra que A [B ¶e enumer¶avel.

Caso 2. A \B6= ¿.Seja C = B ¡ A. Ent~ao A [ C = A [B e A \ C = ¿; o conjunto C ½ B ¶e ou¯nito ou enumer¶avel [Corol¶ario 4.2 do Teorema 4.8]. Se C ¶e ¯nito, pelo Problema7 dos Exerc¶³cios 4.2.1, A [ C ¶e enumer¶avel, e se C ¶e enumer¶avel, ent~ao A [ C ¶eenumer¶avel, pelo caso 1 acima.

Portanto, o conjunto A [B ¶e enumer¶avel.

Corol¶ario 4.3 Sejam A1; A2; : : : ; An conjuntos enumer¶aveis. Ent~aoSnk=1Ak ¶e enu-

mer¶avel.

Demonstra»c~ao. A demonstra»c~ao ¶e deixada ao leitor, como um exerc¶³cio.

Pedimos ao leitor veri¯car o pr¶oximo exemplo.

Exemplo 4.4 O conjunto Z de todos os inteiros ¶e enumer¶avel.

Teorema 4.10 O conjunto N£ N ¶e enumer¶avel.

Demonstra»c~ao. Considere a fun»c~ao f : N£ N! N dada por

f(j; k) = 2j3k

para todo (j; k) 2 N£ N. Esta fun»c~ao ¶e injetora, de modo queN£ N » f(N£ N) ½ N:

Como N£N ¶e in¯nito, f(N£N) tamb¶em o ¶e. Pelo Teorema 4.8, f(N£N) ¶e enumer¶avele portanto N£ N ¶e enumer¶avel.

Corol¶ario 4.4 Para cada k 2 N, seja Ak um conjunto enumer¶avel satisfazendo Aj \Ak = ¿ para todo j6= k. Ent~ao

S

k2NAk ¶e enumer¶avel.6

Demonstra»c~ao. Para cada k 2 N, seja fk : N! N£ fkg uma fun»c~ao dada por fk(j) =(j; k) para todo j 2 N. Claramente, cada fk : N ! N £ fkg ¶e uma correspondenciaum-a-um. Ou seja, N » N £ fkg. Como Ak » N e N » N £ fkg para cada k 2 N,temos Ak » N £ fkg para cada k 2 N. Segue ent~ao, do Problema 5 dos Exerc¶³cios4.2.1, que

S

k2NAk »S

k2NN£fkg. Mas o conjuntoS

k2NN£fkg ¶e igual ao conjuntoenumer¶avel N£ N. Portanto, Sk2NAk ¶e enumer¶avel.

6Este resultado ¶e verdadeiro sem a hip¶otese \Ak \Aj = ¿ para todo j6= k." Veja Problema 7.

86 Conjuntos Enumer¶aveis e Conjuntos N~ao Enumer¶aveis

Exemplo 4.5 O conjunto Q de todos os n¶umeros racionais ¶e enumer¶avel.

Demonstra»c~ao. Representaremos cada n¶umero racional de maneira ¶unica como p=q,sendo p 2 Z, q 2 N e o m¶aximo divisor comum de p e q igual a 1. Seja Q+ o conjuntode tais elementos com p=q > 0, e seja Q¡ = f¡p=q j p=q 2 Q+g. Ent~ao Q =Q+[f0g[Q¡. ¶E evidente que Q+ » Q¡. Portanto, para mostrar que Q ¶e enumer¶avel,¶e su¯ciente mostrar que Q+ ¶e enumer¶avel. Para este prop¶osito, consideramos a fun»c~aof : Q+ ! N £ N, dada por f(p=q) = (p; q). Como esta fun»c~ao ¶e injetora, temosQ+ » f(Q+) ½ N£ N. Como Q+, como um superconjunto de N, ¶e in¯nito, f(Q+) ¶eum subconjunto in¯nito do conjunto enumer¶avel N£N. Portanto, f(Q+) ¶e enumer¶avele conseqÄuentemente Q+ ¶e enumer¶avel. A demonstra»c~ao est¶a agora completa.

O pr¶oximo teorema indica que os conjunto enumer¶aveis s~ao, em um certo sentido,os menores em \tamanho" dentre os conjuntos in¯nitos.

Teorema 4.11 Todo conjunto in¯nito cont¶em um subconjunto enumer¶avel.

Demonstra»c~ao. Seja X um conjunto in¯nito qualquer. Ent~ao X 6= ¿, de modo quepodemos escolher um elemento, digamos x1, no conjunto X. A seguir, seja x2 umelemento em X ¡ fx1g. De modo semelhante, escolha um elemento x3 do conjunton~ao vazio X ¡ fx1; x2g. Tendo assim de¯nido xk¡1, escolhemos um elemento xk noconjunto X ¡fx1; x2; : : : ; xk¡1g. Tal xk existe para cada k 2 N, porque X ¶e in¯nito, oque garante que X¡fx1; x2; : : : ; xk¡1g 6= ¿ para todo k 2 N. O conjunto fxk j k 2 Ng¶e um subconjunto enumer¶avel de X, e a demonstra»c~ao est¶a completa.

4.3.1 Exerc¶³cios

1. Demonstre a asser»c~ao do Exemplo 4.3: O conjunto Z de todos os inteiros ¶e enu-mer¶avel.2. Demonstre o Corol¶ario 4.3 do Teorema 4.9.3. Demonstre que a uni~ao de um n¶umero ¯nito de conjuntos cont¶aveis ¶e cont¶avel.4. Demonstre que se A e B s~ao conjuntos enumer¶aveis, ent~ao tamb¶em o ¶e A£B. Emparticular, Z£ N, Z£ Z, e Q£Q s~ao enumer¶aveis.5. Encontre uma fun»c~ao injetora f : Q ! Z £ N e de uma demonstra»c~ao alternativapara o Exemplo 4.5.6. Demonstre que o conjunto dos c¶³rculos no plano cartesiano, tendo raios racionais ecentros em pontos com ambas as coordenadas racionais, ¶e enumer¶avel.7. Demonstre que se para cada k 2 N, Bk ¶e um conjunto enumer¶avel, ent~ao

S

k2NBk¶e enumer¶avel.

4.4 Conjuntos n~ao enumer¶aveis

Todos os conjuntos in¯nitos que vimos at¶e o momento s~ao enumer¶aveis. Isto podelevar o leitor a indagar se todos os conjuntos in¯nitos s~ao enumer¶aveis. ¶E comumente

Conjuntos Enumer¶aveis e Conjuntos N~ao Enumer¶aveis 87

pensado que Georg Cantor tentou demonstrar que todo conjunto in¯nito ¶e enumer¶avel,quando iniciou seu desenvolvimento da teoria dos conjuntos. Entretanto, ele surprendeu-se demonstrando que existem conjuntos n~ao enumer¶aveis.

Teorema 4.12 O intervalo aberto ]0; 1[ de n¶umeros reais ¶e um conjunto n~ao enumer¶avel.

Demonstra»c~ao. Expressemos primeiramente cada n¶umero x, x < 0 < 1, comouma expans~ao decimal na forma 0; x1x2x3 : : : , com xn 2 f0; 1; 2; : : : ; 9g para ca-da n. Por exemplo, 1=3 = 0; 333 : : : ,

p2=2 = 0; 707106 : : : . De modo a ter uma

¶unica express~ao, para aqueles n¶umeros com uma expans~ao decimal ¯nita, tais como1=4 = 0; 25, concordaremos em subtrair 1 do ¶ultimo d¶³gito e acrescentar 9's, de modoque 1=4 = 0; 24999 : : : , e n~ao 0; 25000 : : : . Sob este acordo, dois n¶umeros no intervalo]0; 1[ s~ao iguais se e somente se os d¶³gitos correspondentes, de suas expans~oes decimais,s~ao identicos. Assim, se dois tais n¶umeros, x = 0; x1x2x3 : : : e y = 0; y1y2y3 : : : temuma casa decimal, digamos a k-¶esima casa decimal, tal que xk 6= yk, ent~ao x6= y. Este¶e um ponto crucial sobre o qual nossa demonstra»c~ao se apoia.

Agora, suponha que o conjunto ]0; 1[ ¶e enumer¶avel. Ent~ao existe uma correspon-dencia um-a-um f : N »]0; 1[. Ent~ao podemos listar todos os elementos de ]0; 1[ comosegue:

(¤)

f(1) = 0; a11a12a13 : : :Â

f(2) = 0; a21a22a23 : : :Â

f(3) = 0; a31a32a33 : : :... Â

f(k) = 0; ak1ak2ak3 : : :...

em que cada ajk 2 f0; 1; 2; : : : ; 9g.Construiremos um n¶umero z 2 ]0; 1[, que n~ao pode ser encontrado na lista acima de

f(k)'s. Esta contradi»c~ao implicar¶a que nossa suposi»c~ao pr¶evia de que ]0; 1[ ¶e enumer¶avelestava errada, e que portanto ]0; 1[ ¶e n~ao enumer¶avel. Seja z = 0; z1z2z3 : : : de¯nido porzk = 5, se akk 6= 5, e zk = 1 se akk = 5, para cada k 2 N. O n¶umero z = 0; z1z2z3 : : :claramente satisfaz 0 < z < 1; mas z6= f(1) pois z1 6= a11, z6= f(2) pois z2 6= a22, : : : ,e de modo geral z6= f(k) pois zk 6= akk, para todo k 2 N. Portanto, z62 f(N) = ]0; 1[.Temos ent~ao a contradi»c~ao prometida, e a demonstra»c~ao est¶a completa.

Corol¶ario 4.5 O conjunto R dos n¶umeros reais n~ao ¶e enumer¶avel.

Demonstra»c~ao. Fizemos a demonstra»c~ao, no Exemplo 4.3(b), de que R » ]0; 1[. Agora,]0; 1[ ¶e n~ao enumer¶avel; portanto seu conjunto equipotente R tamb¶em ¶e n~ao enumer¶avel(veja Problema 1).

88 Conjuntos Enumer¶aveis e Conjuntos N~ao Enumer¶aveis

Exemplo 4.6 O conjunto de todos os n¶umeros irracionais ¶e n~ao enumer¶avel.

Demonstra»c~ao. Demonstramos, no Exemplo 4.5, que o conjunto Q dos n¶umeros racio-nais ¶e enumer¶avel. O conjunto dos n¶umeros irracionais ¶e, por de¯ni»c~ao, o conjuntoR ¡Q. ¶E f¶acil ver que R ¡Q ¶e um conjunto in¯nito. Para mostrar que R ¡Q ¶e n~aoenumer¶avel, supomos o contr¶ario, que R ¡ Q ¶e enumer¶avel. Segue ent~ao que a uni~ao(R ¡Q) [Q = R ¶e enumer¶avel (Teorema 4.9). Isto contradiz o corol¶ario do Teorema12. Portanto o conjunto R¡Q dos n¶umeros irracionais ¶e n~ao enumer¶avel.

Notas. (1) O m¶etodo de demonstra»c~ao usado no Teorema 4.12 ¶e chamado m¶etododiagonal de Cantor, porque foi criado por Cantor e a constru»c~ao do n¶umero chavez = 0; z1z2z3 : : : , na demonstra»c~ao, ¶e baseada nos d¶³gitos a11; a22; a33; : : : na diagonalprincipal da tabela (¤) de d¶³gitos. Esta demonstra»c~ao, embora possa n~ao ser apreciadapelo iniciante, revela a engenhosidade de Cantor.

(2) A existencia de conjuntos n~ao enumer¶aveis mostra que existem classes deconjunto in¯nitos. Na verdade, como o leitor ver¶a no pr¶oximo cap¶³tulo, existe umaabundancia de \classes de equipotencia" de conjunto in¯nitos.

4.4.1 Exerc¶³cios

1. Sejam A e B dois conjuntos equipotentes. Demonstre que se A ¶e n~ao enumer¶avel,ent~ao B ¶e n~ao enumer¶avel.2. Demonstre que todo superconjunto de um conjunto n~ao enumer¶avel ¶e n~ao enumer¶avel.3. Usando o resultado do Problema 2, acima, de uma demonstra»c~ao alternativa docorol¶ario do Teorema 4.12.4. Demonstre que o conjunto dos n¶umeros irracionais entre 0 e 1 ¶e n~ao enumer¶avel.

5

N¶umeros Cardinais e Aritm¶eticaCardinal

O conceito de n¶umero cardinal ¶e introduzido. Semelhan»cas e diferen»cas entre pro-priedades de n¶umeros cardinais ¯nitos e trans¯nitos s~ao exibidas no curso da explora»c~aoda aritm¶etica cardinal|adi»c~ao, multiplica»c~ao e exponencia»c~ao. O cap¶³tulo termina comuma nota hist¶orica sobre a hip¶otese do cont¶³nuo (generalizada).

5.1 O conceito de n¶umeros cardinais

De modo bem natural, o conceito de n¶umero entrou em nossas vidas bem cedo. Fomoscapazes de notar, por exemplo, a similaridade entre tres ma»c~as e tres laranjas, e adistin»c~ao entre dois dedos e quatro dedos. Embora tiv¶essemos um conceito de n¶umero,a maioria de n¶os n~ao tinha uma de¯ni»c~ao precisa de n¶umero. Soubemos, por exemplo,que 2+3 = 5, 3 < 4, 6£7 = 42, etc. Isto nos leva a acreditar que n~ao precisamos sabero que um n¶umero realmente ¶e; o que devemos saber s~ao a igualdade e a ordem entren¶umeros, e como calcular com eles|exatamente do modo como jogadores de xadrezn~ao se preocupam com o que um cavalo ¶e, mas sim como ele desempenha. Portanto, n~aode¯niremos aqui o que um n¶umero cardinal ¶e,1 mas apenas introduzi-lo-emos como umconceito primitivo relativo ao \tamanho" de conjuntos. As regras importantes guiandoeste novo conceito s~ao

C-1. Cada conjunto A est¶a associado a um n¶umero cardinal, denotado por cardA, epara cada n¶umero cardinal a, existe um conjunto A com cardA = a.

C-2. cardA = 0 se e somente se A = ¿.

C-3. Se A ¶e um conjunto ¯nito n~ao vazio, i.e., A » f1; 2; : : : ; kg para algum k 2 N,ent~ao cardA = k.

1Talvez o leitor deva ser informado que ¶e poss¶³vel de¯nir os n¶umeros cardinais como os \ordinaisiniciais" (Veja p¶agina 138 de S-Y.T. Lin & Y-F. Lin, Set Theory: An Intuitive Approach. HoughtonMi²in Co., Boston, 1974).

89

90 N¶umeros Cardinais e Aritm¶etica Cardinal

C-4. Para quaisquer dois conjuntos A e B, cardA = cardB , A » B.

As regras C-1 e C-3 de¯nem os n¶umeros cardinais de conjuntos ¯nitos| o n¶umero car-dinal de um conjunto ¯nito ¶e o n¶umero de elementos naquele conjunto. Em tratamentosaxiom¶aticos da teoria dos conjuntos, C-1 e C-4 s~ao habitualmente postulados como umaxioma, chamado axioma da cardinalidade. O iniciante pode achar C-1 e C-4 dif¶³ceisde serem aceitos, pois estas regras n~ao dizem muito acerca de cardA quando A ¶e umconjunto in¯nito. Esta di¯culdade ser¶a superada gradualmente enquanto avan»carmos|tal como quando o leitor n~ao sabia o que ¶era c¶alculo, at¶e que chegasse µa metade deseu curso. Neste momento, podemos dizer, grosso modo, que o n¶umero cardinal deum conjunto ¶e a propriedade que o conjunto tem em comum com os conjuntos que s~aoequipotentes a ele.

5.1.1 Exerc¶³cios

1. Mostre que o os n¶umeros naturais s~ao n¶umeros cardinais.2. De exemplos de tres n¶umeros cardinais que n~ao s~ao n¶umeros naturais.

5.2 Ordena»c~ao dos n¶umeros cardinais|O Teorema

de SchrÄoder-Bernstein

Chamaremos o n¶umero cardinal de um conjunto ¯nito de n¶umero cardinal ¯nito, e on¶umero cardinal de um conjunto in¯nito de um n¶umero cardinal trans¯nito. As regrasC-2 e C-3 da se»c~ao anterior mostram que os n¶umeros cardinais ¯nitos s~ao precisamenteos inteiros n~ao negativos. Assim, os n¶umeros cardinais ¯nitos tem uma ordem naturalherdada: 0 < 1 < 2 < ¢ ¢ ¢ < k < k + 1 < ¢ ¢ ¢ . Para dois n¶umeros cardinais trans¯nitosquaisquer, a regra C-4 nos diz quando eles s~ao iguais e quando n~ao s~ao. Mas n~aoestaremos satisfeitos com apenas isto; quando eles foram diferentes, gostar¶³amos desaber qual deles ¶e \menor" que o outro.

De¯ni»c~ao 5.1 Sejam A e B conjuntos. Ent~ao dizemos que cardA ¶e menor que cardB,e denotamos isto por cardA < cardB, quando A ¶e equipotente a um subconjunto deB, mas o conjunto B n~ao ¶e equipotente a nenhum subconjunto de A.

Embora esta de¯ni»c~ao seja projetada para ordenar n¶umeros cardinais, ela se aplica an¶umeros cardinais ¯nitos tamb¶em, e quando aplicada a n¶umeros cardinais ¯nitos o re-sultado ¶e o mesmo que a ordem natural tradicional mencionada acima.

Exemplo 5.1 cardN < cardR.

Demonstra»c~ao. Como o conjunto N ¶e um subconjunto de R, N ¶e equipotente a umsubconjunto de R, N » N ½ R, mas pela Se»c~ao 4.4, Cap¶³tulo 4, sabemos que o conjunto

N¶umeros Cardinais e Aritm¶etica Cardinal 91

in¯nito R ¶e n~ao enumer¶avel. Portanto, R n~ao ¶e equipotente a nenhum subconjunto deN. Pela De¯ni»c~ao 5.1, temos cardN < cardR.

At¶e agora, n~ao nos ¶e claro como dois n¶umeros cardinais se comparam quando oconjunto A ¶e equipotente a um subconjunto de B e o conjunto B ¶e equipotente a umsubconjunto de A. Georg Cantor conjeturou que, neste caso, cardA deveria ser iguala cardB. Mais tarde, nos anos 1890's, esta conjetura foi demonstrada, independente-mente, por ambos F. Bernstein no semin¶ario de Cantor, e por E. SchrÄoder, baseado emum c¶alculo l¶ogico. Este resultado celebrado ¶e agora conhecido geralmente por Teoremade SchrÄoder-Bernstein.

Teorema 5.1 (Teorema de SchrÄoder-Bernstein) Se A e B s~ao conjuntos, tais queA ¶e equipotente a um subconjunto de B e B ¶e equipotente a um subconjunto de A,ent~ao A e B s~ao equipotentes.

Demonstraremos primeiramente o seguinte caso especial do Teorema 5.1, do qual oTeorema 5.1 segue facilmente.

Lema 5.1 Se B ¶e subconjunto de A e existe uma inje»c~ao f : A! B, ent~ao A e B s~aoequipotentes.

Demonstra»c~ao. Se B ¶e A, ent~ao a fun»c~ao identidade em A ¶e uma tal h. Suponhamosque B ¶e um subconjunto pr¶oprio de A, e seja C o conjunto

S

n¸0 fn(A¡B), sendo f 0

a fun»c~ao identidade em A e, para cada inteiro positivo k e para cada x 2 A, fk(x) =f(fk¡1(x)). Para cada z em A, de¯na h(z) como segue:

h(z) =

½

f(z) se z 2 C

z se z 2 A¡ C

Observe que A¡B ¶e um subconjunto de C, f(C) ½ C, e que se m e n s~ao dois inteirosn~ao negativos distintos, digamos m < n, ent~ao fm(A¡B) e fn(A¡B) s~ao disjuntos.Pois, caso contr¶ario, existem x e x0 em A¡B tais que fm(x) = fn(x0), o que acarretafn¡m(x) = x 2 B \ (A¡B), uma contradi»c~ao. Finalmente, pela de¯ni»c~ao de h e pela¶ultima observa»c~ao, temos

h(A) = (A¡ C) [ f(C)

=

"

A¡[

n¸0

fn(A¡B)

#

[ f

Ã

[

n¸0

fn(A¡B)

!

=

"

A¡[

n¸0

fn(A¡B)

#

[

Ã

[

n¸1

fn(A¡B)

!

= A¡ (A¡B)

= B

92 N¶umeros Cardinais e Aritm¶etica Cardinal

Destas observa»c~oes e do fato de que f ¶e injetora, segue que h : A! B ¶e uma bije»c~ao.Isto completa a demonstra»c~ao do lema.

A principal id¶eia por detr¶as da demonstra»c~ao acima pode ser visualizada no seguintediagrama ilustrativo, em que o retangulo inteiro representa o conjunto A:

Figura 17.

Demonstra»c~ao do Teorema 5.1. Sejam A0 e B0 subconjuntos de A e B, respectivamente,tais que A » B0 e B » A0, e sejam f0 : A » B0 e g0 : B » A0 duas bije»c~oes. Sejaf : A! A0 dada por f(x) = g0(f0(x)), que ¶e uma inje»c~ao. Portanto, pelo lema acima,existe uma bije»c~ao h : A » A0. ConseqÄuentemente, a composi»c~ao g

¡10 ± h : A » B, das

duas bije»c~oes h : A » A0 e g¡10 : A0 » B, ¶e uma bije»c~ao.

2

¶E conveniente escrever cardA · cardB como signi¯cando cardA < cardB oucardA = cardB. O seguinte corol¶ario ¶e uma conseqÄuencia imediata do Teorema deSchrÄoder-Bernstein.

Corol¶ario 5.1 Se A e B s~ao conjuntos tais que cardA · cardB e cardB · cardAent~ao cardA = cardB.

At¶e o momento, conhecemos muito pouco sobre n¶umeros cardinais trans¯nitos, porquevimos apenas dois tais n¶umeros cardinais, cardN e cardR. Naturalmente, gostar¶³amosde saber se h¶a outros n¶umeros cardinais trans¯nitos. A resposta a esta quest~ao ¶e dadana pr¶oxima se»c~ao|existe na verdade um suprimento ilimitado de n¶umeros cardinaistrans¯nitos distintos.

Uma outra quest~ao importante ¶e esta: Se m e n s~ao dois n¶umeros cardinais ¯nitosdistintos, ent~ao ou m < n ou n < m; ¶e isto tamb¶em verdadeiro para n¶umeros cardinaistrans¯nitos? A resposta ¶e a¯rmativa, mas a demonstra»c~ao depende de um resultado dopr¶oximo cap¶³tulo, e ¶e portanto adiada at¶e o Teorema 6.1 do Cap¶³tulo 6.

2Esta demonstra»c~ao e o lema precedente foram adotados de R.H. Cox, \A Proof of the Schroeder-Bernstein Theorem", American Mathematical Monthly, 75, No. 5 (1968), 508.

N¶umeros Cardinais e Aritm¶etica Cardinal 93

5.2.1 Exerc¶³cios

1. Seja n um n¶umero cardinal ¯nito qualquer. Demonstre que n < cardN.2. Seja a um n¶umero cardinal trans¯nito qualquer. Demonstre que cardN · a. Assim,cardN ¶e o menor n¶umero cardinal trans¯nito.3. Sejam A e B dois conjuntos. Demonstre que cardA · cardB se e somente se existeuma injec~ao f : A! B.4. Sejam A, B e C conjuntos. Demonstre que(a) Se cardA · cardB e cardB · cardC ent~ao cardA · cardC.(b) Se cardA < cardB e cardB < cardC ent~ao cardA < cardC.

5. Demonstre que se A e B s~ao conjuntos tais que A ½ B ent~ao cardA · cardB.6. Demonstre que se A, B e C s~ao conjuntos tais que A ½ B ½ C e A » C, ent~aoA » B.

5.3 N¶umero cardinal de um conjunto das partes|

Teorema de Cantor

SejaX um conjunto. Recordemos que o conjunto das partes }(X), deX, ¶e o conjunto detodos os subconjuntos deX (Se»c~ao 2.2, Cap¶³tulo 2). O pr¶oprio Georg Cantor demonstrouque cardX < card}(X). A signi¯cancia deste teorema ¶e que ele prove um modo decontruir uma longa seqÄuencia de novos n¶umeros cardinais trans¯nitos. Por exemplo,temos

cardR < card}(R) < card}(}(R)) < ¢ ¢ ¢ :

Teorema 5.2 (Teorema de Cantor) Se X ¶e um conjunto, cardX < card}(X).

Demonstra»c~ao. Se X = ¿, ent~ao card¿ = 0 < 1 = card}(¿). Portanto, resta provaro caso em que X 6= ¿. Neste caso, a fun»c~ao g : X ! }(X), dada por g(x) = fxg 2}(X), para todo x 2 X, ¶e injetora. Logo, o conjunto X ¶e equipotente ao subconjuntoffxg j x 2 Xg de }(X) ou, equivalentemente, cardX · card}(X). A partir disto,para mostrar que cardX < card}(X), ¶e su¯ciente mostrar que X n~ao ¶e equipotente a}(X).

Assuma, em contr¶ario, que exista uma bije»c~ao f : X » }(X); nosso prop¶osito ¶emostrar que esta suposi»c~ao leva a uma contradi»c~ao. Considere o conjunto S = fx 2X j x62 f(x)g, que consiste daqueles elementos de X que n~ao est~ao em suas imagenssob f . Como S 2 }(X) e f : X » }(X), existe um elemento e 2 X tal que f(e) = S.Ou e 2 S ou e62 S.

Caso 1. e 2 S.

Segue, pela de¯ni»c~ao de S, que e62 f(e); isto ¶e imposs¶³vel, pois f(e) = S e e62 S.

Caso 2. e62 S.

94 N¶umeros Cardinais e Aritm¶etica Cardinal

Como f(e) = S, temos e62 f(e). ConseqÄuentemente, pela de¯ni»c~ao de S, e 2 Se portanto e 2 f(e). Isto novamente ¶e imposs¶³vel.

Uma contradi»c~ao foi obtida e a demonstra»c~ao do Teorema de Cantor est¶a completa.

Em vista do Teorema de Cantor, uma quest~ao bem natural a surgir foi,

Existe um n¶umero cardinal x tal que

cardN < x < card}(N)?

Esta quest~ao, chamada o problema do cont¶³nuo, capturou a aten»c~ao de Cantor e outrosmatem¶aticos por muito tempo. Veremos mais sobre este problema na Se»c~ao 5.8.

5.3.1 Exerc¶³cios

1. Demonstre que n~ao existe um n¶umero cardinal maior de todos.2. Sejam A e B conjuntos. Demonstre que se A » B ent~ao card}(A) = card}(B).3. Seja A um conjunto enumer¶avel. Demonstre que o conjunto das partes de A, }(A),¶e n~ao enumer¶avel.

5.4 Adi»c~ao de n¶umeros cardinais

J¶a existe uma aritm¶etica para n¶umeros cardinais ¯nitos. Por exemplo, se k e l s~aodois n¶umeros cardinais ¯nitos, a soma k + l e o produto kl tem seus signi¯cados tradi-cionais. Tentaremos agora generalizar estes conceitos de modo a cobrir os n¶umeroscardinais trans¯nitos tamb¶em; ou seja, desenvolver uma aritm¶etica que se aplica a todosos n¶umeros cardinais, ¯nitos ou trans¯nitos, que preserve os signi¯cados e propriedadestradicionais da aritm¶etica dos n¶umeros cardinais ¯nitos.

De¯ni»c~ao 5.2 Sejam a e b n¶umeros cardinais. A soma cardinal de a e b, denotada pora+ b, ¶e o n¶umero cardinal card(A[B), em que A e B s~ao conjuntos disjuntos tais quecardA = a e cardB = b.

Para mostrar que a De¯ni»c~ao 5.2 est¶a bem-de¯nida, o leitor deveria primeiro observar quepara quaisquer dois n¶umeros cardinais a e b (n~ao necessariamente distintos), pela regraC-1 da se»c~ao 5.1, existem conjuntos X e Y tais que a = cardX e b = cardY , sendoos conjuntos X e Y n~ao necessariamente disjuntos. Mas isto n~ao nos causa nenhumproblema, pois podemos selecionar A = X £ f0g e B = Y £ f1g; ent~ao A » X,B » Y e A \ B = ¿. Logo a + b = card(A [ B) e isto ¶e de¯nido de maneira ¶unica;pois se existem outros conjuntos disjuntos A0 e B0 tais que A0 » A e B0 » B ent~ao,pelo Teorema 4.6 do Cap¶³tulo 4, temos (A0 [ B0) » (A [ B) ou, equivalentemente,card(A0 [B0) = card(A [B).

Desta forma, acabamos de demonstrar o seguinte teorema:

N¶umeros Cardinais e Aritm¶etica Cardinal 95

Teorema 5.3 Sejam a e b n¶umeros cardinais. Ent~ao

(a) Existem conjuntos disjuntos A e B tais que cardA = a e cardB = b.

(b) Se A, B, A0 e B0 s~ao conjuntos tais que cardA0 = cardA, cardB0 = cardB,A \B = ¿, e A0 \B0 = ¿, ent~ao card(A0 [B0) = card(A [B).

O seguinte exemplo mostra que a De¯ni»c~ao 5.2 concorda com a soma ordin¶aria dedois n¶umeros naturais, quando aplicada a dois n¶umeros cardinais ¯nitos.

Exemplo 5.2 Encontre a soma cardinal 4 + 3 dos dois n¶umeros cardinais ¯nitos 4 e 3.

Solu»c~ao. Como N7 = N4 [ f5; 6; 7g, cardN4 = 4, cardf5; 6; 7g = 3, e os conjuntos N4e f5; 6; 7g s~ao disjuntos, temos

4 + 3 = card(N4 [ f5; 6; 7g)

= cardN7 = 7

o que coincide com a soma ordin¶aria de dois inteiros.

Como a uni~ao de conjuntos ¶e comutativa e associativa, temos as seguintes pro-priedades correspondentes acerca da soma cardinal.

Teorema 5.4 Sejam x, y, e z n¶umeros cardinais quaisquer. Ent~ao

(a) x+ y = y + x (Comutatividade).

(b) (x+ y) + z = x+ (y + z). (Associatividade).

Seguindo Georg Cantor, os s¶³mbolos @0 (leia-se aleph3 zero; @ ¶e a primeira letra do

alfabeto hebraico) e c tem sido usados para denotar, respectivamente, o n¶umero cardinalde um conjunto enumer¶avel e o n¶umero cardinal do continuum4, continuum signi¯candoo conjunto dos n¶umeros reais. Em outras palavras, @0 = cardN e c = cardR.

Exemplo 5.3 Encontre a soma cardinal @0 + @0.

Solu»c~ao. Sejam Np e Ni, respectivamente, os conjuntos de n¶umeros naturais parese n¶umeros naturais ¶³mpares. Ent~ao, Np e Ni s~ao subconjuntos de N enumer¶aveis edisjuntos, e a uni~ao deles ¶e N. ConseqÄuentemente, pela De¯ni»c~ao 5.2,

@0 + @0 = cardNp + cardNi

= card(Np [Ni)

= cardN

= @0

3Pronuncia-se como \¶alef". (N. do T.)4Tamb¶em chamado cardinal do cont¶³nuo. (N. do T.)

96 N¶umeros Cardinais e Aritm¶etica Cardinal

O resultado do Exemplo 5.3 ¶e uma propriedade distintiva dos n¶umeros cardinaistrans¯nitos; para n¶umeros cardinais ¯nitos, n +m = n ¶e verdadeiro apenas se m = 0.O leitor poderia demonstrar, como exerc¶³cio, que c + c = c.

Exemplo 5.4 Encontre a soma cardinal @0 + c.

Solu»c~ao. J¶a aprendemos, do Exemplo 4.3, Se»c~ao 4.2, do Cap¶³tulo 4, que o intervaloaberto ]0; 1[ e o conjunto R, dos n¶umeros reais, s~ao equipotentes. Portanto, card ]0; 1[=cardR = c. Seja S = N[ ]0; 1[. Ent~ao, como N e ]0; 1[ s~ao disjuntos, cardS = @0+ c.Por outro lado, como R » ]0; 1[½ S e S » S ½ R, pelo Teorema de SchrÄoder-Bernstein(Teorema 5.1), temos S » R. Portanto, @0 + c = c.

5.4.1 Exerc¶³cios

1. Demonstre que x+ 0 = x para todo n¶umero cardinal x.2. Sejam x e y dois n¶umeros cardinais. Demonstre que x+ y = y + x.3. Sejam x, y, e z n¶umeros cardinais. Demonstre que (x+ y) + z = x+ (y + z).4. Seja n um n¶umero cardinal ¯nito qualquer. Demonstre que(a) n+ @0 = @0(b) n+ c = c.

5. Demonstre que c+ c = c.6. Sejam x, y e z n¶umeros cardinais.(a) Demonstre que se x · y ent~ao x+ z · y + z.(b) Mostre, atrav¶es de um exemplo, que a parte (a) acima n~ao ¶e verdadeira se \·"

for substitu¶³do por \<".

5.5 Multiplica»c~ao de n¶umeros cardinais

De¯niremos agora a multiplica»c~ao de n¶umeros cardinais de modo que, para n¶umeroscardinais ¯nitos, o resultado coincida com a multiplica»c~ao ordin¶aria de inteiros n~ao neg-ativos.

De¯ni»c~ao 5.3 Para quaisquer dois n¶umeros cardinais a e b, o produto cardinal ab ¶ede¯nido como sendo o n¶umero cardinal do produto cartesiano A£B, sendo cardA = ae cardB = b.

Para ver que a De¯ni»c~ao 5.3 ¶e independente da escolha dos representantes A eB, sejam X e Y conjuntos tais que A » X e B » Y . Ent~ao, pelo Teorema 4.7 doCap¶³tulo 4, A£B » X £ Y e portanto card(A£B) = card(X £ Y ). ¶E tamb¶em claroque esta de¯ni»c~ao d¶a a resposta certa quando a e b s~ao n¶umeros cardinais ¯nitos. Comoa multiplica»c~ao de inteiros n~ao negativos nos ¶e familiar, nosso interesse principal aqui ¶eo produto de n¶umeros cardinais trans¯nitos, e o produto de um n¶umero cardinal ¯nito

N¶umeros Cardinais e Aritm¶etica Cardinal 97

por um n¶umero cardinal trans¯nito. Primeiramente, listemos uma conseqÄuencia f¶acil daDe¯ni»c~ao 5.3

Teorema 5.5 Sejam x, y e z n¶umeros cardinais quaisquer. Ent~ao

(a) xy = yx (Comutatividade).

(b) (xy)z = x(yz) (Associatividade).

(c) x(y + z) = xy + xz (Distributividade).

Demonstra»c~ao. Exerc¶³cio.

Exemplo 5.5 Seja x um n¶umero cardinal arbitr¶ario. Calcule

(a) 1x.

(b) 0x.

(c) @0@0.

Solu»c~ao. Seja A um conjunto tal que cardA = x.

(a) Como o produto cartesiano f1g £ A ¶e equipotente a A, temos 1x = x.

(b) Como ¿£A = ¿, temos 0x = 0.

(c) Como N£ N » N (Teorema 4.10, Cap¶³tulo 4), temos @0@0 = @0.

Exemplo 5.6 Demonstre que cc = c, sendo c = cardR.

Solu»c~ao. Como o conjunto R dos n¶umeros reais e o intervalo aberto unit¶ario ]0; 1[, den¶umeros reais, tem o mesmo n¶umero cardinal c, para mostrar que cc = c, ¶e su¯cientemostrar que existe uma inje»c~ao do produto cartesiano ]0; 1[£ ]0; 1[ no intervalo ]0; 1[.Para este prop¶osito, usaremos o fato de que cada x 2 ]0; 1[ ¶e representado por suaexpans~ao decimal in¯nita, de forma que, por exemplo, o n¶umero 1

2ser¶a 0; 4999 : : : mas

n~ao 0; 5. Deste modo, teremos uma ¶unica express~ao para cada n¶umero em ]0; 1[. Agora,deixaremos ao leitor veri¯car que a fun»c~ao f : ]0; 1[£ ]0; 1[ ! ]0; 1[, de¯nida por

f(0; x1x2x3 ¢ ¢ ¢ ; 0; y1y2y3 ¢ ¢ ¢ ) = 0; x1y1x2y2 ¢ ¢ ¢

¶e injetora. Isto completa a demonstra»c~ao de que cc · c. A demonstra»c~ao de que cc ¸ c¶e deixada ao leitor.

98 N¶umeros Cardinais e Aritm¶etica Cardinal

5.5.1 Exerc¶³cios

1. Demonstre o Teorema 5.5.2. Sejam x, y, e z n¶umeros cardinais tais que x · y. Demonstre que xz · yz.3. Demonstre ou refute a seguinte proposi»c~ao: Se x, y, e z s~ao n¶umeros cardinais taisque x < y e z6= 0, ent~ao xz < yz.4. Seja n um n¶umero cardinal ¯nito, n6= 0. Demonstre que n@0 = @0.5. Sejam x e y n¶umeros cardinais. Demonstre que(a) Se xy = 0 ent~ao x = 0 ou y = 0.(b) Se xy = 1 ent~ao x = 1 e y = 1.

6. Mostre que a fun»c~ao f : ]0; 1[£ ]0; 1[! ]0; 1[, de¯nida por

f(0; x1x2x3 ¢ ¢ ¢ ; 0; y1y2y3 ¢ ¢ ¢ ) = 0; x1y1x2y2 ¢ ¢ ¢

da demonstra»c~ao no Exemplo 5.6, ¶e bijetora.

5.6 Exponencia»c~ao de n¶umeros cardinais

Sejam a e b dois n¶umeros cardinais, ¯nitos ou trans¯nitos. De modo a dar um signi¯cadosatisfat¶orio a ba (leia-se: a-¶esima potencia de b), examinaremos primeiramente o caso¯nito: 23 = 2¢2¢2 e, de modo geral, nm = n¢n¢¢ ¢ ¢¢n (m fatores). Poder¶³amos generalizareste conceito ao caso trans¯nito, introduzindo \produtos cartesianos generalizados", masexiste uma abordagem que funciona sem referencia a produtos cartesianos generaliza-dos. Sejam A um conjunto com m elementos e B um conjunto com n elementos.Quantas fun»c~oes existem de A em B (veja Problema 9, Exerc¶³cios 3.4.1)? Como cadaelemento de A tem n escolhas para sua imagem, e esta sele»c~ao da imagem pode serfeita independentemente m vezes (uma vez para cada elemento de A), a resposta ¶en ¢ n ¢ ¢ ¢ ¢ ¢ n = nm. Este conceito ¶e generalizado como segue:

De¯ni»c~ao 5.4 Sejam a e b n¶umeros cardinais com a6= 0. Sejam a e b conjuntos taisque cardA = a e cardB = b. Denote o conjunto de todas as fun»c~oes de A em B porBA. De¯nimos ba = cardBA.

Antes de aceitar a de¯ni»c~ao 5.4, precisamos veri¯car que esta de¯ni»c~ao ¶e independenteda escolha dos representantes A e B. O seguinte teorema ¶e o que precisamos.

Teorema 5.6 Sejam A, B, X e Y conjuntos tais que A » X, B » Y . Ent~ao BA »Y X .

Demonstra»c~ao. Sejam g : A » X e h : B » Y duas bije»c~oes. Ent~ao de¯nimos a fun»c~ao

à : BA ! Y X

N¶umeros Cardinais e Aritm¶etica Cardinal 99

por Ã(f) : X ! Y , sendo Ã(f)(x) = h ± f ± g¡1(x), para toda f 2 BA.

Af

¡¡¡! B

g

?

?

y

?

?

y

h

X ¡¡¡!Ã(f)

Y

Deixamos ao leitor demonstrar que a fun»c~ao à : BA ! Y X ¶e bijetora.

Exemplo 5.7 Seja A um conjunto. Compare os n¶umeros cardinais card}(A) e 2cardA.

Solu»c~ao. Seja B = f0; 1g. Associamos a cada subconjunto D de A a fun»c~ao carac-ter¶³stica ÂD : A! B, de¯nida no Exemplo 3.8, Cap¶³tulo 3. A fun»c~ao de }(A) em BA,que leva D em ÂD, ¶e bijetora (demonstre isto!). Assim, os conjuntos }(A) e B

A tem omesmo n¶umero cardinal; ou seja card}(A) = 2cardA.

Teorema 5.7 Sejam a, x e y n¶umeros cardinais. Ent~ao axay = ax+y.

Demonstra»c~ao. Sejam A, X e Y conjuntos tais que cardA = a, cardX = x, cardY =y, e X \ Y = ¿. Ent~ao, pela De¯ni»c~ao 5.2, card(X [ Y ) = x+ y. ¶E su¯ciente mostrarque os conjuntos AX£AY e AX[Y s~ao equipotentes. Com este prop¶osito, associamos acada par (f; g) de fun»c~oes, f 2 AX , g 2 AY , a fun»c~ao f [g 2 AX[Y [Veja Teorema 3.8,Cap¶³tulo 3]. Deixamos ao leitor veri¯car que esta associa»c~ao estabelece uma equipotenciaentre os conjuntos AX £AY e AX[Y . Portanto, axay = ax+y.

Teorema 5.8 Sejam x, y e z n¶umeros cardinais. Ent~ao (zy)x = zyx.

Demonstra»c~ao. Sejam X, Y , e Z conjuntos com n¶umeros cardinais x, y e z respec-tivamente. Conforme a De¯ni»c~ao 5.4, o teorema est¶a provado se estabelercemos queZY£Z » (ZY )X . Antes de mostrar esta equipotencia, necessitamos primeiro de umaconven»c~ao notacional: Para uma fun»c~ao dada f : Y £ X ! Z e um elemento dadoa 2 X, existe uma fun»c~ao fa : Y ! Z de¯nida por fa(b) = f(b; a) para todo b 2 Y .Deixamos ao leitor demonstrar que a fun»c~ao à : ZY£X ! (ZY )X , que associa a cadaf 2 ZY£X a fun»c~ao ef 2 (Z

Y )X , dada por ef (a) = fa para todo a 2 X, ¶e uma bije»c~ao.

Recordemo-nos que a A-proje»c~ao pA : A £ B ! A ¶e uma fun»c~ao que associa acada par ordenado (a; b) 2 A £ B o elemento a; a B-proje»cµao pB : A £ B ! B ¶eanalogamente de¯nida [veja Problema 8, Exerc¶³cios 3.5.1].

Teorema 5.9 Sejam a, b e x n¶umeros cardinais. Ent~ao (ab)x = axbx.

100 N¶umeros Cardinais e Aritm¶etica Cardinal

Demonstra»c~ao. Sejam A, B e X conjuntos com n¶umeros cardinais a, b e x, respectiva-mente. A fun»c~ao à : (A£B)X ! AX£BX , que emparelha cada fun»c~ao f : X ! A£Bcom a fun»c~ao (pA ± f; pB ± f) em A

X £BX , ¶e bijetora (Demonstre-o!). Portanto, pelaDe¯ni»c~ao 5.4, (ab)x = axbx.

Recordemo-nos que os s¶³mbolos @0 e c denotam os n¶umeros cardinais dos conjuntosN e R, respectivamente, e que Q » N (veja Exemplo 4.5, Cap¶³tulo 4), e ]0; 1[» R (vejaExemplo 4.3, Cap¶³tulo 4). Assim, @0 ¶e o n¶umero cardinal de Q e c ¶e o n¶umero cardinaldo intervalo ]0; 1[.

Teorema 5.10 2@0 = c.

Demonstra»c~ao. Demonstraremos isto em duas etapas, mostrando primeiro que c · 2@0

e ent~ao que 2@0 · c.

Considere a fun»c~ao f : R! }(Q), de¯nida por

f(a) = fx 2 Q j x < ag; para cada a 2 R

Esta fun»c~ao ¶e injetora: Se a < b s~ao dois n¶umeros reais distintos, ent~ao existe umn¶umero racional r tal que a < r < b.5 Ent~ao r 2 f(b) mas r 62 f(a), e portanto f ¶einjetora. Isto demonstra, usando-se os resultados do Problema 3, Exerc¶³cios 5.2.1, e oExemplo 5.7, que

c · card}(Q) = 2@0

Para provar a desigualdade reversa, seja à : f0; 1gN ! R a fun»c~ao de¯nida por

Ã(f) = 0; f(1)f(2)f(3) ¢ ¢ ¢

em que f 2 f0; 1gN. Note que Ã(f) ¶e um n¶umero decimal (consistindo de 0's e 1's).Se f; g 2 f0; 1gN e f 6= g, ent~ao Ã(f)6= Ã(g) porque as decimais que de¯nem Ã(f) eÃ(g) s~ao diferentes. Portanto, Ã : f0; 1g ! R ¶e injetora, e portanto 2@0 · c.

Corol¶ario 5.2 @0 < c.

Demonstra»c~ao. Pelo Teorema de Cantor (Teorema 5.2) e pelo resultado do Exemplo5.7, temos

@0 < card}(N) = 2cardN = 2@0 = c

5Porque os n¶umeros racionais s~ao um subconjunto denso dos n¶umeros reais.

N¶umeros Cardinais e Aritm¶etica Cardinal 101

5.6.1 Exerc¶³cios

1. Demonstre que a fun»c~ao à : BA ! Y X , da demonstra»c~ao do Teorema 5.6, ¶e bijetora.2. Seja a um n¶umero cardinal arbitr¶ario. Demonstre que a0 = 1, a1 = a, e 0a = 0 sea6= 0.3. Demonstre que 2a > a para todo n¶umero cardinal a.4. Sejam a, b, x, e y n¶umeros cardinais tais que a · b e x · y. Demonstre que ax · by.5. Demonstre que n@0 = c = @@00 para todo n ¸ 2 ¯nito.6. Demonstre que c@0 = c = cn para qualquer n ¸ 1 ¯nito.7. Seja C o conjunto de todos os n¶umeros complexos. Demonstre que cardC = c.8. Demonstre que @0c = c.9. Demonstre que a fun»c~ao de }(A) em f0; 1gA, que associa cada D em }(A) a ÂD, ¶ebijetora.10. Sejam A, X, e Y conjuntos tais que X e Y s~ao disjuntos. Demonstre que a fun»c~aode AX £ AY em AX[Y , que associa cada (f; g) em AX £ AY a f [ g em AX[Y , ¶ebijetora.11. Demonstre que a fun»c~ao à : ZY£X ! (ZY )X , na demonstra»c~ao do Teorema 5.8, ¶ebijetora.12. Demonstre que a fun»c~ao à : (A£B)X ! AX £BX , na demonstra»c~ao do Teorema5.9, ¶e bijetora.

5.7 Outros exemplos de aritm¶etica cardinal

Exemplo 5.8 Demonstre que cc = c, usando o Teorema 5.10 [cf. Exemplo 5.6].

Demonstra»c~ao. Dos Teoremas 5.7 e 5.10, e do Exemplo 5.3, @0 + @0 = @0, segue que

cc = 2@02@0 = 2@0 = c

Exemplo 5.9 Compare o n¶umero cardinal do conjunto ff j f : R ! Rg, de todas asfun»c~oes de R em R, com o n¶umero cardinal de R.

Solu»c~ao. Temos

cardff j f : R! Rg = cc De¯ni»c~ao 5.4

= (2@0)c Teorema 5.10

= 2@0c Teorema 5.8

= 2c Problema 8, Exerc¶³cios 5.6.1

> c Exemplo 5.7, Teorema 5.2

Portanto, cardff j f : R! Rg > cardR.

Exemplo 5.10 Sejam C(R;R) e C(Q;R) os conjuntos de fun»c~oes reais cont¶³nuas, comdom¶³nio R e Q, respectivamente. Seja K(R;R) o conjunto de todas as fun»c~oes reaisconstantes com dom¶³nio R. Demonstre que

cardC(R;R) = cardC(Q;R) = cardK(R;R) = c

102 N¶umeros Cardinais e Aritm¶etica Cardinal

Demonstra»c~ao.6 A cada fun»c~ao f : R ! R, corresponde uma fun»c~ao f jQ : Q ! R,de¯nida por (f jQ)(x) = f(x), para todo x 2 Q. A fun»c~ao f jQ ¶e chamada a restri»c~aode f a Q. Portanto, existe uma fun»c~ao natural

à : C(R;R)! C(Q;R)

que leva cada f 2 C(R;R) em sua restri»c~ao f jQ. ¶E claro que a restri»c~ao de uma fun»c~aocont¶³nua ¶e cont¶³nua. Portanto à ¶e uma fun»c~ao bem-de¯nida.

Da propriedade de densidade dos n¶umeros racionais dentro dos n¶umeros reais,segue que para cada n¶umero real x existe uma seqÄuencia fxn j n 2 Ng, de n¶umerosracionais, tal que

limn!1

xn = x

ConseqÄuentemente, se duas fun»c~oes cont¶³nuas f; g : R! R tem a propriedade deque f(x0) = g(x0) para todo x0 2 Q, ent~ao f(x) = g(x) para todo x 2 R. Em outraspalavras, a fun»c~ao à : C(R;R)! C(Q;R) ¶e injetora. Portanto temos

cardC(R;R) · cardC(Q;R)

· cardRQ

= c@0

= (2@0)@0

= 2@0@0

= 2@0 = c

pelos Teoremas 5.8 e 5.10.

Agora, considere o conjunto K(R;R) de todas as fun»c~oes reais constantes, comdom¶³nio R. Como para cada n¶umero real a, existe uma fun»c~ao constante fa : R ! R,de¯nida por fa(R) = fag, temos

cardK(R;R) = c

Como cada fun»c~ao constante fa : R ! R ¶e cont¶³nua, temos K(R;R) ½ C(R;R).Portanto,

c = cardK(R;R) · cardC(R;R)

o que, combinado com a desigualdade obtida no ¶ultimo par¶agrafo, nos d¶a

c = cardK(R;R) · cardC(R;R) · cardC(Q;R) · c

Isto completa a demonstra»c~ao de que cardC(R;R), cardC(Q;R) e cardK(R;R) s~aotodos iguais a c.

O resultado do Exemplo 5.10 indica que as fun»c~oes constantes s~ao t~ao \numerosas"quanto as fun»c~oes cont¶³nuas. Esta ¶e outra ilustra»c~ao das propriedades curiosas dosconjuntos in¯nitos.

6A demonstra»c~ao pode ser omitida, a crit¶erio do professor.

N¶umeros Cardinais e Aritm¶etica Cardinal 103

Exemplo 5.11 Encontre o n¶umero cardinal do conjunto D(R;R) de todas as fun»c~oesreais diferenci¶aveis de uma vari¶avel real.

Solu»c~ao. Como cada fun»c~ao constante ¶e diferenci¶avel e cada fun»c~ao diferenci¶avel ¶econt¶³nua, temos

K(R;R) ½ D(R;R) ½ C(R;R)

Pelo exemplo 5.10, temos

c = cardK(R;R) · cardD(R;R) · cardC(R;R) = c

Portanto, cardD(R;R) = c.

5.7.1 Exerc¶³cios

1. Mostre que o espa»co n-dimensional Rn = R £ R £ ¢ ¢ ¢ £ R (n fatores) cont¶em\exatamente tantos" pontos quanto o intervalo aberto unit¶ario ]0; 1[.2. O espa»co de Hilbert cl¶assico consiste de todas as seqÄuencias in¯nitas(x1; x2; x3; : : : ) de n¶umeros reais, chamadas pontos, para as quais a s¶erie x

21+x

22+x

23+¢ ¢ ¢

converge. Mostre que o espa»co de Hilbert cl¶assico cont¶em \exatamente tantos" pontosquanto a reta real R.3. Seja R@0 o conjunto de todas as seqÄuencias in¯nitas (x1; x2; x3; : : : ) de n¶umerosreais, chamadas pontos no espa»co R@0 . Um ponto reticulado em R@0 ¶e um ponto(x1; x2; x3; : : : ) tal que todos os xk's s~ao inteiros. Mostre que o espa»co R

@0 cont¶em\exatamente tantos" pontos quanto o conjunto de pontos reticulados em R@0 .4. Mostre que existem \exatamente tantas" fun»c~oes de uma vari¶avel real que assumemapenas os valores 0 e 1 quantas fun»c~oes reais de n vari¶aveis, sendo n um n¶umero naturalqualquer.5. Seja f o n¶umero cardinal do conjunto ff j f : R ! Rg de todas as fun»c~oes reais deuma vari¶avel real. Mostre que

fn = f@0 = fc = f

para todo n 2 N.

5.8 A hip¶otese do cont¶³nuo e sua generaliza»c~ao

Como todo conjunto in¯nito cont¶em um conjunto enumer¶avel (Teorema 4.11, Cap¶³tulo4), o n¶umero cardinal @0 ¶e o menor n¶umero cardinal trans¯nito. Uma quest~ao importante,conhecida como o problema do cont¶³nuo, foi levantada por Cantor, em torno de 1880:Existe um n¶umero cardinal que est¶a estritamente entre @0 e 2

@0(= c)? Em linguagem deconjuntos, existem subconjuntos n~ao enumer¶aveis de R com n¶umero cardinal menor queo de R? Cantor e muitos matem¶aticos de ponta tentaram em v~ao resolver este problema.Como nenhum tal conjunto foi encontrado em parte alguma na matem¶atica cl¶assica, eparecia n~ao haver nenhum modo de encontrar algum, foi conjeturado por Cantor e outrosque a resposta ao problema do cont¶³nuo deveria ser n~ao. Esta conjetura ¶e conhecidacomo hip¶otese do cont¶³nuo.

104 N¶umeros Cardinais e Aritm¶etica Cardinal

Hip¶otese do Cont¶³nuo. N~ao h¶a nenhum n¶umero cardinal x satisfazendo @0 < x <

c(= 2@0).

Uma quest~ao intimamente relacionada ao problema do cont¶³nuo, citado habitual-mente como problema do cont¶³nuo generalizado, ¶e o seguinte: Existe algum n¶umerocardinal que est¶a estritamente entre um n¶umero cardinal trans¯nito a e 2a? Esta quest~aotamb¶em n~ao foi respondida. A conjetura de que n~ao existe um tal n¶umero cardinal ¶echamada hip¶otese do cont¶³nuo generalizada.

Hip¶otese do Cont¶³nuo Generalizada. Para qualquer n¶umero cardinal trans¯nito a,n~ao h¶a nenhum n¶umero cardinal x tal que a < x < 2a.

Logo em 1900, no Congresso Internacional de Matem¶aticos, em Paris, o grandematem¶atico alem~ao David Hilbert7 (1862{1943) apresentou uma lista de 23 problemasmatem¶aticos n~ao resolvidos, sendo o primeiro deles o problema do cont¶³nuo. Nenhumprogresso foi feito em solucionar este problema at¶e 1938, quando Kurt GÄodel8 (1906{1978), o not¶avel l¶ogico do s¶eculo, demonstrou que se a hip¶otese do cont¶³nuo ¶e adicionadaaos axiomas usuais das teoria dos conjuntos, ent~ao qualquer contradi»c~ao que poderiaser implicada por este sistema de axiomas pode ser formulada como uma contradi»c~aoimplicada pelos axiomas iniciais (sem a hip¶otese do cont¶³nuo generalizada) sozinhos.9

Em outras palavras, a hip¶otese do cont¶³nuo generalizada ¶e relativamente consistentecom os axiomas da teoria dos conjuntos.

Finalmente, em 1963, uma conquista signi¯cativa foi feita pelo jovem matem¶aticoPaul J. Cohen (1934{ ) da Stanford University, que declarou que a hip¶otese do cont¶³nuogeneralizada ¶e indemonstr¶avel com base nos axiomas usuais da teoria dos conjuntos.Portanto, o status da hip¶otese do cont¶³nuo, na teoria dos conjuntos, ¶e an¶alogo ao do

7David Hilbert (1862{1943), um matem¶atico not¶avel de todos os tempos, foi professor de matem¶aticana Universidade de GÄottingen, Alemanha (1895{1943). In°uenciou totalmente o mundo da matem¶aticamoderna, desde a ¶algebra do 19o s¶eculo at¶e a l¶ogica moderna e a f¶³sica matem¶atica. O famoso espa»code Hilbert ¶e uma de suas muitas contribui»c~oes. Hilbert acreditava que todas as id¶eias matem¶aticasencaixavam-se num todo harmoniosamente.

8Kurt GÄodel (1906{1978) do Institudo de Estudos Avan»cados de Princeton, em Nova Jersey, nasceuna Tchecoslov¶aquia. Conseguiu fama primeiramente aos 25. Estudiosos famosos, incluindo BertrandRussel (1872{1970) e Alfred North Whitehead (1861{1947), haviam sugerido a existencia de guiasabsolutos µa veracidade ou falsidade de certas proposi»c~oes matem¶aticas. GÄodel chocou o mundo de-monstrando que o que Russel e Whitehead buscavam n~ao existia. Suas outras grandes contribui»c~oesincluem a demonstra»c~ao da completude da l¶ogica de quanti¯cadores e a demonstra»c~ao da consistenciade ambos a hip¶otese do cont¶³nuo generalizada e o axioma da escolha.

9Veja K. GÄodel, The Consistency of the Axiom of Choice and of the Generalized Continuum Hypotesiswith the Axioms of Set Theory, Princeton University Press, Princeton, N.J., 1940, 66 pp. Rev. ed.,1951, 74 pp.

N¶umeros Cardinais e Aritm¶etica Cardinal 105

axioma das paralelas de Euclides (o Quinto Postulado) na geometria. Podemos postul¶a-los ou neg¶a-los, em qualquer caso obtendo um teoria matem¶atica consistente.