Baixe o app para aproveitar ainda mais
Prévia do material em texto
� INTRODUC� � AO POR QUE ESTUDAR OS INTEIROS� Para a maioria das pessoas� �n�umero� quer dizer n�umero inteiro positivo� Os inteiros rela� tivos� os racionais� os reais e os complexos foram concebidos� aos poucos� �a medida que as necessidades pr�aticas ou te�oricas o exigiam� Ainda hoje� os algoritmos usados para somar� multiplicar e dividir n�umeros racionais est�ao baseados nos algoritmos correspondentes para a soma� multiplica c�ao e divis�ao de inteiros� Assim� as necessidades do dia�a�dia exigem o dom� nio das regras operacionais dos inteiros� Por isso� todo professor deve compreend�e�las� a �m de poder ensin�a�las� Do ponto de vista hist�orico� �e interessante observar que os racionais antecedem de muito a aceita c�ao dos inteiros relativos� Os eg� pcios e os babil�onios trabalhavam livremente com fra c�oes os primeiros de maneira pesada e inconveniente� pois s�o admitiam fra c�oes do tipo � n �aceitavam tamb�em a fra c�ao ����� Os segundos� gra cas a sua nota c�ao posicional� com base ��� usavam livremente as fra c�oes sexagesimais� an�alogas �as nossas fra c�oes deci� mais estas fra c�oes sexagesimais foram utilizadas tamb�em pelos cientistas e matem�aticos gregos sempre que necessitavam efetuar c�alculos com n�umeros racionais� J�a na Matem�atica pura� os gregos s�o reconheciam a exist�encia de inteiros positivos� substituindo as fra c�oes por raz�oes entre inteiros� A hist�oria fascinante dos v�arios sistemas num�ericos pode ser lida no livro de George Ifrah� �N�umeros� a Hist�oria de uma Grande Inven c�ao�� Em particular� a aceita c�ao dos n�umeros negativos e complexos �e interessante� pois mostra como id�eias matem�aticas im� portantes por vezes demoram at�e serem totalmente aceitas� Os matem�aticos� na tarefa de tornarem rigorosa a Matem�atica� a partir do s�eculo XIX� mostraram como os n�umeros relativos� racionais� reais e complexos podem todos ser cons� tru� dos a partir dos n�umeros naturais� Nas palavras do matem�atico alem�ao Leopold Kro� necker ������ ������ �Deus fez os n�umeros naturais� Todo o resto �e trabalho do homem�� Nesta generaliza c�ao progressiva do conceito de n�umero� a qual n�ao seguiu a ordem hist�orica da utiliza c�ao deles� a passagem realmente dif� cil �e a de n�umero racional para n�umero real� � Isso pode ser feito pelo m�etodo dos cortes de Dedekind � ou usando as chamadas sucess�oes de Cauchy � de n�umeros racionais� como fez Peano � � Outra raz�ao para estudarmos os inteiros �e que eles s�ao o prot�otipo de uma estrutura alg�ebrica muito importante� a de anel comutativo com identidade �mais precisamente� de dom� nio de integridade�� As generaliza c�oes sucessivas do conceito de n�umero �racionais� reais e complexos� sempre preservaram esta estrutura� A cren ca de que ela deveria ser sempre mantida para qualquer tipo de �n�umero� criado pelos matem�aticos s�o foi rompida com o descobrimento dos quaternions pelo irland�es William Rowan Hamilton ������ ������ a partir de quem a � Algebra passou a ser encarada como o estudo das estruturas alg�ebricas� Ainda outra raz�ao para o estudo dos inteiros �e simplesmente est�etica� O estudo das propriedadas dos n�umeros primos tem se revelado fonte de belos e profundos resultados� cujo estudo algumas vezes muito contribuiu para o desenvolvimento da Matem�atica� Al�em disso� o estudo dos inteiros �e uma �otima maneira de exercitar o h�abito de fazer conjecturas e demonstra c�oes� A possibilidade de �experimenta c�ao� com os inteiros �e muito grande� pelo menos t�ao grande� se n�ao maior� do que com geometria� Recentemente� tem� se dado muita �enfase �a necessidade de um ensino mais criativo em Matem�atica� que fuja ao modelo �de�ni c�ao� teorema� corol�arios�� o qual �e um dos respons�aveis pela falta de interesse dos alunos pela Matem�atica� Neste sentido� os inteiros s�ao um �otimo campo para experi�encias e explora c�ao� a �m de desenvolver a criatividade dos alunos� � Julius W� Richard Dedekind ������ ���� � matem atico alem�ao� � Augustin�Louis Cauchy �� ��� ��� � matem atico franc�es� desenvolveu o rigor na An alise Matem atica e no c alculo das s eries� Tratou tamb em das fun�c�oes de uma vari avel complexa e criou a teoria dos grupos �nitos� Tamb em enunciou teoremas fundamentais sobre os determinantes e sobre equa�c�oes diferenciais� � Giuseppe Peano ������ ���� � matem atico italiano� professor da Universidade de Turim� fez trabalhos sobre a An alise Matem atica e sobre os fundamentos da Matem atica� Descobriu uma curva que passa por todos os pontos de um quadrado e axiomatizou os n umeros naturais� Criou tamb em uma l �ngua universal� � CAP � ITULO � O Princ��pio da Indu�c�ao Finita Antes de abordarmos o estudo dos n�umeros naturais� estudaremos o princ��pio da indu�c�ao matem�atica� oum�etodo da indu�c�ao �nita � � Ele �e uma t�ecnica poderosa para demons� trar a�rma c�oes relativas aos n�umeros naturais� � E particularmente �util quando suspeitamos que uma a�rma c�ao relativa aos n�umeros naturais �e verdadeira e desejamos demonstr�a�la� Daremos� neste cap� tulo� o enunciado do princ� pio da indu c�ao� ilustraremos seu uso com alguns exemplos e proporemos exerc� cios para serem resolvidos empregando�o� No cap� tulo seguinte� mostraremos como esse princ� pio se insere na fundamenta c�ao da Arit� m�etica e como as propriedades b�asicas das opera c�oes com n�umeros naturais dependem dele� Seja P�n� uma proposi c�ao relativa ao n�umero natural n por exemplo� P�n� pode ser uma das a�rma c�oes� a� P�n�� � � Um conjunto A com n elementos tem exatamente � n subconjuntos distintos�� b� P�n�� � n � � � n � � � n � � � n �� �e um inteiro�� c� P�n�� ��a� b� n � P n i�� � n i � a n�i b i �� d� P�n�� �O inteiro n� maior do que �� pode ser escrito como um produto de n�umeros primos�� � A palavra �indu�c�ao�� em Matem atica� tem signi�cado diferente do que possui nas ci�encias experimentais� Nestas� baseando�se em casos conhecidos� o cientista �induz� resultados gerais� isto e� passa do particular ao geral� Em Matem atica� �indu�c�ao� e uma t ecnica que permite demonstrar resultados gerais� � e� P�n�� �A soma dos �angulos internos de um pol� gono convexo de n lados �e igual a ��n� �� retos�� � E f�acil dar muitos outros exemplos de a�rma c�oes verdadeiras relativas a n�umeros naturais� Em muitos casos� o princ� pio da indu c�ao �nita� tamb�em chamado de princ� pio da indu c�ao matem�atica� permite demonstr�a�las� Seu enunciado �e o seguinte� Princ��pio da indu�c�ao �nita� Dado o n�umero inteiro positivo a� seja P�n� uma asser c�ao relativa aos inteiros n � a� a� �� a� �� � � � Se a� P�a� �e verdadeira e b� Supondo P�k� verdadeira pudermos demonstrar que P�k� �� �e verdadeira ent�ao� P�n� ser�a verdadeira para todo n � a� a� �� a� � � � � As demonstra c�oes por indu c�ao �nita ocorrem em todos os n� veis da Matem�atica� do mais elementar aos mais avan cados� Variam de extremamente simples a muito dif� ceis� Aqui� obviamente� trataremos de problemas de Matem�atica elementar� a n� vel do segundo grau� Exemplo ���� Demonstre� por indu�c�ao em n� que a desigualdade de Bernoulli � � �� � x� n � � � nx vale para todo n � �� �� � � �� desde que se tenha � � x � �� �Aqui� x �e um n�umero real qualquer� inteiro ou n�ao�� Com efeito� se n � �� temos que � � x � �� x� portanto a desigualdade �e v�alida para n � �� Suponha agora que a desigualdade seja v�alida para um certo n�umero natural n� Temos ent�ao ���x� n � ��nx� Multiplicando ambos os membros desta desigualdade pelo n�umero � � x �oqual �e positivo� por hip�otese� vem �� � x� n �� � x� � �� � nx��� � x�� � Jacques Bernoulli ������� �� � matem atico sui�co� � Lembrando que �� � x� n �� � x� � �� � x� n�� e desenvolvendo o produto �� � nx��� � x�� obtemos �� � x� n�� � � � �n� ��x� nx � � Como nx � n�ao pode ser negativo� conclu� mos que �� � x� n�� � � � �n� ��x� Exemplo ���� Mostre que� para n � �� �� � � �� vale � � � � � � � � �� n � n�n� �� � � Seja P�n� a asser c�ao �a soma dos naturais � � � � � � �� n �e igual a n�n�� � �� Temos� �� P��� �e v�alida� pois a soma dos naturais de � at�e � vale � e �e claro que � � ������ � � �� Suponha agora que P�k� seja v�alida� isto �e� que a soma dos naturais de � a k seja igual a k�k�� � � Ent�ao a soma dos naturais de � a k� � �e � � � � � � �� �k� �� � �� � � � � � �� k� � �k� �� � � k�k� �� � � �k� ��� pois estamos aceitando a hip�otese de indu c�ao� ou seja� que � � � � � � �� k � k�k� �� � � Mas� k�k� �� � � �k� �� � �k� ���k� �� � � Logo a validez de P�k� implica a de P�k� ��� o que conclui a demonstra c�ao� Exemplo ���� Um conjunto A com n elementos possui � n subconjuntos distintos� � Para provar esta a�rma c�ao� de�namos P�n�� � � Um conjunto A com n elementos tem exatamente � n subconjuntos distintos�� �Aqui� n �e um inteiro n�ao�negativo�� a� Se n � �� ent�ao A � �� e o conjunto das partes de A �e P�A� � f�g� donde o n�umero de elementos de P�A� �e �� ou seja� � � � b� Suponha agora verdadeiro que qualquer conjunto com k elementos tem � k sub� conjuntos distintos� A partir disso� demonstraremos que qualquer conjunto com k � � elementos tem � k�� subconjuntos distintos� Com efeito� seja A � fa � � a � � � � � � a k � a k�� g um conjunto com �k � �� elementos� Os subconjuntos de A dividem�se em dois tipos� os que cont�em a k�� e os que n�ao cont�em a k�� � Contaremos� �� O n�umero de subconjuntos de A que n�ao cont�em a k�� � �� O n�umero de subconjuntos de A que cont�em a k�� � �� Seja B � fa � � a � � � � � � a k g� O n�umero de subconjuntos de A que n�ao cont�em a k�� �e obviamente igual ao n�umero de subconjuntos de B� Ora� como B tem k elementos e estamos aceitando a hip�otese de indu c�ao para conjuntos com k elementos� o n�umero de subconjuntos de B �e � k � �� Um subconjunto de A que cont�em a k�� �e da forma X � fa k�� g� onde X �e um subconjunto de B� Ent�ao� o n�umero dos subconjuntos de A que cont�em a k�� �e igual ao n�umero dos subconjuntos de B� Como B tem k elementos� vemos que o n�umero de subconjuntos de A que cont�em a k�� �e � k � Assim� o n�umero total de subconjuntos de A ser�a � k �� k � � k ����� � � k � � � � k�� � Portanto� admitindo a validez de P�k�� demonstramos que vale P�k� ��� isto �e� que o n�umero de subconjuntos de um conjunto com k � � elementos �e � k�� � Isto conclui a demonstra c�ao por indu c�ao� Exemplo ���� Demonstre que � n � n�� para n � �� Vamos usar o princ� pio da indu c�ao com a � �� Com efeito� se n � �� ent�ao � � � �� � �� � ��� Suponha agora que� para um inteiro n � �� se tenha � n � n� Mostremos que da� decorre que � n�� � �n � ��� Ora� como � � n � �� �lembre�se que n � �� segue�se� � multiplicando membro a membro esta desigualdade pela desigualdade � n � n�� que ��� n � �n� ��n�� ou seja� � n�� � �n� ���� o que conclui a demonstra c�ao� O princ� pio da indu c�ao �nita �e particularmente �util quando� baseando�nos em ex� peri�encias� acreditamos que um resultado �e verdadeiro e desejamos prov�a�lo� Exemplo ���� Ache uma f�ormula para a soma � � � � � � � � � � � �� ��n� �� � � Como a soma dos n primeiros n�umeros naturais �e dada por um polin�omio do segundo grau em n� tentaremos ver se a soma dos quadrados dos n primeiros n�umeros � mpares �e dada por um polin�omio do grau �� Por enquanto� isso n�ao passa de uma experi�encia que estamos fazendo� Suponhamos portanto que� exitem constantes A�B�C e D tais que a igualdade � � � � � � � � � � � �� ��n� �� � � An � � Bn � � Cn�D valha para todo n�umero natural n e tentemos determinar os coe�cientes A� B� C e D� Ent�ao� para n � �� temos � � A� B� C�D para n � �� temos �� � �A� �B� �C�D para n � �� temos �� � ��A� �B� �C�D para n � �� temos �� � ��A� ��B� �C�D� Obtemos assim o sistema linear A� B� C�D � � �A� �B� �C�D � �� ��A� �B� �C�D � �� ��A� ��B� �C�D � ��� � cujas inc�ognitas s�ao A�B�C e D� Vemos facilmente que as solu c�oes deste sistema s�ao A � � � � B � �� C � � � � � D � �� Isto nos leva a conjeturar que� para todo n�umero natural n� vale � � � � � � � � �� ��n� �� � � � � n � � � � n � � � n��n� ����n� ��� � E importante perceber que n�ao �zemos uma demonstra c�ao de que a f�ormula acima �e v�alida para todo n� Com efeito� o que provamos foi que a express�ao da direita coincide com a da esquerda para n � �� �� � e �� Tentaremos mostrar que isso �e verdade para n qualquer� Para faz�e�lo� usaremos indu c�ao �nita� Como j�a vimos que P��� �e v�alida� come camos a indu c�ao supondo que a f�ormula seja verdadeira para um inteiro positivo k� � � � � � � � � �� ��k� �� � � � � � k � ��k� �� � ��k� ��� Desejamos ent�ao mostrar que � � � � � � � � �� ���k� ��� �� � � � � � �k� �� � ���k� ��� �� � ���k� �� � ��� ou seja� que � � � � � � � � �� ��k� �� � � � � � �k� �� � ��k� �� � ��k� ��� Mas � � � � � � � � �� ��k� �� � � �� � � � � � � � �� ��k� �� � � � ��k� �� � � � � � � k � ��k� �� � ��k� �� � ��k� �� � � pois estamos supondo que � � � � � � � � �� ��k� �� � � � � � k � ��k� �� � ��k� ��� � Temos ent�ao � � � k � ��k� �� � ��k� �� � ��k� �� � � � ��k� ��� � � k��k� �� � �k� �� � � ��k� �� � ��k � � �k� �� � ��k� �� � ��k� ���k� ��� como quer� amos demonstrar� Podemos ent�ao a�rmar que � � � � � � � � �� ��n� �� � � � � n � � � � n � � � n��n� ����n� �� vale para qualquer n inteiro positivo� O perigo de fazer generaliza c�oes apressadas relativamente a asser c�oes sobre inteiros �ca evidenciado com o seguinte exemplo� Exemplo ���� Considere o polin�omio p�n� � n � � n� �� e a a�rma�c�ao �o valor de p�n� �e sempre um primo para n � �� �� �� �� � � ��� Embora isso seja verdadeiro para n � �� �� �� � � � � ��� p���� � �� � � ����� � �� � n�ao �e primo� logo a a�rma c�ao n�ao �e verdadeira� Semelhantemente� a express�ao q�n� � n � � ��n � ���� fornece primos para n � �� �� � � � � ��� mas q���� � �� � � �� � �� � ���� � ���� n�ao �e primo� pois �e divis� vel por ��� A moral da hist�oria �e� S�o aceite que uma a�rma c�ao sobre os inteiros �e realmente verdadeira para todos os inteiros se isso houver de fato sido demonstrado� O m�etodo da indu c�ao matem�atica como t�ecnica de demonstra c�ao foi usado explici� tamente pela primeira vez pelo italiano Francesco Maurolycus ������ ������ Pascal � o empregou para deduzir rela c�oes sobre os coe�cientes binomiais no Tri�angulo de Pascal� Na pr�atica� usamos frequentemente o princ� pio da indu c�ao �nita quando dizemos ���� e assim sucessivamente�� Ao fazermos isso� estamos reconhecendo�geralmente mental� mente ou ap�os alguns c�alculos� que o fen�omeno estudado �e bem regular� que a validade do � Blaise Pascal ������ ���� � matem atico� m �stico e �l osofo franc�es� Aos � anos escreveu um trabalho de Geometria Projetiva� o �Ensaio sobre as C�onicas�� Pascal constru �u uma m aquina de calcular� fez a famosa experi�encia sobre o v acuo� em Paris� e desenvolveu o C alculo das Probabilidades� explorando as propriedades do �Tri�angulo de Pascal�� Usando os �indivis �veis� demonstrou v arios resultados de c alculo integral� Abandonou a Matem atica� dedicando�se �a Filoso�a e �a defesa do Cristianismo� �� resultado enunciado independe dos valores particulares de n dados como exemplo� Isso �e exatamente o princ� pio da indu c�ao �nita� Observa�c�oes �� Para habituar�se com o m�etodo de demonstra c�ao por indu c�ao �e preciso pratic�a�lo muitas vezes� a �m de perder aquela vaga sensa c�ao de desonestidade que o principiante tem quando admite que o fato a ser provado �e verdadeiro para n� antes de demonstr�a�lo para n� �� �� O m�etodo de indu c�ao �e tamb�em usado para de�nir indutivamente ou por recorr�encia fun c�oes de INI em um conjunto Y� Isso ser�a visto no pr�oximo cap� tulo� �� Pratique tamb�em �com modera c�ao� o exerc� cio de descobrir o erro em paradoxos que resultam do uso inadequado do m�etodo de indu c�ao� Vejamos tr�es desses so�smas� Exemplo ���� Seja P�n� a a�rma�c�ao� Se um conjunto de n bolas cont�em uma bola preta� ent�ao todas as bolas do conjunto s�ao pretas� Demonstraremos a verdade desta a�rma c�ao� usando o princ� pio da indu c�ao �nita� Como no mundo certamente existe uma bola preta� teremos ent�ao demonstrado que todas as bolas do mundo s�ao pretas� �� P��� certamente �e verdadeira� pois se um conjunto de uma bola cont�em uma bola preta� todas as bolas do conjunto s�ao pretas� �� Aceitemos agora que P�k� seja verdadeira para um n�umero natural k arbitr�ario� e mostremos que P�k� �� �e verdadeira� Seja um conjunto fb � � b � � � � � � b k�� g de k � � bolas� que cont�em alguma bola preta� Sem perda de generalidade� podemos supor que ela seja b � � Considere agora o conjunto fb � � b � � � � � � b k g� Ele cont�em k bolas e uma delas �b � � �e preta� Ent�ao� pela hip�otese de indu c�ao� todas as bolas do conjunto s�ao pretas� ou seja� as bolas b � � b � � � � � � b k s�ao todas pretas em particular� b � �e preta� Consideremos agora o conjunto fb � � � � � � b k�� g� que cont�em k elementos� J�a demons� tramos que b � �e preta� logo este conjunto cont�em uma bola preta� Ent�ao� pela hip�otese de indu c�ao� todas suas bolas s�ao pretas� Isto �e� b � � � � � � b k�� s�ao pretas� Mas ent�ao todas as bolas b � � b � � � � � � b k�� s�ao pretas� �� Mostramos assim que todas as bolas do mundo s�ao pretas� Mas isso �e obviamente falso� Onde est�a nosso erro Ele n�ao �e devido a termos suposto que a bola preta era b � � Isso n�ao traz nenhum problema� O exemplo seguinte �e uma reformula c�ao abstrata do anterior� Exemplo ���� Toda fun�c�ao f � X� Y� cujo dom� nio �e um conjunto �nito� X �e constante� Demonstrao� Isto �e obviamente verdadeiro se X tem apenas � elemento� Supondo a a�rma c�ao verdadeira para todos os conjuntos com n elementos� seja f � X � Y de�nida num conjunto X com n�� elementos� Considere um elemento a � X� Como X � � X�fag tem n elementos� f assume o mesmo valor c � Y em todos os elementos de X � � Agora troque a por um outro elemento b � X � � Obt�em�se X �� � X� fbg um conjunto com n elementos �entre os quais a�� Novamente pela hip�otese de indu c�ao� f �e constante e igual a c em X �� � Logo f�a� � c e da� f � X � Y �e constante� �Aqui o erro reside no uso inadequado da hip�otese de indu c�ao� O racioc� nio empregado sup�oe implicitamente que X tem pelo menos � elementos� Na realidade� n�ao vale a implica c�ao P���� P����� Vejamos outro exemplo de �demonstra c�ao� falsa usando o princ� pio da indu c�ao �nita� Exemplo ���� Dois inteiros positivos quaisquer s�ao iguais� Com efeito� seja P�n� a proposi c�ao �se a e b s�ao inteiros positivos tais quemax �a� b� � n� ent�ao a � b �� Obviamente P��� �e correta� pois se max �a� b� � �� ent�ao a � b � �� Suponha agora que P�r� seja verdadeira e sejam a e b inteiros quaisquer tais que max �a� b� � r� �� Considere ent�ao os inteiros � � a � � e � � b � �� Ent�ao� max��� �� � r� donde � � �� logo a � b� e P�r� �� �e verdadeira� o que conclui a demonstra c�ao por indu c�ao� Em geral� pseudo�demonstra c�oes usando o princ� pio da indu c�ao �nita� como os tr�es exemplos acima� t�em seus problemas nos casos em que n �e pequeno� normalmente na pas� sagem de n � � para n � �� ou de n � � para n � �� Voc�e conhece outras �demonstra c�oes� falsas por indu c�ao Em algumas situa cSes �como a do Teorema ��� que veremos a seguir�� ao tentarmos provar um fato por meio do princ� pio da indu c�ao� sentimos que� usando apenas a validez �� de P�k�� n�ao parece poss� vel provar a de P�k���� Em vez disso� para estabelecer P�k��� precisamos supor P���� P���� � � �� P�k� simultaneamente� Isto nos conduz ao segundo princ��pio da indu�c�ao� que apresentaremos e usaremos agora� e cuja justi�cativa ser�a dada no cap� tulo seguinte� Segundo princ��pio da indu�c�ao� Dado um inteiro a� seja P�n� uma a�rma c�ao relativa aos inteiros n� n � a� a� �� a� �� � � � Se �� P�a� �e verdadeira e �� Para cada inteiro k � a� a validade de P�a�� P�a� ��� � � � � P�k� acarreta a validade de P�k� ��� ent�ao� P�n� �e v�alida para todos os inteiros n � a� Usaremos o segundo princ� pio da indu c�ao para demonstrar o seguinte resultado fun� damental da Aritm�etica dos inteiros� o qual ser�a muito usado no restante deste texto� Teorema ���� Qualquer inteiro n maior do que � pode ser escrito como um produto de primos� Demonstra c�ao� Considere a a�rma c�ao �o inteiro n ou �e primo ou pode ser escrito como um produto de primos�� para n � �� �� �� � � � Usaremos a segunda forma do princ� pio da indu c�ao� tomando a � �� �� O n�umero � �e primo� logo vale P���� ��Seja k um inteiro� k � �� Suponha que a a�rma c�ao seja v�alida para todos os inteiros maiores que ou iguais a � e menores que ou iguais a k� Mostraremos que ela �e v�alida para o inteiro k� �� Se o inteiro k�� �e primo� nada h�a a demonstrar� Suponha portanto que k�� � a �b� onde a e b s�ao inteiros maiores do que �� Ent�ao obviamente a � k� � e b � k� �� Logo� pela hip�otese de indu c�ao� a se escreve como um produto de primos a � p � � p � � � � � � p s � �� Analogamente� pela hip�otese de indu c�ao� b se escreve como um produto de primos b � q � � q � � � �q t � Ent�ao� a � b � p � � p � � � �p s � q � � q � � � �q t � um produto de primos� como quer� amos demonstrar� Apresentamos mais um exemplo de utiliza c�ao desta forma do princ� pio da indu c�ao� Sabe�se que� tra cando diagonais internas que n�ao se cortam� pode�se decompor qualquer pol� gono em tri�angulos justapostos� Isto �e evidente quando o pol� gono �e convexo� basta �xar um v�ertice e tra car as diagonais a partir dele� Se o pol� gono n�ao �e convexo� a prova requer mais cuidados � O leitor pode experimentar com um pol� gono n�ao�convexo e veri�car que h�a muitas maneiras diferentes de decomp�o�lo em tri�angulos justapostos mediante diagonais internas� Mas vale o resultado seguinte� no qual usaremos o segundo princ� pio da indu c�ao � � Exemplo ����� Qualquer que seja a maneira de decompor um pol� gono P� de n lados� emtri�angulos justapostos por meio de diagonais internas que n�ao se intersectam� o n�umero de diagonais utilizadas �e sempre n� �� Demonstrao� Com efeito� dado n� suponhamos que a proposi c�ao acima seja verdadeira para todo pol� gono com menos de n lados� Seja ent�ao dada uma decomposi c�ao do pol� gono P� de n lados� em tri�angulos justapostos� mediante diagonais internas� Fixemos uma dessas diagonais� Ela decomp�oe P como reuni�ao de dois pol� gonos justapostos P � � de n � lados� e P � � de n � lados� onde n � � n e n � � n� logo a proposi c�ao vale para os pol� gonos P � e P � � Evidentemente� n � � n � � n� �� Vide LIMA� Elon Lages� �Meu Professor de Matem atica e Outras Hist orias�� IMPA�VITAE� Rio de Janeiro� pag� ���� � Para uma demonstra�c�ao do mesmo fato usando boa�ordena�c�ao� veja �Revista do Professor de Matem atica�� vol� ��� pag� ��� �� ENTRA A FIGURA V As d diagonais que efetuam a decomposi c�ao de P se agrupam assim� n � � � delas decomp�oem P � � n � � � decomp�oem P � e uma foi usada para separar P � de P � � Portanto d � n � � � � n � � � � � � n � � n � � �� Como n � � n � � n� �� resulta que d � n� �� Isto completa a demonstra c�ao� Voc�e certamente ter�a notado algo estranho em nossa apresenta c�ao do princ� pio da in� du c�ao �nita� N�os o enunciamos e o empregamos mas nada foi dito sobre como chegamos a ele� � E um teorema Se isso acontece� qual sua demonstra c�ao � E simplesmente uma regra emp� rica que a experi�encia mostrou funcionar En�m� o que �e o princ� pio da indu c�ao �nita A resposta depende de como voc�e encara os n�umeros naturais� � E poss� vel construir os n�umeros naturais a partir da teoria dos conjuntos� como fez Richard Dedekind� que de�niu conjunto �nito como aquele que n�ao admite bije c�ao sobre uma parte pr�opria e n�umero natural como o n�umero cardinal de um conjunto �nito� Outro ponto de vista� de maior simplicidade conceitual �e por isso quase universalmente adotado hoje em dia� �e o de Giuseppe Peano� onde o princ� pio da indu c�ao aparece como um axioma� isto �e� como uma das propriedades de�nidoras dos n�umeros naturais� Este �e o ponto de vista que adotaremos no cap� tulo seguinte� �� EXERC � ICIOS ���� Prove� por indu c�ao� que � � � � � � � � �� n � � n�n�� ��n�� � � ���� Num pol� gono com n � � lados� o n�umero de diagonais �e maior do que n� ���� Prove� por indu c�ao� que ��n � ���n� n � n� para todo n � �� �Sugest�ao� Observe que �n�����n��� � �n� ���n e eleve ambos os membros desta desigualdade �a pot�encia n���� Conclua da� que a seq!u�encia �� p �� � p �� � p �� � p �� � � � �e decrescente a partir do terceiro termo� ���� Para todo n � INI� ponha x n � � �n�� � n�n�� � n e prove� por indu c�ao� que se tem x n � n�� n�� � Conclua� a partir da� � que a seq!u�encia de termo geral � n�� n � n �e crescente� �Sugest�ao� observe que x n�� � � n�� n�� � � � n n�� � x n e use a hip�otese de indu c�ao�� ���� Demonstre que a soma dos n primeiros n�umeros � mpares �e n � � ou seja� que � � � � � � � � �� ��n� �� � n � � ���� Determine A n se A � � � � � � � � ���� �A Torre de Han�oi� S�ao dados tr�es suportes A� B e C� No suporte A est�ao encaixados n discos� cujos di�ametros� de baixo para cima� est�ao em ordem estritamente decrescente� Mostre que �e poss� vel� com � n � � movimentos� transferir todos os discos para o suporte B� usando o suporte C como auxiliar� de modo que jamais� durante a opera c�ao� um disco maior �que sobre um disco menor� ENTRA A FIGURA A ���� Demonstre que �n � � �n � � �n� � para n � �� �� ���� Considere n retas em um plano� Mostre que o �mapa� determinado por elas pode ser colorido com apenas duas cores sem que duas regi�oes vizinhas tenham a mesma cor� ����� Mostre que� se n � �� ent�ao n n � n� ����� Ache uma express�ao para � � � � � � � � � � � �� n � � ����� Mostre que � �� ���� �� ���� �� ��� � � ��n�n����n��� � n�n����n����n������ ����� Mostre que � ��� � � ��� � � � �� � ��n�� ��n�� � n �n�� � ����� Ache uma express�ao para � � �� � � � �� � � � �� � � � �� n � n� ����� Demonstre que � n n�� � ��n � �n� � � para todo n�umero natural n � �� ����� S�ao dadas n retas �em posi c�ao geral� em um plano� isto �e� tais que n�ao h�a entre elas duas que sejam paralelas nem tr�es que possuam um ponto comum� Ache uma express�ao� em fun c�ao de n� para o n�umero de regi�oes que as n retas dadas determinam no plano� ����� Demonstre que se n �e � mpar� ent�ao x n � a n �e divis� vel por x� a� ����� �Pequeno Teorema de Fermat� Demonstre que se p �e um n�umero primo� ent�ao n p �n �e m�ultiplo de p� ����� Quantas s�ao as sequ�encias de n termos� todos pertencentes ao conjunto f�� �g e que n�ao possuem dois zeros consecutivos ����� Marcam�se n �n � �� pontos distintos sobre uma circunfer�encia� Demonstre que h�a �k������� n ��k� �� n modos de color� �los� usando k cores distintas� de modo que n�ao haja dois pontos consecutivos com a mesma cor� ����� Mostre que para cada n�umero natural p maior ou igual a �� existem naturais dis� tintos n � � n � � � � � � n p � tais que � n � � � n � � � � �� � n p � �� ����� Seja A uma matriz quadrada tal que A � � A� Mostre que A n � A� ����� Em um torneio disputado por n pessoas� cada uma delas joga com todas as outras� N�ao havendo empates� mostre que �e poss� vel rotular os jogadores como P � � P � � � � � � P n � de modo que P � venceu P � � P � venceu P � �� � �� P n�� venceu P n � �� ����� �A sequ�encia de Fibonacci � � Um casal de coelhos adultos gera um casal de �lhotes por m�es� o qual� por sua vez� se reproduzir�a� gerando tamb�em um casal de �lhotes por m�es� a partir de dois meses de idade� Tem�se� no m�es �� um casal de coelhos adultos� Supondo todos os coelhos imortais� determine a� quantos casais de coelhos nascer�ao no m�es �� b� quantos casais de coelhos nascer�ao no m�es n c� qual a quantidade total de casais de coelhos existentes no m�es n� ����� A sequ�encia de Fibonacci� F � � F � � � � � � F n � � � � �e de�nida por F � � F � � � e por F n�� � F n�� � F n � Mostre que� F n � ��� p � n ���� p � n � n p � � ����� Em um corredor h�a ���� arm�arios fechados� numerados sucessivamente de � a ����� Um gaiato percorre o corredor e reverte a posi c�ao das portas de todos os arm�arios� Em seguida� outro gaito reverte a posi c�ao das portas dos arm�arios cujos n�umeros s�ao m�ultiplos de �� Um terceiro gaiato reverte em seguida a posi c�ao das portas dos arm�arios cujos n�umeros s�ao m�ultiplos de �� e assim sucessivamente� para os m�ultiplos de �� �� �� � � � � ��� e ����� Quais os n�umeros dos arm�arios cujas portas estar�ao abertas ao �m do processo Quantos s�ao estes arm�arios ����� Dado um conjunto �nito� mostre que �e poss� vel ordenar seus subconjuntos� por inclus�ao� de modo que cada subconjunto seja obtido a partir do anterior pelo acr�escimo ou pela supress�ao de um �unico elemento� � Leonardo de Pisa ��� ��� � ������ � matem atico italiano� publicou em ���� o Liber Abaci� �� CAP � ITULO � N � UMEROS NATURAISA �nalidade deste cap� tulo �e abordar� de forma sucinta� a sequ�encia dos n�umeros naturais� sobre a qual pode ser constru� do todo o edif� cio da Matem�atica como ci�encia dedutiva� Esta �ultima frase j�a nos d�a id�eia da import�ancia do assunto� Sua enorme relev�ancia� entretanto� n�ao decorre de complexas concep c�oes �los�o�cas nem repousa sobre intricadas constru c�oes matem�aticas� Pelo contr�ario� a compreens�ao do que s�ao e do que signi�cam os n�umeros naturais se faz a partir de id�eias extremamente simples e espont�aneas� como mostraremos a seguir� Esse entendimento� essa forma �nal bem�acabada de apresentar os n�umeros naturais� surgiu no �nal do s�eculo XIX e encontrou sua express�ao mais l� mpida nos trabalhos de Richard Dedekind e Giuseppe Peano� �� ��� A SEQ U ENCIA DOS NTMEROS NATURAIS Os n�umeros naturais constituem um modelo matem�atico� uma escala padr�ao� que nos permite a opera c�ao de contagem� A seq!u�encia desses n�umeros �e uma livre e antiga cria c�ao do esp� rito humano� Comparar conjuntos de objetos com essa escala abstrata ideal �e o processo que torna mais precisa a no c�ao de quantidade esse processo �a contagem� pressup�oe portanto o conhecimento da seq!u�encia num�erica� Familiarizarmo�nos com tal seq!u�encia �e nosso objetivo imediato� Sabemos que os n�umeros naturais s�ao �� �� �� �� �� � � � A totalidade desses n�umeros constitui um conjunto� que indicaremos com o s� mbolo INI e que chamaremos de conjunto dos n�umeros naturais� Portanto INI � f�� �� �� �� �� � � �g� Evidentemente� o que acabamos de dizer s�o faz sentido quando j�a se sabe o que �e um n�umero natural� Nos par�agrafos seguintes� vamos fazer de conta que esse conceito nos �e desconhecido e procuraremos investigar o que h�a de essencial na seq!u�encia �� �� �� �� �� � � � Deve�se a Peano a constata c�ao de que se pode elaborar toda a teoria dos n�umeros na� turais a partir de quatro fatos b�asicos� conhecidos atualmente como os axiomas de Peano� Noutras palavras� o conjunto INI dos n�umeros naturais possui quatro propriedades funda� mentais� das quais resultam� como conseq!u�encias l�ogicas� todas as a�rma c�oes verdadeiras que se podem fazer sobre esses n�umeros� Come caremos nosso estudo com o enunciado e a aprecia c�ao do signi�cado dessas qua� tro proposi c�oes fundamentais a respeito dos n�umeros naturais� �� ��� OS AXIOMAS DE PEANO Um matem�atico pro�ssional� em sua linguagem direta e objetiva� diria que o conjunto INI dos n�umeros naturais �e caracterizado pelas seguintes propriedades� A� Existe uma fun c�ao s � INI � INI� que associa a cada n � INI um elemento s�n� � INI� chamado o sucessor de n B� A fun c�ao s � INI� INI �e injetiva C� Existe um �unico elemento � no conjunto INI tal que � �� s�n� para todo n � INI D� Se um subconjunto X INI �e tal que � � X e s�X� X �isto �e� n � X � s�n� � X�� ent�ao X � INI� �Observe que� como estamos chamando de INI o conjunto dos n�umeros naturais� a nota c�ao n � INI signi�ca que n �e um n�umero natural� � As a�rma c�oes A� B� C e D s�ao os axiomas de Peano� A nota c�ao s�n� �e provis�oria� Depois de de�nirmos adi c�ao� escreveremos n� � em vez de s�n�� Como concess�ao �a fraqueza humana� nosso matem�atico nos faria a gentileza de refor� mular os axiomas de Peano em linguagem corrente� livre de nota c�ao matem�atica� E nos diria ent�ao que as a�rma c�oes acima signi�cam exatamente o mesmo que essas outras� A�� Todo n�umero natural possui um �unico sucessor� que tamb�em �e um n�umero natural B�� N�umeros naturais diferentes possuem sucessores diferentes �Ou ainda� n�umeros que t�em o mesmo sucessor s�ao iguais�� C�� Existe um �unico n�umero natural que n�ao �e sucessor de nenhum outro� Este n�umero �e representado pelo s� mbolo � e chamado de �n�umero um� D�� Se um conjunto de n�umeros naturais cont�em o n�umero � e� al�em disso� cont�em o sucessor de cada um de seus elementos� ent�ao esse conjunto coincide com INI� isto �e� cont�em todos os n�umeros naturais� A partir da� � retomamos a palavra para dizer que o sucessor de � chama�se �dois�� o sucessor de dois chama�se �tr�es�� etc� Nossa civiliza c�ao progrediu ao ponto em que temos um sistema de numera c�ao� o qual nos permite representar� mediante o uso apropri� ado dos s� mbolos �� �� �� �� �� �� �� �� � e �� todos os n�umeros naturais� Al�em disso� nossa linguagem tamb�em fornece nomes para os primeiros termos da seq!u�encia dos n�umeros �� naturais� �N�umeros muito grandes n�ao t�em nomes espec� �cos� ao contr�ario dos menores� como �mil novecentos e noventa e quatro�� Quem sabe� por exemplo� o nome do n�umero de �atomos do universo � Voltando a usar a nota c�ao s�n� para o sucessor do n�umero natural n� teremos ent�ao � � s���� � � s���� � � s���� � � s���� etc� Assim� por exemplo� a igualdade � � s��� signi�ca apenas que estamos usando o s� mbolo � para representar o sucessor de �� A seq!u�encia dos n�umeros naturais pode ent�ao ser indicada assim� � s � � s � � s � � s � � � � � As "echas ligam cada n�umero ao seu sucessor� Nenhuma "echa aponta para �� pois este n�umero n�ao �e sucessor de nenhum outro� O diagrama acima diz muito sobre a estrutura do conjunto INI dos n�umeros naturais� Mediante uma an�alise cr� tica� veremos agora qual o signi�cado dos axiomas de Peano� Para melhor entend�e�los buscaremos situa c�oes em que eles n�ao valem� O axioma A cont�em a id�eia de que o conjunto dos n�umeros naturais �e discreto� �Em oposi c�ao a cont� nuo� como o conjunto dos pontos de uma reta� � Exemplo ���� Uma situa�c�ao em que n�ao vale o axioma B �e indicada no diagrama abaixo� Nele� tem se o conjunto X � f�� �� �� �g e a fun�c�ao s � X� X� com s��� � �� s��� � �� s��� � �� s��� � �� ENTRA FIGURA I A fun c�ao s n�ao �e injetiva� pois s��� � s���� embora � �� �� J�a o diagrama seguinte exibe um caso em que valem os axiomas A e B mas n�ao vale C� �� ENTRA FIGURA II Aqui� temos X � f�� �� �g e a fun c�ao s � X� X� dada por s��� � �� s��� � �� s��� � �� �e injetiva mas todo elemento n � X �e �sucessor� de algum outro elemento de X pois s �e sobrejetora� Exemplo ���� Neste exemplo� valem os axiomas A e B mas n�ao valem C nem D� Ele se exprime pelo diagrama� ENTRA FIGURA III Aqui� INI �e o conjunto dos n�umeros naturais mas a fun c�ao s � INI � INI �e de�nida por s�n� � n � �� Ent�ao n�ao vale o axioma C porque os elementos � e � gozam ambos da propriedade de n�ao serem da forma s�n� para nenhum n � INI� Tampouco vale o axioma D porque se considerarmos o conjunto X � f�� �� �� � � �g formado pelos n�umeros � mpares� veremos que vale � � X e� al�em disso� n � X � s�n� � n� � � X mas n�ao se tem X � INI� Um exemplo em que valem os axiomas A� B e C mas falha o axioma D �e proposto no Exerc� cio ���� Evidentemente� ao apresentarmos estes contra�exemplos estamos violando o trato de n�ao admitir conhecimento algum sobre os n�umeros naturais� Note�se por�em que as consi� dera c�oes acima n�ao fazem parte da teoria� Elas servem apenas para ajudar a compreens�ao e delimitar o alcance dos axiomas� �� ��� O AXIOMA DA INDUC� � AO Um dos axiomas de Peano� o �ultimo� possui claramente uma natureza mais elaborada do que os demais� Ele �e conhecido como o axioma da indu�c�ao� Dado o seu maior grau de complexidade� e dada tamb�em sua grande import�ancia� faremos dele uma an�alise mais detida� acompanhada de coment�arios� O signi�cado informal do axioma D �e que todo n�umero natural pode ser obtido a partir de � por meio de repetidas aplica c�oes da opera c�ao de tomar o sucessor� Assim� por exemplo� � �e o sucessor do sucessor de �� � �e o sucessor do sucessor do sucessor de �� etc� Para seestudar melhor o axioma da indu c�ao �e �util reexaminar o Exemplo ���� no qual INI � f�� �� �� � � �g mas a fun c�ao s � INI� INI foi modi�cada� pondo�se s�n� � n� �� Ent�ao� se come carmos com � e a este n�umero aplicarmos repetidamente a opera c�ao de tomar o �sucessor� �nesta nova acep c�ao� obteremos s��� � �� s��� � �� s��� � �� etc�� e nunca chegaremos a qualquer n�umero par� Portanto� o diagrama ENTRA FIGURA IV exibe uma fun c�ao injetiva s � INI� INI para a qual n�ao �e verdade que todo n�umero natural n pode ser obtido� a partir de �� mediante repetidas aplica c�oes da opera c�ao de passar de k para s�k�� Dentro de um ponto de vista estritamente matem�atico� podemos reformular o axioma da indu c�ao do seguinte modo� Um subconjunto X INI chama�se indutivo quando s�X� X� ou seja� quando n � X� s�n� � X� ou ainda� quando o sucessor de qualquer elemento de X tamb�em pertence a X� Dito isto� o axioma da indu c�ao a�rma que o �unico subconjunto indutivo de INI que cont�em o n�umero � �e o pr�oprio INI� �� No Exemplo ���� os n�umeros � mpares �� �� �� � � � formam um conjunto indutivo que cont�em o elemento � mas n�ao �e igual a INI� O papel fundamental do axioma da indu c�ao na teoria dos n�umeros naturais e� mais geralmente� em toda a Matem�atica� resulta do fato de que ele pode ser visto como um m�etodo de demonstra c�ao� chamado o m�etodo de indu�c�ao matem�atica� ou princ� pio da indu�c�ao �nita� ou princ� pio da indu�c�ao� conforme explicaremos agora� Seja P uma propriedade que se refere a n�umeros naturais� Um dado n�umero natural pode gozar ou n�ao da propriedade P� Por exemplo� seja P a propriedade de um n�umero natural n ser sucessor de outro n�umero natural� Ent�ao � n�ao goza da propriedade P� mas todos os demais n�umeros gozam de P� O princ� pio da indu c�ao diz o seguinte� Princ��pio da indu�c�ao� Seja P uma propriedade referente a n�umeros naturais� Se � goza de P e se� al�em disso� o fato de o n�umero natural n gozar de P implicar que seu sucessor s�n� tamb�em goza de P� ent�ao todos os n�umeros naturais gozam da propriedade P� Para ver que o princ� pio da indu c�ao �e verdadeiro �uma vez admitidos os axiomas de Peano� basta observar que� dada a propriedade P cumprindo as condi c�oes estipuladas no enunciado do princ� pio da indu c�ao� o conjunto X dos n�umeros naturais que gozam da propriedade P cont�em o n�umero � e �e indutivo� Logo X � INI� isto �e� todo n�umero natural goza da propriedade P� No que se segue� veremos diversos exemplos de demonstra c�oes por indu c�ao� �Chama�se assim uma demonstra c�ao baseada no princ� pio da indu c�ao�� Pode�se mesmo dizer que todas as propriedades b�asicas dos n�umeros naturais s�ao demonstradas por indu c�ao� Como n�ao dispomos ainda dos instrumentos de trabalho para lidar com esses n�umeros �as opera c�oes fundamentais e a no c�ao de ordem� �menor do que� e �maior do que�� vamos ilustrar o m�etodo de prova por indu c�ao com um exemplo bem simples� Exemplo ���� Entre os axiomas de Peano n�ao consta explicitamente a a�rma�c�ao de que todo n�umero �e diferente do seu sucessor� a qual provaremos agora� �� Demonstrao� Seja P esta propriedade� Mais precisamente� dado o n�umero natural n� escrevamos P�n� para signi�car� abreviadamente� a a�rma c�ao n �� s�n�� Ent�ao P��� �e verdadeira� pois � �� s���� j�a que � n�ao �e sucessor de n�umero algum em particular� � n�ao �e sucessor de si pr�oprio� Al�em disso� se supusermos P�n� verdadeira� isto �e� se admitirmos que n �� s�n�� ent�ao s�n� �� s�s�n��� pois a fun c�ao s � INI� INI �e injetiva� Mas a a�rma c�ao s�n� �� s�s�n�� signi�ca que P�s�n�� �e verdadeira� Assim� a verdade de P�n� acarreta a verdade de P�s�n��� Pelo princ� pio da indu c�ao� todos os n�umeros naturais gozam da propriedade P� ou seja� s�ao diferentes de seus sucessores� Nas demonstra c�oes por indu c�ao� a hip�otese de que a propriedade P �e v�alida para o n�umero natural n �da qual deve decorrer que P vale tamb�em para s�n�� chama�se hip�otese de indu�c�ao� Exemplo ���� O princ� pio da indu�c�ao n�ao �e utilizado somente como m�etodo de demons tra�c�ao� Ele serve tamb�em para de�nir fun�c�oes f � INI� Y que t�em como dom� nio o conjunto INI dos n�umeros naturais� Em geral� para se de�nir uma fun c�ao f � X � Y requer�se que seja dada uma regra bem determinada� a qual mostre como se deve associar a cada elemento x � X um �unico elemento y � f�x� � Y� Entretanto� no caso particular em que o dom� nio da fun c�ao �e o conjunto INI dos n�umeros naturais� a �m de de�nir uma fun c�ao f � INI � Y n�ao �e necess�ario dizer� de uma s�o vez� qual a receita que d�a o valor f�n� para todo n � INI� Basta que se tenha conhecimento dos seguintes dados� ��� O valor f��� ��� Uma regra que permita calcular f�s�n�� quando se conhece f�n�� Esses dois dados permitem que se conhe ca f�n� para todo n�umero natural n� �Diz� se ent�ao que a fun c�ao f foi de�nida por recorr�encia�� Com efeito� se chamarmos de X o conjunto dos n�umeros naturais n para os quais se pode determinar f�n� o dado ��� acima nos mostra que � � X e o dado ��� assegura que n � X� s�n� � X� Logo� pelo axioma da indu c�ao� tem�se X � INI� �� Observa c�ao� Uma fun c�ao f � INI� Y cujo dom� nio �e o conjunto dos n�umeros naturais chama�se uma seq�u�encia ou sucess�ao de elementos de Y� A nota c�ao usada para uma tal seq!u�encia �e �y � � y � � � � � � y n � � � ��� onde se usa y n em vez de f�n� para indicar o valor da fun c�ao f no n�umero n� O elemento y n chama�se n �esimo termo da seq!u�encia� ��� ADIC� � AO DE NTMEROS NATURAIS Nosso primeiro exemplo de uma fun c�ao de�nida por recorr�encia �e a adi�c�ao de n�umeros naturais� Para de�nir a adi c�ao� �xaremos um n�umero natural arbitr�ario k e de�niremos a soma k� n para todo n � INI� Fixado k � INI� a correspond�encia n � k�n ser�a uma fun c�ao f � INI� INI� f�n� � k�n� chamada �somar k�� Ela se de�ne por recorr�encia� a partir dos seguintes dados� ��� k� � � s�k�� ��� k� s�n� � s�k� n�� Portanto� k� � �e� por de�ni c�ao� o sucessor de k� E se conhecermos k� n saberemos o valor de k� s�n� por de�ni c�ao tem�se k � s�n� � s�k � n�� Isto nos permite conhecer k� n para todo n � INI� A partir de agora� usaremos a nota c�ao de�nitiva n� � em vez de s�n�� Usando as nota c�oes de�nitivas n�� em vez de s�n� e �k�n�� � em vez de s�k�n�� a igualdade ��� se escreve ent�ao assim� �� � � k� �n� �� � �k� n� � �� Portanto as igualdades ��� e ��� ou� equivalentemente� ��� e ��#� de�nem� por recor� r�encia� a soma k� n de dois n�umeros naturais quaisquer k e n� As propriedades da adi c�ao de n�umeros naturais s�ao provadas por indu c�ao� Vejamos dois exemplos� Teorema ���� �Associatividade da adi c�ao� k � �n � p� � �k � n� � p� para quaisquer k� n� p � INI� �� Demonstrao� Fixados arbitrariamente k� n � INI� a associatividade k � �n � p� � �k � n� � p �e verdadeira quando p � �� por de�ni c�ao� �Vide ��#�� Supondo�a verdadeira para p� tem�se sucessivamente� k� �n� �p� ��� � k� ��n� p� � �� por ��#� � �k� �n� p�� � � novamente por ��#� � ��k� n� � p� � � pela hip�otese de indu c�ao � �k� n� � �p� �� outra vez por ��#�� Segue�se ent�ao que a lei associativa k� �n� p� � �k�n� � p �e v�alida para quaisquer n�umeros naturais k� n� p� Teorema ���� �Comutatividade da adi c�ao� k� n � n� k para quaisquer k� n � INI� Demonstrao� A comutatividade n� p � p�n se prova usando duas vezes o princ� pio da indu c�ao� Primeiro consideramos o caso p � �� A igualdade n � � � � � n �e obviamente verdadeira quando n � �� Supondo�a v�alida para um certo valor de n� tem�se a hip�otese de indu c�ao n � � � � � n� Somando � a ambos os membros desta igualdadee usando a associatividade� vem �n� �� � � � �� � n� � � � � � �n� ��� Segue�se que n� � � � � n para todo n � INI� Vemos� portanto� que a comutatividade n � p � p � n �e verdadeira quando p � �� Admitamos agora �hip�otese de indu c�ao� que ela valha para um certo p e mostremos que isto acarreta sua validez para p� �� Com efeito� temos sucessivamente n� p � p� n hip�otese de indu c�ao �n� p� � � � �p� n� � � somando � a ambos os membros n� �p� �� � �p� n� � � associatividade � � � �p� n� comutatividade da soma com � � �� � p� � n associatividade � �p� �� � n comutatividade da soma com �� �� Segue�se que n� p � p� n para quaisquer n� p � INI� Outra propriedade importante da adi c�ao �e a demonstrada a seguir� Teorema ���� �Lei do corte� Para quaisquer n�umeros naturais m�n� p� se m�p � n� p� ent�ao m � n� Demonstrao� Com efeito� de m�� � n�� segue�se que m � n em virtude do axioma B de Peano� Logo a lei do corte vale para p � �� Supondo�a v�alida para um certo n�umero natural p �hip�otese de indu c�ao�� mostremos que se pode tamb�em cortar p��� Admitamos ent�ao que se tenha m� �p� �� � n� �p� ��� Pela associatividade� esta igualdade equivale a �m� p� � � � �n� p� � �� Cortando � de ambos os membros� vem m� p � n� p� Pela hip�otese de indu c�ao� conclu� mos que m � n� Assim m� �p� �� � n� �p� ��� m � n portanto a Lei do Corte �e v�alida em geral� A lei do corte equivale �a a�rma c�ao de que� para todo k � INI� a aplica c�ao f k � INI� INI� dada por f k �n� � n� k� �e injetiva� �� ��� ORDEM A adi c�ao de n�umeros naturais permite introduzir uma rela c�ao de ordem em INI� De�ni�c�ao Dados os n�umeros naturais m�n diremos que m �e menor do que n� e escreve� remos m � n� para signi�car que existe p � INI tal que n � m � p� Neste caso� diz�se tamb�em que n �e maior do que m e escreve�se n � m para exprimir que se tem m � n� A nota c�ao m � n signi�ca que m � n ou m � n� Por de�ni c�ao tem�se portanto m � m � p para quaisquer m�p � INI� Em particular� m � m � �� Segue�se tamb�em da de�ni c�ao da rela c�ao � que � � n para todo n�umero natural n �� �� pois� pelo axioma C� n �� � implica que n �e sucessor de algum n�umero natural m� ou seja� n � m � � � � �m� logo n � �� Assim� � �e o menor dos n�umeros naturais� Provaremos a seguir as propriedades b�asicas da rela c�ao de ordemm � n que de�nimos� A primeira delas �e a transitividade� Teorema ���� �Transitividade� Se m � n e n � p� ent�ao m � p� Demonstrao�m � n� n � p� n � m�k� p � n�r� p � �m�k��r � m��k�r�� m � p� Outra importante propriedade da rela c�ao de ordem �e que� dados dois n�umeros na� turais diferentes m e n� ou se tem m � n ou ent�ao n � m� Esta propriedade pode ser reformulada de outra maneira� como segue� Diremos que os n�umeros naturais m e n s�ao compar�aveis quando se tem m � n� ou m � n ou n � m� Podemos ent�ao enunciar o seguinte teorema� Teorema ���� �Comparabilidade� Todo n�umero natural n �e compar�avel com qualquer n�umero natural m� �� Demonstrao� Isto se prova por indu c�ao� O n�umero � �e compar�avel com qualquer outro n�umero natural pois j�a sabemos que que � � m para todo m �� �� Suponhamos agora que o n�umero n seja compar�avel com todos os n�umeros naturais� Mostremos� a partir da� � que n�� tamb�em tem essa propriedade� Com efeito� seja m � INI tomado arbitrariamente� Sabemos que se tem m � n� ou m � n ou n � m� Examinemos cada uma dessas possibilidades� Se for m � n ent�ao m � n� �� Se for m � n� ent�ao m � n� �� Se for n � m ent�ao m � n � p� Neste caso� h�a duas possibilidades� Ou se tem p � �� donde m � n � �� ou ent�ao p � �� logo p � � � p � � e portanto m � �n � �� � p � e conclu� mos que n � � � m� Em qualquer hip�otese� vemos que n � � �e compar�avel com qualquer n�umero naturalm� Por indu c�ao� �ca provada a comparabilidade de dois n�umeros naturais quaisquer m�n� A comparabilidade dos n�umeros naturais �e complementada pela proposi c�ao abaixo� Teorema ���� �Tricotomia� Dados m�n � INI� qualquer das a�rma�c�oes m � n� m � n� n � m exclui as outras duas� Demonstrao� Se tiv�essemos m � n e m � n� ent�ao seria m � m� p� donde m� � � m� p� � e� cortando m� concluir� amos que � � p� �� um absurdo� pois � n�ao �e sucessor de p� Portanto m � n �e� analogamente� n � m� �e incompat� vel com m � n� Do mesmo modo� se tiv�essemos m � n e n � m� ent�ao ter� amos n � m � p e m � n � k� do que resultaria n � n � k � p� logo n � � � n � k � p � �� e cortando n concluir� amos que � � k� p� �� um absurdo� O teorema seguinte mostra que n e n� � s�ao n�umeros consecutivos� Teorema ���� N�ao existem n�umeros naturais entre n e n� �� Demonstrao� Se fosse poss� vel ter n � p � n��� ter� amos p � n� k e n� � � p� r� logo n� � � n� k� r� Cortando n� obter� amos � � k� r� Por de�ni c�ao� isto signi�caria k � �� o que �e absurdo� pois j�a vimos que k �� �� k � �� A conex�ao entre a rela c�ao de ordem e a opera c�ao de adi c�ao �e dada pelo seguinte teorema� �� Teorema ���� �Monotonicidade da Adi c�ao� Se m � n� ent�ao m� p � n� p� Demonstrao� Usando a de�ni c�ao de �� temos que m � n � n � m � k � n � p � �m� k� � p�m� p � n� p� A rec� proca da monotonicidade �e a lei do corte para desigualdades� m � p � n � p � m � n� O leitor poder�a prov�a�la por absurdo� usando a tricotomia e a pr�opria monotonicidade� ��� BOA ORDENAC� � AO De�ni�c�ao Dado o subconjunto A INI� diz�se que o n�umero natural a �e o menor �ou primeiro� elemento de A quando a � A e� al�em disso� a � x� para todos os elementos x � A� Por exemplo� � �e o menor elemento de INI� De agora em diante� dado n � INI� indicaremos com I n o conjunto dos n�umeros naturais p tais que � � p � n� Assim� I � � f�g� I � � f�� �g� I � � f�� �� �g� etc� As propriedades da rela c�ao de ordem m � n demonstradas na se c�ao anterior para os n�umeros naturais �exceto o Teorema ���� s�ao igualmente v�alidas para os n�umeros in� teiros� racionais e� mais geralmente� para n�umeros reais quaisquer� Existe� por�em� uma propriedade de suma import�ancia que �e v�alida para a ordem entre os n�umeros naturais� mas sem equivalente para n�umeros inteiros� racionais ou reais� Trata�se do Teorema ���� �Princ��pio da boa ordena�c�ao� Todo subconjunto n�ao vazio A INI possui um menor elemento� Demonstrao� Sem perda de generalidade� podemos admitir que � �� A� pois caso contr�ario � seria evidentemente o menor elemento de A� O menor elemento de A� cuja exist�encia queremos provar� dever�a ser da forma n� �� para um certo n�umero natural n� Devemos pois encontrar um n�umero natural n tal que n � � � A e� al�em disso� todos os elementos de A sejam maiores do que n� logo maiores do que �� �� � � � � n� Noutras palavras� procuramos um n�umero natural n tal que I n INI � A e n � � � A� Com esse objetivo� consideramos o conjunto X � fn � INI I n INI�Ag� �� Portanto� X �e o conjunto dos n�umeros naturais n tais que todos os elementos de A s�ao maiores do que n� Como estamos supondo que � �� A� sabemos que � � X� Por outro lado� como A n�ao �e vazio� nem todos os n�umeros naturais pertencem a X� ou seja� temos X �� INI� Pelo axioma D� vemos que o conjunto X n�ao �e indutivo� isto �e� deve existir algum n � X tal que n� � �� X� Isto signi�ca que todos os elementos de A s�ao maiores do que n mas nem todos s�ao maiores do que n��� Como n�ao h�a n�umeros naturais entre n e n��� conclu� mos que n� � pertence a A e �e o menor elemento de A� O teorema abaixo cont�em uma aplica c�ao do princ� pio da boa ordena c�ao� Teorema ����� Toda fun�c�ao mon�otona n�ao crescente f � INI� INI �e constante a partir de um certo ponto� �Isto e� existen � � INI tal que f�n� � f�n � �� para todo n � n � �� Demonstrao� Seja f�n � � o menor elemento do conjunto X � ff���� � � � � f�n�� � � �g� En� t�ao n � n � � f�n� � f�n � � �porque a fun c�ao f �e mon�otona n�ao�crescente� o que acarreta que f�n� � f�n � � �porque f�n � � �e o menor elemento de X�� Corol�ario� N�ao existem seq!u�encias decrescentes n � � n � � � � � de n�umeros naturais� Com efeito� do contr�ario� pondo f�k� � n k � obter� amos uma fun c�ao estritamente decrescente f � INI� INI� O princ� pio da boa ordena c�ao pode muitas vezes ser usado em demonstra c�oes� substi� tuindo o princ� pio da indu c�ao� Vejamos um exemplo desse uso� Dissemos anteriormente que um subconjunto X INI chama�se indutivo quando n � X � n � � � X� ou seja� quando X cont�em o sucessor de cada um dos seus elementos� O princ� pio da indu c�ao a�rma que se um conjunto indutivo X cont�em o n�umero � ent�ao X cont�em todos os n�umeros naturais� Vamos usar o princ� pio da boa ordena c�ao para provar que se um conjunto indutivo X cont�em o n�umero a� ent�ao X cont�em todos os n�umeros naturais maiores do que a� A prova desta a�rma c�ao se faz por absurdo� como ocorre em geral quando se usa a boa ordena c�ao� Suponhamos� ent�ao� que existam n�umeros naturais maiores do que a n�ao pertencentes ao conjunto indutivo X� Seja b o menor desses n�umeros� Como b � a� podemos escrever b � c��� onde� pela de�ni c�ao de b� tem�se necessariamente c � X� Mas� como X �e indutivo� isto obriga que b � c� � � X� uma contradi c�ao� �� A proposi c�ao que acabamos de demonstrar pode ser reenunciada da seguinte forma� Teorema ����� �Princ��pio da indu�c�ao generalizado� Seja P uma propriedadereferente a n�umeros naturais� cumprindo as seguintes condi�c�oes� ��� O n�umero natural a goza da propriedade P ��� Se um n�umero natural n goza da propriedade P ent�ao seu sucessor n�� tamb�em goza de P� Ent�ao todos os n�umeros naturais maiores do que ou iguais a a gozam da propriedade P� Observa c�ao� No Cap� tulo �� este teorema foi chamado de princ� pio da indu c�ao� Exemplo ���� Para exibir uma situa�c�ao simples onde se emprega o princ� pio da indu�c�ao generalizado� usaremos a multiplica�c�ao de n�umeros naturais� que ser�a de�nida na se�c�ao �� Trata�se de provar que �n � � � � n � para todo n � �� Esta a�rma c�ao� �que �e falsa para n � �� ��� vale quando n � �� Supondo�a v�alida para um certo n� mostremos que da� decorre sua validez para n� �� Com efeito� ��n� �� � � � �n� � � � � � n � � pela hip�otese de indu c�ao � � n � � n pois � n � ���� � � �� � ����� � � �� � � n�� � Exemplo ���� Usando a desigualdade �n� � � � n � que acabamos de provar para n � �� podemos demonstrar que n � � � n para todo n � �� empregando novamente o princ� pio da indu�c�ao generalizado� �� Demonstrao� Com efeito� vale � � � � � pois �� � ��� Supondo v�alida a desigualdade n � � � n para um certo valor de n� da� segue�se que �n� �� � � n � � �n� � � � n � �n� � pela hip�otese de indu c�ao � � n � � n pelo exemplo anterior � � n�� � Portanto P�n�� P�n���� Pelo princ� pio da indu c�ao generalizado� segue�se que P�n� vale para todo n � �� Evidentemente� a desigualdade n � � � n �e falsa para n � �� �� �� �� ��� SEGUNDO PRINC � IPIO DA INDUC� � AO Em algumas situa c�oes� ao tentarmos fazer uma demonstra c�ao por indu c�ao� na passagem de n para n��� sentimos necessidade de admitir que a proposi c�ao valha n�ao apenas para n e sim para todos os n�umeros naturais menores do que ou iguais a n� A justi�cativa de um racioc� nio desse tipo se encontra no Teorema ����� �Segundo princ��pio da indu�c�ao� Seja X INI um conjunto com a seguinte propriedade� Dado n � INI� se todos os n�umeros naturais menores do que n pertencem a X� ent�ao n � X� Nestas condi�cSes� o conjunto X �e necessariamente igual a INI� Ent�ao X � INI� Demonstrao� Com efeito� supondo� por absurdo� que X �� INI� isto �e� que INI � X �� �� seja n o menor elemento do conjunto INI � X� ou seja� o menor n�umero natural que n�ao pertence a X� Isto quer dizer que todos os n�umeros naturais menores do que n pertencem a X� Mas ent�ao� pela propriedade �I�� n pertence a X� uma contradi c�ao� Segue�se que INI� X � � e X � INI� Observa�c�ao� Se um conjunto X INI goza da propriedade �I�� para que um n�umero natural n n�ao pertencesse a X seria necess�ario que existisse algum n�umero natural r � n tal que r �� X� Em particular� se n � �� como n�ao existe n�umero natural menor do que �� a hip�otese � �� X n�ao pode ser cumprida� Noutras palavras� �I� j�a cont�em implicitamente �� a a�rma c�ao de que � � X� Assim� ao utilizar o segundo princ� pio da indu c�ao� n�ao �e preciso estipular que X cont�em o n�umero �� Toda propriedade P que se re�ra a n�umeros naturais de�ne um subconjunto X INI� a saber� o conjunto dos n�umeros naturais que gozam da propriedade P� �E reciprocamente� todo conjunto X INI de�ne uma propriedade referente a n�umeros naturais� a saber� a propriedade de pertencer a X�� Deste modo� �propriedade� e �conjunto� s�ao no c�oes equivalentes� Por isso� �e natural que o segundo princ� pio da indu c�ao possua a formula c�ao seguinte� onde ele aparece como o Teorema ����� �Segundo m�etodo de demonstra�c�ao por indu�c�ao� Seja P uma pro priedade referente a n�umeros naturais� Dado n � INI� se a validade de P para todo n�umero natural menor do que n implicar que P �e verdadeira para n� ent�ao P �e verdadeira para todos os n�umeros naturais� Demonstrao� Com efeito� nas condi c�oes do enunciado� o conjunto X dos n�umeros na� turais que gozam da propriedade P satisfaz a condi c�ao �I� do segundo princ� pio da indu c�ao� logo X � INI e P vale para todos os n�umeros naturais� �� ��� NTMEROS CARDINAIS At�e agora� n�ao h�a nenhuma rela c�ao entre o processo de contar e os n�umeros naturais� No entanto� historicamente� estes n�umeros surgiram da contagem de objetos discretos� Como recuperar� em um contexto matem�atico� esta rela c�ao b�asica entre os n�umeros naturais e a contagem Lembremos que� dado n � INI� escrevemos I n � fp � INI p � ng� portanto I n � f�� �� � � � � ng� Uma contagem dos elementos de um conjunto n�ao�vazio X �e uma bije c�ao f � I n � X� O n�umero natural n chama�se ent�ao o n�umero cardinal� ou a cardinalidade� ou o n�umero de elementos do conjunto X� Diz�se tamb�em que X possui n elementos� Dada uma contagem f � I n � X� podemos por x � � f���� x � � f���� � � � � x n � f�n� e escrever X � fx � � x � � ���� x n g� O conjunto X chama�se um conjunto �nito quando existe n � INI tal que X possui n elementos� Um exemplo �obvio de conjunto �nito �e I n � Evidentemente� a fun c�ao identidade f � I n � I n �e uma contagem� logo I n possui n elementos� Um conjunto X diz�se in�nito quando n�ao �e �nito� Isto signi�ca que para nenhum n � INI pode existir uma bije c�ao f � I n � X� Um exemplo de conjunto in�nito �e o pr�oprio conjunto INI dos n�umeros naturais� pois nenhuma fun c�ao f � I n � INI pode ser sobrejetiva� n�ao importa qual n se tome� De fato� dada f� tomamos k � f��� � f��� � � � �� f�n� e vemos que k � f�x� para todo x � I n � logo k �� f�I n �� e f n�ao �e sobrejetiva� A �m de que n�ao haja ambig!uidade quando se falar do n�umero de elementos de um conjunto �nito X� �e necess�ario provar que todas as contagens de X fornecem o mesmo resultado� Noutras palavras� dado o conjunto X� os n�umeros naturais m�n e asbije c�oes f � I m � X� g � I n � X� devemos mostrar que se tem m � n� Come camos observando que se f e g s�ao bije c�oes� ent�ao � � g �� �f � I m � I n tamb�em �e uma bije c�ao� Basta portanto provar o seguinte� Teorema ����� Dados m�n � INI� se � � I m � I n �e uma bije�c�ao� ent�ao m � n� �� Demonstrao� Com efeito� chamemos de X o conjunto dos n�umeros naturais n que t�em a seguinte propriedade� s�o existe uma bije c�ao � � I m � I n quandom � n� Evidentemente� � � X� Suponhamos agora que n � X� Dada uma bije c�ao � � I m�� � I n�� � duas coisas podem acontecer� Primeira� ��m � �� � n � �� Neste caso� a restri c�ao � � I m � I n �e uma bije c�ao� logo m � n� donde m� � � n� �� Segunda� ��m� �� � b� com b � n� �� Neste caso� consideramos a � � �� �n��� e de�nimos uma nova bije c�ao � � I m�� � I n�� � pondo ��m � �� � n � �� ��a� � b e ��x� � ��x� para os demais elementos x � I m�� � Ent�ao reca� mos no caso anterior e novamente conclu� mos que m� � � n� �� Isto mostra que n � X � n � � � X� logo X � INI e a unicidade do n�umero cardinal de um conjunto �nito �ca demonstrada� Agora os n�umeros naturais n�ao s�ao apenas elementos do conjunto�padr�ao INI� mas servem tamb�em para responder perguntas do tipo �quantos elementos tem o conjunto X �� ou seja� podem ser usados tanb�em como n�umeros cardinais� A adi c�ao de n�umeros naturais se relaciona com a cardinalidade dos conjuntos por meio da seguinte proposi c�ao� Teorema ����� Sejam X� Y conjuntos �nitos disjuntos� Se X tem m elementos e Y tem n elementos� ent�ao X � Y tem m� n elementos� Demonstrao� Com efeito� se f � I m � X e g � I n � Y s�ao bije c�oes� de�nimos uma bije c�ao h � I m�n � X � Y por h�x� � f�x� se � � x � m e h�m� x� � g�x� se � � x � n� o que conclui a demonstra c�ao� Prova�se� por indu c�ao� que todo subconjunto de um conjunto �nito X �e tamb�em �nito e seu n�umero de elementos �e menor do que ou igual ao de X �� � Um subconjunto X INI chama�se limitado quando existe algum k � INI tal que n � INI� n � k �ou seja� todo elemento de X �e menor do que ou igual a k�� Teorema ����� Todo subconjunto �nito X � fn � � n � � � � � � r g INI �e limitado� �� Veja E� L� LIMA� �An alise Real�� IMPA� Rio de Janeiro� vol �� pag� �� �� Demonstrao� Com efeito� tomando k � n � � � � �� n r vemos imediatamente que k �e maior do que qualquer elemento de X� Usando o fato de que todo subconjunto de um conjunto �nito tamb�em �e �nito� pode� mos provar que� reciprocamente� todo subconjunto limitado X INI �e �nito� Com efeito� se X �e limitado� ent�ao existe k � INI tal que n � X� n � k� Isto signi�ca que todo n�umero n pertencente a X pertence tamb�em ao conjunto �nito I k f�� �� � � � � kg� ou seja� que X I k � logo X �e �nito� Dado o conjunto X INI� se o n�umero natural k �e maior do que ou igual a qualquer elemento de X� diz�se que k �e uma cota superior do conjunto X� Assim� os conjuntos limitados X INI �ou seja� os �nitos� s�ao aqueles que possuem cotas superiores� Se X INI �e um conjunto limitado �isto �e� �nito�� o princ� pio da boa ordena c�ao assegura que entre os n�umeros naturais k que s�ao cotas superiores de X existe um menor de todos� Esta menor cota superior de X pertence necessariamente ao conjunto X e �e� portanto� o maior elemento de X� Assim� todo conjunto limitado �isto �e� �nito� de n�umeros naturais possui um elemento m�aximo� � E conveniente incluir� por de�ni c�ao� o conjunto vazio entre os conjuntos �nitos e dizer que o seu n�umero de elementos �e zero� Embora zero n�ao seja um n�umero natural� ele passa a ser o n�umero cardinal do conjunto vazio� �� ��� MULTIPLICAC� � AO DE NTMEROS NATURAIS Fixado um n�umero natural k� a multiplica�c�ao por k associa a todo n�umero natural n o produto nk de�nido por indu c�ao� da seguinte maneira� ��� � � k � k ��� �n� �� � k � n � k� k� O produto n � k escreve�se tamb�em nk e l�e�se �n vezes k�� A de�ni c�ao acima diz portanto que uma vez k �e igual a k e n� � vezes k �e igual a n vezes k mais �uma vez� k� Assim� por de�ni c�ao� � � k � k� k� � � k � k� k� k� etc� Noutras palavras� n � k �n vezes k� �e a soma de n parcelas iguais a k� Como no caso da adi c�ao� prova�se que a multiplica c�ao de n�umeros naturais goza das propriedades abaixo� Associatividade� �m � n� � k � m � �n � k� Comutatividade� m � k � k �m Distributividade� m � �n� k� � m � n�m � k Lei do Corte� m � k � n � k�m � n Monotonicidade� m � n�m � k � n � k� Exemplo ���� Segue se da monotonicidade que s�o se pode ter m � n � � quando m e n forem ambos iguais a �� Demonstrao� Com efeito� se tivermos� por exemplo� m � �� a monotonicidade im� plicar�a m � n � n e� como n � �� da� se seguir�a que m � n � �� Exemplo ���� Decorre tamb�em da monotonicidade que se a � b e c � d ent�ao ac � bd� Demonstrao� Com efeito� a � b � ac � bc e c � d � bc � bd� Ent�ao� pela transitividade� ac � bd� �� EXERC�CIOS ���� Construa um esquema de setas come cando com os n�umeros � mpares� seguidos dos n�umeros pares divis� veis por � em ordem decrescente e� por �m� os pares n�ao divis� veis por � em ordem crescente� Noutras palavras� tome X � INI e de�na s � X � X pondo s�n� � n� � se n n�ao �e divis� vel por �� s�n� � n � � se n for m�ultiplo de �� Mostre que s � X� X cumpre os axiomas A� B� C mas n�ao D� ���� De�na� por recorr�encia� uma fun c�ao f � INI� INI estipulando que f��� � � e f�n��� � ��f�n� � �� D�e uma f�ormula expl� cita para f�n�� ���� D�e uma f�ormula expl� cita para f � INI � INI sabendo que f��� � �� f��� � � e f�n� �� � �f�n� ��� �f�n�� ���� Seja X INI um conjunto indutivo n�ao�vazio� Mostre que existe a � INI tal que X � fn � INI n � ag� ���� Demonstre a lei do corte para desigualdades� m� p � n� p�m � n� ���� Demonstre as propriedades multiplicativa� associativa e comutativa da multiplica c�ao de n�umeros naturais� ���� Mostre que vale a distributividade� m��n� k� � m�n�m�k� ���� Mostre que vale a lei do corte� m�k � n�k�m � n� ���� Mostre que vale a monotonicidade� m � n� m�k � n�k� ����� Use a distributividade de duas maneiras diferentes para calcular �m� n��� � �� e aplique em seguida a lei do corte para obter uma nova prova de que m� n � n�m� �� ����� Um conjunto S INI� n�ao�vazio� �e limitado superiormente� se existe um natural k tal que para todo natural x � S� ent�ao x � k� Mostre que todo conjunto S limitado superiormente possui um maior elemento� �Isto �e� existe m � S tal que x � m� para todo x � S�� ����� Dado um conjunto �nito� mostre que �e poss� vel ordenar seus subconjuntos� por inclus�ao� de modo que cada subconjunto seja obtido a partir do anterior pelo acr�escimo ou pela supress�ao de um �unico elemento� ����� Demonstre� usando boa ordena c�ao� o Exemplo ����� �� CAP � ITULO � DIVISIBILIDADE E O TEOREMA FUNDAMENTAL DA ARITM � ETICA Apresentaremos inicialmente algumas de�ni c�oes e resultados b�asicos da Aritm�etica dos n�umeros naturais que levam �a de�ni c�ao fundamental de n�umero primo� Todas estas id�eias s�ao usadas desde a escola elementar� Nosso objetivo �e rev�e�las� sistematiz�a�las e explor�a�las em exemplos e problemas interessantes� ��� DIVISIBILIDADE Dizemos que o n�umero natural a divide o n�umero natural b� o que representamos por ajb� se existe um n�umero natural c tal que b � a � c� Dizemos ent�ao que b �e um m�ultiplo de a� ou que a divide b� ou que a �e um fator de b ou ainda que a �e divisor de b� e escrevemos ajb� Dizemos tamb�em que a divis�ao de b por a �e exata� Na matem�atica grega� dizia�se quea �mede� b� uma alus�ao clara ao fato de que ent�ao se trabalhava com grandezas �em nosso caso� o segmento de reta de comprimento a est�a contido exatamente c vezes no segmento de reta de comprimento b�� Todo este cap� tulo est�a centrado em torno da no c�ao de divisibilidade� O primeiro resultado que apresentamos �e um crit�erio� �util em demonstra c�oes e problemas� que usa divisibilidade para decidir se dois n�umeros naturais s�ao iguais� Embora o zero n�ao seja um n�umero natural� n�os o empregaremos por vezes� para simpli�car enunciados e demonstra cSes� Teorema ���� Sejam a� e b n�umeros naturais� Se a divide b e b divide a� ent�ao a � b� �� Demonstrao� Com efeito� se ajb� ent�ao existe um n�umero natural c tal que b � a � c� Se bja� existe ent�ao um n�umero natural d tal que a � b � d� Segue�se que b � �bd�c � bdc� Cortando d� vem � � dc� Pelo Exemplo ��� con� clu� mos que d � � e c � �� donde a � b� Teorema ���� Se a� b e c s�ao n�umeros naturais e ajb e ajc� ent�ao aj�b� c�� Demonstrao� Com efeito� se ajb� ent�ao existe k � tal que b � k � a� Se ajc� existe k � tal que c � k � a� Assim� b � c � k � a� k � a � �k � � k � �a� donde aj�b� c�� como quer� amos demonstrar� A rec� proca deste teorema nem sempre �e verdadeira� � E f�acil achar n�umeros naturais a� b e c tais aj�b� c� mas a n�ao divide b e a n�ao divide c por exemplo� �j�� � ��� mas � n�ao divide � �� � j�� e � n�ao divide � �� � j��� Pedimos que o leitor demonstre� como exerc� cio� o seguinte teorema Teorema ���� Se a� b e c s�ao n�umeros naturais tais que ajb e bjc� ent�ao ajc� Um n�umero natural chama�se par se �e m�ultiplo de � e � mpar se n�ao �e m�ultiplo de �� �� ��� OS PRIMOS E O TEOREMA FUNDAMENTAL DA ARITM � ETICA Dizemos que um n�umero natural �e primo se ele �e diferente de � e se os �unicos divisores de p s�ao � e p� O menor primo �e �� pois seus �unicos divisores s�ao � e �� O conceito de n�umero primo �e fundamental em Teoria dos N�umeros� a parte da Matem�atica que estuda as propriedades dos n�umeros inteiros� Alguns teoremas profundos e poderosos dizem respeito a n�umeros primos� Alguns dos problemas relativos aos pri� mos t�em enunciados enganosamente f�aceis� mas cujas solu c�oes se revelam diabolicamente dif� ceis� Um fato importante� j�a conhecido dos matem�aticos gregos� cuja demonstra c�ao se en� contra nos Elementos de Euclides �Proposi c�ao XX� do Livro IX� �e que existe uma in�nidade de primos� Apresentaremos a demonstra c�ao deste fato ap�os termos introduzido a divis�ao de n�umeros naturais� O resultado a seguir� j�a demonstrado no Cap� tulo �� �Teorema ����� �e fundamental pois mostra o papel importante desempenhado pelos primos no estudo dos n�umeros naturais� qualquer n�umero natural pode ser obtido como o produto de n�umeros primos� Al�em disso� a demonstra c�ao deste fato mostra a utiliza c�ao do segundo princ� pio da indu c�ao� Devido a sua import�ancia� repetimos a demonstra c�ao� Exemplo ���� Qualquer n�umero natural n maior do que � pode ser escrito como um produto de primos� Demonstra�c�ao� Considere a a�rma c�ao �P�n�� o n�umero natural n �e primo ou ent�ao pode ser escrito como um produto de primos�� para n � �� �� �� � � � Usaremos a segunda forma do princ� pio da indu c�ao� tomando n � �� �� Como � �e primo� P��� �e verdadeira� ��Seja k um n�umero natural com k � �� Suponha que a a�rma c�ao P�n� seja v�alida para todos os n�umeros naturais maiores que ou iguais a � e menores que ou iguais a k� Mostraremos que ela �e v�alida para o n�umero natural k� �� Se k� � �e primo� nada h�a a demonstrar� Se k� � n�ao pe primo� ent�ao k� � � a � b� onde a e b s�ao n�umeros naturais maiores do que ou iguais a �� � E claro que � a � k � � e �� b � k� �� Pela hip�otese de indu c�ao� P�a� e P�b� s�ao verdadeiras� Noutras palavras� a � p � � p � � � � � � p s e b � q � � q � � � �q t se escrevem ambos como produtos de primos� Ent�ao k� � � a � b � p � � p � � � �p s � q � � q � � � �q t � �e um produto de primos� como quer� amos demonstrar� Mostraremos a seguir que esta decomposi c�ao de um n�umero natural em produto de n�umeros primos �e �essencialmente �unica�� Com isso� queremos dizer que se escrevermos n � p � � � �p � � � � � � p � k k � com os p i distintos entre si� ent�ao qualquer outra decomposi c�ao do n�umero natural n em um produto de pot�encias de primos distintos entre si fornecer�a exatamente os mesmos primos p i elevados �as pot�encias � i � com poss� veis mudan cas de ordem entre os p i � Este resultado �e conhecido como teorema fundamental da Aritm�etica e merece seu nome� Para completar a demonstra c�ao do teorema fundamental da Aritm�etica� necessitamos de um resultado pr�evio� Teorema ���� Seja n um n�umero natural cuja decomposi�c�ao em fatores primos �e essen cialmente �unica� Suponha que n � ab e que o primo p divide o produto ab �ou seja� divide n�� Ent�ao ou p divide a ou p divide b� �Observe que a e b n�ao s�ao necessariamente primos�� Demonstrao� Com efeito� se p n�ao for fator primo nem de a nem de b� existem decom� posi c�oes de a e de b que n�ao cont�em o fator primo p� Obtemos ent�ao uma decomposi c�ao de ab em fatores primos que n�ao cont�em o primo p� Por outro lado� como pjab� p comparece em alguma decomposi c�ao de ab em fatores primos� Assim� n admite duas decomposi c�oes em fatores primos essencialmente distintas� o que �e uma contradi c�ao� Podemos agora demonstrar o teorema fundamental da Aritm�etica� �� Teorema ���� Todo n�umero natural admite� de maneira essencialmente �unica� uma de composi�c�ao em produto de n�umeros primos� Demonstrao� Com efeito� j�a mostramos� usando o segundo princ� pio da indu c�ao ma� tem�atica� que existe uma tal decomposi c�ao� Resta mostrar que ela �e �unica� a menos da ordem em que nela comparecem os fatores primos� Para fazer isso� usaremos o princ� pio da boa ordena c�ao� Suponha que existam n�umeros naturais que possam ser decompostos em produtos de primos segundo duas maneiras essencialmente distintas� Ent�ao� pelo princ� pio da boa ordena c�ao� existe o menor destes� o qual chamaremos de m� Assim� m pode ser escrito como m � p � p � � � �p r e como m � q � q � � � �q s � duas decomposi c�oes em fatores primos essencialmente distintas al�em disso� qualquer n�u� mero natural menor do quem admite uma �unica decomposi c�ao em fatores primos� a menos da ordem destes fatores� Podemos supor� sem perda de generalidade� que p � � p � � � � � � p r � q � � q � � � � � � q s � A�rmamos que p � �� q � � Com efeito� suponha que p � � q � � Ent�ao� como p � p � � � �p r � q � q � � � �q s � usando a lei do cancelamento� segue�se que p � p � � � �p r � q � q � � � �q s � �� O n�umero natural acima� p � p � � � �p r � �e menor do que m e tem duas decomposi c�oes em primos essencialmente distintas� o que �e uma contradi c�ao� Assim� p � �� q � � Suponha� sem perda de generalidade� que p � � q � e considere o n�umero natural m � � m� p � q � q � � � �q s � Temos ent�ao que m � � q � q � � � �q s � p � q � � � �q s � �q � � p � ��q � q � � � �q s �� Como q � � p � � vemos que m � �e realmente um n�umero natural� Al�em disso� segue�se da de�ni c�ao de m � que m
Compartilhar