Theorem. Let $X$ be a countably infinite set and $Y$ be a finite set. Then $X\cup Y$ is countably infinite.
Proof. Since $X$ is a countably infinite set, then there exists a bijection function $f\colon \mathbb{N}\longrightarrow X$ and since $Y$ is a finite set, then $X\cup Y$ is (why) is infinite. Therefore there exists (why) a bijection function $g\colon X\longrightarrow X\cup Y$ so $g\circ f\colon \mathbb{N}\longrightarrow X\cup Y$ is a 1-1 and surjective function. This means that $X\cup Y$ is countably infinite.
Could you please tell me the reason of the two WHYs?
How to complete this proof? Union of a countably infinite set and a finite set is countably infinite
2
$\begingroup$
$\endgroup$
-
$\begingroup$ Where did you find this proof? I'd have given it somewhere between 10% to 0% score in an exam. $\endgroup$ – Asaf Karagila♦ Sep 3 '15 at 13:59
-
$\begingroup$ @AsafKaragila: In a non-official textbook! Is it wrong? $\endgroup$ – Sisabe Sep 3 '15 at 14:00
-
$\begingroup$ Well, this “proof” basically says “prove it”, because the existence of $g$ is exactly the same as saying that $X\cup Y$ is countably infinite. Moreover the fact that $Y$ is finite has nothing to do with $X\cup Y$ being infinite. $\endgroup$ – egreg Sep 3 '15 at 14:05
-
$\begingroup$ @egreg: So could you please help me prove it? $\endgroup$ – Sisabe Sep 3 '15 at 14:10
-
$\begingroup$ First (why) $|X \cup Y| \ge |X| = +\infty$ $\endgroup$ – gt6989b Sep 3 '15 at 14:14
2
$\begingroup$
$\endgroup$
The first “why” has no explanation; the fact that $X\cup Y$ is infinite stems from $X$ being infinite.
The second “why” is exactly the whole proof.
Since $Y$ is finite, also $Y'=Y\setminus X$ is finite. Note that $X\cup Y=X\cup Y'$ and $X\cap Y'=\emptyset$. Since $Y'$ is finite, there exist $d\in\mathbb{N}$ and a bijection $$ h\colon\{0,1,\dots,d-1\}\to Y' $$ Define $$ g\colon\mathbb{N}\to X\cup Y' $$ by $$ g(n)=\begin{cases} h(n) & \text{if $n<d$}\\[6px] f(n-d) & \text{if $n\ge d$} \end{cases} $$ Can you prove $g$ is bijective?
(Note: if you're afraid about the case when $d=0$, that is, $Y'=\emptyset$, don't be; anyhow, in this case there's exactly nothing to prove.)
-
$\begingroup$ Thanks for your answer. I know how to prove that g is 1-1, but don't know how to prove it is a surjective. Could you please explain it? $\endgroup$ – Sisabe Sep 3 '15 at 14:34
-
$\begingroup$ @Sisabe If an element is in $Y'$, then it belongs to the image of $h$ (hence of $g$). Otherwise it belongs to the image of $f$, say $f(m)$. Then $g(m+d)=f(m)$. $\endgroup$ – egreg Sep 3 '15 at 14:38
-
$\begingroup$ sorry, but I'm very newbie in Set Theory. Could you please explain the proof of the surjectivity in more details? I have been told only this method to proof the surjectivity: $\forall z \in X\cup Y', \exists $ a $n\in \mathbb{N}$ such that $g(n)=z$ $\endgroup$ – Sisabe Sep 4 '15 at 14:01
-
$\begingroup$ @Sisabe Isn't it what I showed? If $x\in X\cup Y'$, then either $x\in Y'$ or $x\in X$. In the first case the surjectivity of $g$ says $x=g(n)$, for some $n$, $0\le n<d$, so that $x=h(n)$. In the second case, $x=f(m)$ for some $m$, because $f$ is surjective; then $x=f(m)=h(d+m)$. $\endgroup$ – egreg Sep 4 '15 at 14:01
