2
$\begingroup$

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

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

$\endgroup$
  • $\begingroup$ What's your definition of $X$ being infinite? $\endgroup$ – Paul K Sep 10 '18 at 15:51
  • $\begingroup$ @PaulK $X$ is infinite if and only if $X$ is not finite. $\endgroup$ – LE Anh Dung Sep 10 '18 at 15:55
  • $\begingroup$ @PaulK of infinite cardinality $\endgroup$ – Michał Zapała Sep 10 '18 at 15:57
  • $\begingroup$ The proof is somewhat lacking in elegance, but formally correct $\endgroup$ – Michał Zapała Sep 10 '18 at 15:58
  • $\begingroup$ @MichałZapała I'm very curious about your elegant approach. Could you please elaborate on it? $\endgroup$ – LE Anh Dung Sep 10 '18 at 16:08
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you so much! $\endgroup$ – LE Anh Dung Sep 12 '18 at 8:55
  • $\begingroup$ After I read your answer carefully, I found that your approach is much more elegant and simpler than mine. I decided to re-formalize it into a proof in my own words and posted as an answer at the end of this thread. If you don't mind, please have a look at it! Many thanks for you! $\endgroup$ – LE Anh Dung Sep 12 '18 at 11:13
  • $\begingroup$ Typo: I think you mean $\psi(x) = f(m-n)$ when $x = f(m)$, $m \ge n$. $\endgroup$ – Dan Velleman Sep 13 '18 at 21:32
  • $\begingroup$ @DanVelleman Thanks for noting! $\endgroup$ – egreg Sep 13 '18 at 21:34
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.