Fundamentos de Matemática

Prévia do material em texto

2008
ME-100
Fundamentos de Matemática
Mauro S. de F. Marques
– p. 1/30
CAPÍTULO 3
Induçªo matemÆtica
msdfm
– p. 2/30
3.1 Introdução
O Princípio da Indução matemática é uma importante ferramenta
para demonstarção da validade de argumentos envolvendo
“números naturais”.
O entendimento do Princípio da Indução matemática é
equivalente ao entedimento da definição do conjunto dos
“números naturais”.
Os números naturais fornecem uma estrutura matemática, uma
escala, que nos permite contar , ato natural ao raciocínio humano.
Essa estrutura também torna precisa a noção de quantidade.
Formalmente, define-se os números naturais de forma simples e
elegante através dos Axiomas de Peano.
msdfm
– p. 3/30
Axioma: “Premissa considerada necessariamente
evidente e verdadeira, fundamento de uma
demonstraçªo, porØm ela mesma indemonstrÆvel,
originada, segundo a tradiçªo racionalista, de
princípios inatos da consciŒncia ou, segundo os
empiristas, de generalizaçıes da observaçªo empírica
[O princípio aristotØlico da contradiçªo ("nada pode
ser e nªo ser simultaneamente") foi considerado desde
a Antiguidade um axioma fundamental da �loso�a.]”
msdfm
– p. 4/30
Um axioma é considerado algo óbvio ou um consenso inicial
necessário para a construção de uma teoria.
Na matemática, um axioma é uma hipótese inicial de qual outros
enunciados são logicamente derivados.
Em contraste aos teoremas, axiomas não podem ser derivados
por princípios de dedução e demonstráveis por derivações
formais, eles são hipóteses iniciais.
Em muitos contextos, "axioma", "postulado"e "hipótese"são
usados como sinônimos.
Um axioma não é necessariamente uma verdade, mas apenas
uma premissa usada em uma dedução, visando obter resultados.”
msdfm
– p. 5/30
3.2 Números naturais: Axioma de Peano
No livro, "Arithmetices Principia Nova Methodo Exposita”,
Giussepe Peano (1858-1932) elabora a teoria completa dos
números naturais a partir de quatro premissas básicas,
conhecidas como Axiomas de Peano.
Em palavras, os Axiomas de Peano se resumem a:
A1. Todo natural possui um único relativo, que também é um natural.
A2. Naturais que têm o mesmo relativo são iguais, ou equivalentemente, naturais diferentes
possuem relativos diferentes
A3. Existe um único natural ♠ que não é relativo de nenhum outro.
A4. Se um conjunto X tem como elementos ♠ e o relativo de cada um de seus elementos, então
esse conjunto contém todos os naturais.
O natural ♠ é usualmente denotado por 1!
msdfm
– p. 6/30
Matemáticamente os Axiomas de Peano se resumem a:
Considere um conjunto N tal que,
A1. ∃ s : N 7→ N,3 ∀n ∈ N ∃s(n) ∈ N.
A2. A função s : N 7→ N é injetiva.
A3. ∃ 1 ∈ N,3 1 6= s(n)∀n ∈ N.
A4.
(
∀X ⊂ N 3 (1 ∈ N) ∧ (n ∈ X⇒ s(n) ∈ X
)
⇒
(
X = N
)
.
O conjunto N é chamado conjunto dos nu´meros naturais, e um
elemento n de N de nu´mero natural. s(n) chamado o relativo
de n.
msdfm
– p. 7/30
Podemos então denotar
s(1) = 2, s(2) = s(s(1)) = 3, s(3) = s(s(2)) = s(s(s(1))) = 4, . . .
Outros podem preferir a notacão,
1 = I, s(I) = II, s(II) = s(s(I)) = III, s(III) = s(s(II)) = s(s(s(I))) = IV, . . .
ou
1 = { }, s(1) = s({ }) = {{ }}, s(s(1)) = s({{ }}) = s(s({ })) = {{{ }}}, . . .
ou
1, s(1) = s, s(s(1)) = s ◦ s, s(s(s(1))) = s ◦ s ◦ s, . . .
msdfm
– p. 8/30
Adic¸a˜o de nu´meros naturais
Considere a função
S : N× N 7→ N,
chamada somar, definida da forma: Para todom ∈ N,
F1. S(m, 1) = s(m)
F2. S(m, s(n)) = s(S(m,n))
Portanto,S(m, 1) é, por definição, o relativo dem.
Se conhecermos S(m,n), saberemos o valor de S(m, s(n)). Isto
nos permite conhecer S(m,n) para todo n em N e todom em N.
S(m, 2) = S(m, s(1)) = s(S(m, 1)) = s(s(m)),
S(m, 3) = S(m, s(2)) = s(S(m, 2)) = s(s(s(m))), . . .
msdfm
– p. 9/30
A partir deste ponto podemos usar a notação usual para S(m,n)
“S(m,n) ≡ m+ n”.
Assim,m+ 1 = S(m, 1) = s(m), m+ 2 = S(m, 2) = S(m, s(1)) = s(m+ 1), . . .
. . . , (m+ n) + 1 = S(m+ n, 1) = s(m+ n) . . .
Portanto,
s(m) = m+ 1,∀k ∈ N.
Por F2 sabemos que
m+ (n+ 1) = (m+ n) + 1.
Assim, (F1) e (F2) definem, por recorrência, a “soma”m+ n de dois números naturais
quaisquer,m e n em N.
Claramente + é uma relação binária em N.
msdfm
– p. 10/30
Multiplicac¸a˜o de nu´meros naturais
A multiplicaçªo de nœmeros naturais se de�ne de
modo anÆlogo à adiçªo.
Considere a funçªo
M : N× N 7→ N,
chamadamultiplicar, de�nida da forma: Para todo
m ∈ N,
F1. M(m, 1) = m
F2. M(m, (n+ 1)) =M(m,n) +m.
msdfm
– p. 11/30
O produto (multiplicac¸a˜o)M(m,n) é usualmente escrito nas
formas:
M(m,n) ≡ mn ≡ m · n ≡ m× n
e lê-se “m vezes n”.
A definição acima diz que:
(i) 1 vezm é igualm.
(ii) (m vezes n+ 1,) é igual am vezes n mais (uma vez)m,
isto é,
m · (n+ 1) = (m · n) +m.
Assim,
m · 2 = m+m,m · 3 = m+m+m, . . . .
msdfm
– p. 12/30
Exercicios: Usando a definição:
3.1 Demonstre que a função “somar” é associativa e comutativa.
3.2 Demonstre que a função “somar” satisfaz a Lei do Corte, isto é,
m+ n = m+ k ⇒ n = k, ∀m,n, k ∈ N.
3.3 Demonstre que a função “multiplicar” é associativa e comutativa.
3.4 Demonstre que a função “somar” satisfaz a Lei do Corte, isto é,
n ·m = n · k ⇒ m = k, ∀n,m, k ∈ N.
3.5 Demonstre que a função “multiplicar” é distributiva com relação a função “somar” isto é,
n · (m+ k) = (n ·m) + (n · k), ∀n,m, k ∈ N.
msdfm
– p. 13/30
Ordem
A soma (adição) de números naturais induz uma relação de ordem em N. Ou seja: Dados dois
números naturaism e n dizemos que m ·e menor do que n , escreve-sem < n,
∃k ∈ N,3 n = m+ k.
Neste caso diz-se também que n ·e maior do que m e escreve-se n > m. Dizemos que n maior
ou igual am oum nemor ou igual a n se
(m ≤ n)⇔ (m < n) ∨ (m = n).
Analogamente podemos escrever (m ≥ n) Note que, pela definição
m < m+ k, ∀ n,m, k ∈ N.
Em particular,
∀n ∈ N, 1 ≤ n ∧ n < s(n) = n+ 1.
s(n) o relativo de um número natural n pode agora ser chamado, sem risco de confusão, de
sucessor de n
msdfm– p. 14/30
Exercicios:
3.6 Mostre que < é uma relação em N que é transitiva.
3.7 A relação < em N é reflexiva? Simétrica?
3.8 A proposição abaixo é falsa ou verdadeira? Explique!
∀n,m ∈ N, (n < m) ∨ (n = m) ∨ (m < n).
As proposições (n < m), (n = m) e (m < n) são exclusivas?
3.9 Mostre que:
∀n,m, k ∈ N,m < n ⇒ (m+ k < n+ k) ∧ (m · k < n · k).
Use redução ao absurdo e a “Lei do Corte”.
msdfm
– p. 15/30
3.3 Princípio de indução
O œltimo dos Axiomas de Peano possui uma natureza
mais complexas e tambØm Ø conhecido como o
axioma da induçªo.
O Axioma da Induçªo Ø fundamental para a teoria dos
nœmeros naturais e para a matemÆtica em geral. Ele
fornece um mØtodo de demonstraçªo, chamado
Me´todo de Induc¸a˜o Matema´tica, ou Princı´pio da
Induc¸a˜o Finita, ou Princı´pio da Induc¸a˜o.
msdfm
– p. 16/30
O Princípio da Indução diz o seguinte:
“ Seja p(·) uma func¸a˜o proposicional em N. Se p(1) e´ verdade e
para todom em N, p(m) implica p(m+ 1), enta˜o p(n) e´ verdade
para todo n em N, isto e´,
(
p(1) ∧
(
∀m ∈ N, p(m)⇒ p(m+ 1)
))
⇒
(
∀n ∈ N, p(n)
)
,
Note que
(
p(1) ∧ (∀m ∈ N, p(m)⇒ p(m+ 1)
)
⇒ p(1)⇒ p(2)⇒ p(3)⇒ · · · ⇒ p(n)⇒ · · ·
msdfm
– p. 17/30
Em outros termos:
“Seja S um subconjunto de N que satisfaz
(i) 1 ∈ S.
(ii) ∀n ∈ S⇒ (n+ 1) ∈ S.
Enta˜o
S = N”.
msdfm
– p. 18/30
Exemplos: 1. Para todo n ∈ N,
1 + 2 + · · ·+ n =
n(n+ 1)
2
.
De fato:
1 =
1(1 + 1)
2
=
1 · 2
2
=
2
2
= 1,
logo a proposição é válida para n = 1. Vamos assumir que o resultado é válido param ∈ N
(hipótese de indução), isto é,
1 + 2 + · · ·+m =
m(m+ 1)
2
.
Temos então que
1+2+· · ·+m+(m+1) =
m(m+ 1)
2
+(m+1) = (m+1)
(m
2
+1
)= (m+1)
(m+ 2
2
)
=
(m+ 1)
(
(m+ 1) + 1
)
2
.
Logo, o resultado é válido para todo n ∈ N. msdfm– p. 19/30
2. Fixado x > 0, para todo n ∈ N,
(1 + x)n ≥ 1 + xn.
De fato:
(1 + x)1 = 1 + x = 1 + x1 ≤ 1 + x1.
logo a proposição é válida para n = 1. Vamos assumir que o resultado é válido param ∈ N
(hipótese de indução), isto é,
(1 + x)m ≥ 1 + xm.
Temos então que
(1 + x)m+1 = (1+ x)m(1 + x) ≥ (1 + xm)(1 + x) = 1+ xm + x+ xm+1 ≥ 1 + xm+1.
Logo, o resultado é válido para todo n ∈ N.
msdfm
– p. 20/30
3. Para todo n ∈ N,n3 − n é divisível por 3. De fato:
13 − 1 = 1− 1 = 0 = 3× 0.
logo a proposição é válida para n = 1. Vamos assumir que o resultado é válido param ∈ N
(hipótese de indução), isto é,
∃k ∈ N 3 m3 −m = 3k.
Temos então que
(m+1)3−(m+1) = m3+3m2+3m+1−m−1 = (m3−m)+3(m2+m) = 3k+3(m2+m) = 3(k+m2+m) = 3l, l ∈ N.
Logo, o resultado é válido para todo n ∈ N.
msdfm
– p. 21/30
Exercicios:
Mostre usando a técnica de indução que para todo número
natural n:
3.6. n2 ≥ n.
3.7. 12 + 22 + 32 + · · ·+ n2 = n(n+1)(2n+1)
6
.
3.8. 13 + 23 + 33 + · · ·+ n3 =
(
n(n+1)
2
)2
.
3.9. 1 + 3 + 5 + 7 + · · · (2n− 1) = n2.
msdfm
– p. 22/30
3.10.
(
1− 1
2
)(
1− 1
3
)
· · ·
(
1− 1
n+1
)
= 1
n+1
3.11. ∀x, y ∈ R,
xn+1 − yn+1 = (x− y)(xn + xn−1y + · · ·+ xyn−1 + y).
3.12. 2−1 + 2−2 + 2−3 + · · ·+ 2−n ≤ 1.
Interprete o resultado!
3.13 ∀M ∈ N, ∃n ∈ N 3 1 + 2−1 + 3−1 + · · ·+ n−1 > M.
Interprete o resultado!
msdfm
– p. 23/30
3.4 Formas equivalentes de indução
As duas proximas proposições são equivalentes ao Princípio de
Indução e em algumas situações podem ser mais convenientes.
A primeira delas é referida como Princı´pio da Boa Ordenac¸a˜o,
segue do Princípio de Indução.
Proposic¸a˜o 1. Todo subconjunto na˜o vazio de N tem um menor
elemento. Em outras palavras
∀S ⊂ N, S 6= ∅, ∃m ∈ S 3, ∀n ∈ S,m ≤ n.
Demonstrac¸a˜o: Se 1 é elemento de S, nada resta a ser provado.
Vamos assumir então que 1 não pertence a S.
msdfm
– p. 24/30
Usaremos a técnica de redução ao absurdo. Suponhamos que S não tem um menor elemento, ou
seja,
∀m ∈ S, ∃n ∈ S 3 n < m.
Seja
T = {m ∈ N : (∀n ∈ N, n ≤ m)⇒ n 6∈ S}.
Claramente,
1 ∈ T
e, pela definição de T ,
∀k ∈ T ⇒ 1, 2, . . . k 6∈ S.
∀k ∈ T ⇒ k + 1 6∈ S
pois pois caso contrário (k + 1) seria o menor elemento de S. Logo Pelo principio de indução,
T = N ∧ S = ∅
o que é uma contradição. Logo,S tem um menor elemento.
c.q.d
msdfm
– p. 25/30
A próxima proposição é conhecida como Princı´pio de Induc¸a˜o
Completa, é consequência do Princípio da Boa Ordenação.
Proposic¸a˜o 2. Seja S um subconjunto de N que satisfaz:
(i) 1 ∈ S.
(ii) ∀n ∈ N, {1, 2, . . . , n} ⊂ S → (n+ 1) ∈ S.
Enta˜o
S = N
Demonstrac¸a˜o: Se
Sc = ∅
a proposição está demonstrada.
msdfm
– p. 26/30
Suponhamos então
Sc 6= ∅.
Pela Proposição 2, existe um menor elemento de Sc, digamosm+ 1. De (i)
1 ∈ S → 1 6∈ Sc → (m+ 1) 6= 1.
Claramente
2, 3, . . .m ∈ S
pois caso contrariom+ 1 não seria o menor elemento de Sc. Mas (ii)
({1, 2, . . . ,m} ⊂ S → (m+ 1) ∈ S.
Logo temos uma contradição. Segue que
Sc = ∅ → S = N.
c.q.d
msdfm
– p. 27/30
Para completar a equivalência proposta, resta mostar que o Princípio de Indução Completa
implica no Princípio de Indução.
Proposic‚ ˜ao 3. Seja S um subconjunto de N que satisfaz:
(i) 1 ∈ S.
(ii)
(
∀n ∈ N, n ∈ S
)
→ (n+ 1) ∈ S.
Ent
˜
ao
S = N.
Demonstrac‚ ˜ao: A proposição
∀n ∈ N, {1, 2, . . . , n} ⊂ S → n ∈ S
é trivialmente verdadeira. Logo temos
(
(∀n ∈ N, {1, 2, . . . , n} ⊂ S → n ∈ S) ∧ (∀n ∈ N, n ∈ S → (n+ 1) ∈ S)
)
.
Consequentemente (
∀n ∈ N, {1, 2, . . . , n} ⊂ S
)
→ (n+ 1) ∈ S.
Ou seja S satisfaz as condições da Proposição 2, mostrando que
S = N.
c.q.d
msdfm
– p. 28/30
As Proposiçıes 1,2 e 3 mostram que
(Princípio de Indução)
⇓
(Princípio da Boa Ordenação)
⇓
(Princípio de Indução Completa)
⇓
(Princípio de Indução).
Em outras palavras, os três principios são equivalentes.
msdfm
– p. 29/30
Exercı´cios:
3.14 Mostre usando o Princípio da Boa Ordenaçªo
1 + 2 + · · ·+ n =
n(n+ 1)
2
3.14 Mostre usando o Princípio da Boa Ordenaçªo os
Exercícios 3.6 a 3.9.
msdfm
– p. 30/30
	small 3.1 Introduc c~ao
	small 3.2 N'umeros naturais: Axioma de Peano
	small 3.3 Princ'{i }pio de induc c~ao
	small 3.4 Formas equivalentes de induc c~ao