bc1405 – Princípios de indução e boa ordem

— Princípio da Boa Ordem (PBO) —

Teorema 3 (PBO) Todo ${A \subset {\mathbb N}}$ não-vazio tem um menor elemento, ou seja, existe ${a\in {\mathbb N}}$ tal que

$\displaystyle \begin{array}{rcl} &&a\in A \\ &&\forall x\in A,~a\leq x. \end{array}$

Demonstração: Se ${0\in A}$ então ${0}$ é o menor elemento de ${A}$ pois ${0\leq n}$ para todo natural ${n}.$ De fato ${0+n=n}$ , donde ${0\leq n}$ . Supondo ${0\not\in A}$ definimos

$\displaystyle X:=\{n\in{\mathbb N}\colon \text{ para todo } k \leq n,~k \notin A\}$

e notamos que ${0\in X}$ (pois, ${0\not\in A}$ ). Se valer que ${n\in X \Rightarrow n+1\in X}$ para todo natural ${n}$ , então teremos ${X={\mathbb N}}$ pelo axioma de indução, o que não é verdade (por quê?), portanto existe um natural ${m}$ tal que ${m\in X}$ e ${m+1 \not\in X}$ .

De ${m\in X}$ temos que ${n \notin A}$ para todo ${n\leq m}$ e de ${m+1\in X}$ temos ${m+1\in A}$ e como não há ${p}$ , ${m<p<m+1}$ , ${m+1}$ é menor elemento de ${A}$ . De fato,

$\displaystyle x\in A \Rightarrow x > m$

portanto, pelo exercício 9, ${x \geq m+1}$ . $\Box$

Exercício 10 Prove que não existe natural ${p}$ tal que ${n<p<n+1}$ , qualquer que seja ${n\in{\mathbb N}}$ .

Exercício 11 ${A\subseteq {\mathbb N}}$ é dito limitado superiormente se existir um natural ${n}$ tal que

$\displaystyle \forall x\in A,~ x\leq n$

e se ${n}$ com a propriedade acima pertence a ${A}$ ele é dito maior elemento de ${A}$ . Mostre que se ${A}$ é limitado superiormente e não vazio então admite maior elemento.

Exemplo 2 Para toda função não-crescente ${f\colon {\mathbb N}\rightarrow{\mathbb N}}$ existe um natural ${n_0}$ a partir do qual ${f}$ é constante. A imagem da função, ${\mathrm{Im} (f)}$ , é um subconjunto não vazio de naturais. Seja ${n_0}$ um natural tal que ${f(n_0)}$ é o menor elemento de ${\mathrm{Im}(f)}$ . Como ${f}$ é não-crescente ${n\geq n_0 \Rightarrow f(n) \leq f(n_0)}$ , mas ${f(n)\not< f(n_0)}$ pois ${f(n_0)}$ é o menor elemento de ${\mathrm{Im}(f)}$ , portanto ${n\geq n_0 \Rightarrow f(n) =f(n_0)}$ .

— Princípios de Indução —

O axioma de indução tem um papel de fundamental não só na teoria dos números naturais como em toda matemática. É visto como um método de demonstração, conhecido como Princípio de Indução Matemática ou Princípio de Indução Finita, usualmente expresso da seguinte maneira

${P(n)}$ é um predicado sobre ${{\mathbb N}}$

Princípio da Indução Finita (PIF). Se são satisfeitas as condições

${P(0)}$ é verdadeiro, e
para todo ${k\geq 0}$ , se ${P(k)}$ é verdadeiro então ${P(k+1)}$ é verdadeiro,

então ${P(n)}$ é verdadeiro para todo natural ${n}$ .

Esse princípio decorre facilmente do axioma da Indução se tomarmos ${X}$ como o conjunto dos naturas para os quais o predicado é verdadeiro, isto é,

$\displaystyle X=\{n\in{\mathbb N}\colon P(n) \text{ \'e verdadeiro}\}$

da condição 1 temos ${0\in X}$ da condição 2 temos que se ${k\in X}$ então ${k+1 \in X}$ , portanto, ${X={\mathbb N}}$ . ${\Box}$

Princípio da Indução Finita generalizado (PIFg). Seja ${a}$ um número natural. Se

${P(a)}$ é verdadeiro, e
para todo ${k\geq a}$ , se ${P(k)}$ é verdadeiro então ${P(k+1)}$ é verdadeiro,

então ${P(n)}$ é verdadeiro para todo natural ${n \geq a}$ .

Esse princípio decorre do Princípio da Boa Ordem da seguinte forma: suponha que não vale a sentença “ ${P(n)}$ é verdadeiro para todo natural ${n \geq a}$ ”, logo

$\displaystyle A:=\{n\in{\mathbb N}\colon n\geq a \text{ e }P(n) \text{ n\~ao \'e verdadeiro}\}$

é não vazio, portanto admite um menor elemento ${b:=\min A}$ .

${b>a}$ (estrito pois ${a\notin A}$ ) logo ${b}$ não é zero, portanto ${b-1}$ está definido, ademais de ${b>a}$ temos ${b-1\geq a}$ (pelo exercício 9) mas como ${b}$ é o menor elemento de ${A}$ devemos ter ${b-1\not \in A}$ , ou seja, ${P(b-1)}$ é verdadeiro. Mas, isso implica (condição 2) que ${P(b)}$ é verdadeiro, uma contradição. ${\Box}$

Exemplo: ${2^n < n!}$ para todo ${n\geq 4}$ : ${P(n)}$ é ${2^n < n!}$ que é verdadeiro para ${n=4}$ (confira). Seja ${k}$ um natural maior ou igual a ${4}$ e assumamos que ${P(k)}$ é verdadeiro, ou seja

$\displaystyle 2^k < k! \ \ \ \ \ (14)$

Pela escolha de ${k}$ , ${ k > 1 \Rightarrow k+1 > 2 \Rightarrow (k+1)\cdot k! > 2\cdot k!}$ , portanto ${(k+1)! > 2\cdot k!}$ e usando (14) ${ (k+1)! > 2^{k+1} }$ . Pelo PIFg, ${2^n < n!}$ para todo ${n\geq 4}$ .

Princípio da Indução Finita, segunda forma (PIF2). Seja ${a}$ um número natural. Se

${P(a)}$ é verdadeiro, e
${P(k)}$ verdadeiro para todo ${k\in \{a,a+1,\dots,n\}}$ implica ${P(n+1)}$ verdadeiro,

então ${P(n)}$ é verdadeiro para todo natural ${n \geq a}$ .

— Exercícios —

Seja um número natural e um predicado sobre . Verifique o seguinte Princípio de Indução: Se

${P(a)}$ é verdadeiro, e
${P(b)}$ verdadeiro para todo ${b\in \{a,a+1,\dots,k\}}$ implica ${P(k+1)}$ verdadeiro,

então ${P(n)}$ é verdadeiro para todo natural ${n \geq a}$ .
Seja uma sequência (estritamente) crescente de números naturais. Verifique o seguinte Princípio de Indução: Se ${P(n)}$ é um predicado a respeito de ${n\in{\mathbb N}}$ de modo que

${P(a_i)}$ é verdadeiro para todo ${i\in {\mathbb N}}$ e
${P(j)}$ verdadeiro implica ${P(j-1)}$ verdadeiro, para todo ${j> a_1}$

então ${P(n)}$ é verdadeiro para todo ${n\geq a_1}$ .
Descubra uma falha na prova: todos os números naturais são iguais Denotamos por ${\max(a,b)}$ o maior número natural dentre ${a}$ e ${b}$ . Vamos mostrar por indução que se ${\max(a,b)=n}$ então ${a=b}$ .
(a) Se ${\max(a,b)=0}$ então ${a=b=0}$ .
(b) Suponha que se ${\max(a,b)=k-1}$ então ${a=b}$ .
Vamos mostrar que

se ${\max(a,b)=k+1}$ então ${a=b}$ .

Suponha que ${\max(a,b)=k+1}$ . Então ${\max(a-1,b-1)=k}$ e pela hipótese indutiva ${a-1=b-1}$ , portanto ${a=b}$ .
Sejam ${A_1,A_2,\dots,A_n}$ conjuntos e ${n\geq 2}$ . Suponha que para dois conjuntos quaisquer ${A_i}$ e ${A_j}$ vale que ${A_i\subseteq A_j}$ ou ${A_j \subseteq A_i}$ . Prove, por indução, um desses conjuntos é subconjunto de todos eles.
Prove, usando indução, que todo número natural, exceto o zero, pode ser expresso como soma de potências distintas de ${2}$
Demonstre usando indução:
1. ${9 + 9\cdot 10 + 9\cdot 10^2 + \cdots + 9\cdot 10^{n-1}=10^n -1}$ .
2. ${1+3 +5+ \cdots +(2n-1) = n^2}$ .
3. ${1+2+4+\cdots +2n=n(n+1)}$
4. ${2^n \leq 2^{n+1}-2^{n-1}-1}$
5. ${n!<n^n}$ , ${n\geq 2}$
6. ${1^3+3^3+\cdots + (2n+1)^3=(n+1)^2(2n^2+4n+1)}$