Exercício 1.21. Considere a seguinte afirmação:
“Entre quaisquer
carros, todos têm a mesma cor.”
Um aluno apresenta a seguinte “demonstração” por indução no número
de carros:
Base: Para
, a afirmação é verdadeira, pois um grupo com apenas um carro tem, trivialmente, todos os seus integrantes da mesma cor.
Passo indutivo: Suponha que a afirmação seja verdadeira para
carros. Considere agora
carros,
Os primeiros
carros,
têm todos a mesma cor, pela hipótese de indução. Analogamente, os últi
carros,
também têm todos a mesma cor. Como esses dois grupos têm carros em comum, conclui-se que todos os
carros têm a mesma cor.
Identifique o erro nessa demonstração.
“Entre quaisquer
Passo 1
Vou listar com clareza o que o enunciado dá e o que pede (sem resolver nada ainda).
- Afirmação a ser verificada: “Entre quaisquer
carros, todos têm a mesma cor.” - Demonstração proposta pelo aluno:
- Base: para
a afirmação é verdadeira. - Passo indutivo: assumir a afirmação verdadeira para
carros; então, dados carros , os primeiros (isto é, ) têm a mesma cor por hipótese; os últimos (isto é, ) também têm a mesma cor por hipótese. Como esses dois grupos “têm carros em comum”, conclui-se que todos os carros têm a mesma cor.
- Base: para
- O que o exercício pede: identificar o erro nessa demonstração.
Passo 2
Breve aula sobre como prova por indução funciona (para ficar bem claro o que é exigido).
- Para provar uma propriedade
para todo inteiro por indução, precisam ser mostradas duas coisas: - Base:
é verdadeira. - Passo indutivo: para todo
, a partir de deve-se deduzir . Ou seja, a implicação deve ser válida para todo na faixa considerada.
- Base:
- Importante: o passo indutivo tem de funcionar para qualquer
(inclusive para ). Não basta que ele funcione apenas para alguns ; o encadeamento da indução depende de que a implicação valha sempre.
Passo 3
Análise detalhada do argumento do aluno e identificação do ponto frágil.
- Denotemos os dois grupos usados no passo indutivo por
- O argumento do aluno usa que
tem todos os carros de mesma cor (pela hipótese ) e que também tem todos os carros de mesma cor; então como contém carros, isso força as cores a serem iguais em e , e assim todos os carros teriam a mesma cor. - Calculemos o tamanho da interseção:
que tem exatamente elementos. Logo . - Observação crucial: se
(isto é, se ), então não é vazio e o raciocínio de “ligar” as cores funciona: um carro comum faz a ponte entre os dois blocos e garante que as cores coincidam. - Porém, se
, então : os conjuntos são que são disjuntos. Nesse caso NÃO existe carro em comum que permita concluir que a cor de é igual à cor de . Portanto o passo indutivo, tal como foi escrito, falha exatamente na transição .
Passo 4
Um contraexemplo simples para mostrar que a afirmação geral é falsa e que o “buraco” identificado é real.
- Considere dois carros
e com cores diferentes (por exemplo, vermelho e azul). Então a propriedade “todos os carros têm a mesma cor” é falsa para . - Temos
verdadeira (um único carro tem cor única), mas é falsa. Logo a prova por indução que só tem a base e o passo com o argumento acima não consegue estabelecer ; e como é falsa, a afirmação original também é falsa.
Passo 5
Explicação de como consertar (ou esclarecer) o argumento e por que isso não salva a afirmação original.
- Se o aluno tivesse provado a base para
e também para (ou, equivalentemente, começasse a indução a partir de assumindo e provando para todo ), então o passo indutivo funcionaria para todo porque aí sempre teríamos . - Mas na prática
é falsa (como mostrei com o contraexemplo), portanto não há como consertar a prova para obter a afirmação original. O erro não é um mero detalhe de escrita: é uma falha lógica na hipótese necessária para que a implicação indutiva seja válida para todos os .
Passo 6
Resumo didático e motivador (para você lembrar na prova).
- A indução exige que o passo indutivo funcione para todo
do domínio; aqui ele falha em porque os dois subconjuntos considerados ficam disjuntos, então não há elemento que force igualdade de cor entre os blocos. - Em linguagem curta: o aluno assumiu implicitamente que os dois grupos de
carros sempre têm interseção não vazia, mas isso é falso quando . Esse é o erro lógico. - Fica a dica: quando usar indução, verifique sempre explicitamente se o passo indutivo vale mesmo para os menores valores de
(especialmente na transição do caso base).
Resposta
O erro é supor que os dois subconjuntos de
carros sempre se sobrepõem. Para
os conjuntos
e
são disjuntos, portanto não há elemento comum que ligue as cores, e o passo indutivo falha na transição
.