Prouvez que toute fonction injective de $\{ 1, \dots, n \}$ en lui-même est bijectif.

Aug 19 2020

Il s'agit de l'exercice 1 de la page 50 de l' analyse I par Amann et Escher. J'ai trouvé des questions similaires ici et ici, mais aucune de ces questions n'a de solution qui utilise ce qui est évoqué dans le texte.

Exercice:

Ma tentative:

Il semble simple de soutenir que, puisqu'une fonction injective envoie chaque élément de son domaine à un élément différent du codomain, elle doit "frapper" tous les éléments de $\{ 1, \dots, n \}$. Je ne suis pas sûr que ce soit assez formel, et en tout cas il n'utilise pas l'indice donné.

Si j'utilise l'indice, alors le cas de base d'une fonction injective $\{ 1 \} \to \{ 1 \}$est définitivement bijectif. Supposons que toute fonction injective de$\{ 1, \dots, n \}$ à $\{ 1, \dots, n \}$ est bijective, et considère la fonction injective $f \colon \{ 1 , \dots, n + 1 \} \to \{ 1 , \dots, n + 1 \}$comme décrit. Nous voulons montrer que$f$ est bijectif.

Il me semble qu'il y a au moins deux moyens de base pour montrer que $f$est bijectif. Tout d'abord, nous pouvons montrer que c'est surjectif, ce qui implique de considérer un élément$l \in \{ 1 , \dots, n + 1 \}$ et montrant qu'il existe un élément $m$ dans le même ensemble de sorte que $f(m) = l$. La deuxième façon est de montrer qu'il existe une fonction$i$ tel que $f \circ i$est la fonction d'identité. Cependant, une preuve inductive devrait vraiment utiliser l'hypothèse inductive, et je ne suis pas sûr qu'aucune de ces tactiques le fasse.

Je trouve l'indice donné assez mystifiant, mais j'ai rassemblé quelques réflexions concernant l'indice ci-dessous.

  1. je vois ça $g$est bijectif. C'est presque la fonction d'identité sauf qu'elle envoie$k$ à $n + 1$ et $n + 1$ à $k$.
  2. Puisque $f$ et $g$ sont injectifs, $h$ est également injectif.
  3. Je vois aussi ça $g$ annule quoi $f$ fait pour $n + 1$, Par conséquent $h(n + 1) = n + 1$.
  4. La fonction $h$ est presque le même que $f$, sauf pour l'échange effectué par $g$ comme décrit en 1.
  5. La restriction $h \mid \{ 1, \dots, n\}$ n'envoie aucun élément à $n + 1$, parce que le seul élément qui $h$ envoie à $n + 1$ est $n + 1$, et $n + 1$ est en dehors de la restriction.

Je n'ai aucune idée de comment transformer cela en preuve. J'apprécie toute aide.

Réponses

2 BrianM.Scott Aug 19 2020 at 03:56

Vous avez toutes les pièces. Tu le sais$h\upharpoonright\{1,\ldots,n\}$ est une injection de $\{1,\ldots,n\}$à lui-même, donc par l'hypothèse d'induction, c'est une bijection. Tu sais aussi que$h(n+1)=n+1$, donc $h$ est une bijection de $\{1,\ldots,n+1\}$à lui-même. Enfin, vous pouvez facilement vérifier que$f=g\circ h$, et $g$ est clairement un so $f$ est une composition de bijections de $\{1,\ldots,n+1\}$ à lui-même et est donc aussi une telle bijection.

Votre première tentative consiste essentiellement à faire des vagues.

3 JoséCarlosSantos Aug 19 2020 at 03:55

Comme vous l'avez écrit, l'affaire $n=1$est facile. Supposons que chaque carte injective de$\{1,2,\ldots,n\}$ en lui-même est bijectif et laisse $f$ être une carte inactive de $\{1,2,\ldots,n+1\}$en lui-même. Il y a deux possibilités:

  1. $f(n+1)=n+1$: Puis, depuis $f$ est injectif, $f\bigl(\{1,2,\ldots,n\}\bigr)\subset \{1,2,\ldots,n\}$. Donc, par l'hypothèse d'induction, chacun$k\in\{1,2,\ldots,n\}$ est égal à $f(l)$, pour certains $l\in\{1,2,\ldots,n\}$. Puisque$f(n+1)=n+1$, $f$ est bijectif.
  2. $f(n+1)=k$, pour certains $k<n+1$: Ensuite $g\circ f$ Plans $n+1$ dans $n+1$ et ce qui a été écrit dans le paragraphe précédent montre que $g\circ f$est bijectif. Puisque$g$ est bijectif, $f=g^{-1}\circ(g\circ f)$ et donc $f$ est bijective aussi.
1 EthanHorsfall Aug 19 2020 at 04:01

Supposons que notre hypothèse d'induction soit que, si une fonction d'un ensemble à n éléments à un ensemble de n éléments est injective, alors elle est bijective.

(Notez que nous faisons une déclaration un peu plus large que de parler de cet ensemble, ce qui nous permettra d'éviter le désordre avec le dossier)

Maintenant, nous prouvons le cas n + 1. Soit f une fonction injective entre deux ensembles de taille n + 1.$f: X \rightarrow Y, |X| = n+1, |Y|=n+1$

Prendre un élément arbitraire de $X$, dire $x$, et considérons la fonction de mappage de X sans x à Y sans f (x). Cette nouvelle fonction,$f^*$, est définie, car aucun deux points n'ont été envoyés au même élément dans Y. Par hypothèse de récurrence, cette fonction est surjective et donc bijective. Nous pouvons maintenant conclure que f défini sur tout X est surjectif lorsqu'il est envoyé à Y, car le seul élément restant était f (x), qui est dans l'image de x.

Fondamentalement, nous supprimons un élément, en regardant f défini sur X \ {x}, et en soutenant qu'il est surjectif à Y {f (x)}. Ensuite, nous regardons X, Y et pouvons voir que si X \ {x} à Y \ {f (x)} est surjectif, alors f est surjectif de X à Y.