2
$\begingroup$

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

$\endgroup$
5
  • 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
    Commented 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$ Commented Jun 8, 2019 at 20:26
  • 3
    $\begingroup$ That's a pretty horrible "proof". Look for a better book, if that is its standard. $\endgroup$ Commented 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
    Commented May 26, 2020 at 21:04
  • $\begingroup$ The above statement can be stronger math.stackexchange.com/a/1967807/1059606. $\endgroup$
    – An5Drama
    Commented May 2 at 2:18

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
5
  • 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
    Commented Jun 8, 2019 at 21:13
  • $\begingroup$ @Akerbeltz, I made a mistake in writing. I believe it is now correct. $\endgroup$
    – Mrcrg
    Commented Jun 8, 2019 at 21:16
  • $\begingroup$ It is still wrong; where are you sending $b$ to? $\endgroup$
    – Akerbeltz
    Commented Jun 8, 2019 at 21:32
  • $\begingroup$ @Akerbeltz I defined $b=a_0$, so $f(b)=a_1$ $\endgroup$
    – Mrcrg
    Commented Jun 8, 2019 at 21:34
  • $\begingroup$ If $A=\mathbb{N}$, someone may think it is impossible to have one infinite subset because of the definition of "Countably Infinite". But it is not that case. $\endgroup$
    – An5Drama
    Commented May 2 at 1:44
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ For reference, 1. $\preccurlyeq$ is a symbol to denote "injective" although it is not used in some books. 2. "then there exists an infinite countable subset of $A$": the reference link in the answer proves this part almost same as the Mrcrg's reference link ProofWiki Proof_4 where $n$ is one finite number therefore we can't directly use $F_n$. $\endgroup$
    – An5Drama
    Commented May 1 at 10:43
  • $\begingroup$ $T$ in the above ProofWiki is same as $U$ in the wikipedia proof of the above theorem where they also share the same idea. $\endgroup$
    – An5Drama
    Commented May 1 at 13:05

You must log in to answer this question.

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