Definição 10.1 Os números naturais são definidas usando os axiomas de Peano.
(P1): O número \(1\) é natural.
(P2): Todo número natural \(n\) tem um sucessor denotado por \(S(n)\).
(P3): O número \(1\) não é sucessor de nenhum natural.
(P4): Se \(n,m\) são naturais tais que \(S(n)=S(m)\), então \(n=m\).
(P5): Seja \(X\) é um conjunto de números naturais tal que
\(1\in X\); e
se \(n\in X\), então \(S(n)\in X\).
Então temos que \(X\) contem todos os números naturais.
Note que \(1\) é um número natural notável, pois ele é o “primeiro” número natural. Os outros naturais são \[
2=S(1),\quad 3=S(2)=S(S(1)),\quad 4=S(3)=S(S(2))=S(S(S(1))), \quad \mbox{etc}.
\] O Axioma 5. diz que todo número natural pode ser obtido continuando este processo. O conjunto dos números naturais é denotado por \(\N\). Note que o nosso conceito de naturais começa com o número \(1\) e o número zero não é considerado (por nos) natural.
10.2 O Princípio da Indução
O Axioma 5. é conhecido como o Axioma da Indução ou Princípio da Indução. Este axioma é útil se queremos provar alguma afirmação sobre números naturais. Assuma por exemplo que \(P(n)\) é um predicato válido para o conjunto \(\N\) dos naturais (veja a Definição 4.1). Para provar que \(P(n)\) é verdadeira para todo \(n\in\N\), é suficiente provar que
\(P(1)\) é verdadeira; e
se \(P(n)\) é verdadeira para algum \(n\in\N\), então \(P(S(n))\) é também verdadeira.
Se denotamos \[
X=\{n\in\N\mid P(n)\mbox{ é verdadeira}\}
\] então temos pelo item 1. que \(1\in X\) e pelo item 2. que se \(n\in X\), então \(S(n)\in X\). Ora segue do Axioma da Indução que \(X=\N\). Ou seja, \(P(n)\) é verdadeiro para todo \(n\in \N\).
Vamos ilustrar este princípio por provar uma afirmação simples.
Lema 10.1 Se \(n\in\N\), então \(n=1\) ou \(n=S(n')\) com algum \(n'\in \N\).
Comprovação. O predicato que queremos provar é \[
P(n)\colon n=1\lor (\exists n'\in\N: n=S(n')).
\] Primeiro vamos provar que a afirmação é verdadeira quando \(n=1\). Este passo chama-se base da indução. Ou seja, precisamos provar \[
P(1)\colon 1=1\lor (\exists n'\in\N:1=S(n')).
\] Esta afirmação é claramente verdadeira, pois \(1=1\).
Para executar o item 2., nós assumimos que \(P(n)\) é verdadeira; ou seja \(n=1\) ou \(n=S(n')\) com algum \(n'\in\N\). Esta suposição chama-se hipótese da indução. Observe que nós não provamos que a \(P(n)\) é verdadeira, mas simplesmente assumimos isso. Depois no passo indutivo, provamos, usando a hipótese da indução, que \[
P(S(n))\colon S(n)=1\lor (\exists n'\in\N:S(n)=S(n'))
\] é verdadeira. Mas note que esta afirmação é verdadeira pois o segundo termo da disjunção é verdadeira tomando \(n'=n\).
10.3 Aritmética
Definição 10.2 Definimos duas operações entre números inteiros.
Primeiro defina a adição com as seguintes duas regras para todo \(n,m\in\N\):
(A1):\(n+1=S(n)\);
(A2):\(n+S(m)=S(n+m)\).
Defina a multiplicação com as seguintes duas regras para todo \(n,m\in\N\):
(M1):\(n\cdot 1=n\);
(M2)\(n\cdot S(m)=n\cdot m+n\).
Note que estas definições podem ser vistas como definições recursivas. O seguinte exemplo simples ilustra o uso destas regras.
Exemplo 10.1 Vamos calcular por exemplo que \(2+2=2\cdot 2=4\) usando a Definição 10.2. Primeiro, \[
2+2=2+S(1)=S(2+1)=S(S(2))=4.
\] Depois, \[
2\cdot 2=2\cdot S(1)=2\cdot 1+2=2+2=4.
\]
A afirmação \(2+2=4\) parece óbvia para quem cursou o ensino fundamental, mas, se nos perguntarmos “como se demonstra matematicamente que \(2+2=4\)?”, muita gente não saberia responder. A questão pode soar trivial, mas a busca por uma demonstração rigorosa nos leva ao cerne dos fundamentos da matemática. Uma das primeiras tentativas sistemáticas de axiomatizar a matemática foi o Principia Mathematica, de Bertrand Russell e Alfred North Whitehead, publicado entre 1910 e 1913. Famosamente, a demonstração de que \(1+1=2\) só aparece na página 379.
Os seguintes dois vídeos falam sobre o assunto.
Vamos provar primeiro alguma afirmações simples sobre as operações com os naturais.
Lema 10.2 As seguintes são verdadeiras para todo \(a\in\N\).
\(1+a=a+1=S(n)\);
\(1\cdot a=a\cdot 1=a\).
Comprovação.
Vamos usar indução.
Base da indução: provar que \(1+1=1+1=S(1)\). Isso segue da regra (A1).
Hipótese da indução (HI): assuma que \(1+a=a+1\) com algum \(a\in\N\).
Passo indutivo: precisa provar que \(1+S(a)=S(a)+1=S(S(a))\). Isso segue pois, usando regra (A1), temos que \[
S(a)+1=S(S(a)).
\] Agora, usando regra (A1) e (HI), obtemos que \[
1+S(a)=S(1+a)=S(a+1)=S(S(a)).
\] Portanto item 1. é verdadeiro para todo \(a\in\N\).
De novo, a prova segue indução.
Base da indução: provar que \(1\cdot 1=1\cdot 1 =1\). Isso segue da regra (A1).
Hipótese da indução (HI): assumimos que \(1\cdot a=a\cdot 1 =a\) para algum \(a\in\N\).
Passo indutivo: Provar que \(1\cdot S(a)=S(a)\cdot 1=S(a)\). De fato, \[
1\cdot S(a)=1\cdot a+1=a+1=S(a)=S(a)\cdot 1,
\] usando (M2), (HI), (A1), (M1).
Lema 10.3 As operações \(+\) e \(\cdot\) entre os números naturais satisfazem as seguintes propriedades para todo \(a,b,c\in\N\).
\((a+b)+c=a+(b+c)\) (associatividade da adição);
\(a+b=b+a\) (comutatividade da adição);
\((a+b)c=ac+bc\) (lei distributiva);
\((ab)c=a(bc)\) (associatividade da multiplicação);
\(ab=ba\); (comutatividade da multiplicação)
se \(a+c=b+c\), então \(a=b\) (lei cancelativa para adição).
Comprovação. Vamos provar apenas algumas destas afirmações. O resto é exercício.
Observe que a afirmação 1. contem \(3\) variáveis e podemos escolher qualquer para ser a variável da indução. Nós vamos fazer indução por \(c\).
Base da indução: \(c=1\). Neste caso precisa provar que \((a+b)+1=a+(b+1)\) para todo \(a,b\in\N\). De fato, \[
(a+b)+1=S(a+b)
\] e \[
a+(b+1)=a+S(b)=S(a+b).
\] Portanto, vale que \((a+b)+1=a+(b+1)\) para todo \(a,b\in\N\).
Hipótese de indução. Assuma que \((a+b)+c=a+(b+c)\) vale para algum \(c\in \N\) e para todo \(a,b\in\N\).
O passo indutivo. Precisa provar que \((a+b)+S(c)=a+(b+S(c))\) vale para todo \(c\in\N\). De fato, \[
(a+b)+S(c)=S((a+b)+c)=S(a+(b+c))=a+S(b+c)=a+(b+S(c)).
\]
Indução por \(b\). Base da indução: Provar para \(b=1\). Ou seja, \(a+1=1+a\). Mas isso segue do Lema 10.2.
Hipótese da indução: Assumir que \(a+b=b+a\) vale para todo \(a\in\N\) e algum \(b\in \N\).
Passo indutivo: Provar que \(a+S(b)=S(b)+a\) vale para todo \(a\in \N\). De fato, temos que \[\begin{align*}
a+S(b)&=S(a+b)=S(b+a)=b+S(a)=b+(a+1)\\&=b+(1+a)=(b+1)+a=S(b)+a.
\end{align*}\] Note que nesta conta usamos, (A2), (HI), (A2), (A1), a base da indução, associatividade, (A1).
Indução por \(c\).
Base da indução: Provar para \(c=1\). Ou seja, \((a+b)\cdot 1=a\cdot 1+b\cdot 1\). Mas isso segue da regra (M1) aplicando três vezes.
Hipótese da indução: Assumir que \((a+b)c=ac+bc\) vale para todo \(a,b\in\N\) e algum \(c\in \N\).
Passo indutivo: Provar que \((a+b)S(c)=aS(c)+bS(c)\). De fato, \[\begin{align*}
(a+b)S(c)&=(a+b)c+(a+b)=(ac+bc)+(a+b)\\&=((ac+bc)+a)+b=(ac+(bc+a))+b\\&=(ac+(a+bc))+b=((ac+a)+bc)+b\\&=(ac+a)+(bc+b)=aS(c)+bS(c).
\end{align*}\] Deixamos para o leitor identificar as regras que foram usadas em dada um dos passos na conta anterior.
Indução por \(c\).
Base da indução: Provar para \(c=1\). Ou seja, \((ab)\cdot 1=a(b\cdot 1)\). Mas isso segue da regra (M1).
Hipótese da indução: Assumir que \((ab)c=a(bc)\) vale para todo \(a,b\in\N\) e algum \(c\in \N\).
Passo indutivo: Precisa provar que \((ab)S(c)=a(bS(c))\) vale para todo \(a,b\in\N\). De fato, \[
(ab)S(c)=(ab)c+ab=a(bc)+ab=a(bc+b)=a(bS(c)).
\]
Indução por \(b\).
Base da indução: Provar para \(b=1\). Ou seja, \(a\cdot 1=1\cdot a\) para todo \(a\in\N\). Isso segue do Lema 10.2.
Hipótese da indução: Assumir que \(ab=ba\) algum \(b\in\N\) e todo \(a\in\N\).
Passo indutivo: Precisa provar que \(aS(b)=S(b)a\) para todo \(a\in\N\). De fato, \[
aS(b)=ab+a=ba+a=ba+1\cdot a=(b+1)a=S(b)a.
\]
Indução por \(c\).
Base da indução: Provar para \(c=1\). Ou seja, se \(a+1=b+1\), então \(b=c\). Assuma que \(a+1=b+1\). Isso implica por (A1) que \(S(a)=S(b)\). Ora, \(a=b\) segue do Axioma (P4).
Hipótese da indução: Assumir que \(a+c=b+c\) implica que \(a=b\) para todo \(a,b\in\N\).
Passo indutivo: Assuma que \(a+S(c)=b+S(c)\). Isso implica que \[
S(a+c)=a+S(c)=b+S(c)=S(b+c).
\] Ora, Axioma (P4) implica que \(a+c=b+c\) e a hipótese da indução implica que \(a=b\).
Observe que as afirmações do Lema 10.3 implicam também a lei distributiva \(a(b+c)=ab+ac\) e também a lei cancelativa que \(a+b=a+c\) implica \(b=c\).
Nós não definimos nem a subtração nem a divisão entre números naturais, pois o conjunto dos naturais não é fechado para estas operações. Portanto, elas não são consideradas operações destes números.
10.4 Ordenação
Tendo minerado as operações \(+\) e \(\cdot\) para os naturais e algumas das suas propriedades, a seguinte tarefa é definir a ordenação entre os naturais.
Definição 10.3 Sejam \(a,b\in\N\). Dizemos que \(a<b\) (\(a\) é menor que \(b\)) se \(b=a+c\) com algum \(c\in\N\). Dizemos que \(a\leq b\) (\(a\) é menor ou igual a \(b\)) se \(a=b\) ou \(a<b\). Quando \(a<b\) pode também escrever que \(b>a\). Similarmente, quando \(a\leq b\), pode também escrever que \(b\geq a\).
Lema 10.4 Temos as seguintes propriedades para todo \(a,b,c\in\N\).
\(1\leq a\).
a relação \(\leq\) é reflexiva: \(a\leq a\);
a relação \(\leq\) é antissimétrica: se \(a\leq b\) e \(b\leq a\), então \(a=b\);
a relação \(\leq\) é transitiva: se \(a\leq b\) e \(b\leq c\), então \(a\leq b\).
Comprovação.
Indução por \(a\). Se \(a=1\), então \(1\leq 1\), pois \(1=1\). Assuma que \(1\leq a\) com algum \(a\); ou seja \(1=a\) ou \(1<a\) e neste segundo caso \(a=1+c\) com algum \(c\in\N\). Se \(1=a\), então \(S(a)=S(1)=1+1\) e \(1<S(a)\). Se \(a=1+c\), então \(S(a)=S(1+c)=(1+c)+1=1+(c+1)\) e \(1<S(a)\).
Como \(a=a\), temos que \(a\leq a\) e a relação é reflexiva.
Assuma que \(a\leq b\) e \(b\leq a\), mas \(a\neq b\). Nós procuramos uma contradição. Neste caso, \(a<b\) e \(b<a\). Portanto \(b=a+c_1\) e \(a=b+c_2\) com \(c_1,c_2\in\N\) e \[
a=b+c_2=a+c_1+c_2.
\] Logo, \[
1+a=a+1=S(a)=S(a+c_1+c_2)=a+c_1+c_2+1=c_1+c_2+1+a.
\] Agora, a lei cancelativa implica que \[
1=c_1+c_2+1=S(c_1+c_2)
\] e isso contradiz ao Axioma (P3).
Assuma que \(a\leq b\) e \(b\leq c\) e provaremos que \(a\leq c\). Se \(a=b\) ou \(b=c\), então \(a\leq c\) vale trivialmente. Assuma que \(a<b\) e \(b<c\). Então \(b=a+c_1\) e \(c=b+c_2\) com \(c_1,c_2\in\N\). Ora, \[
c=b+c_2=a+c_1+c_2.
\] Logo \(a<c\) e \(a\leq c\) também vale.
Corolário 10.1 A relação \(\leq\) é uma ordem parcial no conjunto \(\N\) (veja Definição 6.8).
Lema 10.5 A ordenação \(\leq\) entre os números naturais é uma ordenação total. Ou seja, se \(a,b\in\N\), então \[
a<b\quad\mbox{ou}\quad a=b\quad\mbox{ou}\quad b<a
\] (veja Definição 6.9).
Comprovação. Vamos por indução em \(a\). Se \(a=1\), então a afirmação segue pelo item 1. do Lema 10.4. Assuma que a afirmação é verdadeira para algum \(a\in\N\); ou seja, \(a=b\) ou \(a<b\) ou \(b<a\) vale para todo \(b\in\N\). Provaremos que \(S(a)=b\) ou \(S(a)<b\) ou \(b<S(a)\) também vale. Se \(a=b\), então \(S(a)=a+1=b+1\) e \(S(a)>b\). Assuma que \(a<b\); ou seja \(b=a+c\) com algum \(c\in\N\). Se \(c=1\), então \(b=a+1=S(a)\) e \(S(a)=b\) vale. Se \(c\neq 1\), então \(c=S(c')\) pelo Lema 10.2 e \[
b=a+c=a+S(c')=S(a+c')=S(c'+a)=c'+S(a).
\] Logo, \(S(a)<b\). Ora se \(b<a\), então \(a=b+c\) com algum \(c\in \N\). Neste caso, \[
S(a)=S(b+c)=b+S(c)
\] e \(b<S(a)\) também vale.
Lema 10.6 Temos as seguintes propriedades para \(a,b,c\in\N\).
Se \(a<b\) então \(a+c<b+c\).
Se \(a<b\) então \(ac<bc\).
Comprovação.
Assuma que \(a<b\). Então \(b=a+x\) com algum \(x\in\N\). Logo \[
b+c=a+x+c=a+c+x
\] e \(a+c<b+c\).
Assuma que \(a<b\) e \(b=a+x\) com algum \(x\in \N\). Logo, \[
bc=(a+x)c=ac+xc
\] e \(ac<bc\).
Corolário 10.2 Vale a lei cancelativa para a multiplicação. Ou seja, se \(ac=bc\), então \(a=b\) para todo \(a,b,c\in\N\).
Comprovação. Assuma que \(ac=bc\). A relação \(a<b\) é impossível, pois neste caso vale \(ac<bc\). Similarmente, \(b<a\) é também impossível. Ora, segue do Lema 10.5 que a única opção é \(a=b\).
10.5 A segunda forma do Princípio da Indução
O Princípio da Indução pode ser formalizado na seguinte maneira que é equivalente ao princípio na Seção 10.2. Assuma que \(P(n)\) é um predicato válido para o conjunto \(\N\) dos naturais (veja a Definição 4.1). Para provar que \(P(n)\) é verdadeira para todo \(n\in\N\), é suficiente provar que
\(P(1)\) é verdadeira; e
se \(P(a)\) é verdadeira para todo \(a\in \{x\in \N\mid 1\leq a\leq n\}=\{1,\ldots,n\}\), então \(P(S(n))\) é também verdadeira.
10.6 A boa ordenação dos naturais
Definição 10.4 Seja \(Y\) um conjunto com ordem total \(\preceq\) (Definição 6.9). Dizemos que \(Y\) está bem ordenado se todo subconjunto não vazio \(X\subseteq Y\) possui menor elemento. Ou seja, se \(X\subseteq Y\) tal que \(X\neq \emptyset\), temos que \[
\exists a\in X:(\forall b\in X: a\preceq b).
\]
Lema 10.7 Temos que \(\N\) com a ordenação acima definida é um conjunto bem ordenado.
Comprovação. Seja \(X\subseteq \N\) um subconjunto que não possui menor elemento. Vamos provar que \(X=\emptyset\). De fato vamos provar por indução que \(n\not\in X\) para todo \(n\in \N\).
Base da Indução: Se \(n=1\) e \(n\in X\), então \(n=1\) é necessariamente menor elemento de \(X\), pois ele é o menor natural por item 1. do Lema 10.4. Como \(X\) não possui menor elemento, obtemos que \(1\not\in X\).
Hipótese da Indução: Assuma para todo \(a\in\{1,\ldots,n\}=\{x\in \N\mid 1\leq x\leq n\}\) que \(a\not\in X\).
Passo indutivo: Supondo a Hipótese da Indução, se \(S(n)\in X\), \(S(n)\) seria menor elemento de \(X\) (pois \(1,\ldots,n\not\in X\)). Como \(X\) não possui menor elemento, temos \(S(n)\not\in X\).
Portanto \(n\not\in X\) para todo \(x\in \N\) e assim \(X=\emptyset\). Ou seja, um subconjunto de \(\N\) que não possui menor element precisa ser igual a \(\emptyset\).
10.7 Provas por indução – Os números de Fibonacci
Definimos a sequência de Fibonacci na forma seguinte: \(F_1=1\), \(F_2=1\), \(F_{k+2}=F_{k}+F_{k+1}\) para \(k\geq 1\). Aplicando a definição, temos que \[
F_1=1,\ F_2=1,\ F_3=2,\ F_4=3,\ F_5=5,\ F_6=8,\ F_7=13,\ \mbox{etc}.
\]
Lema 10.8 As seguintes propriedades são válidas para a sequência de Fibonacci e para \(m,n\geq 1\):
\(F_1+F_2+\cdots+F_n+1=F_{n+2}\);
\(F_1+F_3+\cdots+F_{2n+1}=F_{2n+2}\);
\(F_2+F_4+\cdots+F_{2n}+1=F_{2n+1}\);
\(F_1^2+F_2^2+\cdots+F_n^2=F_nF_{n+1}\);
\(F_{m+1}F_n+F_{m+2}F_{n+1}=F_{m+n+2}\);
\(F_{n+1}^2+F_{n+2}^2=F_{2n+3}\).
Comprovação. Vamos provar algumas destas igualdades, o resto é exercício para o leitor. As provas vão por indução.
Base da indução: \(n=1\), temos que \[
F_1+1=1+1=2=F_3.
\]
Hipótese da Indução: Assuma que a afirmação vale para algum \(n\geq 2\).
Provamos por indução em \(n\). Base da Indução:\(n=1\). Neste caso \[
F_{m+1}F_1+F_{m+2}F_2=F_{m+1}+F_{m+2}=F_{m+3}=F_{m+n+2}
\] vale para todo \(m\in \N\).
Hipótese da Indução: Assuma para algum \(n\in \N\) e para todo \(m\in \N\) que \[
F_{m+1}F_n+F_{m+2}F_{n+1}=F_{m+n+2}.
\]
Passo Indutivo: Provaremos a afirmação para \(n+1\). \[\begin{align*}
F_{m+1}F_{n+1}+F_{m+2}F_{n+2}&=F_{m+1}F_{n+1}+F_{m+2}(F_n+F_{n+1})\\&=
F_{m+1}F_{n+1}+F_{m+2}F_n+F_{m+2}F_{n+1}\\&=(F_{m+1}+F_{m+2})F_{n+1}+F_{m+2}F_{n}\\
&=F_{m+3}F_{n+1}+F_{m+2}F_n=F_{m+1+n+2}=F_{m+n+3}.
\end{align*}\]
Segue do item 5. Aplicando \(F_{m+1}F_n+F_{m+2}F_{n+1}=F_{m+n+2}\) com \(m=n\) e substituindo \(n\) por \(n+1\), obtemos \[
F_{n+1}F_{n+1}+F_{n+2}F_{n+2}=F_{n+(n+1)+2},
\] isto é, \[
F_{n+1}^2+F_{n+2}^2=F_{2n+3}.
\]