Me encontré con el siguiente ejercicio, mientras que el auto-estudio de Terrence Tao del libro de Análisis I:
Ejercicio 3.6.4 Deje $X$ $Y$ finita de conjuntos. A continuación,$Y^X$, el conjunto de funciones con dominio $X$ y el rango de $Y$, es finito y $\#(Y^X)=\#(Y)^{\#(X)}$.
Nota: Esta pregunta se ha hecho dos veces antes (aquí y aquí) en este sitio. Mi intento fue una prueba por inducción, que no estaba presente en cualquiera de estos puestos. Por ello, pido simplemente que todas las respuestas correctas a mi paso inductivo, o cualquier otro error, y no dar soluciones alternativas. Con eso en mente, aquí está mi ir:
Deje $X$ $Y$ finita de conjuntos con bijections $f:X\to\Bbb N_n$ $g:Y\to\Bbb N_m$ (donde $\Bbb N_n$ denota el conjunto de números naturales a menos de $n$, donde yo estoy usando la convención de que los números naturales empezar en cero). En esta prueba, se corrige $m$ e inducir a los en $n$. Si sucede que $n=0$,$\#(Y^X)=1$, ya que existe una única función de $\emptyset\to Y$ (singularidad es un vacío de la verdad, en este caso). Desde $m^0=1$, la demanda es trivial en este caso, y podemos suponer que la $n>0$. Si sucede que $n=1$, $Y^X$ es el conjunto de todas las funciones $\{*\}\to Y$ $X$ es un singleton conjunto. Aviso de que si la imagen de $\{*\}$ bajo cualquiera de estos mapas es mayor que uno, la imagen de $x$ no puede ser único, lo que contradice nuestra suposición de que $Y^X$ sólo consta de funciones. Por lo tanto, la imagen de uno de estos mapas es un singleton, y basta con contar las elemtnts de $Y$ $\{*\}$ permanece fijo: $$\#(Y^X)=\#\left(\bigcup_{y\in Y}\{y\}\right)=\#(Y)^{\#\{*\}}.$$ Además, supongamos que nuestro reclamo tiene para algunos $n\in\Bbb N$. Entonces, si $x'\notin X$ y $Z=X\cup\{x'\}$, $$\begin{align}Y^Z :&=\{f\mid \operatorname{dom}(f)=Z\land \operatorname{ran}(f)=Y\} \\ &=\{(x,y)\in f\mid x\in X\cup\{x'\}\land y\in Y\} \\ &= (?) \\ &=Y^X\times Y^{\{x'\}},\end{align}$$ y, por lo tanto, $$\#(Y^Z)=m^n\times m=m^{n+1}.$$ De esta manera se cierra la inducción. Lo que me estoy perdiendo en el paso inductivo? Lo que debería ir en lugar de $(?)$ en la tercera línea de arriba? Parece plausible que funciona a ser $Y^X\times Y^{\{x'\}}$, de lo contrario, no estoy seguro de cómo aplicar la hipótesis inductiva. También, uno puede llegar a una contradicción de la demanda original, teniendo en cuenta $$\begin{align}\#(Y^Z)&=\#\left(\{f\mid \operatorname{dom}(f)=X\land \operatorname{ran}(f)=Y\}\cup \{f\mid \operatorname{dom}(f)=\{x'\}\land \operatorname{ran}(f)=Y\}\right) \\ &= m^n+m\neq m^{n+1} \end{align}.$$ ¿Por qué es esto incorrecto? Gracias de antemano.
Actualización: Combinatoria hablando, la carnalidad de la $Y^Z$ debe $\#(Y^X)\times\#(Y)$, como se puede emparejar $\{x'\}$ con cada elemento de la $Y$, que como se mencionó anteriormente, debe ceder el cardinalidad de a $Y$. Pero, esto está en contradicción con lo que he escrito antes, y todavía estoy interesado en por qué es falso.
