Verdadeiro ou falso? Justifique. Seja f: A \rightarrow B uma função:
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 f: A \to B, 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.

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 S é finito se existe um inteiro n\ge 0 e uma bijeção entre S e o conjunto \{1,\dots,n\}. Aqui:
  • \{1,\dots,n\} é o conjunto dos primeiros n inteiros positivos (quando n=0 interpretamos \{1,\dots,0\}=\emptyset);
  • “bijeção” significa uma função que é injetora (elementos distintos de S têm imagens distintas) e sobrejetora (toda etiqueta em \{1,\dots,n\} é atingida).
    Exemplo simples: \{a,b,c\} é finito porque há bijeção com \{1,2,3\}. O conjunto vazio \emptyset é finito porque corresponde a n=0.

Passo 3

Estratégia da prova: vou provar por indução no número de elementos n de um conjunto finito S que todo subconjunto T\subseteq S é finito. A ideia intuitiva: se S tem n elementos, qualquer subconjunto tem no máximo n elementos, logo corresponde a algum \{1,\dots,k\} com k\le n.

Passo 4

Base da indução ( n=0). Se |S|=0 então S=\emptyset. Os subconjuntos de \emptyset são apenas \emptyset e este conjunto é finito (corresponde a n=0). Portanto a afirmativa vale para n=0.

Passo 5

Passo indutivo. Suponha que a afirmativa seja verdadeira para todo conjunto com n\) elementos (hipótese de indução): qualquer subconjunto de um conjunto com \(n\) elementos é finito. Agora considere um conjunto \(S\) com \(|S|=n+1\). Escolha um elemento qualquer \(a\in S\). Seja \(T\) um subconjunto qualquer de \(S\). Existem dois casos: - Caso 1: \(a\notin T\). Então \(T\subseteq S\setminus\{a\}\). Mas \(S\setminus\{a\}\) tem \(n\) elementos, então, pela hipótese de indução, \(T\) é finito. - Caso 2: \(a\in T\). Então considere \(T' := T\setminus\{a\}\). Temos \(T'\subseteq S\setminus\{a\}\), e portanto, pela hipótese de indução, \(T'\) é finito: existe \(k\ge 0\) tal que existe bijeção \(\varphi: T' \to \{1,\dots,k\}\). Agora constrói-se uma bijeção de \(T\) para \(\{1,\dots,k+1\}\) definindo \[\psi(x)=\begin{cases} \varphi(x), & x\in T',\\[4pt] k+1, & x=a. \end{cases}
Essa \psi\] é bem definida, injetora e sobrejetora, logo é uma bijeção entre \(T e \{1,\dots,k+1\}. Assim T é finito.
Em ambos os casos T é finito. Isso conclui o passo indutivo.]

Passo 6

Pelo princípio da indução, a propriedade vale para todo n: se S é finito (isto é, |S|=n para algum n), então qualquer subconjunto T\subseteq S também é finito. Logo a afirmação é verdadeira.

Resposta

Verdadeiro.

Exercícios relacionados