Buscar

ARITMÉTICA (TEORIA-IMPA) - ELL, PAULO CÉSAR, MORGADO, WAGNER

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

Continue navegando