Questão 1 Se
é um conjunto finito e a
, usando a definição de conjunto finito, mostre que
é também finito.
Passo 1
O enunciado dá:
-
é um conjunto finito. -
.
O que se pede:
- Mostrar que
também é finito.
Informações relevantes que vou usar (não estou resolvendo ainda, apenas listando):
- A definição de conjunto finito que vou usar: existe
e uma bijeção . - Vou precisar das definições de função injetiva, sobrejetiva e bijetiva.
Passo 2
Vamos revisar com calma os conceitos que vamos usar (aquelas “aulas rápidas” para você não se perder).
Definição de bijeção:
- Uma função
é injetiva se, para quaisquer , implica . - Uma função
é sobrejetiva se, para todo , existe tal que . - Uma função é bijetiva se é simultaneamente injetiva e sobrejetiva. Uma bijeção estabelece uma “correspondência um a um” entre os elementos de
e os de .
O que significa dizer "
é finito" (usada aqui):
- Significa que existe um número natural
tal que há uma bijeção
Esse
é o número de elementos de
(a cardinalidade
).
Exemplo concreto (para intuir): se
então existe bijeção com
, por exemplo
.
Passo 3
Começo a construção formal: como
é finito, escolha
e uma bijeção
Como
, o valor
está bem definido e pertence a
.
Observação: isso mostra que
não é vazio (pois contém
), logo
.
A ideia será construir explicitamente uma bijeção
o que provará que
é finito (com exatamente
elementos).
Passo 4
Definição da função
Explicando em palavras: pego a numeração dada por
e “retiro” o número
(o rótulo de
), recompactando os rótulos maiores que
diminuindo-os em
. Assim os rótulos possíveis para
ficam exatamente em
.
Preciso agora mostrar que
é bem definida, injetiva e sobrejetiva.]
Passo 5
Verificação de que
é bem definida:
- Para
tem-se e , logo ou ou . Em ambos os casos a fórmula de descreve um número em . Assim está sempre em . Logo é bem definida como função .
Passo 6
Verificação de injetividade de
:
Sejam tais que
. Vamos analisar os casos possíveis de acordo com os valores
e
.
Sejam
-
Se
e , então e . Assim . Como é injetiva, segue . -
Se
e , então e . Assim , logo . Como é injetiva, segue . -
Se
e (ou vice-versa), então enquanto (porque dá ). Assim , o que impede . Logo esse caso não ocorre.
Portanto, sempre que
concluímos
. Logo
é injetiva.
Passo 7
Verificação de sobrejetividade de
:
Pegue um . Queremos encontrar
com
.
Pegue um
-
Se
: como é sobrejetiva, existe tal que . Como , esse não é , logo . Para esse temos então . -
Se
(isto é, ): considere . Como é sobrejetiva, existe com . Note que , então esse também não é , logo . Para esse temos e então .
Em ambos os subcasos encontramos
com
. Portanto
é sobrejetiva.
Passo 8
Conclusão:
é injetiva e sobrejetiva, logo é bijeção entre
e
. Pela definição de conjunto finito usada, isso mostra que
é finito.
Além disso, se
então
.