Prove que qualquer função injetiva de $\{ 1, \dots, n \}$ para si mesmo é bijetivo.
Este é o Exercício 1 da página 50 da Análise I de Amann e Escher. Eu encontrei perguntas semelhantes aqui e aqui, mas nenhuma dessas perguntas tem uma solução que use o que é sugerido no texto.
Exercício:
Minha tentativa:
Parece simples argumentar que, uma vez que uma função injetiva envia cada elemento em seu domínio para um elemento diferente no codomínio, ela tem que "acertar" todos os elementos em $\{ 1, \dots, n \}$. Não tenho certeza se isso é formal o suficiente e, de qualquer forma, não usa a dica dada.
Se eu usar a dica, o caso básico de uma função injetiva $\{ 1 \} \to \{ 1 \}$é definitivamente bijetivo. Suponha que qualquer função injetiva de$\{ 1, \dots, n \}$ para $\{ 1, \dots, n \}$ é bijetivo, e considere a função injetiva $f \colon \{ 1 , \dots, n + 1 \} \to \{ 1 , \dots, n + 1 \}$conforme descrito. Queremos mostrar isso$f$ é bijetivo.
Parece-me que existem pelo menos duas maneiras básicas de mostrar que $f$é bijetivo. Primeiro, podemos mostrar que é sobrejetivo, o que envolve considerar algum elemento$l \in \{ 1 , \dots, n + 1 \}$ e mostrando que existe um elemento $m$ no mesmo conjunto de forma que $f(m) = l$. A segunda maneira é mostrar que existe uma função$i$ de tal modo que $f \circ i$é a função de identidade. No entanto, uma prova indutiva deve realmente usar a suposição indutiva, e não tenho certeza se nenhuma dessas táticas o faz.
Eu acho a dica dada muito misteriosa, mas coletei algumas idéias a respeito da dica abaixo.
- eu vejo isso $g$é bijetivo. É quase a função de identidade, exceto que envia$k$ para $n + 1$ e $n + 1$ para $k$.
- Desde a $f$ e $g$ são injetivos, $h$ também é injetivo.
- Eu também vejo isso $g$ desfaz o que $f$ faz para $n + 1$, conseqüentemente $h(n + 1) = n + 1$.
- A função $h$ é quase o mesmo que $f$, exceto para a troca feita por $g$ conforme descrito em 1.
- A restrição $h \mid \{ 1, \dots, n\}$ não envia nenhum elemento para $n + 1$, porque o único elemento que $h$ envia para $n + 1$ é $n + 1$, e $n + 1$ está fora da restrição.
Não tenho ideia de como transformar isso em uma prova. Agradeço qualquer ajuda.
Respostas
Você tem todas as peças. Você sabe disso$h\upharpoonright\{1,\ldots,n\}$ é uma injeção de $\{1,\ldots,n\}$para si mesmo, então, pela hipótese de indução, é uma bijeção. Você também sabe disso$h(n+1)=n+1$, assim $h$ é uma bijeção de $\{1,\ldots,n+1\}$para si mesmo. Finalmente, você pode verificar facilmente que$f=g\circ h$, e $g$ é claramente tão $f$ é uma composição de bijeções de $\{1,\ldots,n+1\}$ para si mesmo e, portanto, também é uma bijeção.
Sua primeira tentativa é basicamente acenar à mão.
Como você escreveu, o caso $n=1$é fácil. Suponha que cada mapa injetivo de$\{1,2,\ldots,n\}$ em si mesmo é bijetivo e deixe $f$ ser um mapa inetivo de $\{1,2,\ldots,n+1\}$em si mesmo. Existem duas possibilidades:
- $f(n+1)=n+1$: Então, desde $f$ é injetivo, $f\bigl(\{1,2,\ldots,n\}\bigr)\subset \{1,2,\ldots,n\}$. Então, pela hipótese de indução, cada$k\in\{1,2,\ldots,n\}$ é igual a $f(l)$, para alguns $l\in\{1,2,\ldots,n\}$. Desde a$f(n+1)=n+1$, $f$ é bijetivo.
- $f(n+1)=k$, para alguns $k<n+1$: Então $g\circ f$ mapas $n+1$ para dentro $n+1$ e o que foi escrito no parágrafo anterior mostra que $g\circ f$é bijetivo. Desde a$g$ é bijetivo, $f=g^{-1}\circ(g\circ f)$ e entao $f$ é bijetivo também.
Seja nossa hipótese de indução que, se uma função de um conjunto com n elementos para um conjunto com n elementos é injetiva, então é bijetiva.
(Observe que estamos fazendo uma declaração um pouco mais ampla do que falar sobre este conjunto, o que nos permitirá evitar confusão com o trabalho do caso)
Agora, provamos o caso n + 1. Seja f uma função injetiva entre dois conjuntos de tamanho n + 1.$f: X \rightarrow Y, |X| = n+1, |Y|=n+1$
Pegue um elemento arbitrário de $X$, diga $x$e considere a função do mapeamento de X sem x para Y sem f (x). Esta nova função,$f^*$, é definido, porque nenhum ponto foi enviado para o mesmo elemento em Y. Por hipótese de indução, essa função é sobrejetiva e, portanto, bijetiva. Agora podemos concluir que f definido em todo X é sobrejetivo quando enviado para Y, pois o único elemento remanescente era f (x), que está na imagem de x.
Basicamente, estamos removendo um elemento, observando f definido em X \ {x}, e argumentando que é sobrejetivo para Y {f (x)}. Então olhamos para X, Y e podemos ver que se X \ {x} para Y \ {f (x)} é sobrejetiva, então f é sobrejetiva de X para Y.