[skip-to-content]

Seção 1.4 O Princípio da Boa Ordem e O Princípio de Indução

Subseção 1.4.1 O Princípio da Boa Ordem

Definição 1.4.1.

Dizemos que um subconjunto \(S\) de \(\mathbb{Z}\) é limitado inferiormente, se existir \(c\in \mathbb{Z}\) tal que \(c\leq x\) para todo \(x\in S\text{.}\) Diremos que \(a\in S\) é um menor elemento de \(S\) se \(a\leq x\) para todo \(x\in S\text{.}\)

O número \(1\) é o menor dos números naturais, como veremos na próxima proposição.

Se \(n=1\) não temos o que demonstrar. Suponha a afirmação válida para algum \(n\in \mathbb{N}\text{,}\) ou seja, \(1\leq n\text{.}\) Como \(n\lt n+1\text{,}\) pela Proposição 1.3.3 obtemos \(1\leq n+1\text{.}\) Logo, pela Definição 1.1.2 (Princípio de Indução), a afirmação é verdadeira para todo \(n\in \mathbb{N}\text{.}\)

Como \(n\lt m\text{,}\) temos \(m-n\in \mathbb{N}\text{.}\) Se \(m-n = 1\text{,}\) temos

\begin{equation*} n+1 = m. \end{equation*}

Se \(m-n>1\text{,}\) temos \(m-n-1\in\mathbb{N}\text{.}\) Logo,

\begin{equation*} n+1\lt m. \end{equation*}

Portanto, \(n+1\leq m\text{.}\)

Reciprocamente, suponha que \(n+1\leq m\text{.}\) Como \(n\lt n+1\text{,}\) se \(n+1=m\text{,}\) temos \(n\lt m\text{,}\) se \(n+1\lt m\text{,}\) o resultado segue por transitividade.

O próximo resultado é uma das principais propriedades da relação de ordem "menor que" entre os números naturais, ele é chamado Princípio da Boa Ordem, muitas vezes abreviado por PBO.

Considere o conjunto \(M=\{n\in \mathbb{N}~;~ n\leq x, \forall x\in S\}\text{.}\) Claro que \(1\in M\text{.}\) Como \(S\neq \varnothing\text{,}\) tome \(s\in S\text{.}\) Então \(s+1\notin M\text{,}\) pois \(s+1\) não é menor ou igual a \(s\text{.}\) Assim, \(M\neq \mathbb{N}\text{.}\) Como \(1\in M\) e \(M\neq \mathbb{N}\text{,}\) deve existir \(m\in M\) tal que \(m+1\notin M\text{,}\) caso contrário, pelo Princípio de Indução (item 3 do Axioma 1.1.1), \(M\) deveria ser igual a \(\mathbb{N}\text{.}\)

Vamos mostrar que \(m\) é o menor elemento de \(S\text{.}\)

Como \(m\in M\text{,}\) temos \(m\leq x, \forall x\in S\text{.}\) Ainda precisamos verificar que \(m\in S\text{.}\) Suponha, por absurdo, que \(m\notin S\text{.}\) Então, \(m\lt x, \forall x\in S\text{.}\)

Pelo Lema 1.4.3, teríamos \(m+1\leq x,\forall x\in S\text{,}\) do que resultaria \(m+1\in M\text{,}\) em contradição com a escolha de \(m\text{.}\) Logo, \(m\in S\text{.}\)

Observação 1.4.5.

O resultado do Teorema 1.4.4 também é válido para subconjuntos de \(\mathbb{Z}\text{,}\) limitados inferiormente.

Exemplo 1.4.6.

Não existe nenhum número inteiro \(n\) tal que \(0\lt n \lt 1\text{.}\)

Solução

Suponha por absurdo que exista \(n\) com essa propriedade. Logo, o conjunto \(S = \{ z \in \mathbb{Z}~;~ 0\lt z \lt 1 \}\) é não vazio, além de ser limitado inferiormente. Portanto, \(S\) possui um menor elemento \(a\in \mathbb{N}\text{,}\) pois \(a>0\) e \(\mathbb{Z} = \mathbb{N}\cup\{0\}\cup (-\mathbb{N})\text{.}\) Como

\begin{equation*} 0\lt a \lt 1, \end{equation*}

pela Proposição 1.3.5, multiplicando esta última desigualdade por \(a\text{,}\) obtemos

\begin{equation*} 0\lt a^2 \lt a \lt 1, \end{equation*}

logo \(a^2\in S\) e \(a^2\) é menor que o menor elemento de \(S\text{,}\) uma contradição. Portanto, \(S=\varnothing.\)

Exemplo 1.4.7.

Dado um inteiro \(n\) qualquer, não existe nenhum número inteiro \(m\) tal que \(n\lt m\lt n+1\text{.}\)

Solução

Suponha, por absurdo, que exista um número inteiro \(m\) satisfazendo as desigualdades

\begin{equation*} n\lt m \lt n+1. \end{equation*}

Logo, pela Proposição 1.3.4, somando \((-n)\) obtemos

\begin{equation*} 0\lt m-n\lt 1, \end{equation*}

o que contradiz o exemplo anterior.

Subseção 1.4.2 Mais sobre o Princípio de Indução

Uma vez que \(s(n)=n+1\) para qualquer número natural \(n\text{,}\) podemos enunciar o Princípio de Indução como segue.

Definição 1.4.8.

(Princípio de Indução) Se uma propriedade P é válida para o número 1 e se, P válida para o número \(k+1\) sempre que P é válida para o número \(k\text{,}\) então P é válida para todos os números naturais.

Exemplo 1.4.9.

Prove que \(1+3+5+7+\cdots+(2n-1)=n^2\text{,}\) para todo \(n\in\mathbb{N}\text{.}\)

Solução

Vamos testar o caso \(n=1\text{.}\) Do lado esquerdo da igualdade temos apenas o número \(1\text{,}\) do lado direito temos \(1^2\text{,}\) ou seja, temos \(1 = 1^2\) e a afirmação é verdadeira para o número \(1\text{.}\)

Agora, suponha que a afirmação seja verdadeira para algum número \(k\in \mathbb{N}\text{,}\) ou seja, estamos supondo que

\begin{equation} 1+3+5+7+\cdots+(2k-1)=k^2\label{eq-indoex}\tag{1.4.1} \end{equation}

é verdadeiro.

Somando \(2(k+1)-1\text{,}\) do lado esquerdo da igualdade (1.4.1), ficamos com

\begin{equation*} \underbrace{1+3+5+7+\cdots+(2k-1)}_{\quad\quad\quad\quad=k^2, \text{ pela H.I.}} + \underbrace{(2k+1)}_{2(k+1)-1} = k^2+(2k+1) = (k+1)^2. \end{equation*}

Ou seja, o caso \(k+1\) é válido sempre que o caso \(k\) seja válido. Portanto, pela Definição 1.4.8, a igualdade é válida para todos os números naturais.

Definição 1.4.10.

(Princípio de Indução Generalizado) Se uma propriedade P é válida para o número natural \(a\) e se, P for válida para o número \(k+1\) sempre que P for válida para o número \(k\text{,}\) com \(k\geq a\text{,}\) então P é válida para todo número natural \(n\geq a\text{.}\)

Definição 1.4.11.

(Princípio de Indução Completa) Se uma propriedade P é válida para o número 1 e se, P válida para um número \(k+1\) sempre que P for válida para os números \(1,2,\cdots,k\text{,}\) então P é válida para todos os números naturais.