Vtyjkyuk

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

My attempt:

Let $|A|=n$. We will prove by induction on n. It's clear that the the theorem is trivially true for $n=0$. Assume the theorem is true for all $n=k$. For $n=k+1$, then $|A setminus a|=k$ for some $a in A$. Thus $X setminus (A setminus a) sim X$ by inductive hypothesis, or $(X cap a) cup (X setminus A) sim X$, or $a cup (X setminus A) sim X$. We have $a cup (X setminus A) sim X setminus A$ since the theorem is true for $n=1$. Hence $X setminus A sim a cup (X setminus A) sim X$. Thus $X setminus A sim X$. This completes the proof.

Does this proof look fine or contain gaps? Do you have suggestions? Many thanks for your dedicated help!

Update: Here I prove that the theorem is true for $n=1$.

Assume that $A = a$ and consequently $X setminus A= X setminusa$. It's clear that $|X setminus A| le |X|$. Next we prove that $|X| le |X setminus A|$. Since $X$ is infinite, there exists $B subsetneq X$ such that $B sim X$ (Here we assume Axiom of Countable Choice). Thus $|X|=|B|$. There are only two possible cases.

1. $a in X setminus B$

Then $B subseteq X setminus a=X setminus A$ and consequently $|X|=|B| le |X setminus A|$. Thus $|X| le |X setminus A|$ and $|X setminus A| le |X|$. By Schröder–Bernstein theorem, we have $|X setminus A| = |X|$. It follows that $X setminus A sim X$.

2. $a in B$.

Let $b in X setminus B$. We define a bijection $f:X setminus a to X setminus b$ by $f(x)= x$ for all $x in X setminus a,b$ and $f(b)=a$. Thus $X setminus a sim X setminus b$. Since $b in X setminus B$, it follows from Case 1 that $X setminus b sim X$. Hence $X setminus a sim X setminus b sim X$. Thus $X setminus a = X setminus A sim X$.

To sum up, $X setminus A sim X$ for all $|A|=1$.

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 $gcolon0,1,dots,n-1to A$, for some $ninmathbbN$.

Fix an injection $fcolonmathbbNto Xsetminus A$ (which exists because $Xsetminus A$ is infinite, assuming countable choice) and define $psicolon Xsetminus Ato X$ by
$$
psi(x)=begincases
x & xnotin f(mathbbN) \[4px]
g(m) & x=f(m),quad 0 le m < n \[4px]
f(m-n) & x=f(m),quad m ge n
endcases
$$
Prove $psi$ is a bijection.

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.

I found that @egreg's solution is very elegant, so I want to re-formalize it into the below proof. All credits go to @egreg.

Lemma 1: If $A$ is finite and $B$ is countably infinite, then $Acup B$ is countably infinite.

Lemma 2: If $X$ is infinite and $A$ is finite, then $Xsetminus A$ is infinite.

Lemma 3: If $Y$ is infinite, then there exists $Bsubsetneq Y$ such that $B$ is countably infinite. (Here we assume Axiom of Countable Choice)

Since $X$ is infinite and $A$ is finite, then $Xsetminus A$ is infinite by Lemma 2.

Since $Xsetminus A$ is infinite, there exists $Bsubsetneq Xsetminus A$ such that $B sim Bbb N$ by Lemma 3.

Since $A$ is finite and $B$ is countably infinite, then $Acup B sim Bbb N$ by Lemma 1.

Since $B sim Bbb N$ and $Acup B sim Bbb N$, $B sim Acup B$ and thus there exists an bijection $f_1:B to Acup B$.

Let $f_2:Xsetminus Asetminus B to Xsetminus Asetminus B$ be the identity map on $Xsetminus Asetminus B$. Then $f_2$ is a bijection.

We define $f:Xsetminus A to X$ by $f(x)=f_2(x)$ for all $x in Xsetminus Asetminus B$ and $f(x)=f_1(x)$ for all $x in B$. Thus $f$ is a bijection.

Hence $Xsetminus A sim X$.