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.
Proposição 1.4.2.
\(1\leq n\text{,}\) para todo \(n\in\mathbb{N}\text{.}\)
Demonstraçã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{.}\)
Lema 1.4.3.
Sejam \(m,n\in\mathbb{N}\text{.}\) Então, \[n\lt m ~~\text{ se, e somente se, } n+1\leq m.\]
Demonstração.
Como \(n\lt m\text{,}\) temos \(m-n\in \mathbb{N}\text{.}\) Se \(m-n = 1\text{,}\) temos
Se \(m-n>1\text{,}\) temos \(m-n-1\in\mathbb{N}\text{.}\) Logo,
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.
Teorema 1.4.4.
(Princípio da Boa Ordem) Se \(S\) é um subconjunto não vazio de \(\mathbb{N}\text{,}\) então \(S\) possui um menor elemento.
Demonstração.
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çãoSuponha 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
pela Proposição 1.3.5, multiplicando esta última desigualdade por \(a\text{,}\) obtemos
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çãoSuponha, por absurdo, que exista um número inteiro \(m\) satisfazendo as desigualdades
Logo, pela Proposição 1.3.4, somando \((-n)\) obtemos
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çãoVamos 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
é verdadeiro.
Somando \(2(k+1)-1\text{,}\) do lado esquerdo da igualdade (1.4.1), ficamos com
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.