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 últimos
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.
“Entre quaisquer
Passo 1
O enunciado apresenta a afirmação: “Entre quaisquer
carros, todos têm a mesma cor.”
O aluno dá uma prova por indução com estas partes:
O aluno dá uma prova por indução com estas partes:
- Base: para
a afirmação é verdadeira (um carro só tem uma cor). - Passo indutivo: assumindo a afirmação verdadeira para
carros, toma-se uma coleção de carros considera-se o primeiro subconjunto de carros e o segundo . Pela hipótese de indução é monocromático e também; como conclui-se que as cores coincidem e, assim, todos os carros têm a mesma cor.
O que nos pede: verificar se a prova está correta; se não, apontar o erro e explicar didaticamente por que falha (mostrando o que exatamente não vale e um contraexemplo simples).
Passo 2
Relembrando o princípio da indução (de forma clara e simples): para provar uma propriedade
para todo inteiro
por indução, é preciso:
- Provar a base:
é verdadeira. - Provar o passo indutivo: para todo
, assumir verdadeira e a partir disso provar .
Se ambas as etapas valem para todo
apropriado, então
vale para todo
. Importante: o passo indutivo deve ser válido para o primeiro
que segue a base (ou seja, deve funcionar para
se a base foi
). Não se pode tacitamente assumir que o passo funciona apenas para
grandes — ele precisa valer já logo após a base.
Passo 3
Formalizando o argumento do aluno:
- Define-se
: “qualquer conjunto de carros é monocromático”. - Base:
é verdadeira. - Passo: suponha
verdadeira e tome carros . Os conjuntos têm tamanho . Pela hipótese é toda de uma cor e também. O argumento final usa que contém carros (por exemplo ), logo como esse carro comum pertence a ambos os conjuntos suas cores coincidem e assim todos os carros têm a mesma cor.
Esse é o raciocínio dado — parece elegante e curto. Agora vamos checar cada passo com cuidado.
Passo 4
Onde está o problema? analisar a interseção dos conjuntos:
-
. O número de elementos dessa interseção é . - Se
(ou seja, se ), então a interseção não é vazia e de fato há um carro comum cuja cor faz a ligação entre os dois subconjuntos. - Porém, quando
temos . Ou seja, para os conjuntos são e então . Neste caso NÃO há carro em comum que force as cores a coincidirem. Portanto o argumento do aluno usa implicitamente a hipótese , que só é verdadeira quando . Mas a prova de indução precisa que o passo indutivo funcione também para (para poder deduzir a partir de ). Logo existe uma falha lógica: o passo indutivo, tal como apresentado, não é válido para .
Em termos simples: o argumento só funciona a partir do caso em que os dois subconjuntos de tamanho
têm interseção não vazia, ou seja, para
. Ele não prova
a partir de
. Como a indução começa em
, o elo
falta.
Passo 5
Exemplo concreto que destrói a afirmação (contraexemplo fácil): considere
e dois carros distintos
tais que
é vermelho e
é azul. Claramente nem todos os carros (os dois) têm a mesma cor, logo
é falsa. Portanto a afirmação “entre quaisquer
carros todos têm a mesma cor” não é verdadeira para todo
. Uma prova por indução que pretendesse mostrar isso deveria ser capaz de provar
a partir de
, mas o passo do aluno não faz isso (porque falta interseção).
Passo 6
Como interpretar e aprender com isso (dica prática para a prova):
- Verifique sempre se o passo indutivo funciona para o menor
possível (o que segue imediatamente da base). Não aceite argumentos que tacitamente usam propriedades que só surgem em casos maiores. - Identifique hipóteses escondidas: aqui a hipótese escondida era “os dois subconjuntos de tamanho
têm interseção não vazia”. Tornar essa hipótese explícita mostra que o argumento só vale para . - Se um passo indutivo requer uma propriedade adicional (como interseção não vazia), então ou:
- prove essa propriedade separadamente para o caso inicial (por exemplo prove
diretamente), ou - ajuste a base da indução para começar num
maior (por exemplo comece a indução em ) — mas isso só é aceitável se a afirmação for verdadeira a partir daquele ponto. No nosso caso é falsa, então não há conserto possível: a afirmação original é falsa.
- prove essa propriedade separadamente para o caso inicial (por exemplo prove
Passo 7
Resumo final e conclusão: a prova do aluno é falaciosa porque o passo indutivo usa a interseção não vazia de
e
, o que falha no caso
(passo de
para
). A afirmação é falsa (contraexemplo: dois carros de cores diferentes). Portanto a “demonstração” não é correta.
Resposta
A demonstração é falha; o erro ocorre no passo indutivo ao assumir que
(isso requer
), logo o passo de
para
não está provado. A afirmação é falsa (contraexemplo: dois carros de cores diferentes).