Re: [obm-l] Inducao

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 14.12.04 17:51, Ana Evans at ana_ev@yahoo.com wrote:

> 
>>> 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 fato, na presenca dos outros axiomas de Peano, este principio da boa
ordenacao eh equivalente ao principio da inducao.

> 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
> 
Um outro problema eh que voce estah tratando os naturais como numeros
cardinais, o que eh desnecessario.

Pra provar que Inducao ==> Boa Ordenacao, faca o seguinte:

Seja A um subconjunto nao-vazio de N = {0,1,2,3,...}

Se 0 pertence a A, entao acabou: 0 eh o menor elemento de A.

Caso contrario, seja B = {m em N | 0, 1, ..., m nao pertencem a A}.

Claramente, 0 pertence a B.

Mas como A <> vazio, temos B <> N, pois B estah contido em N - A.

Logo, pelo principio da inducao, deve haver n em B tal que n+1 nao pertence
a B (essa eh a sacada da demonstracao - voce consegue ver porque isso eh
verdade?).

Assim, n pertence a B ==> 0, 1, ..., n nao pertencem a A.
Mas n+1 nao pertence a B.
Se n+1 nao pertencesse a A, entao teriamos que 0, 1, ..., n, n+1 nao
pertenceriam a A e, portanto, n+1 pertenceria a B ==> contradicao.
Logo, n+1 deve pertencer a A e, dado que 0, 1, ..., n nao pertencem a A, n+1
serah justamente o menor elemento de A.

[]s,
Claudio.

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