Suppose $X$ is infinite and $A$ is a finite subset of $X$. Then $X$ and $X \setminus A$ are equinumerous

Solution 1:

Your proof is correct except for the step where you say that $\{a\} \cup (X \setminus A) \sim X \setminus A$ by inductive hypothesis. I assume you are applying the inductive hypothesis (to the set $\{a\} \cup (X \setminus A)$) in the case $n=1$, which is fine as long as $k \ge 1$. But your proof does not work in the case $k=0$. In other words, your proof correctly shows that if the theorem holds for $n=1$, then it holds for all larger values of $n$. But it does not prove that it holds for $n=1$.

In fact, the proof for $n=1$ is rather tricky. Here's a nice exercise: prove that the $n=1$ case for an infinite set $X$ is equivalent to the statement that $X$ contains a subset that is equinumerous to the set of positive integers. Now, the statement that every infinite set contains a subset equinumerous with the positive integers cannot be proven without some form of the axiom of choice. Therefore the proof of the $n=1$ case will also require the axiom of choice.

Solution 2:

The proof (with the update) seems correct.

Assuming choice (or at least countable choice), we can do it perhaps more easily.

Since $A$ is finite, there is a bijection $g\colon\{0,1,\dots,n-1\}\to A$, for some $n\in\mathbb{N}$.

Fix an injection $f\colon\mathbb{N}\to X\setminus A$ (which exists because $X\setminus A$ is infinite, assuming countable choice) and define $\psi\colon X\setminus A\to X$ by $$ \psi(x)=\begin{cases} x & x\notin f(\mathbb{N}) \\[4px] g(m) & x=f(m),\quad 0 \le m < n \\[4px] f(m-n) & x=f(m),\quad m \ge n \end{cases} $$ Prove $\psi$ is a bijection.