Seja X neq emptyset. Prove que X é infinito se, e somente se, forall n in N não existe uma aplicação sobrejetiva f: In X.

Passo 1

Primeiro, vamos entender o que o exercício está pedindo. Temos um conjunto $ X $ que não está vazio ($ X \neq \emptyset $). Precisamos provar que $ X $ é infinito se, e somente se, para todo número natural $ n $, não existe uma função sobrejetiva $ f: I_n \rightarrow X $, onde $ I_n = {1, 2, \dots, n} $.
Aqui, o conteúdo estudado envolve conceitos de conjuntos finitos e infinitos e funções sobrejetivas (funções que cobrem todo o conjunto de chegada). Vamos precisar entender o que significa um conjunto ser infinito e o que é uma função sobrejetiva para resolver esse problema.

Passo 2

Vamos começar entendendo o que significa um conjunto ser infinito. Um conjunto $ X $ é dito infinito se ele não possui um número finito de elementos. Ou seja, não existe um número natural $ n $ tal que $ X $ tenha exatamente $ n $ elementos.
Por outro lado, uma função sobrejetiva $ f: A \rightarrow B $ é uma função onde, para todo elemento $ b $ em $ B $, existe pelo menos um elemento $ a $ em $ A $ tal que $ f(a) = b $. Isso significa que todos os elementos de $ B $ são “alcançados” pela função $ f $.

Passo 3

Primeiro, vamos provar a direção “se $ X $ é infinito, então para todo $ n \in \mathbb{N} $, não existe uma função sobrejetiva $ f: I_n \rightarrow X $”.
Suponha que $ X $ seja infinito. Vamos mostrar que não existe uma função sobrejetiva de $ I_n $ para $ X $ para qualquer $ n $.
Se $ X $ é infinito e $ I_n $ tem apenas $ n $ elementos (um número finito), então, ao mapear cada elemento de $ I_n $ para $ X $, estaremos mapeando um número finito de elementos para um conjunto infinito. Isso significa que sempre haverá elementos em $ X $ que não são atingidos pela função $ f $, pois não há quantidade suficiente de elementos em $ I_n $ para cobrir todo $ X $. Portanto, não pode existir uma função sobrejetiva nesse caso.

Passo 4

Agora, vamos provar a direção “se para todo $ n \in \mathbb{N} $, não existe uma função sobrejetiva $ f: I_n \rightarrow X $, então $ X $ é infinito”.
Suponha que para todo número natural $ n $, não existe uma função sobrejetiva de $ I_n $ para $ X $. Queremos mostrar que $ X $ é infinito.
Se $ X $ fosse finito, digamos com $ m $ elementos, então poderíamos escolher $ n = m $ e definir uma função bijetiva (que é tanto injetiva quanto sobrejetiva) de $ I_m $ para $ X $, já que ambos teriam o mesmo número de elementos. Isso contradiz nossa suposição inicial de que não existe tal função sobrejetiva para nenhum $ n $. Portanto, $ X $ não pode ser finito, ou seja, deve ser infinito.

Resposta

Portanto, mostramos que $ X $ é infinito se, e somente se, para todo $ n \in \mathbb{N} $, não existe uma função sobrejetiva $ f: I_n \rightarrow X $. Isso conclui a prova.

Exercícios relacionados