Recorrência, operações nos naturais naturais e relação de ordem nos números naturais

Prévia do material em texto

Recorrência, operações nos naturais e 
relação de ordem.
Apresentação: Johnattan B. Prates
Definição por Recorrência:
• Relação de recorrência (ou passo recorrente) é uma técnica matemática que
permite definir uma sequência, conjuntos ou até mesmo algoritmos partindo de
problemas particulares para problemas genéricos, ou seja, por intermédio de uma
regra pode-se calcular qualquer termo em função do(s) antecessor(es)
imediatos(s);
• As relações de recorrência são compostas por duas partes importantes: a(s)
condição(ões) inicial(is) que deve(m) ser conhecida(s) e a equação de recorrência
que é a regra que permitirá calcular os próximos termos em função dos
antecessores;
• A equação de recorrência não pode definer sequências sem as condições iniciais,
isto é, não é uma relação de recorrência.
Definição por Recorrência:
• Para resolver esses problemas recorremos a outros recursos: as recursões ou
recorrências. A principal ideia por trás das recorrências é expressar uma
quantidade �� em função de quantidades anteriores ����, ����, … , ��.
• Uma sequência é definida recursivamente se ela for dada por uma regra
(recorrência) que permite calcular um termo qualquer por meio de um ou mais
termos anteriores. Por exemplo: Progressão Aritmética, Progressão Geométrica,
potências com expoente maior do que 1, como, por exemplo:
1. Progressões Aritméticas: 	� = 	��� + �;
2. Progressões Geométricas: 	� = 	���
;
Exemplos por Recorrência:
1. A sequência (��) dos números naturais ímpares 1,3,5,7, … pode ser
definida por ���� = �� + 2 � ≥ 1 , com �� = 1 . Assim, �� = 2� − 1 para
todo � ∈ ℕ é solução dessa recorrência.
2. Qualquer Progressão Aritmética (��) de razão � e primeiro termo 	
pode ser definida por ���� = �� + � � ≥ 1 , com �� = 	.
3. Qualquer Progressão Geométrica (��) de razão 
 e primeiro termo 	
pode ser definida por ���� = 
�� (� ≥ 1), com �� = 	.
4. Define-se o fatorial �! de um número natural � como:1! = 1, � (� + 1)! = �! · (� + 1).
O que é uma sequência:
Uma sequência, como sugere o nome, é uma “coleção de elementos” de
natureza qualquer, ordenados. Na verdade, trata-se apenas de elementos
de um conjunto etiquetados com os números naturais.
O que é uma sequência:
• Etiquetar com os números naturais os elementos de um conjunto A,
significa dar uma função: 	: ℕ → !� → 	(�)
• A definição formal de uma sequência em um conjunto A é apenas uma
função 	 de ℕ em !.
• Como uma função é dada quando se conhece a imagem de todos os
elementos do seu domínio, uma sequência a pode ser representada
como: 	 1 , 	 2 , … , 	 � , …
• ou ainda, denotando 	(�) por 	� , podemos representá-la por:	�: 	�, 	�, … , 	�, …
Propriedades da potência:
• Seja a um elemento de um conjunto A munido de uma multiplicação
sujeita às leis básicas da aritmética. Vamos definir as potências 	� , com� ∈ ℕ, por recorrência.
• Ponhamos 	� = 	. Supondo 	� definido, defina	��� = 	� ∗ 	
• Vamos estabelecer, por meio de indução, as propriedades usuais das
potências.
• Sejam 	, # ∈ ! e $, � ∈ ℕ. Então:
1. 	% ∗ 	� = 	��%
2. 	% � = 	%�
3. 	 ∗ # � = 	� ∗ #�
	% ∗ 	� = 	%��
1.	% ∗ 	� = 	��%
Hip: 	% ∗ 	� = 	��%
Tese: 	%����
Fixemos 	 ∈ ! e $ ∈ ℕ, arbitrariamente. Demonstremos a propriedade por
indução sobre �:
Para � = 1, a propriedade é válida, pois, pelas definições,	% ∗ 	� = 	% ∗ 	 = 	%��
Por outro lado, supondo que 	% ∗ 	� = 	��%, temos que:
	% ∗ 	��� = 	 ∗ 	� ∗ 	 = 	% ∗ 	� ∗ 	 = 	%����
prova a nossa propriedade.
	% � = 	%�
2. 	% � = 	%�
Hip: 	% � = 	%�
Tese: 	%∗ ���
Fixemos 	 ∈ ! e $ ∈ ℕ, arbitrariamente. Demonstremos a propriedade por
indução sobre �:
Para � = 1, a propriedade é válida, pois, pelas definições,	% � = 	%
Por outro lado, supondo que 	% � = 	%�, temos que:
	% ��� = 	% � ∗ 	% = 	%� ∗ 	% = 	%��% = 	%∗ ���
prova a nossa propriedade
	 ∗ # � = 	� ∗ #�
3. 	 ∗ # � = 	� ∗ #�
Hip: 	 ∗ # � = 	� ∗ #�
Tese: 	��� ∗ #���
Fixemos 	 ∈ ! e $ ∈ ℕ, arbitrariamente. Demonstremos a propriedade por
indução sobre �:
Para � = 1, a propriedade é válida, pois, pelas definições,	 ∗ # � = 	 ∗ #
Por outro lado, supondo que 	 ∗ # � = 	� ∗ #�, temos que:
	 ∗ # ��� = 	 ∗ # � ∗ 	 ∗ # � = 	� ∗ #� ∗ 	 ∗ # = 	��� ∗ #���
prova a nossa propriedade
Provar que 3 divide 5� + 2 · 11�:
• Vamos provar que 3 divide 5� + 2 · 11� , nos inteiros, para todo � ∈ ℕ.
• De fato, para � = 1, temos que 3 divide 5� + 2 ∗ 11� = 27.
• Suponha, agora, que, para algum � ≥ 1, saibamos que 3 divide 5� + 2 ∗11�. Logo, existe um número inteiro 	 tal que
5� + 2 ∗ 11� = 3	
• Para � + 1, temos: 5��� + 2 ∗ 11��� = 5 ∗ 5� + 2 ∗ 11 ∗ 11� =5 ∗ 5� + 5 ∗ 2 ∗ 11� − 5 ∗ 2 ∗ 11� + 2 ∗ 11 ∗ 11�5 ∗ 5� + 2 ∗ 11� + 2 ∗ (11 ∗ 11� − 5 ∗ 11�)= 5 ∗ 5� + 2 ∗ 11� + 6 ∗ 2 ∗ 11'
• O 6 ∗ 2 ∗ 11' é divisivel por 3 e 5 ∗ 5� + 2 ∗ 11� é divisivel por 3, por
hipotese de indução.
Provar que 3 divide 5� + 2 · 11�:
• Cujo segundo membro é divisível por 3 por ser igual a 3 ∗ (5	 + 4 · 11� )
• Assim, provamos que 3 divide 5��� + 2 ∗ 11��� , o que, acarreta que 3
divide 5� + 2 ∗ 11�, para todo número natural �.
Como provar que a desigualdade 2� > )* é verdadeira para todo 
valor de � natural maior do que ou igual a 5?
• Fazemos isso baseados na seguinte pequena generalização:
• Seja + � uma sentença aberta sobre ℕ, e seja 	 ∈ ℕ. Suponha que:
1. +(	) é verdadeira, e
2. Qualquer que seja � ∈ ℕ, com � ≥ 	 , sempre que +(�) é verdadeira,
segue-se que + � + 1 é verdadeira.
Então, +(�) é verdadeira para todo número natural � ≥ 	.
Como provar que a desigualdade 2� > )* é verdadeira para todo 
valor de � natural maior do que ou igual a 5?
• Vamos mostrar que a desigualdade na sentença aberta +(�) ∶ 2� > �� é
verdadeira, para todo número natural � ≥ 5.
• Note que +(1) ∶ 2� > 1� é verdadeira, +(2) ∶ 2� > 2� é falsa, +(3) ∶ 2. > 3� é falsa e +(4) ∶ 2/ > 4� é falsa. Tudo isso não importa, pois queremos
verificar a veracidade dessa desigualdade para � ≥ 5.
• De fato, temos que +(5) ∶ 20 > 5� é verdadeira. Seja � ≥ 5 tal que 2� > �� .para n + 1 temos: 2��� > � + 1 �.
Como provar que a desigualdade 2� > )* é verdadeira para todo 
valor de � natural maior do que ou igual a 5?
• Transitividade da desigualdade (rascunho):2��� > � + 1 �2��� > �� + 2� + 12��� > 2�� > �� + 2� + 1
Precisamos provar que: 2�� > �� + 2� + 1�� > 2� + 1�� − 2� > 1� � + 2 > 1
Isso é verdade para � ≥ 5.
Progressões:
• Iremos agora, usando recorrência, definir Progressões Aritméticas e
Progressões Geométricas:
Exemplo: Uma Progressão Aritmética (P.A.) é uma sequência de números
(	�) tal que, a partir do segundo termo, cada termo 	� é igual ao anterior	��� somado a um número fixo � chamado de razão.
Método da galinha:
• A indução empírica foi batizada, de modo irônico, pelo matemático, filósofo e
grande humanista inglês do século passado, Bertrand Russel (1872-1970), de
indução galinácea, com base na seguinte historinha:
• Havia uma galinha nova no quintal de uma velha senhora. Diariamente, ao
entardecer, a boa senhora levava milho às galinhas. No primeiro dia, a galinha,
desconfiada, esperou que a senhora se retirasse para se alimentar. No segundo
dia, a galinha, prudentemente, foi se alimentando enquanto a senhora se
retirava. No nonagésimo dia, a galinha, cheia de intimidade, já não fazia caso da
velha senhora. No centésimo dia, ao se aproximar a senhora, a galinha, por
indução, foi ao encontro dela para reclamar o seu milho. Qual não foi a sua
surpresa quando a senhora pegou-a pelo pescoço com a intenção de pô-la na
panela.
Progressões:
• Portanto, é dado o primeiro termo 	� e define-se recorrentemente:	� = 	��� + � se � ≥ 2.
• Para achar uma fórmula fechada para o termo de ordem � da sequência, observe
que: 	� = 	� + �, 	. = 	� + � = 	� + 2�, 	/ = 	. + � = 	� + 3�
• Pelo “método da galinha” de Bertrand Russel, já podemos adivinhar os próximos 
termos: 	0 = 	/ + � = 	� + 4�, 	7 = 	� + 5�, … , 	� = 	� + � − 1 �, …
• Portanto, parece plausível que a fórmula para o termo geral de uma P.A. de
primeiro termo 	� e razão � seja	� = 	� + � − 1 �, para todo� ∈ ℕ
Progressões:
• Vamos agora demonstrar essa fórmula por indução.
Hip: 	� = 	� + � − 1 ∗ �
Tese:	��� = 	� + ��
• Inicialmente, observe que a fórmula é verdadeira para � = 1, pois ela se reduz à
igualdade 	� = 	�.
• Suponha agora que a fórmula seja correta para algum � ∈ ℕ; isto é, que 	� = 	� + (� − 1)�. Temos que:	��� = 	� + � = 	� + � − 1 � + � = 	� + ��
• O que mostra que a fórmula é verdadeira para � + 1. Portanto, ela é
correta para todo � ∈ ℕ.
Progressões:
• Agora, nos propomos a achar uma fórmula para a soma:8� = 	� + 	� + ⋯ + 	�
dos n primeiros termos de uma P.A. (	�)
• Vamos usar, para isso, o método de Gauss:
• Somando a igualdade acima, membro a membro, com ela mesma,
porém com as parcelas do segundo membro em ordem invertida, temos:
A soma (	� + 	�) se repete � vezes:
• Daí, segue-se que 28� = 	� + 	� ∗ � e, portanto,
8� = 	� + 	� ∗ �2
Progressões:
• Uma Progressão Geométrica (P.G.) é uma sequência de números (	�) tal que, a
partir do segundo termo, cada termo 	� é igual ao anterior 	��� multiplicado por
um número fixo 
 chamado de razão.
• Portanto, é dado o primeiro termo 	� e define-se recorrentemente	� = 	��� ∗ 
, se � ≥ 2.
• Para achar uma fórmula fechada para o termo de ordem � da sequência, observe 
que:
• 	� = 	�
, 	. = 	�
 = 	�
�, 	/ = 	.
 = 	�
., 	0 = 	/
 = 	�
/ 
• Novamente, pelo “método da galinha” de Bertrand Russel, podemos adivinhar os 
próximos termos: 	7 = 	�
0, 	: = 	�
7, … , a' = a�q'��, …
Portanto, é plausível que a fórmula para o termo geral de uma P.G. de primeiro termo 	� e razão q seja 	� = 	�
���, para todo � ∈ ℕ.
Progressões:
• Vamos demonstrar essa fórmula por indução. Inicialmente, observe que a fórmula
é verdadeira para � = 1, pois ela se reduz à igualdade 	� = 	�.
• Hip: 	� = 	�
���
• Tese:	��� = 	�
�
• Suponha, agora, que a fórmula seja correta para algum � ∈ ℕ,isto é, que 	� = 	�
���. Multiplicando por q ambos os lados dessa igualdade, segue que
	��� = 	�
 = 	�
���
 = 	�
�
• o que mostra que a fórmula é correta para � + 1. Portanto, ela é correta para todo� ∈ ℕ
Progressões:
• Vamos, a seguir, achar uma fórmula para a soma 8� dos primeiros termos de uma
P.G.
• Escreva: 8� = 	� + 	�
 + 	�
� + ⋯ + 	�
���
• Note que: 
8� = 	�
 + 	�
� + ⋯ + 	�
��� + 	�
�
8� = 8� − 	� + 	�
�
8� − 8� = 	�
� − 	�8� 
 − 1 = 	�
� − 	�
8� = 	�
� − 	�
 − 1
Portanto,
8� = 	�
� − 	�
 − 1 =
	�
 − 	�
 − 1
Exercícios:
• Ache uma fórmula fechada para a soma 2 + 4 + · · · + 2�:
• Podemos definir a sequência (2,4,6, … , 2�) como progressão aritmética com 	� = 2 e	� = 2�, que tem como soma é:
8� = 	� + 	� ∗ �2
8� = 2 + 2� ∗ �2
8� = 2� + 2�
�
2
8� = 2 ∗ (� + �
�)
28� = � + ��
Exercícios:
• Ache uma fórmula fechada para a somas 2 + 4 + · · · + 2�
• Podemos definir a sequência (2,4,8, … , 2�) como progressão aritmética com 	� = 2,q = 2 e 	� = 2�, temos que a soma é:
8� = 	�
 − 	�
 − 1
8� = 2
� ∗ 2 − 2
2 − 18� = 2 ∗ 2� − 2
Exercícios:
• Uma vitória régia encontra-se em um tanque de água. Sabendo que ela dobra de
área a cada dia e que, no final de 20 dias, ocupa toda a superfície do tanque, em
qual dia ela ocupará a metade da superfície do tanque?
Exercícios:
• Em uma cidade de 5.000 habitantes, alguém resolve espalhar um boato.
Considerando que, a cada 10 minutos, uma pessoa é capaz de contar o caso para 3
pessoas desinformadas, determine em quanto tempo toda a cidade fica
conhecendo o boato.
• 1,3,9,27, …
• 	� = 1 
 = 3 ?� = 5000
8� = 	� ∗ (
� − 1)

 − 1
5000 = 1 ∗ (3� − 1)3 − 13� − 1 = 100003� = 9999� ≅ 8,38
Aproximadamente 83 minutos
Recorrência, operações nos naturais e 
relação de ordem.
Apresentação: Johnattan B. Prates
Adição nos naturais:
• Definição: (Adição em ℕ) Seja ?: ! → ! a função dada pelo axiomas de Peano.
Dados $, � ∈ ℕ, sua soma $ + � ∈ ! é definida por$ + � = ?�($)
• A definição diz que somar $ com � é tomar o natural $ e iterá-la � vezes. Da
definição de soma e (1) temos,$ + 1 = ?� $ = ?($)
Definição: B $ + 0 = $$ + ? � = ?($ + �)
Isto é, fixado $, se C = 0, $ + C = $ e se C ≠ 0, C = ?(�) para algum � ∈ !, daí $ + C = $ + ?(�) = ?($ + �)
Ou ainda, $ + ? ? 0 = ? $ + ? 0 = ?(? $ ),
E assim por diante. Esta é a ideia intuitiva que iremos formalizar a seguir utilizando o
Princípio da Indução, que mostra que $ + � está definido para todos $, � ∈ !.
Adição nos naturais:
• Preposição: A soma $ + � está definida para todo par $, � E� !.
Demonstração: De fato, vamos definir o conjunto 8% = {� ∈ !|$ + � �?Há E�JK�KE	}, para
cada $ ∈ ! fixado arbitrariamente.
1. $ + 0 está definido, portanto, 0 ∈ 8%.
2. Seja M ∈ 8%, isto é, $ + M está definido. Temos que $ + ? M = ?($ + M) está definido,
logo ?(M) ∈ 8%.
Logo, por indução, 8% = !. Como $ é arbitrário, 8% = ! para todo $ ∈ !. Sendo assim,$ + � está definida para todo par $, � E� !N!, o que significa que a adição é, de fato,
uma operação em !.
Adição nos naturais:
• Introduziremos agora a notação para os números naturais que é conhecida desde
o ensino básico.
• Definição: Indica-se por 1 e lê-se um o elemento de ! que é sucessor de 0, ou seja,1 = ? 0 .
• Preposição: Para todo $ ∈ !, tem-se ?($) = $ + 1 e ?($) = 1 + $. Portanto $ + 1 = 1 + $.
Provemos as duas igualdades:
Temos que $ + 1 = $ + ?(0) = ?($ + 0) = ?($), ou seja, $ + 1 = ?($)
Adição nos naturais:
• Consideremos agora o conjunto O = {$ ∈ ! | ?($) = 1 + $} e provemos por
indução que O = !:
1. Claramente 1 + 0 = 1 = ?(0), sendo assim, ?(0) = 1 + 0 e portanto, 0 ∈ O.
2. Seja, agora, $ ∈ O, isto é, ?($) = 1 + $. Daí ?(1 + $) = ?(?($)) e como ?(1 + $) = 1 + ?($), obtemos 
P� ?(?($)) = 1 + ?($) e, portanto, ?($) ∈ O.
Sendo assim, O = !.
Adição nos naturais:
• Já temos as notações 0 e 1 = s(0). Vamos definir, agora, a continuação:
?(1) = 2 (EQK?), ?(2) = 3 (H�ê?), ?(3) = 4 (
P	H�Q), ?(4) = 5 (SK�SQ) 
• E assim sucessivamente. Esta é a notação indo-arábica de base dez para os
elementos de ! . Dessa forma, A contém o seguinte conjunto:{0, ?(0), ?(?(0)), ?(?(?(0))), . . . } = {0, 1, 2, 3, . . . }.
Adição nos naturais:
• O teorema seguinte mostra que os axiomas de Peano formalizam a ideia intuitiva
do conjunto dos números naturais, isto é, A não contém elementos além desses:
• Teorema: ! = {0, 1, 2, 3, . . . }
• Demonstração. Seja ℕ = {0, 1, 2, 3, . . . } subconjunto de !. Verifiquemos por indução
que ℕ = !:
1. Por construção 0 ∈ N;
2. Novamente por construção,ℕ contém o sucessor de qualquer elemento contido
nele, ou seja, se � ∈ ℕ, então ?(�) ∈ ℕ. Logo,ℕ = !.
Adição nos naturais:
• Definição: Chamaremos este conjunto ! de Conjunto do Números Naturais e
denotaremos, a partir daqui, por ℕ . Utilizando a notação anterior, temos as
seguintes adições em ℕ:
1. 1 + 1 = ?(1) = 2; 2. 2 + 1 = ?(2) = 3; 3. 3 + 1 = ?(3) = 4; 4. 3 + 2 = 3 + ?(1) = ?(3 + 1) = ?(4) = 5; 5. 0 + 2 = 0 + ?(1) = ?(0 + 1) = ?(1 + 0) = ?(1) = 2.
Adição nos naturais:
• Vamos enunciar e demonstrar agora uma proposição que será fundamental para
a prova do próximo teorema.
• Proposição: Para todo $ ∈ ℕ, temos que $ + 0 = $ = 0 + $.
Demonstração. Por definição $ + 0 = $. Provemos agora que 0 + $ = $. De fato,
consideremos o conjunto !U = {$ ∈ ℕ| 0 + $ = $}.
1. Por definição 0 + 0 = 0, portanto 0 ∈ !U;
2. Suponhamos M ∈ !U, isto é, 0 + M = M e provemos que ?(M) ∈ !U. Com efeito, 0 + ?(M) = ?(0 + M) = ?(M), ou seja, ?(M) ∈ !U. Logo, por indução, concluímos que !U = ℕ.
Adição nos naturais:
• O seguinte teorema mostra as propriedades da adição que são admitidas
intuitivamente desde a escola.
• Teorema: Se $, � � C são números naturais arbitrários, temos que as seguintes
armações são verdadeiras:
1. Propriedade associativa da adição: $ + (� + C) = ($ + �) + C.
2. Propriedade comutativa da adição: � + $ = $ + �.
3. Lei do cancelamento da adição: $ + C = � + C ⇒ $ = �.
Propriedade associativa da adição:
1. Propriedade associativa da adição: $ +(� + C) = ($ + �) + C.
Para esta prova, consideremos o conjunto !(%,�) = {C ∈ ℕ| $ + (� + C) = ($ + �) + C} com $ � � naturais fixados arbitrariamente. Vamos aplicar indução sobre este
conjunto:
a) Temos que $ + (� + 0) = $ + � = ($ + �) + 0, logo, 0 ∈ !(%,�) ;
b) Suponhamos que M ∈ !(%,�) , isto é, $ + (� + M) = ($ + �) + M. Agora, provemos
que ?(M) ∈ !(%,�) . De fato,($ + �) + ?(M) = ?(($ + �) + M), e por hipótese,
($ + �) + ?(M) = ?($ + (� + M)), daí, por definição da soma dos naturais,
($ + �) + ?(M) = $ + ?(� + M), o que significa, por definição da soma dos naturais
($ + �) + ?(M) = $ + (� + ?(M)), logo, ?(M) ∈ ! %,� .
Propriedade comutativa da adição:
2. Propriedade comutativa da adição: � + $ = $ + �.
Para esta prova, consideremos o conjunto !� = {$ ∈ ℕ| � + $ = $ + �}, com �
fixado arbitrariamente e provemos que ℕ = !�
Temos, pela proposição anterior, que � + 0 = 0 + �, portanto, 0 ∈ !�;
Suponhamos que M ∈ !�, ou seja, � + M = M + �, e provemos que ?(M) ∈ !�. De fato,� + ?(M) = ?(� + M) = ?(M + �) = (M + �) + 1 , daí, pelo primeiro item deste
teorema, a propriedade associativa:
� + ?(M) = M + (� + 1), e por proposição anterior (n + 1 = 1 + �), obtemos
� + ?(M) = M + (1 + �) = (M + 1) + � e assim,
� + ?(M) = ?(M) + �, o que significa que ?(M) ∈ !�
Concluímos assim, por indução, que !� = ℕ.
Assoc.
Lei do cancelamento da adição:
Consideremos o conjunto !($, �) = {C ∈ ℕ| $ + C = � + C ⇒ $ = �}. Provemos
agora que !%,� = ℕ.
Temos que 0 ∈ ! %,� , CQK? $ + 0 = � + 0 ⇒ $ = �, pela proposição.
Suponhamos M ∈ ! %,� , isto é, $ + M = � + M ⇒ $ = �. Temos que$ + ?(M) = � + ?(M) ⇒ ?($ + M) = ?(� + M) , def. soma dos naturais⇒ ($ + M) + 1 = (� + M) + 1 , Associativa dos naturais e preposição (M + 1 = 1 + M)⇒ $ + (1 + M) = � + (1 + M) Associativa dos naturais⇒ $ + 1 + M = � + 1 + M ⇒ ? $ + M = ? � + M, por hipótese de indução⇒ ?($) = ?(�)⇒ $ + 1 = � + 1 ⇒ $ = � 
Logo, $ + ?(M) = � + ?(M) ⇒ $ = �, ou seja, ?(M) ∈ ! %,� . Desta forma, concluímos
que ! %,� = ℕ.
Multiplicação nos naturais:
• Assim como foi definida a adição, definiremos agora a operação que chamaremos
de multiplicação:
• Definição: Dado $ ∈ !, definimos recursivamente:
B $ ∗ 0 = 0$ ∗ � + 1 = $ ∗ � + $
• Ou seja, fixado $, se C = 0, $ · C = 0 e se C ≠ 0, C = � + 1, para algum � ∈ W, daí$ · C = $ · (� + 1) = $ · � + $.
• Para designar $ ∗ �, usaremos a notação de justaposição $�. Será enunciado e
provado, a seguir, um teorema com as propriedades da multiplicação, mas antes
disso, enunciaremos duas proposições que serão úteis para a demonstração de tal
teorema.
Multiplicação nos naturais:
• Preposição: Para todo $ ∈ ℕ, temos que 0 · $ = 0.
Demonstração: Consideremos o conjunto 8 = $ ∈ ℕ 0 ∗ $ = 0} e utilizemos indução
para mostrar que 8 = ℕ.
1. 0 · 0 = 0 por definição, portanto, 0 ∈ ℕ;
2. Suponhamos que M está em 8, ou seja, 0 · M = 0 e provemos que ?(M) ∈ 8. De fato,
0 · ?(M) = 0(M + 1) = 0M + 0, por definição, e ainda, 0M + 0 = 0M = 0, por hipótese
de indução. Logo, 0 · ?(M) = 0, ou seja, ?(M) ∈ 8.
Dessa forma, concluímos que S = ℕ.
Def mult Prepo. $ + 0 = $ e def. mult. 
Multiplicação nos naturais:
• Preposição: Sejam $, � ∈ ℕ tais que $ + � = 0. Então $ = � = 0.
• Demonstração:
• Suponhamos � ≠ 0, isto é, � = ?(��) = �� + 1, para algum �� ∈ ℕ. Sabemos que
0 = $ + � = $ + (�� + 1) = ($ + ��) + 1 = ?($ + ��), pela associativa. O que é
um absurdo pois 0 não é sucessor de nenhum elemento de ℕ. Logo, � = 0, sendo
assim, $ + � = 0 ⇒ $ + 0 = 0 ⇒ $ = 0, como queríamos.
Assoc. adição nos ℕHip
Multiplicação nos naturais:
• Teorema: Sejam $, �, C ∈ ℕ, então são válidos os itens abaixo:
1. $� ∈ ℕ, isto é, a multiplicação é uma operação em ℕ;
2. Existe um elemento neutro multiplicativo: 1 · � = � · 1 = �;
3. Distributividade: $(� + C) = $� + $C e ($ + �)C = $C + �C;
4. Associatividade: $(�C) = ($�)C;
5. $� = 0 ⇒ $ = 0 QP � = 0;
6. Comutatividade: $� = �$
$� ∈ ℕ, isto é, a multiplicação é uma operação em ℕ; 
• Consideremos o conjunto 8% = {� ∈ ℕ | $� �?Há E�JK�KEQ} para $ ∈ ℕ fixado
arbitrariamente.
• $ · 0 = 0 está definido, logo, 0 ∈ 8%;
• Suponhamos M ∈ ℕ e provemos que ?(M) ∈ ℕ. De fato, $ · ?(M) = $(M + 1) = $M + $.
Por hipótese de indução $M está definido e, como visto na seção anterior, a soma
de quaisquer dois naturais também. Logo, $ · ?(M) = $M + $ está definido, o que
significa que ?(M) ∈ 8%.
• Sendo assim, por indução 8$ = ℕ. Como $ foi fixado arbitrariamente, a igualdade
vale para qualquer $ ∈ ℕ.
Def. mult. nos ℕ
Existe um elemento neutro multiplicativo: 1 · � = � · 1 = �:
• Temos que � · 1 = �(0 + 1), e por definição �(0 + 1) = � · 0 + � = �, logo, � · 1 = �.
Agora, para mostrar que 1 · � = � para todo � ∈ ℕ, consideremos o conjunto 8 = {� ∈ ℕ| 1 · � = �}, e mostremos que ℕ = 8.
• Temos que 1 · 0 = 0, por definição, logo, 0 ∈ 8;
• Suponhamos que M ∈ 8, ou seja, 1 · M = M. Sabemos que 1 · (M + 1) = 1 · M + 1,
daí, por hipótese de indução, 1 · (M + 1) = M + 1. Portanto, M + 1 ∈ 8.
• Sendo assim, por indução 8 = ℕ.
Def. mult. nos ℕ
Distributividade: $(� + C) = $� + $C e $ + � C = $C + �C:
• Sejam m, n naturais fixados arbitrariamente e usemos indução sobre C . Seja!%,� = {C ∈ ℕ| $(� + C) = $� + $C}.
• De fato, 0 ∈ !%,� pois $(� + 0) = $� e $� + $ · 0 = $�, ou seja, $(� + 0) = $� +$ · 0;
• Mostremos agora que, se M ∈ !%,�, isto é, $(� + M) = $� + $M, então (M + 1) ∈ !%,�.
Com efeito, $ � + M + 1 = $ � + M + 1 = $ � + M + $ = $� + $M + $ =
 $� + ($M + $) = $� + ($(M + 1)). Todas estas igualdades se justificam com base
em propriedades estabelecidas anteriormente. Sendo assim, (M + 1) ∈ !%,�.
• Assim, concluímos, por indução, que !%,� = ℕ.
Assoc. adição nos ℕ Def. mult. nos ℕ Def. mult. nos ℕ Assoc. adição nos ℕ
Def. mult. nos ℕ
Associatividade: $(�C) = ($�)C; 
• Novamente, consideremos $, � ∈ W fixados arbitrariamente e apliquemos
indução sobre C. Seja 8%,� = {C ∈ ℕ| $(�C) = ($�)C}: 
• $(� · 0) = $ · 0 = 0 � ($�) · 0 = 0, logo, $(� · 0) = ($�) · 0. Assim, 0 ∈ 8%,�;
• Suponhamos que M ∈ 8%,� , isto é, $(�M) = ($�)M . Consideremos as seguintes
igualdades:
• $(�(M + 1)) = $(�M + �) = $(�M) + $� = ($�)M + $� = ($�)(M + 1). 
• Dessa forma, M + 1 ∈ 8%,�.
• Logo, 8%,� = ℕ.
Def. mult. nos ℕ Dist. mult. nos ℕ Hip Dist. mult. nos ℕ
$� = 0 ⇒ $ = 0 QP � = 0; 
• Seja $� = 0. Suponhamos � ≠ 0. Então � = �� + 1 para algum �� �$ ℕ. Assim,
$� = 0 ⇒ $(�� + 1) = 0 ⇒ $�� + $ = 0, daí, por proposição anterior ($ + � = 0.
Então $ = � = 0), $�� = $ = 0. Da mesma forma, supondo $ ≠ 0, concluímos que� = 0. Como queríamos.
Def. mult. nos ℕHip
Comutatividade: $� = �$
• Suponhanhamos 8% = {� ∈ ℕ| $� = �$}, para um $ ∈ ℕ fixados arbitrariamente.
Mostremos que 8% = ℕ:
• Por definição, $ · 0 = 0 e, pela proposição anterior, 0 · $ = 0, logo, $ · 0 = 0 · $,
isto é, 0 ∈ 8%;
• Suponhamos M ∈ 8%, ou seja, $M = M$. Temos que
$(M + 1) = $M + $ = M$ + $, por hipótese de indução, e ainda, M$ + $ = (M + 1)$. Sendo assim, $(M + 1) = (M + 1)$, que significa M + 1 ∈ 8%.
• Logo, por indução, 8% = ℕ . Como m é arbitrário, a igualdade vale para todo$ �$ ℕ.
Def. mult. nos ℕ Hip Dist. mult. nos ℕ
Relação de ordem em N:
• A ideia intuitiva que trazemos desde a escola, de que 0 é menor que 1, que é
menor que 2 e assim sucessivamente, vem da relação de ordem que existe nos
naturais, que nos permite comparar os números deste conjunto, formalizando a
ideia intuitiva.
• Definição: Seja X uma relação binária em um conjunto não vazio ! e�, Y, Z elementos quaisquer de !. Dizemos que X é uma relação de ordem em !
quando satisfaz as seguintes condições:
1. Reflexividade:�X�;
2. Antissimetria: se �XY � YX�, então � = Y;
3. Transitividade: se �XY � YXZ, então �XZ
• Dizemos ainda que tal ! , diferente de vazio e munido de uma relação X , é
chamado de conjunto ordenado
Relação de ordem em N:
• Vamos definir agora uma relação de ordem em ℕ através da operação adição, o
que o torna um conjunto ordenado.
• Definição: Dados $, � ∈ ℕ, dizemos que $X� se existir C ∈ W tal que � = $ + C
• Exemplo:
1. Temos que 2X7, pois 7 = 2 + 5;
2. 4X4, dado que 4 = 4 + 0
Relação de ordem em N:
• Preposição: A relação X da definição do slide anterior é uma relação de ordem emℕ.
• De fato, vejamos que valem as propriedades reflexiva, antissimétrica e transitiva:
• Reflexiva: dado $ ∈ W, claramente $ = $ + C, para C = 0 ∈ W, logo, $X$;
• Antissimétrica: sejam $, � ∈ W, $X� � �X$, isto é, existem C, 
 ∈ W, tais que � = $ + C e $ = � + 
. Substituindo a primeira igualdade na segunda, obtemos,
• $ = ($ + C) + 
 ⇒ $ = $ + (C + 
), o que significa que C + 
 = 0, assim, pela
proposição já mostrada anterior, C = 
 = 0, logo, $ = �.
Assoc. adição nos ℕ
Relação de ordem em N:
• 3. Transitiva: Sejam [, $, � ∈ W, [X$ � $X�, ou seja, existem C, 
 ∈ ℕ tais que $ = [ + C � � = $ + 
. Substituindo a primeira igualdade na segunda, obtemos, � = ([ + C) + 
, ou ainda, � = [ + (C + 
). Temos que C + 
 = � ∈ ℕ, portando, podemos
reescrever a última equação como segue: � = [ + �. Sendo assim, concluímos
que, [X�.
• Logo, a relação X é de ordem em ℕ, como queríamos.
Relação de ordem em N:
• Definição: Sejam $, � ∈ ℕ e X a relação da definição de relação. Se $X�, diremos
que $ é menor ou igual a � e passaremos a escrever $ ≤ � no lugar de X, ou seja,$ ≤ � significará $X�.
• Seja (!, +) um grupo abeliano e ≤ uma relação de ordem em ! que satisfaz 	 ≤ # ⇔ # = 	 + S para algum S ∈ !. Denotamos por A∗ = ! \{0}, O� = {� ∈ O | � ≥ 0} e O� = {� ∈ O | � ≤ 0}. 
• Seguem algumas variações desta notação:
• $ ≤ � pode ser escrito como � ≥ $. Leremos � é maior ou igual a $; •
• Se $ ≤ �, mas $ ≠ �, escrevemos $ < � e dizemos que $ é menor que �;
• $ < � pode ser escrito como � > $ e leremos � é maior que $.
Relação de ordem em N:
• Definição: Sejam $, � ∈ W, dizemos que $ é menor do que �, o que denotamos
por $ < �, se, e somente se, existe C ∈ W tal que � = $ + C.
• Preposição: (Propriedades da relação de ordem). Sejam $, �, C ∈ W. A relação <
tem as seguintes propriedades:
• (1) Transitividade. $ < � � � < C ⇒ $ < C.
• (2) Tricotomia. Dados $, � ∈ W, uma e apenas uma das seguintes alternativas é
valida ou $ = � QP $ < � QP � < $.
• (3) Monotonicidade da adição. $ < � ⇒ $ + C < � + C, para todo C ∈ W.
• (4) Monotonicidade da multiplicação. $ < � ⇒ $ · C < � · C, para todo C ∈ W.
(1) Transitividade. $ < � � � < C ⇒ $ < C
• Existem ��, �� ∈ ℕ tal que $ + �� = � e � + �� = C. Assim, existe (�� + ��) ∈ ℕ tal que
• $ + �� + �� = $ + �� + �� = � + �� = C. Portanto, $ < C.
Assoc. adição nos ℕ
Lei da Tricotomia dos Naturais:
• Preposição: (Lei da Tricotomia dos Naturais). Para quaisquer $, � ∈ ℕ temos que
uma, e somente uma, das relações seguintes ocorre:1. $ < �2. $ = �3. $ > �
Demonstração: Vamos mostrar primeiro que duas delas não podem ocorrer
simultaneamente e depois mostrar que obrigatoriamente uma delas deve ocorrer.
Lei da Tricotomia dos Naturais:
1. $ < �2. $ = �3. $ > �
• Claramente, 1 e 2, não podem ocorrer simultaneamente, pois, teríamos � = $ + C com C ∈ ℕ∗ e $ = � , daí, substituindo a segunda igualdade na primeira,
obteríamos que, $ = $ + C e disso, C = 0, o que é uma contradição, pois, C ∈ ℕ∗.
Da mesma forma, 2 e 3 não podem ocorrer juntas.
• Suponhamos agora que 1 e 3 ocorram ao mesmo tempo, isto é, n = $ + C � $ = � + 
, com C, 
 ∈ ℕ∗. Substituindo a primeira igualdade na segunda, obtemos, $ = ($ + C) + 
 ou ainda, $ = $ + (C + 
), que nos remete a 0 = C + 
 . Pela
proposição anterior, concluímos que C = 
 = 0, o que é uma contradição, poisC, 
 ∈ ℕ∗.
Lei da Tricotomia dos Naturais:
Mostremos esta parte por indução. Seja a = {� ∈ ℕ| � = $ QP � > $ QP � < $} com$ sendo um natural qualquer.
• Temos que 0 ∈ a, pois 0 = $ ou 0 ≠ $. Se 0 ≠ $, pela proposição anterior, 0 < $.
• Suponhamos agora que M ∈ a, isto é, M = $ QP M > $ QP M < $. Analisemos os
três casos:a) M = $ ⇒ M + 1 = $ + 1 ⇒ M + 1 > $ ⇒ M + 1 ∈ a;b) M > $ ⇒ M = $ + C para C ∈ ℕ∗ ⇒ M + 1 = $ + C + 1 ⇒ M + 1 = $ + C + 1 ⇒ M + 1 > $ ⇒ M + 1 ∈ a;c) M < $ ⇒ $ = M + C para C ∈ ℕ∗. Como C ≠ 0, temos que C = C� + 1 com C� ∈ ℕ.
Logo, $ = M + C ⇒ $ = M + (C� + 1) ⇒ $ = (M + 1) + C� . Se C� = 0 teremos$ = M + 1 � CQ�H	�HQ, M + 1 ∈ a. Se C� ≠ 0, então, M + 1 < $, logo, M + 1 ∈ a.
Sendo assim, concluímos que, se M ∈ a, então M + 1 ∈ a.
Logo, por indução, W = a.
(3) Monotonicidade da adição. $ < � ⇒ $ + C < � + C, para todo C ∈ W.
• Existe 
 ∈ W tal que $ + 
 = �
• $ + C + 
 = $ + 
 + C = � + C.
• Ou seja, $ + C < � + C
Assoc. adição nos ℕ
(4) Monotonicidade da multiplicação. $ < � ⇒ $ · C < � · C, para todo C ∈ W.
• Existe 
 ∈ W tal que $ + 
 = �
• $ ∗ C + 
 ∗ C = $ + 
 ∗ C = � ∗ C
• Ou seja, $ ∗ C < � ∗ C
Relação de ordem em N:
Concluímos da relação de ordem em N que, se 	 ∈ ℕ, então, 	 < ?(	), pois ?(	) = 	 + 1. Dessa forma 0 < 1 < 2 < 3 < . . .. Notemos, ainda, que não existem naturais entre	 � ?(	), para todo 	 ∈ ℕ, pois 	 < � < 	 + 1 implicaria, pelo teorema anterior, que	 + 1 ≤ � < 	 + 1, ou seja, 	 + 1 < 	 + 1, o que não pode acontecer.