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

Question

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.

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$.

Answer 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 $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.

Answer 2

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.

Answer 3

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 $A\cup B$ is countably infinite.

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

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

---

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

Since $X\setminus A$ is infinite, there exists $B\subsetneq X\setminus A$ such that $B \sim \Bbb N$ by Lemma 3.

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

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

Let $f_2:X\setminus A\setminus B \to X\setminus A\setminus B$ be the identity map on $X\setminus A\setminus B$. Then $f_2$ is a bijection.

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

Hence $X\setminus A \sim X$.