Augusto César Morgado

Paulo Cezar Pinto Carvalho

MATEMÁTICA DISCRETA

1ª edição
Rio de Janeiro
2014
Sociedade Brasileira de Matemática
•1seM
COLEÇÃO DO PROFESSOR DE MATEMATICA

Logaritmos - E. L. Lima
Análise Combinatória e Probabilidade com as soluções dos exercícios - A. C. Morgado. J. B. Pitombelra, P. C. P. Carvalho e
P. Fernandez
Medida e Forma em Geomerria (Comprimento, Área, Volume e Semelhança) - E. L. Lima
Meu Professor de Matemática e outras Histórias - E. L Lima
' Coordenadas no Plano com as soluções dos exercfdos - E. L. Uma com a colaboração de P. C. P. Carvalho
Trigonometria, Números Complexos - M. P. do Carmo, A. C. Morgado e E. Wagner, Notas Históricas de J. B. Pitombeira
Coordenadas no Espaço - E. L Lima
Progressões e Matemática Financeira - A. C. Morgado, E. Wagner e S. C. Zani
Construções Geométr,cas - E. Wagner com a colaboração de J. P. Q. Carneiro
Introdução à Geometria Espada/ - P. C. P. Carvalho
Geometria Euclidiana Plana - J. L. M. Barbosa
Isometrias - E. L. Lima
A Matemática do Ensino Médio Vol. 1- E. L. Lima, P. C. P. Carvalho, E. Wagner e A. C. Morgado
A Matemática do Ensino Médio Vol. 2- E. L Uma, P. C. P. Carvalho, E. Wagner e A. C. Morgado
A Matemática do Ensino Médio Vol. 3 - E. L. Lima, P. C. P. Carvalho, E. Wagner e A. C. Morgado
Matemaiica e Ensino - E. L. Lima
Temas e Problemas - E. L Uma, P. C. P. Carvalho, E. Wagner e A. C. Morgado
Episódios da História Anriga da Matemática - A. Aaboe
Exame de Textos: Análise de livros de Matemática - E. L. Lima
A Matemática do Ensino Media Vol. 4 -Exerc,c,os e Soluções - E. L. Lima, P. C. P. Carvalho, E. Wagner e A. C. Morgado
Construções Geométricas: Exercícios e Soluções - S. Lima Netto
Um Convite à Matemática- D.C de Morais Rlho
Tópicos de Matemática Elementar- Volume 1 - Números Reais - A. Caminha
Tópicos de Macemática Elementar - Volume 2 - Geometria Euclidiana Plana - A. Caminha
Tópicos de Matemática Elementar - Volume 3 - Introdução à Análise - A. Caminha
Tópicos de Matemática Elementar - Volume 4 - Combinatoria - A. Caminha
Tópicos de Matemática Elementar - Volume 5 - Teoria dos Números - A. Caminha
Tópicos de Matemática Elementar- Volume 6 - Polinômios - A. Caminha
Treze Viagens pelo Mundo da Matemática - C. Correia de Sa e J. Rocha (editores)
Como Resolver Problemas Matemâticos - T. Tao
Geometria em Sala de Aula - A. C. P. Hellmeister, coordenadora

COLEÇÃO PROFMAT

Introdução à Algebra Linear - A. Hefez e C.S. Fernandez

Tópicos de Teoria dos Números -C. G. Moreira , F. E Brochero e N. C. Saldanha
Polinómios e Equações Algébricas - A. Hefez. e M.L Villela
Tópicos de Historia de Matemática - T. Roque e J. Bosco Pitombeira
Recursos Computacionais no Ensino de Matemática - V. Giraldo, P. Caetano e F. Mattos
Temas e Problemas Elementares - E. L Lima, P. C. P. Carvalho, E. Wagner e A. C. Morgado
Números e Funções Reais - E. Lages Lima
Aritmétíca - A. Hefez
Geometr,a - A. Caminha
Avaliação Educacional - M. Rabelo
Prefácio IX

1 Números N aturais 1
1.1 Introc!U<;ão . . . 2
1.2 :\'úmeros Ordinais . 2
1.3 Adição. m11ltiplicaçãn e orcleru
Ex0rricios . . . . . . . . . . . 8
1.-! :\' (1merm, :'faturais <' Cont agPm . 10
Exerdc:ios . . . . . . . . . . . . 13

2 O Método d a Indução 15
2.1 lnlroclução . . . . . . . . . . . . . . . L6
2.2 Definições por i11duçào ou recorrência 16
2.3 Dcmrmstramlo igualdacles 17
2.-1 Deu1ouslra11clo desiguakladcs . 1!)
2.5 ApliraçÕ<'f: cm Ari1.111é1 ica 20
2.6 Resolvendo problemas colli o 1uétocio <ln indu<;ão . 21
Exercídoi-:. . . . . . . . . . . . . . . . . 25
2. 7 Outras forma:-- do Princípio da lud u<;ão 27
Exercícios 32

3 Progr essõ es 35
3.1 Progressões Aritrn<"ticas 36
3.2 Termo geral de wua Progres:são Arit111é>tiu1 3G
3.3 Soma dos Tenuos de lllllél Progrrc;são AritmétieH . 39
;3.4 Proµ;re::;:sõcis .\ritrnétí<-a.s dí' Ordí'm S11µerior .!]
3.5 Souuu, Polinomiais -!:j
Ex0rdcios . . . . . 18
:3.5 Progre~.,:;Õe!:> Geométricas ,)-!
:1. 7 Tenno G<'ral de um Progressão Geomélrita
3.b A Fórmula rlm:; Tax.l:ili EquiYalonte~ . . . . .
3.D ./\ Soma do~ TPrtuus ele mua ProgrC's:-:ião Geomél rica

V
St.\!.\HTO

VIII
 Est ,c livro é hascíldo. prinripéllmcntc. nos capítulos csrritos por Augusto Crsar !\forgéldo para o
\'ol1111H' 2 d0 A~ [at.<'rnálica elo Ensino Médio. publicado pela Coleção do Professor ck MatemâtiC'a.
,la SB~l. O prinrip..il fl<'ré:;;C'imo foi a inrl11são dos rapí[Link] rC'lritivos no conjunto do:c, números
uaturms <' ,10 Pri11cípin ela Indução Finirn, com o cluplo propósito dC' fornccc>r a bns<' tc•ónrn
aproprir1d<1 parn o assunto C' atrnclC'r ..'1 ementa da disciplin,1 1\Ii\12 - ='-f;itcmfltira Disrrf'tH do
Profmnt.
!\<1 revi:..ào do 1m1lrrial ant crinrmcntc pnhlicaclo. a maior dúvida foi sohr<' como proceder c-ou1
r<'laç,io ao capítulo ck' ~fatemática Fiuai1c<'ira. escrito <'lll uma é'poca cm qu<' o Brasil vivia uma
n ·alidacle hem clifere11t e da al m1I. ern que Uixas de jmos anuais da ordrm <l<' 50% <'rmn c-om1111s.
lmcwlmPntP. c·onsid<'r<'i n•0s,-rcwr o capítu lo, suhst il uiudo os exemplos por situAÇÕC's mais atuais.
Preferi. 110 t'Ilt auto. m, maior parle clo1:> casos. rrcserva1 a 111C'mória da ohrn inic-ial. q_nc rcAet e
o bumor e' a pPrsoualicladc• dP 1\forga<lo, acr0scC'11tandn notas C'xplicativas sempre quC' n situação
de:,,critc:1 uilo rnrrespoucl<1 il rea1i<lacle atual.
Ao longo de' todo o liHo, foram HCT<'SC'C'utados 110,·os C'X<'ITícios. muitos <lelC's proYC'nicntcs de
ex<Hne::, ele Acei;:,o e Qualifieaç~o elo Profn 1al. dC' aYal iaçÕ<'i-i ant C'riorC's da disciplina 1'f A 12 e de
pronir-- da OBt IEP. Em pflrticular. o mpít11lo de Cornbiuat ória ganhou uma sC'ção d0 rC'visào . para
permitir ao leitor se exercitar no ai:.suulo. sem que a técnica a !i<'l' m,ada seja sngrrida pC'lo tópiro
<lC'ndo e<;tudado. Tambt'>m foi ac-rPsc·eutada. 1io capítulo sohr" Prohabilida<le. mm1 introdução ao
c·ü11cei lo ele Yalor ei;peraclo.
Gostaria de Pxpre<;sar meus ngTadc'c·imrutos a Slicila Zani, p0la permissão para usar e adaptar
o material original elo Prof. ~lorgado. e a P<ltricia Fonteucllc. pelo m1xílio na rC'visào do capítulo
sobre :\latemática Financc1rn.
Rio de .Janeiro. [Link]'iro dr 2014

Paulo Cezar Pinto Carvalho

lm;tituto d<-' ~J..,temM,irn Pmn <' Aplicada - Th fPA <'
Escolrt d<' J\latC'1m\1 ic;i Aplkacla - EJ\IAp FGV

LX
PlU·.F.\( "!()

X
NÚMEROS NATURAIS
 C'APÍTl"I.O 1 Nl'i\ lE [Link] .:'\ATlºR.-\ IS

1.1 Introdução
A primeira experiênC'ia que a maior parte de nó:; tem rorn a l\Iatemáti<"a é por meio <lo processo
de contagem. É importante obs<'rvar (tuc aprender a contar tem dnas [Link] he111 cListilltas. com
graus de cmnpl<."xidadP também distintos:

• Na prinwirn f'tnpa, c'[Link]'nd0mos a 0nunciar ama S<'<Juêncü-t de palavras ( 11rn. dois. três .... ).
scw ai rilmir signifkaclo a elas:

• Algnm tem pn depois. ;i prcndcmos a usar es1 a Sf'C[Uf'uc·i..i para co11tu r os elcU1e11tos <le UlU
conj1111to. 011 seja, <'[Link]<'r urna rnrr<'spondén<"ir1 entn-' o:-. elouwutos <lo cu11jw1to e c::.la::.
palttvTct.S q11c c·hanrnmos de númC'rm, . .~\lgo notável. quE:' não C'llSt,ai11os a ub::;en·êu. é que.
não import,1 f'OlllO façamos a corrcspondê>ncia. o núnH'ro final é sP111pn• o mesmo a ele,
clenominarnos o núrncro clc rlcm<'ntos elo <'Onjnuto .

.A nwsma l ar<>fa <'111 dr rns C'l apas clC'VC' S<'r C'lllpn'<'ll<licla ao se est ahelecer a limdawenlaçào
matemMicn apropriada para os números rwturais . Ao olliar os númerm, 11at nntb como uma
:-.irnples seq11rnda. estamos diélntr cio qrn' drn.11uuuos de' nú111eros ord111a1.,. [Link] a seguir.
Pnquant.o SL'll uso comn instnuncntn de rontagc•m rcmc'tc• à noção <le 11:1ímcro (·nrdinal. Psi uclncla
uo fim cle-Stt' rapíl 11 Jn.

1. 2 N ún1eros Ordinais
Como dcsrreYcr mM<'maticanwntC' a est [Link] elo conjmllo dos u(uueros uat urni.,;. no semi<lo
dC' uúmeros ordinais? Como cm outros ramot> <la ~Intcmátic-a. i:-;to (, fc>ito por nwio de uma fala
<lc> propried::idrs rssc•ndais. rhamacla.-. ele' ([Link]. que c:arac1.eriie111 a est ru lura da srquênda. sem

ninbiguidadrs ou prop1iC'délCl<'S f--Upé'rfiuas. isto é. qu<::• J)OS8..Ull sn obt idas das <lc'lll,:Ü.s. Giuscppe
Peano ( 18,:38-19;32) propôf> nma lista de' axiomas. baseado ua noc;ão de s11tPssor de um uúmero
11ah1ral (int uitivam<'nt<'. o qu<' Ycm logo dC'pois dele na fo;ta dos númPros nrtturni::-i). A construçfiu
ele Peano c·Mar1 critél o ronjunto dos números na [Link] N por mc>io dos sc>guint es -! a.xiou1as:

1. Tnclo munC'ro natural tem 1U11 único sucessor. que t ambé111 é 11 m níw1ero 11al mal.

2. Kúuwro;:; nal urais diferente~ tem suce&som, difcreut ei:..

3. Exi:-;l.e 1m1 ú II ico número uai ural. debigua<lu por 1. que uào é suc:es~or de nenhum outro.

4. Seja S um c:oujunto <lc uúmerot:. naturi1il, (islo é. X e N). Se 1 E X e ::.e. além di::,hO. o
sucessor de ca<la elemenLo <le X aiu<la penence a X. então X = N.

2
 i\(:\IEHOS ()f{l)l:'\.\IS C .\l'Í 11 · 1.o I

A noção de sucessor de um número natural está intimamente relacionada à idéia de adição: tomar
o ;:iutessor é [Link] a sornar uma Lu1idade. corno discutido em mais dC'tallic na seção L.3. Os
axiomas de Peano podem ser reescritos como se segue. representando como n + 1 o sucessor de
ll :

1. Todo número nMma1 n. tem 11ru sucessor. reµreseutaclo por 11 + 1.

2. Se m + l = n + 1. então m = ri.
3. Existe um único número [Link]. designado por 1. tal que ll + 1 =-J. 1, µara todo ·n E N.
4. Seja X um coujm1Lo de númeroi:, naturai1:i (isto é. X e N). Se J E X e se. além disso,
H + 1 E X. para cada n E X. emão X= N.

OBSERVAÇÃO 1.1.
O terceiro [Link] estabelece 1 corno sendo o único número natural que não é o sucessor de
nenhum ou tro e que. portanto. representa o ·-pon to de partida'' no conj unLo N = {1. 2. 3.... }
dos números natmais. É comW11. também, adotar-se O cow o ponlo de partida, levando a N =
{O, 1. 2, 3, .. .} . A opção por Ull1a ou outra a lt [Link] é uma questão de goslo ou d e conveniência .

Emhora todos os quatro axiomas sejam fundamentais para a caracterização dos 11C11ueros
[Link], o último. chamado de A:i:iom.a da indução. se destaca. Ele fornece Lilll mecauismo para
ganmrir qn<' nm d~<lo subconjunto X de N inclui , na ,·erdade. todos os [Link] de N. Por esta
rn.ú'io. é nm instrumento fundamcnLal para construir defiuiçõei, e clewoui,trar Leoremas relativos
a nún1C'ros na hrrais (as definições e provas por indução ou recorrência).
Snponbamos q11<' desejemos provar que uma propriedade P(n) relaLiva ao número natural
II seja v,Hida para todos o::, valores [Link] dc> N. Ou seja. desejamos provar que o conjunto

X= {nlP(n)}. q11c é 11m s11l1C'onj11nto de N é. na verdade. igual ao próprio N. Pelo axioma da

Lncl11ção basta mostrar que 1 E X e que o sucessor dc> cada clcmcmo de X rnmbém está em X.
Em Lermo:) da proprjedade P(n). ist.o <Y1u ivalc n mostrar que: i) P(l) é válida; ii) Para lodo
11 EN, a. validez de P('II) implica trn vaLidf'z de P(n + 1). Vc>[Link], estes dois fatos, conclui-se

n \'[Link] de P(n) para todos os valor<'s d~ 11.

O axioma da Indução pode ser reescri to como ab:ú:xo. usando a LinguagE'm de propriedades
(nesLa forma. ele costuma ser chamado de Princípio da lnrfoçrfo Vin-ita 011 rlFI. Tndnção Matemá-
tica):

-!'. Sejn P(n) mna propriedade relativa ao número naLmal n. Suponhai1101:i que

i) P(l) é válida.

3
 C' .\l'Í'l l 1.< > 1 :\('.\11-:l{OS '.\' .\'ITHAIS

li) Parn todo n EN. a u'tlidrz de P(11) implica ua validez de P(n + 1).
E111.ão. P(n) é Yálida para, to<lo n EN.

EXE\lf'L', 1
Con:-.idrrrmos o prob[c,wa de ohler uma expresf':âo para, a soma 1 + :3 + 0 + ... + (2n - 1).
Cnlcnlando ;1 sOlllêl pnra o~ prinwirm, valores 11at urab [Link] 11. oh lemos:
1= 1
1 + :1 =-!
1 + :l + ,) = n
1 + :3 + 5 t- 7 = 16

O cxilmc [Link] [Link]:; acima sugN<' que a ::.uma :,eja sempre igual ao quadraclo cio níllll<'l'O
dr pflrrrlm;, 011 srj,l. ffllC' n afirnrnti\·a P( n) : 1 + :3 + 5 + ... + (211 - 1) = n 2 {- válida parn todo
n E N. O Princípio da Iudução pcrmit e demonstrar este falo. O primeiro passo é:

i) Ycrilicar a validez de> P(n) para ,z = 1.

lsto já foi feito acinrn. quando ,·erilicamos que. para -r1 = l. awhos os lados d!'l igwtldadr
qnr prc>t,<'ndPmo~ provar são ig,11ais a 1.

A :,.cguir. devemo:-. :

ij) verificar que a validez de P(n ), pm-a tml valor arbitrário ele 11. implica ua validez de ?(11+ 1 ).

Ou ::.eja. aduüliuclo que 1 + 3 + 5 + ... + (2n - 1) = n.2 parfl nm ce1to Yalor cll' 11, elevemos
mostrar qu<' 1 + :3 + 5.- · · · + (2n - 1) ..1- (2(n + 1) - l) = (n + 1)2.
Para tal. :-oman1u:- o novo lermo 2(n+ 1) - J a ambos o~ nwmhro:, de 1 +:1+5+· · ·+ '211.-l =
n 2 . Obtemos:
l + :3 + 5 + ... + (211 - l) + (2(n + 1) - l) = n 2 + 2(11 + 1) - 1 = n 2 + 2n + l = (n + 1)2.
Portanto. a validez de P( n) para um valor arbitrário de TI implica Plll sna vfl 1id0z p11rn n + 1.

Logo. pelo Prindpio da Inclução. P(n ). ou sCjil. l + 3 + 5 + .. . + 2n - 1= ,,:z. é válida parn Lodo
II EN.

O BSERVAÇÃO 1.2.
A verificação de que P (l ) é válida costtwia ser chamada ele [Link] [Link] df' uma demonstntc;ão
por indução. enquanto a <lemoustrai;ão de tlue a validcz d e P (n) implica na validrz de P (n +
l ) é cliama<la de JHU,~o de indução. O passo <le iucJuc;ão cost uma ger a r C'O nfusão no p1imeiro

4
 :\ I>IC,' .\<>. !\ li' LT li 'LI<'.\<,'.\.(> E l >H 1>E!\I (' \l'Íl t 1.() 1

conlalo com [Link].01istrações por iu<lução. Pode parf'c-er. à primeira vista. que f'st amo::, u:,ando. na
demonstração, exatat11eule aquilo yue <le!-[Link]!- provar (ou seja. P(n)). Na verdade>, o seglllldo
passo requer a prova da iwplicação P(n) ::::} P(n + 1). Como oronE' na pron'I de qualquer
impl icação . isto é Jeito [Link] a validcz elo aniccC'dentc-. ou hipótese ([Link] caso cLaurnda
ele hipótese de md'Uçâo) P(1t) e lllostraudo que. rlaí. dec;orr<-' a validez do rons€'qn<"nte. on te::,e
P(n + 1). Foi exatamente o que fizemos acima.

[~E~IPLO '.L
Cousi<leremos a ig11akladC' P (n) : 1 + :3 + ... + (2n - 1) = n 2 +L Supondo que P(n) é
rnrclacleira para algum Lemos 1 +3 +5+ ... + 2n- l + 2(11 + 1) -1 = n 2 + l + 2n + 1 = (n + 1) 2 .
,1.

Porrauto. a i..mplicação P(n) ::::::> P(n +])é verdadC'ira para todo 11 EN. embora P(n) scjn falsa
para [Link] 11 (já que, no exemplo anterior. mostramo::, qnc a soma é igual a n 2 e não n. 2 + 1).
Isto ilustra o falo ele que no pa~so C'tn (JHC' provamos a implica ção P(n) ~ P (n + 1) não estamos
u::;unclo o [Link] que [Link]::, [Link]. _\Taturalmente, a prova por indução falha por não
c:;0r possível mostrar o caso base (P( l ) é fal:-m).

1.3 Adição , multiplicação e ordem

~o exemplo acima. utilizamos as propricdüdcs con heciclm, ela adição e multiplicação COill

uúwerm, [Link]. que são a base para a [Link]ção das expressões que lá ocorreram. Tais
prnprieclades podem ser dc'monstradas formalmente. usando o Princípio ela Inclução. Para i~to.
110 entru.1to. é preciso [Link].r apropriadamente a adiç ..fo e a [Link];ão. Para isto, recorremos
[Link]• ao mecanismo da indução. Seja a(n) um an-ibuto rclnlivo eh.> n(w1cro natural 11. Se
definimos a( l ) <' [Link],tabelecernos C'orno 0(11 + L) podr srr ohtido c1 partir de a(n), para n E N
arbitrá rio, o Axioma da [ndução garnnt r que o atributo n(n.) estará definido para cada 11 E N.
Definições con::,Lrnídas clcsta forma são [Link] de dE'finições por mduçào ou recorrência.
Por ex<'mplo. H somR m +n d<' dois números natmais pode ser uefinida por rf'corrê>ncia <lo
::-.eguinte modo:

DEFINIÇÃO 1.3.

i) m + 1é definido. como fizemos antes. como o sucessor de 111.

ii) m + (n + 1) {> definido romo o Sl tce8sor ele m. + n. ou seja. corno (m +TI ) + l.

5
 .\(:\IEHOS l\.YI'LIH.\IS

A ddiuic;ào Hcirna rorrrsponde à ideia wt1titiva d<:> que o valor <le 1t1+11 é ubli<lo acre1:.celila11do-
c;;(' 11 vc~es uma 11nicla<ll-- n 111.

Pnra a mult ipfü·Hçàu, podemo1:, defi11 ir:

DEFINlÇÃO 1.4.

i) rn. l = m .

ii) m.( 11 + 1) =HUI+ 111.

.\ parr ir d<'SSH.'- definições, podem ser dcmouslradas t"IB propriedade · usuai:- dc1 adição e wulti-
plicação. Ilm,[Link] c5le falo com a clcllloill!traçãu <la proµrie<la<le di::ilribuLirn da 111ult iplic:1-l(;ào
C'lll r<'lação à adição.

TEORE'MA 1.5.
Para quaisqner números naturais m, n e p. vale (m + n ).p = m. 11 + m .7).

D EMOJ\STRAÇÃO.
\·amo:,, utilizar indução <'lll p.

i) A propriedade é válida µara µ = 1. já que ( Til + 11) · 1 = 111 + 11 e 111. l + 11.1 = 111 + 11.
ii) Supouhawm, que a prnprif"dade i:,pja [Link]<la pari'l 11m c·prlo 11. ou ::;E'jfl. (m+n).11 = 111.11..1..111.p.

Tf'ums, prla definição indutiva da multip li cação: (m + n). (JJ + 1) = ( m ~ n) .p + ( m +n) ~ las.
pela hipól <'SC d<' indução. ( m + n).p = m .JJ + r, .p. Port.fü1l o. ( 111 + 11). (JJ+ l) = (111.p + 11 .JJ) +
(ir,+ n) = m.p -i- 111 + n.p + n (aqui, usamos as propriC'dades comutativa C' associativa <la
adição. qn<:> clC'V<'riru.u ler sido provada:-:. prc,·iarncnl e). ]\ las. pela der-inição <lP mnllipliC'clÇào.
IPwos 1n.p+111 = 111.(p+l) e> n.p+n = n.(p+ 1). Logo. (17i+n).(p-l) = m.(p+l)+n.(p, 1).
A::i:,im. êl alinualiva é válida l,Ulll>é'w para J) + 1.

Port,Rnto. pelo Prwcípio da Indll(;iio. H proprirdadc (, válic.h1 parêl qunisqu0r m. 11 <.' p u,nurais.

A i11lro<lnção da.'> opcrac;õc:, aritrnélic:as permite tornar precisa uma [Link] uoc;ão fuu<lamenlal
para números natmrus: a<le ordem.
DEFINIÇÃO 1.6.
Sejam m e n números naturais. Dizemos que m < n quando existe um número mü1.u-al p tal
quem+ p = n.

6
 . \ i>I<,'.\l). >.ll"LTIPI.!C'.\(.\0 E ORDDI ('\l'Í'II Lll l

Desta definição. podem ser obtidas as propriedades [Link] d<1 ordem.

TEOREMA 1.7.

a) Se m < 11 e, n < p, então m < p.

li) Darlos m. n EN. \'file nma. e somentr unrn. dai; alternatiYas: m = 11, 111 < ·11 ou 11 < m.

r) Se m < 11 então. para qualquer p EN. tem-se 111 +p < n +p e mp < 11p.

Além dessai, µropriedadeb. a ordem 11os uínncros ual mai& 1em 1m1R prnprieclc'lcle Cêu·art cr(stica,
c-ouheci<la como a Pro7n"1edadr da Bon Ordrnação:

TEORE!vlA 1.8.
Todo suucoujU11to não yazio X C N possui um mC'nnr demento Isso significa qur exist<? mll
elemento "u E X que é menor elo que todos os demais f'lernent os ele X.

:\'ot,e que a Propricclaclc da Boa Ordeua,ão uão valE' parn a orcl0111 cl0fi11icfa E'lll outros conjuntos
uuméricos; por cxclllplo. o coujunto dos números reais e o dos numeras r<'icÜS positivos são nfio
,·aiim,, mab não pm,suem 1uu nH'llOr rlrmculo.
A <lemow,trac;ão da Propricdauc da Boa Or<lcnação é feita por induçno. mas a adiamo~ para
o próximo capílulo. [Link] cow a demorn,trnçào clP uma Yasiant e elo Priudpio da Indução.
[Link] <le Pnncípio da inclução [Link] to.

7
 (' ,\l'ÍTl ' LO l

Exercícios
1.1. O diagrama ahai-xo. <'m que a sct.a wclica o sucessor de cada elememo. representa a estrnhrra
dos números na htrais [Link] pe)oi., a.-x:iomas de Peano.

~~~,,--.......~~
l 2 3 4 5 6 7

Em cadé1 urn do::. diagramas a seguir. exatamente um dos [Link] de Peano é violado. D iga
qual é ele.

a)

~~~~
1 2 3 J 5 G 7
'--.__.,/

b)

~~~
1 2 3 4 ~ 6 7
"-...__/ "-...__/ ~

e)

~ ,,---....,,~~~
l ? 3 4 5 G 7
'-..__/

<l)

~~~+~~~-
1 2 3 4 5 6 7

1.2. Prove. por indução, que

l+ 22 _,__ 32 -t-···+n 2 =
n(n + 1)(211 -1) .
6
1.3. Diga onde está o erro da seguinte demonstração d~ ~firmativa
1,2+4+ + ... +2"=2 +1 •
11

A proprwdade é lr'ivialmente válida para n = 1. Suponhamo.,; que seja u6lida. para n, ou seja
1+2+4+ + .. .+211 = 2n+l. Enlão 1+2+4+8+ ... +2n+2n+l = 2n+1 +2n+I = 2.2n+l = 2'1+2 .

8
 EXEB< 'Í< 'I< >S C'.\l'ÍTl ' 1.0 J

Portanto, a propriedade tornbém é v6lida pnra n-L l. Logo. pelo Princípio da Indu.çtio Frn'ita.
1+ 2 + 4 + + ... + :2 = 2n+i
11
para. todo n E N.

1.4. Gsaudo iJ1dução e a prop1icdadc associatiY<1 clc1 adição. demonstre a lei do corte: ºSe 111."
e JJ são uúweros naturais tais quC' m + p = n-,- p. cnt.:io m = 11. [Sugestão: nse indução cm
p, notando que o caso base da indução é o segundo a.xio11la de Peauo.l

1.5. Demonstre a propriedade trausitiYa <la ordem: Sem. 11 e p sifo números T1ailmw, lrus que
m < n e 11 < p. cmtno m < p.

9
 C .\ l 'Í'ITI.O l ~(' :\IEHOS t\XITH .-\IS

1.4 Números Naturais e Contagen1

A primeira lrnbilid,1d0 q11e dominamos no uso dos números uatlU·ai::, é a <le conlar, ou ~eja. a
<le <lctenniuar o 11t'm1<"ro dr PlC'rnrntos d<' um conjunto.

DEFINIÇÃO 1.9.
Contar um conjunto X signilica estabelecer uma correspondência biunívoca eutre os [Link]
de X e os de um subconjunto de N da forwa Ín = {:r E
N l.r. < n} = {1.2 ..... n}. Quando é
possível estabelecer tal <.:orTesµondência biunívoca. dizemos que X é um conjunto finito e que n
é o rnímero [Link] ou número de elenientos <le )(.

OBSERVAÇÃO 1.10.
Cma correspondên cia biunívoca entre dois conjuntos X e Y é uma função hijcl iva J:X ~ Y.
ou seja. uma regTa que associa a cada elemento ele X um elemento de Y de modo q11e cada
cleweuto de Y seja imagem de exatamente um elemento de X (isto equivale l'l clizrr que Jé uma
função siruulLaneamente injetiYa e sobrejetiva).

A par! ir desta definiçiio podemos <lrmonsrrar as propricdadrs básicas da contagrm:

TEOREMA 1.11.

fl) O resultado da conlagen1 (ou seja. o número card:inal ele X) é sempre o mesmo, não im.-
porta11do a contagem que seJa Jeit.a.

b) Todo .mbconjunlo }' de um cor1junto finito X é finito e 11() ·) ~ 11(.Y). Tem-sf' n(Y) = n(X)
somente quando Y = X.

A primeira propriedade ju!:,Lifica poclerlllos falar em número ele elt'mentos dP 1m1 ronj11nto
finito: podemos contá-lo ele vários modos. ruas o resultado final é sempre o mesmo. A ~egun<la
relaciona inclusão entre conj unLm, e desigrntlda<les rntre números çanlinais. A dPrnonstração dr
ambas sr faz por indução.
Um conjunto é inJiuito quando não é fi1úto. Por exemplo. N é infinito: dada qualquer fuução
f: Iri -t N. não importa qual n se fixou. µurnus k = /(1) + /(2) + · · · + .f(n) e vemos que, parn
todo J: E ! 11 , lem-se f(.r) < k. logo não exi~le .r E J,1 [Link] qu<' .f(J') = k. Assim . .( não podt" !ler
uma correspondência hiunívora .
A princípio. pode parecer qU<.' a clasBificação ele <'onjuutos C'orno fuutm, 011 infiuilos termina a
clisrnssão. t<.1as, no final do século XL'\.. Gcorg Caulur (1 -15-191 ) lllustrou colllo romparar a car-
dinalidade ele conjunLos infiuilos: um conjunLo pode ser 11 ma is [Link] o"<lo que ouLro. Novrunente.
a ferramenta fundamental é a de correspondência biuuívoca.

10
 1
(' \l'Í ri 1.< > 1

DEFINIÇÃO 1.12.
Dizemos que dois conjuuto::i X e Y t êm a mesma cardinalidade quando é possíYel cst ahcleC'er
uma correpondência biUllÍvoca entre X e Y (isto é. exisl,<' nma função bijeliva, f : X-,. Y).

É clfü·o que a definição acima foz sentido p,m:l conjuntos finitos: conjuntos finitos de mesma
cardinalidade são aqnele::i que lêm o mesmo número de elernenl.o~. ou seja. podem "ier postos
rm correi;:;ponclência bi múvoca com o mC'smo 1,, = { l. 2 .... , n}. Ivia:, ola Lêllllbém se aplica a
coujwllu::. [Link]::..

r,d ;3.
:,.1Pr o
Os coujuutos N dos números naturah, e P = {2n ln E N} dos níuneros pare5 têm a mesma
cardinalidade. Neste caso. a bijeção já estã clacla ua definiç~o rle P: a fuução f : N ---+ P dofinida
por f(n) = 2n é mnr1 bijeção de Nem P.

O que pode s0r surpreendeute neste exemplo é a [Link]ção de que. para conjuntos infinitos.
é perfeitarueute possívd qu<' dois coujunLos leuha.111 a mesma cmdinalidadc. embora um deles
(P neste cr1.,qo) seja um subconjunto próprio de ont-ro (N) (para conjuntos fuútos. isto uão pode
ucurrer. pela segunda propriedade acima).
A principal coulribuição de Cantor foi exibir casos em que não é possível obter uma bijc,ão
entre dois conjuntos infinitos.

EXDlPLO J
Considere o conjunlo C <le lodru, t)equênrias infinitas em que LO<los os lermos são iguais n
fil>

O ou 1. Um exemplo <le elemento de C (, a S<.'quência (O, 1, O. l. ... ). que alterna Lermos O e l. A

[Link] de C é pelo menos a mesma cie N. já q11e é possível esl abclecer uma correspondénria
binnívorR entre N e o [Link] D de C formado pelas Sf:'quências que possuem exatamente
mn termo igual a l (podemos as::iociar o uai w-al 11 à sequência em que o 1 aparece na n-ésima
posição). Isso não impe<le, em princípio. qm' possa lrnvcr urml bijeção entre N e C'. Canlor. no
entanto, mostrou que não há tal bijeção. fazendo com qne C seja "mab iufu1iL0 11 clo que N.
Seu Rrgmneuto foi o seguinte. Suponhamos qur fosse possível construir tun8 [unção .f : N -t C.
cm que cada sequência. ele C aparecesse exatamente unrn \·ez como imagem. Vamos consl ruir mna
sequência s formada por Os e ls (ou seja: um Plrrncmo de C) do sc~guinte modo: se o primeiro
termo da sequência, f (l ) for O. o primeiro Lermo de s é- O: se11ão, é 1. Se o segundo termo da
8l'C}U011cia f (2) for O. o segundo termo de s é O: senão. é 1. Pro~seguimos. sempre escolhendo o
n ésimo termo como sendo o oposto do n ésimo t<'rmo chi sequência f (n). A sequência s assim
construída difere pelo menos ua posição n de cada sequência f(n). Logo. não pertence ã imagem
de f. }Ias nossa supo~ição era ele que todos os elementos de C aparecessem como imagem!

11
 ('.\ l 'ÍT l1 LO 1 N(:\IEROS ): .\1TH .\ 1S

T<'mos. assim. urna romrndição. que 1110::.l ra a [Link] de construir mua bijeção ele _V em
e.
O c·onj11nto C é um exemplo dr c-011junLo infi11i1 0 nii.o e·11·11111<~rá1 1d. í.,w é. qm' uão po<le ser
posto nm con-cspondência biunívoca com o conj1mto drn, ní1mcro:.; natmab. Outro::. exemplos
cl<' c-ouj11ntos uão <:num0ráY0is são os co11j1111t os dos númerns reais e dos uúnwros irracionais. O
conjnnto dos números nlciomús. porc>ru. é cnnmcrávcl (veja o exerddo 1.13).

OBSERVAÇÃO 1.13.
'Cma função de domínio igual a N é chamada de uma ,)equencia. É com·euienle peusar em
uma sequência a : N ~ X como uma lista de valores (a(l ). a(2). a(3) .... ), que muitas vezes
preferimos representar por (a ,.a2.a3 ... . ).
Conjuntos infinitos e conjuntos enumeráveis podem ser caracterizados em termos das propri-
edades das sequências de elemenlos destes conjunlos. como ::;e segue:

• Um coujunlo X é infinito se, e somente se. é possível coustruir uma sequência (a1 . a2 . n3... .)
Clll que os lermos são cleweulos distintos de X (ou seja, quando há Wlia função injetiva

de Nem X).

• Um conjunto infiniLo X é enumerável se. e somente ::;e. ê pm,bíve1 construir uma ::;equên-
cia (a 1, a 2 , a3 •.. . ) incluindo todos os elementos de X (ou seja. quando há m11a função
sobrejetiva de N em X).

12
 EXEIH'Í< 'IOS C.\PÍTl ' LO l

Exercícios
1.6. ProvC', por indução. que se X é Ulll conjumo fuúto com n elE'men1 os, f'Sse elerueulos podem
ser ordeuados de 11 ! modo:,.

1. 7. Prove. por indução. que um c:onjtmlo com n elementos possui 211. subconjuntos.

1.8. D.-1dos 3n objetos de peso::, iguais. exceto nm. mais pesado que o~ demais. 1110stre que é
possível [Link]' este objcro com n pesagens em uma balança de pralos . ..\lostre também
que este é o 11funero mínimo de pesagC'ns q11C' permitem. com certeza, determinar o objeto
ruais pesado.

1.9. Prove que, dado um couju11lo com n elewentos, é possível fa:[Link] uma fila com sem, l>ULco11-
jiU1tos de tal modo que cada subc:onjm1t o da fila pode ser obtido a partir do aulerior µelo
acrésC'i:rno ou pela supressão de Wll único elemento. !Sugestão: para passar de II para n + 1.
liste primeiro os subconjuulm, que não t.êrn um dado clomcnto.]

1.10. Diga onde está o erro na ::.eguinle demom,lnic;ão ela afirmativa "Todas as bolas dC' bili1ar
têm a mc."8ma cor".
St>ja P(n) a propriedade "todas as bolas cm um conjur,to com n bolas têm o nie.<ima cor".
A propriedade é. t.r11,ialme11te verdadeira para n = l. Suponhamos agora que <la seja U(:;r-
dadcira para n e consideremos ·1m1 conJtmlu com n + l bolo.~ B = {b1 . b2 , •..• bn, bn+d· Os
. 11bcon.1unlos {b1. b2, . ... bn,} e {b2 ....• bn. b1,+1} de B lfm n elementos carlo: logo, pela
hipó[Link] de indução, todas as bolas em c,1da um. deles têm o mesma cor. Mas os elemen-
tos b2 .. ... Úk são comuns a esses dois s11,bconJ11ntos. Daí, concluímos que todos os n ...1.. 1
elementos de B têm a mesma cor, o que mostra qu<' a propí!C'dadc vale para 11, 1. Logo.
pelo Prmcípio da Indução. em. uma coleção com n bolas todas têm a mesmo cor, para todo
n EN.

1.11. Diga se cada conjunto abaixo é Iinllo ou iufuúto, justificando:

• o coujunto de todas as pessoas que já \·iveram na Terra.

• o conjunto de todos os múltiplos de 7 cnja repre::,enlação decimal tc,rmina com 357
• o conjunto de todos os números naturais cuja representação decimaJ tenha apenas
algarismos diferentes d e zero, cuja soma seja ineuor que 1000.
• o coojw1to de todos os números racionais que podem s<>r escritos como fração com
denominador meuor que 1000.
• o coujunlo de todos os nÍlmeros primos.

13
 C-\I'ít1 · 1.1> 1 :\(.\IEIH>S :\XI l H .\IS

1.12. Sejam X e 1 · doü, conjuntos [Link] euumC'f{l\·eis. Isto '-ignilica que t•xistnn scqni>ncia~
(.r 1..r 2 .r:•.... ) <' (y 1 .Jh·Y:i···-) iuduindo tudo:-. O:, <'lc'mc1llo::, de Se}. rP::.pectiwml<'ntC'.
Explique' c:omo construir 11111a sequênda iud11i11clo ro<los os elemt•utos de X U} ·. mostrnndo
nssim que X } · 1nmhérn é· <'Durucrá\'el.

1.13. CousidPrP o rn11j1111ro N'.! de> rodos os par<'s onlC'nados d<' nalunrn,. Enrontn• mna
nítlllPru::,
sequencia qm• i11< lua todos o::, elcmeutos de N • mostnmclo assiw que P-1 2 é c•numr.ní.vC'l. fato
2

wo::,t1a que o c-onjnmo elos números raciouais também t,, <'nunwrúvel Po1 quê'?

1.14. l\lostrc• que o <'Onjunto de wdos os :-.11bconJ1111los de N é' não enumerável. !Sugestão: associe
cada subconjunto rle S e\ uma ::.equúucia en1 que os tC'l111os ::,ão i~uais a O 011 LI

1..1