Verdadeiro ou falso? Justifique. Seja
uma função:
Todo subconjunto de um conjunto finito é finito?
Todo subconjunto de um conjunto finito é finito?
Passo 1
O enunciado pergunta se a afirmação a seguir é verdadeira ou falsa e pede justificação: “Todo subconjunto de um conjunto finito é finito.”
Está dado apenas que existe uma função , mas essa informação não é necessária para avaliar a afirmativa sobre conjuntos finitos. O que precisamos tratar é a definição de conjunto finito e a relação entre o tamanho de um conjunto e o tamanho dos seus subconjuntos.
Está dado apenas que existe uma função
Passo 2
Definição precisa de “conjunto finito” que vou usar (uma definição padrão e conveniente para provas por indução): diz-se que um conjunto
é finito se existe um inteiro
e uma bijeção entre
e o conjunto
. Aqui:
-
é o conjunto dos primeiros inteiros positivos (quando interpretamos ); - “bijeção” significa uma função que é injetora (elementos distintos de
têm imagens distintas) e sobrejetora (toda etiqueta em é atingida).
Exemplo simples:é finito porque há bijeção com . O conjunto vazio é finito porque corresponde a .
Passo 3
Estratégia da prova: vou provar por indução no número de elementos
de um conjunto finito
que todo subconjunto
é finito. A ideia intuitiva: se
tem
elementos, qualquer subconjunto tem no máximo
elementos, logo corresponde a algum
com
.
Passo 4
Base da indução (
). Se
então
. Os subconjuntos de
são apenas
e este conjunto é finito (corresponde a
). Portanto a afirmativa vale para
.
Passo 5
Passo indutivo. Suponha que a afirmativa seja verdadeira para todo conjunto com
Essa
e
. Assim
é finito.
Em ambos os casos
é finito. Isso conclui o passo indutivo.]
Passo 6
Pelo princípio da indução, a propriedade vale para todo
: se
é finito (isto é,
para algum
), então qualquer subconjunto
também é finito. Logo a afirmação é verdadeira.
Resposta
Verdadeiro.