Re: [obm-l] Inducao

[Ana Evans <ana_ev@xxxxxxxxx>]

> > Pro pessoal que estah estudando inducao, aqui vao
> dois resultados
> > demonstraveis por inducao e que vao ter utilidade
> pelo resto da sua carreira
> > academica (e talvez ateh mais adiante):
> > 
> > 1) Um sistema linear homogeneo com n incognitas e
> m equacoes tem sempre uma
> > solucao nao-trivial se n > m >= 1. (sugestao: use
> inducao sobre m)
Se m=1 e n>1, entao o sistema eh da forma a_1*x_1
+...a_n*x_n = 0, com todos os a_i's numeros reais nao
nulos.  Entao, x_1 = -(a_2*x_2 +...a_n*x_n)/(a_1).
Atribuindo-se a x_2,....x_n valores tais que pelo
menos um deles nao seja nulo e determinando-se x_1
pela expressao dada, obtemos uma solucao nao trivial
para o sistema.
Suponhamos agora que a hipotese vigore para algum m>=1
Para m+1 equacoes e n>m+1 incognitas, a equacao m+1 eh
da forma a_(m+1)_1*x_1...+a_(m+1))_n*x_n = 0, na qual
pelo menos um dos coeficientes nao e nulo (se todos
fossem nulos, a equacao se resumiria a uma
identidade). Renumerando-se, se necessario, as colunas
da matriz do sistema, podemos supor sem perda de
generalidade que a_(m+1)_1<>0. Assim, atraves de uma
expressao analoga aa apresentada para o caso m=1,
podemos expressar x_1 como uma combinacao linear das
demais incognitas, com termo independente nulo.
Substituindo-se x_1 por tal expressao nas demais
equacoes, o fato do sistema ser linear implica que
obtenhamos no primeiro membro funcoes lineares das
variaveis x_2 a x_n. Como o segundo mebro de todas as
equacoes e nulo, obtemos assim um sistema linear
homogeneo com m equacoes e n-1 incognitas. Como n>m+1,
n-1>m, e a hipotese indutiva implica entao que este
sistema tenha uma solucao nao trivial nas incognitas
x_2,...x_n. Entrando-se com os valores desta solucao 
na epressao que fornece x_1 em funcao de x_2,...x_n,
obtemos, ainda que x_1 =0, uma solucao nao trivial
para o sistema com m+1 equacoes e n>m+1 incognitas,
completando-se assim a inducao e comprovando a tese. 
.       

> > 2) Todo subconjunto de N (inteiros positivos ou
> inteiros nao-negativos,
> > tanto faz!) possui um menor elemento.
Aqui, eu me enrolei. Isto nao eh um pricipio assumido
na formacao do conjunto dos naturais, que leva mais
tarde aa obtencao dos racionais e depois dos reais,
atraves de sequencias de Cauchy ou cortes de Dedekind?
Isto que se pede para demonstrar nao eh uma especie de
axioma, aquele que diz que o conjunto dos naturais
(incluindo ou nao o zero) eh bem ordenado? Nao eh algo
como o pricipio do supremo em R, que nao se demonstra,
mas se assume ser verdadeiro? 

De qualquer forma, eu tentaria fazer o seguinte. Para
conjuntos com n=1 elementos, a proposicao eh
trivialmente verificada. Admitindo-se que seja
verdadeira para algum inteiro positivo n, seja A =
{a_1....a_(n+1)} um subconjunto de N, com n+1
elementos. Temos entao que A = {a_1,....a_n} U
{a_(n+1)}. Por hipotes B = {a_1,....a_n} possui um
menor elemento b. Uma das condicoes b<=a_(n+1) ou
b>a_(n+1) tem necessariamente que vigorar. Se a
primeira vigorar, entao x >= b para todo x de A. Como
b pertence a B contido em A, b pertence a A eh o menor
elemento de A. Se  b>a_(n+1)  vigorar, entao para todo
x de A, x>= a_(n+1) e a_(n+1) eh o menor elemento de
A. Isto mostra a validade da tese para n+1.
Mas ha um detalhe, isto mostra apenas que todo
subconjunto finito de N tem um menor elemento.
Ana


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================