Exercício 2.26. O que significa dizer que
é o menor conjunto indutivo? Explique por que essa propriedade é essencial para a validade da indução.
Passo 1
O enunciado pede duas coisas claras:
- Explicar o que significa dizer que
é o menor conjunto indutivo. - Explicar por que essa propriedade é essencial para a validade da indução.
Informações/condições implícitas no enunciado que vamos usar (não vou resolver aqui, só listar):
- Há a noção de conjunto indutivo (vamos usar a definição padrão abaixo).
- Existe o conjunto
(os naturais na construção de von Neumann) e a ideia de “menor” entre conjuntos indutivos.
Passo 2
Definição de conjunto indutivo (passo didático):
Um conjunto é chamado indutivo se satisfaz duas condições:
Um conjunto
-
. (o “zero” está em ) - Sempre que
, então o sucessor de , definido por , também pertence a .
Expliquei cada parte:
é o conjunto vazio (na construção de von Neumann corresponde a
); o sucessor
pega o conjunto
e o coloca como elemento dentro de si, produzindo o “próximo” natural.
Passo 3
Definição formal de
como menor conjunto indutivo:
A definição padrão é
A definição padrão é
Isto significa que
é a interseção de todos os conjuntos indutivos. A consequência imediata e equivalente à frase “menor conjunto indutivo” é:
- Para todo conjunto indutivo
vale .
Explicação intuitiva do que “menor” quer dizer aqui: entre todos os conjuntos que são indutivos,
contém exatamente os elementos que estão forçados a estar em qualquer conjunto indutivo; portanto não há nenhum conjunto indutivo estritamente contido em
.
Passo 4
Exemplo concreto curto (para fixar):
Na construção de von Neumann:
Na construção de von Neumann:
O conjunto
é
. Se alguém apresentar qualquer conjunto
com
e fechado por sucessor, então necessariamente
(isto é,
) estão todos em
. Por isso
é o “menor” — não sobra nenhum natural que não esteja em todo conjunto indutivo.
Passo 5
Como essa propriedade é usada para provar o princípio da indução (esquema da prova):
Queremos provar que uma propriedade vale para todo
dadas as hipóteses:
Queremos provar que uma propriedade
- (Base)
é verdadeira (aqui ). - (Passo indutivo) Para todo
, se então .
Construção que transforma essa situação em algo sobre conjuntos: defina
Ou seja,
é o conjunto dos naturais que satisfazem
. Agora verificamos que
é indutivo (relativo a
):
- Pela hipótese base,
. - Pela hipótese do passo indutivo, se
então .
Portantoé um conjunto indutivo (ou, mais precisamente, é indutivo em relação aos sucessores dentro de ).
Passo 6
Conectar com o fato de que
é o menor indutivo:
Como é indutivo, e
está contido em todo conjunto indutivo, tem-se
. Mas por definição
. Logo
. Isso significa que
vale para todo
. Assim obtemos a conclusão da indução.
Como
Comentário intuitivo: a razão pela qual isso funciona é que o conjunto dos elementos que satisfazem a propriedade é obrigado a ser um conjunto indutivo (pela base e pelo passo). Como
é o menor indutivo, ele já está inteiro dentro de qualquer indutivo; portanto não sobra nenhum natural que possa escapar à propriedade.
Passo 7
Por que a “menoridade” é essencial (insistindo na ideia):
- Se
não tivesse a propriedade de estar contido em todo conjunto indutivo, então mesmo sabendo que o conjunto (onde vale) é indutivo, não poderíamos concluir que ; poderia haver elementos de fora de . Ou seja, a conclusão "todo natural satisfaz " dependeria de que seja forçado a estar dentro de qualquer conjunto indutivo. - Portanto a validade do esquema de indução depende exatamente dessa característica: transformar a verificação de uma propriedade em mostrar que o conjunto de pontos que satisfazem a propriedade é indutivo e então usar que
é o menor indutivo para garantir que esse conjunto coincide com .
Passo 8
Observação sobre equivalência lógica (bônus didático):
Uma forma de enxergar é que a definição " é a interseção de todos os indutivos" e o princípio da indução são essencialmente equivalentes. A interseção produz uma estrutura mínima que torna a argumentação por conjuntos indutivos possível. Por isso construir os naturais como o menor indutivo e postular a existência de um conjunto indutivo (axioma de infinito, em teoria de conjuntos) é o caminho usado para justificar rigorosamente a indução.
Uma forma de enxergar é que a definição "
Resposta
Significa que
é subconjunto de qualquer conjunto indutivo; equivalentemente
.
Essa propriedade é essencial porque, dado qualquer predicado com
e tal que
, o conjunto
é indutivo; como
está contido em todo indutivo, segue
, ou seja,
vale para todo
.
Essa propriedade é essencial porque, dado qualquer predicado