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 \setminus\{a\}$. 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.
- $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$.
- $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$.
Best Answer
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.