Demuestre que cualquier función inyectiva de $\{ 1, \dots, n \}$ en sí mismo es biyectivo.
Este es el ejercicio 1 de la página 50 del análisis I de Amann y Escher. He encontrado preguntas similares aquí y aquí, pero ninguna de esas preguntas tiene una solución que utilice lo que se sugiere en el texto.
Ejercicio:
Mi intento:
Parece simple argumentar que, dado que una función inyectiva envía cada elemento en su dominio a un elemento diferente en el codominio, tiene que "golpear" todos los elementos en $\{ 1, \dots, n \}$. No estoy seguro de si esto es lo suficientemente formal y, en cualquier caso, no utiliza la sugerencia dada.
Si uso la pista, entonces el caso base de una función inyectiva $\{ 1 \} \to \{ 1 \}$es definitivamente biyectiva. Suponga que cualquier función inyectiva de$\{ 1, \dots, n \}$ a $\{ 1, \dots, n \}$ es biyectiva y considera la función inyectiva $f \colon \{ 1 , \dots, n + 1 \} \to \{ 1 , \dots, n + 1 \}$tal como se describe. Queremos demostrar que$f$ es biyectiva.
Me parece que hay al menos dos formas básicas de demostrar que $f$es biyectiva. Primero, podemos demostrar que es sobreyectivo, lo que implica considerar algún elemento$l \in \{ 1 , \dots, n + 1 \}$ y mostrando que existe un elemento $m$ en el mismo conjunto de modo que $f(m) = l$. La segunda forma es mostrar que existe una función$i$ tal que $f \circ i$es la función de identidad. Sin embargo, una prueba inductiva realmente debería usar la suposición inductiva, y no estoy seguro de que ninguna de estas tácticas lo haga.
Encuentro la sugerencia dada bastante desconcertante, pero he recopilado algunas ideas sobre la sugerencia a continuación.
- veo que $g$es biyectiva. Es casi la función de identidad, excepto que envía$k$ a $n + 1$ y $n + 1$ a $k$.
- Ya que $f$ y $g$ son inyectables, $h$ también es inyectable.
- Yo tambien veo que $g$ deshace lo que $f$ hace a $n + 1$, por lo tanto $h(n + 1) = n + 1$.
- La función $h$ es casi lo mismo que $f$, excepto por el intercambio realizado por $g$ como se describe en 1.
- La restricción $h \mid \{ 1, \dots, n\}$ no envía ningún elemento a $n + 1$, porque el único elemento que $h$ envía a $n + 1$ es $n + 1$y $n + 1$ está fuera de la restricción.
No tengo idea de cómo improvisar esto en una prueba. Agradezco cualquier ayuda.
Respuestas
Tienes todas las piezas. Tú lo sabes$h\upharpoonright\{1,\ldots,n\}$ es una inyección de $\{1,\ldots,n\}$a sí mismo, por lo que por la hipótesis de inducción es una biyección. Tu tambien sabes que$h(n+1)=n+1$, entonces $h$ es una biyección de $\{1,\ldots,n+1\}$a sí mismo. Finalmente, puede verificar fácilmente que$f=g\circ h$y $g$ es claramente un tan $f$ es una composición de biyecciones de $\{1,\ldots,n+1\}$ a sí mismo y, por lo tanto, también es una biyección.
Su primer intento es básicamente saludar con la mano.
Como escribiste, el caso $n=1$es fácil. Suponga que cada mapa inyectivo de$\{1,2,\ldots,n\}$ en sí mismo es biyectivo y deja $f$ ser un mapa inectivo de $\{1,2,\ldots,n+1\}$en sí mismo. Hay dos posibilidades:
- $f(n+1)=n+1$: Entonces, desde $f$ es inyectable, $f\bigl(\{1,2,\ldots,n\}\bigr)\subset \{1,2,\ldots,n\}$. Entonces, por la hipótesis de inducción, cada$k\in\{1,2,\ldots,n\}$ es igual a $f(l)$, para algunos $l\in\{1,2,\ldots,n\}$. Ya que$f(n+1)=n+1$, $f$ es biyectiva.
- $f(n+1)=k$, para algunos $k<n+1$: Entonces $g\circ f$ mapas $n+1$ dentro $n+1$ y lo escrito en el párrafo anterior muestra que $g\circ f$es biyectiva. Ya que$g$ es biyectivo, $f=g^{-1}\circ(g\circ f)$ y entonces $f$ también es biyectiva.
Sea nuestra hipótesis de inducción que, si una función de un conjunto con n elementos a un conjunto con n elementos es inyectiva, entonces es biyectiva.
(Tenga en cuenta que estamos haciendo una declaración un poco más amplia que hablando de este conjunto, lo que nos permitirá evitar el desorden con el trabajo del caso)
Ahora, probamos el caso n + 1. Sea f una función inyectiva entre dos conjuntos de tamaño n + 1.$f: X \rightarrow Y, |X| = n+1, |Y|=n+1$
Toma un elemento arbitrario de $X$decir $x$, y considere la función de mapear X sin xa Y sin f (x). Esta nueva función,$f^*$, está definida, porque no se enviaron dos puntos al mismo elemento en Y. Por hipótesis de inducción, esta función es sobreyectiva y, por lo tanto, biyectiva. Ahora podemos concluir que f definida en todo X es sobreyectiva cuando se envía a Y, ya que el único elemento restante era f (x), que está en la imagen de x.
Básicamente, estamos eliminando un elemento, mirando f definida en X \ {x}, y argumentando que es sobreyectiva a Y {f (x)}. Luego miramos X, Y y podemos ver que si X \ {x} to Y \ {f (x)} es sobreyectiva, entonces f es sobreyectiva de X a Y.