Given sets $X$ and $Y$ we denote the set of functions from $X$ to $Y$ by $\text{Fun}(X,Y)$.


  • $k,n \in \mathbb{Z}^+$
  • $X_1 = \{x_1,x_2\dots, x_{k+1}\}$
  • $Y = \{y_1, y_2, \dots , y_n\}$

Then, for a $y_i \in Y$, we can create the bijection:

$$\{f:X_1 \rightarrow Y \mid f(x_{k+1})=y_i\} \rightarrow \text{Fun}(\{x_1,x_2,\dots,x_k\},Y) \tag{1}$$

defined by

$$f\mapsto f|(X_1 - \{x_{k+1}\}), \tag{2}$$

I would like to prove that the function defined above is a bijection, but the way it is written is new to me.

What I understand is:

Equation (1) is defining the function's domain and codomain. Then, equation (2) tells how to map an element in the domain to an element in the codomain. This says that the bijection will take a function, $f:X_1 \rightarrow Y$ and map it back to $f$ again, except that the domain will now be restricted to $X_1-\{x_{k+1}\}$

How do I use (1) and (2) to show that the defined function is an injection and a surjection?

For injection, I've tried:

Let the $h$ be the function defined.

$$\begin{align} h(f_1)=h(f_2) & \Rightarrow & f_1\mid(X_1 - \{x_{k+1}\}) = f_2\mid(X_1 - \{x_{k+1}\}) \end{align}$$

Since, $f_1(x_{k+1})=f_2(x_{k+1})=y_i$ (because $f_1$ and $f_2$ are in the domain of $h$, we can conclude that $f_1=f_2$, hence $h$ is injective.

Is this good enough?

For surjection, I've tried:

I know I need to show that for any $f\mid(X_1-\{x_{k+1}\}) \in \text{Fun}(X,Y)$:

$$\exists f \in \{f:X_1 \rightarrow Y \mid f(x_{k+1}=y_i)\}, h(f)= f\mid(X_1-\{x_{k+1}\})$$

I can that this is true when I draw the diagrams for the case $|X|=|Y|=2$ but I don't know how to write it formally. Please help.

  • $\begingroup$ You define $k$ but not $n$ in the maximum of the indexes in those sets $\endgroup$ – Alice Ryhl Aug 12 '14 at 13:54
  • $\begingroup$ $n$ is also any positive integer and $|Y|=n$. I've edited my question $\endgroup$ – mauna Aug 12 '14 at 13:57

Your argument for injectivity looks fine, you could maybe be more specific that $f_1=f_2$ since $f_1(x)=f_2(x)$ for all $x\in X_1$.

For surjectivity, given $f:X_1\setminus \{x_{k+1}\}\rightarrow Y$, define a function $\bar f:X_1\rightarrow Y$ by $\bar f(x_{k+1}):=y_i$ and $\bar f(x_i):=f(x_i)$ for all $i\neq k+1$. Then $h(\bar f)=f$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.