# Infinite sets: $A$ is infinite iff there is a bijection between $A$ and $A \cup \{b\}$

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(b):=a_0$$

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

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

q.e.d.

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

• 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. Jun 8, 2019 at 20:20
• 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$). Jun 8, 2019 at 20:26
• That's a pretty horrible "proof". Look for a better book, if that is its standard. Jun 9, 2019 at 0:39
• That was given in a book. I'd say the proof is out and out incorrect. May 26, 2020 at 21:04

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.

• 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$?$-$. Jun 8, 2019 at 21:13
• @Akerbeltz, I made a mistake in writing. I believe it is now correct. Jun 8, 2019 at 21:16
• It is still wrong; where are you sending $b$ to? Jun 8, 2019 at 21:32
• @Akerbeltz I defined $b=a_0$, so $f(b)=a_1$ 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).