If $A$ is a set with $m$ elements and $C \subseteq A$ is a set with $1$ element, then prove that $A \setminus C$ is a set with $m-1$ elements

Question

Definition: $N_m$ = $\{1,2,\ldots,m\}$

My Attempt: Since $A$ is a set with $m \in \mathbb{N}$ elements, there exists a bijection $f:N_m \to A$. We know that $C \subseteq A$ contains just $1$ element, say $a$ (Note that $a \in A$ as well). Let $k \in N_m$ be the element that maps to $a$. We know $k$ is unique because $f$ is also an injection.

We define: $$h(q)= \begin{cases} f(q),&q=1,2,\ldots,k-1 \\[2ex] f(q+1),&q=k,k+1,\ldots,m-1 \end{cases}$$

It is evident that $h:N_{m-1} \to A\setminus C$. All we have to do now is to prove that $h$ is a bijection.

• Injectivity: There are only two possible scenarios for any member of the domain. Either it belongs to $N_{k-1}$ or it belongs to $N_{m-1} \setminus N_{k-1}$.

  1. For any $x_1,x_2 \in N_{k-1}$ such that $x_1 \neq x_2$, $h(x_1),h(x_2) \in f(N_{k-1})$. Since $f$ is injective over $N_{k-1}$, $h(x_1) \neq h(x_2)$.
  2. For any $x_1,x_2 \in N_{m-1} \setminus N_{k-1}$ such that $x_1 \neq x_2$, $h(x_1),h(x_2) \in f(N_{m-1} \setminus N_{k-1})$. Since $f$ is injective over $N_{m-1} \setminus N_{k-1}$, $h(x_1) \neq h(x_2)$.

• Surjectivity: This is the part I cannot figure out. I would like if someone could point me in the right direction.

Answer 1

Consider any element $y\in A\setminus C$. Since $f$ is a bijection, we know that there exists $x_y\in \mathbb{N}_m$ such that $f(x_y) = y$. If $x_y < k$, then $x_y \in \Bbb N_{m-1}$ is such that $h(x_y) = f(x_y) = y$. If $k < x_y \leq m$, then $x_y -1 \in \Bbb N_{m-1}$ is such that $h(x_y - 1) = f(x_y - 1 + 1) = f(x_y) = y$. So for all $y \in A\setminus C$, there is an element $n\in \Bbb N_{m-1}$ such that $h(n) = y$.

Answer 2

Be $b\in A\setminus C$. Since $b\in A$ and $f$ is an injection, there exists a $q$ such that $f(q)=b$, and clearly $q \ne k$. Therefore either $q>k$ or $q<k$. Can you continue from there?

Answer 3

Hint:

Let $x\in A\setminus C$. Then in particular $x\in A$. Therefore $$\exists y\in N_m\ | \ \ f(y)=x$$