I've been struggling to understand the proof of the following theorem given in a book.

Let $A$ be a set and $b \notin A$. Then $A$ is infinite iff there is a bijection between $A$ and $A \cup \{b\}$.

Proof: Since $A$ is infinite, it must be nonempty, i.e. $A=\{a_0,a_1,a_2,...\}$. A bijection $f: (A \cup \{b\}) \rightarrow A$ can be defined by:


$f(a_n):=a_{n+1}$, for $n \in \mathbb{N}$

$f(a):=a$, for $a\in (A\setminus \{b, a_0,a_1,... \})$.


In the last line, I don't understand why the set $A\setminus \{b, a_0,a_1,... \}$ is nonempty. (It is literally the set formed by taking all the elements of $A$ away from $A$.)

  • 2
    $\begingroup$ Why do you think that last set is nonempty? There could be elements beyond $a_0,a_1,a_2,....$ Please use a standard definition of infinite. $\endgroup$
    – Somos
    Jun 8, 2019 at 20:20
  • 3
    $\begingroup$ Writing $A=\{a_0,a_1,a_2,\dots\}$ is misleading (especially after "it must be nonempty, i.e."). This suggests that $A$ is a countable set which is not what is assumed. That said, if $A\setminus\{b,a_0,a_1,\dots\}$ is empty that's not a problem. (Also, it makes no sense to include $b$ there since we already know $b\notin A$). $\endgroup$ Jun 8, 2019 at 20:26
  • 2
    $\begingroup$ That's a pretty horrible "proof". Look for a better book, if that is its standard. $\endgroup$ Jun 9, 2019 at 0:39
  • $\begingroup$ That was given in a book. I'd say the proof is out and out incorrect. $\endgroup$
    – fleablood
    May 26, 2020 at 21:04

2 Answers 2


We know, that the set $A$ is infinite, then it can be countable or uncountable, but regardless of which, the set $A$ contains an infinite countable subset. Suppose $B$ is such a set. So, $B=\{a_1,a_2,...,a_n,...\} \subset A$.

Defining $a_0 = b$, so $B'=B \cup \{b\}=\{b, a_1,a_2,...,a_n,...\} \subset (A~\cup \{b\})$ and the bijection $f: A \cup \{b\} \rightarrow A $ by

$$f(x) = \begin{cases} x , &\text{ if $x \notin B'$} \\ a_{n+1} , &\text{ if $x \in B'$ } \end{cases}$$

Note that, $f(b)=f(a_0)=a_1$, $f(a_1)=a_2, ...$

For the demonstration of the statement "If the set $A$ is infinity, contains an infinite countable subset", se below this ProofWiki.

  • 1
    $\begingroup$ Your answer is wrong; compare it with the one I gave above $-$for example, how can $x$ not be in $B'$, the domain of the function $f$?$-$. $\endgroup$
    – Akerbeltz
    Jun 8, 2019 at 21:13
  • $\begingroup$ @Akerbeltz, I made a mistake in writing. I believe it is now correct. $\endgroup$
    – Mrcrg
    Jun 8, 2019 at 21:16
  • $\begingroup$ It is still wrong; where are you sending $b$ to? $\endgroup$
    – Akerbeltz
    Jun 8, 2019 at 21:32
  • $\begingroup$ @Akerbeltz I defined $b=a_0$, so $f(b)=a_1$ $\endgroup$
    – Mrcrg
    Jun 8, 2019 at 21:34

There is a little bit of confusion regarding your question. For instance, you are assuming that $A$ is infinite countable, and from the statement in the title of your question, that could simply not be the case.

Here is a proof of the right hand side implication. First, since $A$ is infinite, then there exists an infinite countable subset of $A$ (this requires at least assuming AC$_\omega$). Let this set be denoted by $B$, and choose an enumeration of $B$; $B=\{b_n|\;n\in\omega\}$.

On the one hand, we clearly have that $A\preccurlyeq A\cup\{b\}$, via the injective function $i:A\longrightarrow A$ given by: for all $a\in A$, $\;i(a)=a$, that is, $i$ is the inclusion of $A$ into $A\cup\{b\}$.

On the other hand, the function $f:A\cup\{b\}\longrightarrow A$ defined by: for all $x\in A\cup\{b\}$:

$$f(x)=\begin{cases} b_0 \qquad\text{if }x=b\\ b_{n+1}\quad\text{if }x=b_n\text{ for some }n\in\omega\\ x\qquad\text{ in any other case} \end{cases}$$

Is clearly injective, so $A\cup\{b\}\preccurlyeq A$. From the Cantor-Bernstein theorem, we can conclude that $A\approx A\cup\{b\}$.

To prove the other implication, take into account that $A$ is a proper subset of the set $A\cup\{b\}$ which is equinumerous to $A$, so we immediately get that $A\cup\{b\}$ is infinite, as well as $A$ (in some literature this result is known as Dedekind's theorem; if you are iterested about this, i.e., that a set is infinite if and only if it contains a proper subset to which it is equinumerous, you should check my answer to this question).


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .