Dimostrare che qualsiasi funzione iniettiva da $\{ 1, \dots, n \}$ a se stesso è biettivo.

Aug 19 2020

Questo è l'esercizio 1 da pagina 50 dell'Analisi I di Amann ed Escher. Ho trovato domande simili qui e qui, ma nessuna di queste domande ha una soluzione che utilizza ciò che viene accennato nel testo.

Esercizio:

Il mio tentativo:

Sembra semplice sostenere che, poiché una funzione iniettiva invia ogni elemento nel suo dominio a un elemento diverso nel codominio, deve "colpire" tutti gli elementi in $\{ 1, \dots, n \}$. Non sono sicuro che sia abbastanza formale, e in ogni caso non usa il suggerimento dato.

Se uso il suggerimento, allora il caso base di una funzione iniettiva $\{ 1 \} \to \{ 1 \}$è decisamente biettivo. Supponiamo che qualsiasi funzione iniettiva da$\{ 1, \dots, n \}$ per $\{ 1, \dots, n \}$ è biiettiva e considera la funzione iniettiva $f \colon \{ 1 , \dots, n + 1 \} \to \{ 1 , \dots, n + 1 \}$come descritto. Lo vogliamo dimostrare$f$ è biettivo.

Mi sembra che ci siano almeno due modi fondamentali per dimostrarlo $f$è biettivo. In primo luogo, possiamo dimostrare che è suriettivo, il che implica la considerazione di alcuni elementi$l \in \{ 1 , \dots, n + 1 \}$ e mostrare che esiste un elemento $m$ nello stesso insieme tale che $f(m) = l$. Il secondo modo è mostrare che esiste una funzione$i$ tale che $f \circ i$è la funzione di identità. Tuttavia, una dimostrazione induttiva dovrebbe davvero utilizzare l'ipotesi induttiva, e non sono sicuro che nessuna di queste tattiche lo faccia.

Trovo il suggerimento fornito piuttosto sconcertante, ma ho raccolto alcuni pensieri riguardo al suggerimento di seguito.

  1. capisco $g$è biettivo. È quasi la funzione di identità tranne che invia$k$ per $n + 1$ e $n + 1$ per $k$.
  2. Da $f$ e $g$ sono iniettivi, $h$ è anche iniettiva.
  3. Lo vedo anche io $g$ annulla cosa $f$ fa a $n + 1$, quindi $h(n + 1) = n + 1$.
  4. La funzione $h$ è quasi uguale a $f$, ad eccezione dello scambio fatto da $g$ come descritto in 1.
  5. La restrizione $h \mid \{ 1, \dots, n\}$ non invia alcun elemento a $n + 1$, perché l'unico elemento che $h$ invia a $n + 1$ è $n + 1$, e $n + 1$ è al di fuori della restrizione.

Non ho idea di come trasformare questo in una prova. Apprezzo qualsiasi aiuto.

Risposte

2 BrianM.Scott Aug 19 2020 at 03:56

Hai tutti i pezzi. Lo sai$h\upharpoonright\{1,\ldots,n\}$ è un'iniezione di $\{1,\ldots,n\}$a se stesso, quindi per l'ipotesi di induzione è una biiezione. Lo sai anche tu$h(n+1)=n+1$, così $h$ è una biiezione di $\{1,\ldots,n+1\}$a se stesso. Infine, puoi facilmente verificarlo$f=g\circ h$, e $g$ è chiaramente così $f$ è una composizione di biiezioni da $\{1,\ldots,n+1\}$ a se stesso ed è quindi anche una tale biiezione.

Il tuo primo tentativo è fondamentalmente solo il gesto della mano.

3 JoséCarlosSantos Aug 19 2020 at 03:55

Come hai scritto, il caso $n=1$è facile. Supponiamo che ogni mappa iniettiva da$\{1,2,\ldots,n\}$ di per sé è biettivo e lascia $f$ essere una mappa inettiva da $\{1,2,\ldots,n+1\}$in se stesso. Ci sono due possibilità:

  1. $f(n+1)=n+1$: Allora, da allora $f$ è iniettiva, $f\bigl(\{1,2,\ldots,n\}\bigr)\subset \{1,2,\ldots,n\}$. Quindi, per l'ipotesi di induzione, ciascuno$k\in\{1,2,\ldots,n\}$ è uguale a $f(l)$, per alcuni $l\in\{1,2,\ldots,n\}$. Da$f(n+1)=n+1$, $f$ è biettivo.
  2. $f(n+1)=k$, per alcuni $k<n+1$: Poi $g\circ f$ mappe $n+1$ in $n+1$ e quanto scritto nel paragrafo precedente lo dimostra $g\circ f$è biettivo. Da$g$ è biettivo, $f=g^{-1}\circ(g\circ f)$ e così $f$ è anche biettivo.
1 EthanHorsfall Aug 19 2020 at 04:01

Sia la nostra ipotesi di induzione che, se una funzione da un insieme con n elementi a un insieme con n elementi è iniettiva, allora è biiettiva.

(Si noti che stiamo facendo un'affermazione leggermente più ampia rispetto a parlare di questo set, che ci permetterà di evitare confusione con il casework)

Ora, dimostriamo il caso n + 1. Sia f una funzione iniettiva tra due insiemi di dimensione n + 1.$f: X \rightarrow Y, |X| = n+1, |Y|=n+1$

Prendi un elemento arbitrario da $X$, dì $x$e considera la funzione dalla mappatura di X senza x a Y senza f (x). Questa nuova funzione,$f^*$, è definita, perché non sono stati inviati due punti allo stesso elemento in Y. Per ipotesi di induzione, questa funzione è suriettiva e quindi biiettiva. Ora possiamo concludere che f definita su tutto X è suriettiva quando inviata a Y, poiché l'unico elemento rimanente era f (x), che è nell'immagine di x.

Fondamentalmente, stiamo rimuovendo un elemento, guardando f definito su X \ {x} e sostenendo che è suriettivo a Y {f (x)}. Quindi guardiamo X, Y e possiamo vedere che se X \ {x} su Y \ {f (x)} è suriettiva, allora f è suriettiva da X a Y.