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 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

  1. {P(0)} é verdadeiro, e
  2. 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

  1. {P(a)} é verdadeiro, e
  2. 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}

Notemos que, da dedução acima, PBO{\Rightarrow}PIFg. Entretanto, PIFg{\Rightarrow}PIF, basta tomar {a=0}; provamos o PBO usando PIF, isto é, PIF{\Rightarrow}PBO, portanto

PIF{\Rightarrow}PBO{\Rightarrow}PIFg{\Rightarrow}PIF

ou seja, tais princípios são equivalentes.

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

  1. {P(a)} é verdadeiro, e
  2. {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 —

  1. Seja {a} um número natural e {P} um predicado sobre {{\mathbb N}}. Verifique o seguinte Princípio de Indução: Se
    1. {P(a)} é verdadeiro, e
    2. {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}.

  2. Seja {a_i} 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
    1. {P(a_i)} é verdadeiro para todo {i\in {\mathbb N}} e
    2. {P(j)} verdadeiro implica {P(j-1)} verdadeiro, para todo {j> a_1}

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

  3. 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}.

  4. 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.
  5. Prove, usando indução, que todo número natural, exceto o zero, pode ser expresso como soma de potências distintas de {2}
  6. 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)}

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s